Here’s the problem: given n coin flips, what’s the probability that you never see two heads in a row? This seems sort of like it ought to be easy to figure out, but if you try, it’s harder than it seems. The answer ends up being extremely surprising.
To solve it, we would basically need a way to count the number of sequences of T’s and H’s of length n that do not contain the string HH. To save some space and help avoid confusion, let’s give these sequences a name. I’ll call them c-sequences—c for “coin”. So henceforth in this blogpost, a c-sequence is a string consisting of nothing that is not an H or a T, and that does not contain the string HH. Then, to get the probability of never seeing HH in a sequence of n coin flips, we would just divide the number of c-sequences of length n by the total number of sequences of H’s and T’s of length n. So for instance if n=3 then we can just count them. All the sequences of length 3 are
Of those, 3, 4, 6, 7 and 8 are c-sequences. So the probability of flipping a coin 3 times and not getting HH ever is 5/8.
But as n grows, this becomes a really impractical way to do this. If n is, say, 30, then there are 1073741824 total sequences of H’s and T’s. No one wants to list those out and count the ones that don’t contain HH.
Luckily there ends up being a better way, and it’s really cool.
What we would like to have is a function f(n) which gives the number of c-sequences of length n. So as we saw above, f(3)=5, since there are five c-sequences of length 3. Once we figure out how to make f, the answer is easy: it’s just
since there are always 2^n total sequences of length n.
So we’ve reduced the problem to just finding a nice way to construct f(n). That’s where the beautiful part comes in.
We can start constructing f by defining f(0) and f(1). These are special cases since there aren’t any strings HH in the sequences of length 0 or the sequences of length 1 at all, since you need at least two flips to get two heads. I’ll start with f(1) since it makes more sense probably. There are two sequences of length 1:
Both are c-sequences since neither contain HH, so we define f(1)=2. Now f(0) is a little weirder—how many sequences of length 0 are there which do not contain an HH? You might be tempted to say 0, since there aren’t any sequences of H’s and T’s at all of length 0. You wouldn’t be wrong per se, but there’s another possible answer. We could also say that there is exactly one such sequence:
This is called the empty sequence, and it’s a perfectly good sequence that most mathematicians count as a sequence. It doesn’t contain anything that’s not an H or a T, so we can legally include it in the set of sequences of H’s and T’s, and it doesn’t include the string HH, so it’s a c-sequence (you might have thought that the way that I defined a c-sequence was awkwardly wordy—this is why, because that allows for the empty sequence to be a c-sequence). So I’m going to define f(0)=1, as there is one c-sequence of length 0: the empty sequence.
Now comes the really cool part. Think about all the c-sequences of length n where n>1. Any such sequence either ends with H or T. If it with H, then the second to last letter must be T—otherwise the sequence would contain an HH at the end, disqualifying it from being a c-sequence. So the list of c-sequences of length n that end with H looks something like this:
- and so on…
So you can see that every c-sequence of length n ending in H is just a c-sequence of length n-2 with a TH tacked onto the end. In other words, if the above is a list of every c-sequence of length n that ends with H, if we just chop off the TH at the end, then it’s a list of every c-sequence of length n-2. So the number of c-sequences of length n ending with an H is the same as the total number of c-sequences of length n-2.
We can use the same kind of reasoning to look at the c-sequences of length n that end in T. The list of those looks something like this:
- and so on…
So the list of c-sequences of length n which end in a T is exactly the same as the list of all c-sequences of length n-1, but just tacking a T onto the end of each one. So the number of n-length c-sequences ending in T is the same as the number of n-1 c-sequences.
So we’ve just counted all the c-sequences of length n: it’s equal to the number of n-length c-sequences ending in H plus the number of n-length c-sequences ending in T, which is equal to the total number of n-2 length c-sequences plus the total number of n-1 length c-sequences.
In other words, for n>1, f(n)=f(n-2)+f(n-1), which means we can now completely define our function f(n): f(0)=1, f(1)=2, and for n>1, f(n)=f(n-2)+f(n-1).
What’s so cool about that? Well it’s cool in its own right, since we are defining a function in terms of itself. But what makes it even cooler is that that is exactly the world-famous and universally revered Fibonacci sequence—well, almost anyway. Our function f(n) gives the n+2nd Fibonacci number.
So if we let F(n) represent the nth Fibonacci number, then we get a beautiful solution to the original problem: the probability of never seeing two heads in a row in n coin flips is given by:
Incidentally, since I mentioned 30 coin flips above, Wolfram Alpha gives about 0.002 as the probability of never seeing two heads in a row in 30 flips.
Well I thought it was cool anyway.
Inspired, by the way, by a discussion on /r/math.
Americans revere athletic excellence, competitive success, and it’s more than lip service we pay; we vote with our wallets. We’ll pay large sums to watch a truly great athlete; we’ll reward him with celebrity and adulation and will even go so far as to buy products and services he endorses.
But it’s better for us not to know the kinds of sacrifices the professional-grade athlete has made to get so very good at one particular thing. Oh, we’ll invoke lush clichés about the lonely heroism of Olympic athletes, the pain and analgesia of football, the early rising and hours of practice and restricted diets, the preflight celibacy, et cetera. But the actual facts of the sacrifices repel us when we see them: basketball geniuses who cannot read, sprinters who dope themselves, defensive tackles who shoot up with bovine hormones until they collapse or explode. We prefer not to consider closely the shockingly vapid and primitive comments uttered by athletes in postcontest interviews or to consider what impoverishments in one’s mental life would allow people actually to think the way great athletes seem to think. Note the way “up close and personal” profiles of professional athletes strain so hard to find evidence of a rounded human life — outside interests and activities, values beyond the sport. We ignore what’s obvious, that most of this straining is farce. It’s farce because the realities of top-level athletics today require an early and total commitment to one area of excellence. An ascetic focus 37. A subsumption of almost all other features of human life to one chosen talent and pursuit. A consent to live in a world that, like a child’s world, is very small."
It’s sort of weird that this KONY 2012 movie floating around is produced by a group that funds the Ugandan army.
Here’s a picture of the founders of Invisible Children hanging out with the Sudan People’s Liberation Army:
Not that awareness is a bad thing or anything, but, it’s just sort of a weird thing to be singing the praises of the Ugandan and Sudan Armies. Here’s more:
You do not need to ask my permission to share this. Please link it widely. For those asking what you can do to help, please link to visiblechildren.tumblr.com wherever you see KONY 2012 posts.
I do not doubt for a second that those involved in KONY 2012 have great intentions, nor do I doubt for a second that Joseph Kony is a very evil man. But despite this, I’m strongly opposed to the KONY 2012 campaign.
KONY 2012 is the product of a group called Invisible Children, a controversial activist group and not-for-profit. They’ve released 11 films, most with an accompanying bracelet colour (KONY 2012 is fittingly red), all of which focus on Joseph Kony. When we buy merch from them, when we link to their video, when we put up posters linking to their website, we support the organization. I don’t think that’s a good thing, and I’m not alone.
Invisible Children has been condemned time and time again. As a registered not-for-profit, its finances are public. Last year, the organization spent $8,676,614. Only 31% went to their charity program (page 6)*. This is far from ideal, and Charity Navigator rates their accountability 2/4 stars because they haven’t had their finances externally audited. But it goes way deeper than that.
The group is in favour of direct military intervention, and their money funds the Ugandan government’s army and various other military forces. Here’s a photo of the founders of Invisible Children posing with weapons and personnel of the Sudan People’s Liberation Army. Both the Ugandan army and Sudan People’s Liberation Army are riddled with accusations of rape and looting, but Invisible Children defends them, arguing that the Ugandan army is “better equipped than that of any of the other affected countries”, although Kony is no longer active in Uganda and hasn’t been since 2006 by their own admission.
Still, the bulk of Invisible Children’s spending isn’t on funding African militias, but on awareness and filmmaking. Which can be great, except that Foreign Affairs has claimed that Invisible Children (among others) “manipulates facts for strategic purposes, exaggerating the scale of LRA abductions and murders and emphasizing the LRA’s use of innocent children as soldiers, and portraying Kony — a brutal man, to be sure — as uniquely awful, a Kurtz-like embodiment of evil.” He’s certainly evil, but exaggeration and manipulation to capture the public eye is unproductive, unprofessional and dishonest.
As Christ Blattman, a political scientist at Yale, writes on the topic of IC’s programming, “There’s also something inherently misleading, naive, maybe even dangerous, about the idea of rescuing children or saving of Africa. […] It hints uncomfortably of the White Man’s Burden. Worse, sometimes it does more than hint. The savior attitude is pervasive in advocacy, and it inevitably shapes programming. Usually misconceived programming.”
Still, Kony’s a bad guy, and he’s been around a while. Which is why the US has been involved in stopping him for years. U.S. Africa Command (AFRICOM) has sent multiple missions to capture or kill Kony over the years. And they’ve failed time and time again, each provoking a ferocious response and increased retaliative slaughter. The issue with taking out a man who uses a child army is that his bodyguards are children. Any effort to capture or kill him will almost certainly result in many children’s deaths, an impact that needs to be minimized as much as possible. Each attempt brings more retaliation. And yet Invisible Children funds this military intervention. Kony has been involved in peace talks in the past, which have fallen through. But Invisible Children is now focusing on military intervention.
Military intervention may or may not be the right idea, but people supporting KONY 2012 probably don’t realize they’re helping fund the Ugandan military who are themselves raping and looting away. If people know this and still support Invisible Children because they feel it’s the best solution based on their knowledge and research, I have no issue with that. But I don’t think most people are in that position, and that’s a problem.
Is awareness good? Yes. But these problems are highly complex, not one-dimensional and, frankly, aren’t of the nature that can be solved by postering, film-making and changing your Facebook profile picture, as hard as that is to swallow. Giving your money and public support to Invisible Children so they can spend it on funding ill-advised violent intervention and movie #12 isn’t helping. Do I have a better answer? No, I don’t, but that doesn’t mean that you should support KONY 2012 just because it’s something. Something isn’t always better than nothing. Sometimes it’s worse.
If you want to write to your Member of Parliament or your Senator or the President or the Prime Minister, by all means, go ahead. If you want to post about Joseph Kony’s crimes on Facebook, go ahead. But let’s keep it about Joseph Kony, not KONY 2012.
~ Grant Oyston, firstname.lastname@example.org
Grant Oyston is a sociology and political science student at Acadia University in Nova Scotia, Canada. You can help spread the word about this by linking to his blog at visiblechildren.tumblr.com anywhere you see posts about KONY 2012.
*For context, 31% is bad. By contrast, Direct Relief reports 98.8% of its funding goes to programming. American Red Cross reports 92.1% to programming. UNICEF USA is at 90.3%. Invisible Children reports that 80.5% of their funding goes to programming, while I report 31% based on their FY11 fiscal reports, because other NGOs would count film-making as fundraising expenses, not programming expenses.