The Coin Toss Paradox

So I recently started reading this fantastic book from Quanta magazine titled “The Prime Number Conspiracy” that covers some of the biggest problems in modern mathematics and was once again nerd sniped by a math problem.

The book explains that if Alice is flipping a coin looking for the first two consecutive heads she will find it after, on average, six flips. If Bob is flipping looking for the first instance of heads and then tails he will find it on average after four flips.

What the heck!?
The chances of HH appearing are the same as the chances of HT appearing. They’re independent probabilities! How could they result in such different expected outcomes?

Well the proof is not that obvious, to start let’s look at a proof of the HH case.

So we have this recurrence relation given by this Markov chain where

So what does this mean? I chose the ordering of the terms to be quite suggestive. See, a quarter of the time we get HH in the first two flips, half the time we get a tails and have to restart (producing 1+x flips) and a quarter of the time we get HT and have to restart (producing 2+x flips).

If you solve this recurrence you’ll find x=6. But it turns out that the recurrence for HT is a little different. It actually looks like this:

I found this here and it has a pretty good explanation but I figured I’d add my two cents. It’s probably easier to explain this from the inside out, so let’s define our y term which represents the number of flips we’ll have to do to get our T.

In other words, if we just want to know how many flips we need on average to get 1 tails it’s this, which is 2.

I found it to be quite a motivating idea to recall that to get the sequence HT we need two pieces, we need an H and a T. So no matter what every sequence that ends in HT will have the form {some number of Ts, at least zero}{some number of Hs, at least one}{exactly one T}.

So on our first flip half the time we get a T and have to restart, thus the 1/2(1+x) term. Once we’ve found the first H half the time we get another, useless H, and have to flip again, thus the 1/2(1+y) term.

If you solve this you indeed get 4.

So I have one more contribution to add here, and that’s an experimental test. If you don’t believe me, you can try it yourself, I even included a sanity check to show that we on average take 2 flips to get a heads (or a tails):

import scala.util.Random

val random = new Random()

def flipCoin(): Char = { if (random.nextBoolean()) 'H' else 'T' }

def flipUntilSequence(seq: String, history: String): Int = {
if(history.endsWith(seq))
history.length
else
flipUntilSequence(seq, history + flipCoin())
}

val hh_es= for (i <- Range(1, 1000000)) yield flipUntilSequence("HH", "")
val ht_es = for (i <- Range(1, 1000000)) yield flipUntilSequence("HT", "")
val h_es = for (i <- Range(1, 1000000)) yield flipUntilSequence("H", "")

println(s"Average number of flips to get a heads: ${h_es.sum.toDouble / h_es.length}")

println(s"Average number of flips to get HH ${hh_es.sum.toDouble / hh_es.length}")
println(s"Average number of flips to get HT ${ht_es.sum.toDouble / ht_es.length}")

And indeed the result as of my most recent run is:

Average number of flips to get a heads: 2.0016590016590015
Average number of flips to get HH 6.001767001767002
Average number of flips to get HT 3.9996059996059996

So, is there a plain English explanation for why this works? Well I found a lot of the posts in this Stack Overflow thread really helpful but particularly this one. Put simply, in the HT case we can stay indefinitely in the state H_ and any time we hit a T we’re done, in the HH case every time we throw a T we have to start over and wait till the next throw of an H. Order really matters here.


The Coin Toss Paradox was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.

So I recently started reading this fantastic book from Quanta magazine titled “The Prime Number Conspiracy” that covers some of the biggest problems in modern mathematics and was once again nerd sniped by a math problem.

The book explains that if Alice is flipping a coin looking for the first two consecutive heads she will find it after, on average, six flips. If Bob is flipping looking for the first instance of heads and then tails he will find it on average after four flips.

What the heck!?
The chances of HH appearing are the same as the chances of HT appearing. They’re independent probabilities! How could they result in such different expected outcomes?

Well the proof is not that obvious, to start let’s look at a proof of the HH case.

So we have this recurrence relation given by this Markov chain where

So what does this mean? I chose the ordering of the terms to be quite suggestive. See, a quarter of the time we get HH in the first two flips, half the time we get a tails and have to restart (producing 1+x flips) and a quarter of the time we get HT and have to restart (producing 2+x flips).

