On runs of heads and coin tossing

This post was originally inspired by a post on reddit.com discussing Benford's Law.

Problem: what is the probability of finding a run of at least x heads in n tosses of a fair coin?

I borrowed heavily from Schilling [1] to work this out. We're going to recursively count the number of sequences satisfying the problem to give us the probability of finding one during a sequence of tosses.

Let $A(n, x)$ be the number of sequences of length $n$ with a run of at least $x$ heads.

For $n = 3$ and $x = 2$, we have eight total sequences, of which three contain runs of at least 2 heads:

HHH, HHT, HTH, HTT
THH, THT, TTH, TTT

We'll define $A(n, x)$ by constructing successful sequences recursively. If $n < x$ then clearly $A(n, x) = 0$. If $n = x$ then $A(n, x) = 1$ since there is exactly one sequence with at least x heads: the sequence of all heads. If $n > x$ there are three sets of possible sequences:

1. sequences that start with tails and are followed by subsequences of length $(n-1)$. There are $A(n-1, x)$ such sequences that meet our needs:
   

   T...    A(n-1, x)

2. sequences that start with a head and tail and are then followed subsequences of length $(n-2)$. There are $A(n-2, x)$ such subsequences which matter to us:
   

   HT...   A(n-2, x)

   The same holds for up to $(x-1)$ heads followed by a tail.
   

   HHT...  A(n-3, x)
   HHHT... A(n-4, x)
   etc.
   

3. sequences that start with at least x heads and are followed by $(n-x)$ tosses which we aren't interested in, of which there are $2^{n-x}$:
   

   HHHHHHH...  2^(n-x)
   |- x -|
   

So we have a recursive definition to count the number of such sequences:

