A Coin Flip Paradox and the ABRACADABRA Theorem for infinite monkeys: How long does it take? #SoME2

Which takes more coin flips to come up on average, Heads-Tails or Heads-Heads? What about HHTT vs HTHT? Find out how long it takes and why using the magical ABRACADABRA Theorem. The method also works for dice rolls, the speeding rule in Monopoly, or a monkey typing at a typewriter.

Video created for the @3blue1brown Summer of Math Exposition 2 #SoME2

Related Links:

Blog post with more accurate histogram of HT vs HH:

Blog posts on ABRACADABRA Theorem:

Video with more detailed proof:

Solutions using the Markov chain method shown in the intuition section:

Music by Vincent Rubinetti
Thank you Vincent for giving permission to use your wonderful music!
Download the music on Bandcamp:
Stream the music on Spotify:
Track used: Euler's Clock

#math #maths #probability #3blue1brown #some2 #animation

Timestamps:
00:00 HH vs HT
00:36 Simulations and Histogram
02:13 Theoretical averages and E
02:54 HHTT vs HTHT is counterintuitive
03:50 Intuition by partial progress
05:43 Fair casinos and fair bets
06:19 The optional stopping theorem
07:41 Fair casino setup for HT
09:04 Example THHHT and E[N_HT] =4
11:57 Fair casino setup for HH
12:55 Why HH is different and E[N_HH] =6
14:12 Fair casino setup for HTHT
14:34 Why only the last flips matter
15:26 E[N_HTHT] =16+4
15:38 Fair casino setup for HHTT
15:12 E[N_HHTT] = 16
16:12 Other examples and E[N_HHH] =13
16:42 Number of dice rolls to get 666
17:18 Doubles three times in a row
17:39 Monkey at a typewriter
18:40 ABRACADABRA Theorem
19:11 Probability with Martingales

[WannesMalfait]

Wow! This is my favorite SoME2 video (and I have seen a lot of them by now). I just loved everything about it. At the start, like others mentioned, when I saw the 'state transition graph' my mind immediately went to stochastic matrices and how to solve the problem using some linear algebra. The solution presented is much more elegant and simple. The way you lead us to the solution makes me think that I could come up with it myself. Hope your video gets more recognition, because it definitely deserves it!

[TheMightyGiantDad]

The most surprising thing i learned from this is that just because 2 events have the same probability of occurring does not mean it takes the same amount of time for both to occur! Consider the expected number of die rolls to get 6, 6, 6 vs. 1, 2, 3. Great video!

[johnchessant]

Great video! Another interesting phenomenon is called (funnily enough) Penney's game. Let's say players A and B each choose a sequence of heads/tails of length 3, and a coin is flipped until one of their sequences shows up; the player who chose that sequence wins. If B is allowed to base their choice on what A does, then B can win more than half the time no matter what A does. e.g. if A chooses HHT, then B can choose THH, which will appear before HHT with probability 3/4; if A chooses THH, then B chooses TTH and wins with probability 2/3; if A chooses TTH, then B chooses HTT and wins with probability 3/4; and if A chooses HTT, then B chooses HHT and wins with probability 2/3. It's non-transitive!

[samiulhaquerounok]

Most premium quality, knowledge full video I have ever seen.

[pawebielinski]

This is outrageously, midbogglingly awesome.

[chessbot-lbct]

This is such a nice video! I remember a long time back I read about this fact online and I could not come to terms with the fact that THH is objectively easier to get than THT. This video does an amazing job of explaining such a counterintuitive concept. :D

[mgostIH]

This was enlightening, I remember not getting martingales because I saw no application for something we prove can't be exploited, but the analogy with conservation of energy and the multiple examples were really helpful in seeing why one may care about them!

[kaustavghosh]

This is the best explanation of the problem I have seen. Similar solutions can be obtained iteratively for smaller number of characters but always wondered how to generalize it. Finally know how its done and also the fact that this problem has such a cool name.

[Number_Cruncher]

This was completely new to me. I understood your explanation and it's really surprising. I will need to do some calculations and simulations to really believe it. Thanks a lot.

[EpsilonDeltaMain]

Definitely one of the best submissions for SoME2!!

[yoavshati]

Commenting my intuition before watching the video:
An attempt at getting HH or HT starts when getting H (it doesn't really matter how many Ts you got before that). For HH, you either get another H and stop, or get T and have to start over again. For HT you either get T and stop or H and then you're right back where you just were, with an initial H hoping for a T

[yearnEducation]

Great video! Interesting topic and well presented. Keep up the good work!

[FineDesignVideos]

This was a joy to watch and think along with, thank you!

[MaiZhang]

Brilliant video and such an elegant method! I wonder if there's any intuitive explanation of why the more a sequence self-overlaps, the more time it takes for it to show up?

[julianpbt]

Your explanation is very good for getting the answer, but never explains the intuition behind the method we are using. For example, HHHT has 1 checkpoint (T at the 4th spot) and takes 16 flips to get. However HTTH has 2 checkpoints at spots 2 and 3 but takes 18! Can someone explain me why?

[diribigal]

Maybe this is just because the general theorem/approach was new to me, but this seemed even better than your Buffon videos

[thechessplayer]

Easy intuition: when HH fails it starts from scratch when HT fails it starts from halfway. So my guess is HT requires less flips. Another way of thinking about it: after H on average 2 flips to get T. On average two flips to get first H so 4 to get HT. How many flips to get two H in a sequence not necessarily adjacent? Also 4. But additional requirement they have to be adjacent. This is another reason HH should take longer.

Also this problem feels like Knuth Morris Pratt.

[p_sopasakis]

If we have an unfair coin where the probability of heads is 65.14%, then we should expect to observe (H, H) and (H, T) after approx. 2.535 tosses.

[Boringpenguin]

Brings me back to the good old days when I got completely annihilated by Martingales and Stochastic Calculus 😂

[stephenliao]

I solved the HT with recurrence relation and summation skills in 10 minutes, but when I deal with the HH case, the recurrence relation has a solution

And by calculating the infinite summation finally get the correct result after 2 hours.😂