If you solve this recurrence you’ll find x=6. But it turns out that the recurrence for HT is a little different. It actually looks like this:

I found this here and it has a pretty good explanation but I figured I’d add my two cents. It’s probably easier to explain this from the inside out, so let’s define our y term which represents the number of flips we’ll have to do to get our T.

In other words, if we just want to know how many flips we need on average to get 1 tails it’s this, which is 2.

I found it to be quite a motivating idea to recall that to get the sequence HT we need two pieces, we need an H and a T. So no matter what every sequence that ends in HT will have the form {some number of Ts, at least zero}{some number of Hs, at least one}{exactly one T}.

So on our first flip half the time we get a T and have to restart, thus the 1/2(1+x) term. Once we’ve found the first H half the time we get another, useless H, and have to flip again, thus the 1/2(1+y) term.

If you solve this you indeed get 4.

So I have one more contribution to add here, and that’s an experimental test. If you don’t believe me, you can try it yourself, I even included a sanity check to show that we on average take 2 flips to get a heads (or a tails):

import scala.util.Random

val random = new Random()

def flipCoin(): Char = { if (random.nextBoolean()) 'H' else 'T' }

def flipUntilSequence(seq: String, history: String): Int = {
if(history.endsWith(seq))
history.length
else
flipUntilSequence(seq, history + flipCoin())
}

val hh_es= for (i <- Range(1, 1000000)) yield flipUntilSequence("HH", "")
val ht_es = for (i <- Range(1, 1000000)) yield flipUntilSequence("HT", "")
val h_es = for (i <- Range(1, 1000000)) yield flipUntilSequence("H", "")

println(s"Average number of flips to get a heads: ${h_es.sum.toDouble / h_es.length}")

println(s"Average number of flips to get HH ${hh_es.sum.toDouble / hh_es.length}")
println(s"Average number of flips to get HT ${ht_es.sum.toDouble / ht_es.length}")

And indeed the result as of my most recent run is:

Average number of flips to get a heads: 2.0016590016590015
Average number of flips to get HH 6.001767001767002
Average number of flips to get HT 3.9996059996059996

So, is there a plain English explanation for why this works? Well I found a lot of the posts in this Stack Overflow thread really helpful but particularly this one. Put simply, in the HT case we can stay indefinitely in the state H_ and any time we hit a T we’re done, in the HH case every time we throw a T we have to start over and wait till the next throw of an H. Order really matters here.


The Coin Toss Paradox was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.


Print Share Comment Cite Upload Translate
APA
Daniel Kirby | Sciencx (2024-03-30T01:14:52+00:00) » The Coin Toss Paradox. Retrieved from https://www.scien.cx/2021/08/17/the-coin-toss-paradox/.
MLA
" » The Coin Toss Paradox." Daniel Kirby | Sciencx - Tuesday August 17, 2021, https://www.scien.cx/2021/08/17/the-coin-toss-paradox/
HARVARD
Daniel Kirby | Sciencx Tuesday August 17, 2021 » The Coin Toss Paradox., viewed 2024-03-30T01:14:52+00:00,<https://www.scien.cx/2021/08/17/the-coin-toss-paradox/>
VANCOUVER
Daniel Kirby | Sciencx - » The Coin Toss Paradox. [Internet]. [Accessed 2024-03-30T01:14:52+00:00]. Available from: https://www.scien.cx/2021/08/17/the-coin-toss-paradox/
CHICAGO
" » The Coin Toss Paradox." Daniel Kirby | Sciencx - Accessed 2024-03-30T01:14:52+00:00. https://www.scien.cx/2021/08/17/the-coin-toss-paradox/
IEEE
" » The Coin Toss Paradox." Daniel Kirby | Sciencx [Online]. Available: https://www.scien.cx/2021/08/17/the-coin-toss-paradox/. [Accessed: 2024-03-30T01:14:52+00:00]
rf:citation
» The Coin Toss Paradox | Daniel Kirby | Sciencx | https://www.scien.cx/2021/08/17/the-coin-toss-paradox/ | 2024-03-30T01:14:52+00:00
https://github.com/addpipe/simple-recorderjs-demo