$ A(n, x) = \left\{ \begin{array}{ll} 0 & n < x \\ 1 & n = x \\ 2^{n-x} + \sum_{i=1}^{x} A(n-i, x) & n > x \\ \end{array} \right. $

Which means the probability of a run of at least x heads in n tosses is given by

$P(n, x) = A(n, x) / 2^n$

For 200 coin tosses the probability of a run of at least five heads is 97% which I think is surprisingly high. The probability of a run of six heads is 80%.

The case of finding a run of exactly $x$ heads is very similar. The only part that changes is the third sequence type, where it must now end with a tails:

• sequences that have exactly $x$ heads and are followed by a tail and then $(n-x-1)$ tosses which we aren't interested in, of which there are $2^{n-x-1}$:
  

  HHHHHHHT...  2^(n-x-1)
  |- x -|
  

This gives us a recursive definition for $B(n, x)$, the probability of finding a run of exactly x heads in a sequence of n tosses:

$ B(n, x) = \left\{ \begin{array}{ll} 0 & n < x \\ 1 & n = x \\ 2^{n-x-1} + \sum_{i=1}^{x} B(n-i, x) & n > x \\ \end{array} \right. $

Again for 200 tosses, the probability of exactly five heads is mucher lower than at least five heads: 48%. Exactly six heads is only 40%.

It should be possible to find a non-recursive definition of A and B since all they're doing is summing over powers of two.

I miss $\LaTeX$, it's pretty.

[1] The Longest Run of Heads, Mark F. Schilling, The College Mathematics Journal, Vol. 21, No. 3, (1990), pp. 196-207, http://mathdl.maa.org/mathDL/22/?pa=content&sa=viewDocument&nodeId=2681

omg bagels!

A friend of mine gave me a great excuse to bake (like I need it): the Blogger Bake Off. It's a charity drive where bloggers bake bread, share recipes, donate to Breadline Africa, and encourage others to do likewise.

So I took the opportunity to bake my first batch of bagels and I'm pretty darn pleased with how they came out. I wasn't certain how far to stretch out the holes, so there was some variance, but they tasted great with some cream cheese, tomatoes and fresh basil. They also lasted surprisingly well. Most of my homemade loaves last only a day or two before they start going stale (unlike store-bought breads which have agents to prevent them from going stale), but the bagels lasted a good three or four days. At that point they started needing toasting.

Go on, bake bread -- give dough.

A yegg stole my zebu

A while ago I received one of those annoying chain emails which ask you to take the last word in a list, change one letter to find a valid word not already in the list, add it to the end and forward the whole thing to ten friends or you'll die in a horrible car crash.

It got me wondering about words in English. Are most words connected to each other in this way? If not, what do the distinct groups (or cliques in graph parlance) look like? Do two-letter words, three-letter words or four-letter words have more cliques? I decided I'd find out.

Preliminaries

For simplicity, I limited the edit operation to only allow one letter in the word to change (ie. no deletions or insertions) at a time. You can think of the dictionary as an undirected graph, with each node being a word and each edge an edit operation permitting you to travel between adjacent nodes.

My data source is the 2of12inf.txt file from the 12 Dicts package from wordlists.sourceforge.net. It uses American spellings and seems to be a fairly decent list of words (which is to say my 10 minutes of hunting didn't provide me with anything better). It contains:

• 2-letter words: 62
  
• 3-letter words: 642
  
• 4-letter words: 2546
  
• 5-letter words: 5122

Results

A little ruby script yielded the following results.

All 2-letter words belong to the same clique.

Of the 3-letter words, 631 (of 642) belong to the same clique, the remaining 11 are each entirely disconnected from each other. They are,

• nth, ism, urn, ebb, obi, qua, ova, use, ugh, gnu, aha

The 4-letter words are more interesting. 2415 of the 2546 belong to the same clique and the other 131 are divided up into 97 other cliques. Many of the 131 are common words. The 18 cliques with more than one word:

• ache, achy, acme, acne, acre, ashy
  
• info, into, onto, undo, unto
  
• high, nigh, sigh, sign
  
• afar, agar, ajar
  
• also, alto, auto
  
• eddy, edge, edgy
  
• icon, ikon, iron
  
• idle, idly, isle
  
• opal, oral, oval
  
• used, user, uses
  
• bevy, levy
  
• crud, crux
  
• demo, memo
  
• hadj, hajj
  
• idol, idyl
  
• ogle, ogre
  
• orzo, ouzo
  
• thou, thru

The remaining 79 that are stranded on their own:

• adze, agog, ague, ahoy, alga, ammo, amok, anal, ankh, apse, aqua, aura, avow, awol, ayah, bozo, ciao, ditz, ebbs, echo, ecru, egad, emus, ends, envy, epee, epic, espy, euro, evil, exam, expo, guru, hymn, ibex, iffy, imam, iota, isms, jato, judo, kiwi, liar, luau, lynx, meow, myna, nevi, nova, obey, oboe, odor, ohms, okay, okra, once, onyx, orgy, ovum, rely, rhea, rhos, semi, sexy, stye, sync, tofu, tuft, ugly, ulna, upon, urge, uric, urns, void, yegg, yeti, yuan, zebu

The 5-letter words have the most room for sizeable subsets. Of the 5122 words, 3935 fall into a common clique. The next 5 cliques with at least 10 members:

• reset, resew, resow, renew, beset, besot, besom, bosom, begot, begat, began, begun, begum, begin, vegan, bigot, bight, wight, tight, sight, sighs, signs, highs, right, night, might, light, fight, eight, beret, beget (31)
  
• round, wound, would, world, mould, moult, mount, fount, count, court, could, sound, pound, mound, hound, found, bound (17)
  
• acnes, acres, acmes, aches, ached, acted, anted, antes, antis, antic, attic, ashes, ashen, aspen, asses, asset, apses (17)
  
• comic, conic, cynic, tonic, toxic, toxin, topic, tunic, runic, sonic, ionic, colic (12)
  
• overs, overt, avert, alert, ovens, opens, omens, evens, event, avers (10)

The next 31 cliques have between 4 and 9 members, 34 have 3 members each, 108 have 2 members each, and 613 words are stranded on their own.

The joys of a Sunday evening well-spent. I also learnt that nth is a valid word without vowels, a zebu is a breed of cattle, and a yegg is a burglar or safecracker.

The Staff of Life

When I was in Seattle a few weeks ago I bought a copy of The Bread Baker's Apprentice, an instructional text aimed at hobbiest breadmakers. It was the source of my breakthrough loaf--a baguette I made while in Vancouver--and I've wanted to own it ever since. I was like a kid at Christmas, much to the chagrin of my friends (it's a bread book for crying out loud).

My first stab at breadmaking was in 2004 and was dismal. It didn't rise properly, was hard as a rock and far too salty. I ate it all, it was delicious. It was bread from my own two hands and I was hooked. About two years later, after many recipes and attempts, I decided to get serious and borrowed the Bread Baker's Apprentice from the Vancouver Public Library. I was a poor, starving student at the time; buying books (or bread) wasn't on the cards. The baguette took two days to make and consisted solely of flour, water, salt and yeast. No sugar, no honey, no shortcuts. The flavour in it was astounding. It was sweet with a rich texture a lingering aftertaste that I couldn't resist, I just kept going back for more. My German housemate paid me the ultimate compliment by mistaking it for a baguette bought from the local artisan bread shop. I was ruined. I was never going to be happy with the two-hour Jamie Oliver special ever again.

My mother bought me a selection of stone-ground flours recently and I gave them a whirl this weekend. I just took two pain de campagne loaves from the oven. They're not perfect, the longer one is a bit deflated and I can't get the oven to the heat I want since it leaks like a sieve, but I'm two slices in and quite pleased with the result.

Pacific Northwest

I just got back from a two week trip to Seattle and Vancouver. I was in Seattle on business and couldn't turn down the chance to pop up to Vancouver and catch up with some friends.

I managed to fit in a great deal of sushi, which is ridiculously cheap and good in Vancouver, and phở, which I have yet to find at all in Cape Town. Sarah flew into Vancouver for the weekend, Jocelyn had just returned from Australia, and Tarrin was en route from Alaska back to SA, so it worked out incredibly well.

North America's cellphone networks are a complete joke. Roaming gave me no end of hassles and the people at T-Mobile were less than useless. After poorly faking an American accent just to get past their support voice-prompt system (much to my colleague's amusement), I couldn't get them to understand that I was a foreigner roaming inside their country. "No, I'm from South Africa, not in South Africa" was clearly not in their script, so they just looped back to asking me what my mobile number was and getting confused when it started with +27.

I also discovered why Delta's New York-Dakar-Cape Town flight is so cheap: it's 20 hours of hell in what must be the oldest plane in their fleet.

Elasticfox and ssh

I've been working on the Elasticfox Firefox extension, which was recently open sourced. It's a GUI for Amazon's EC2 webservice and is great way to use the service without having to worry about WSDLs and XML.

One improvement I'm pleased with is the support for opening ssh connections to instances. Elasticfox now tries to make good choices for the terminal and ssh programs to run, with the result that it works (almost) out of the box on Mac and *NIX, and (almost-almost) Windows.

For Mac OS X and *NIX, you just need to set the location of your instance ssh keypairs and Elasticfox will launch Terminal and gnome-terminal, respectively. For Windows, you also need to install PuTTY, which Elasticfox expects to find in c:\Program Files\Putty\putty.exe. The error handling when ssh fails has also been improved, which should make getting it to work using your own solution simpler.

Another small improvement is that you can now ssh into many instances in one go, just by selecting more than one in the instance list. This is a real crowd-pleaser when you launch ten instances and, in a few minutes, have logged into all ten, with only a few mouse clicks.

You can install an interim build with these changes if you like to be cutting edge.

If you're new to the extension, take a read through the tutorial that was posted on the EC2 forums.

You might also be interested in the standalone Elasticfox executable for Windows that AideRSS put together. Their description is for an older version of Elasticfox, but the principle is sound. It's particularly useful if the latency between you and EC2 is high enough (because, say, you're at the tip of Africa) that the synchronous API calls hang Firefox.

For the record, the build also includes these updates:

• FIX: sf.net bug 1898177: Adding ICMP firewall rules requires filling in TCP fields.
  
• FIX: sf.net bug 1894182: Choosing security group while launching AMI instance UI bug
  
• opens in a new tab by default
  
• ssh to multiple instances at once
  
• choose platform-dependent defaults for ssh
  
• FIX: redraw lists when sort order has changed
  
• first steps towards branding as Elasticfox
  

Reverse culture shock

I haven't blogged in over a year and recently decided to make a concerted effort to redress the lack of posts.

I've been back in South Africa for 18 months, now; it's been a bumpy ride. I was warned about the reverse culture shock that many people experience when returning to their home country after living away for a long while, but actually experiencing it first hand was (and is) another matter.

For the first few months I was continually frustrated with South Africa. Nothing worked quite as smoothly as in Canada, people seemed rude and had no respect for their fellow man, I struggled to find familiar foods in shops, and perhaps most strikingly, we drive everywhere, and badly at that.

Resuming old friendships was difficult. I changed hugely in Canada, was exposed to new ideas, places and people. My local friends grew too, but in different, more subtle ways. They seemed almost a little parochial, now. It didn't help that every second sentence I uttered began with "In Canada...". When everything you've done for the last three years was in a different country, how do you relate stories without starting them like that? The only other option is to keep quiet and come across as aloof and bored.

"Forward" culture shock takes about six months to overcome. My favourite memory of it is catching the bus to UBC for an early morning class and arriving to realise I had made the whole trip while still half asleep. I hadn't thought about what I was doing since getting up, I had internalised it completely. For a friend in London, it was the agent at the corner cafe getting her favourite brand of cigarettes without her having to ask.

Asking around, I've found that reverse culture shock typically takes twice as long to overcome. It's taken me 1.5 years of living in my home country to feel at home again. I've gradually settled back into the South African way of doing things and remembered that being just a little fucked up is all part of SA's charm. It keeps the politics interesting and the populace on its toes. Moving to Cape Town helped: the driving is just as bad, but at least everyone's chilled out about it. And I can bike to work without too many people looking at my like I'm crazy.

I'm hoping that in 2008 I'll feel even more settled, and maybe even find that sense of contentment that I found in the mountains of BC, but somehow seemed to have lost on the trip home.