Exploring Markov chains and Martingales with kids

Earlier this week I saw a neat tweet from Greg Egan:

If you toss a coin until a sequence of N heads comes up, the probability that this happens after i tosses is the (i–1)th “N-bonacci” number divided by 2^i.

By a Markov chain calculation, the *expected* number of tosses will be 2^N + 2^{N–1} + … + 2.

So, combining the two: pic.twitter.com/kyiIxtlhS5

— Greg Egan (@gregeganSF) December 9, 2019

It reminded me of an old project we did back in 2017 using Markov chains and Martingales:

The Most Interesting Piece of Math I Learned in 2017 -> The COVFEFE Problem

The Martingale take on the COVFEFE problem (and the amazing ABRACADABRA problem) came from this paper:

Martingale’s and the ABRACADABRA problem by Di Ai

This week I was using some of the Markov chain ideas for a few fun projects with my older son who is studying linear algebra. Today I though it would be fun to revisit the COVFEFE problem and then look at some coin flipping examples inspired by Greg’s tweet.

We started with a brief discussion of the COVFEFE problem and then switched to coin flipping at the end. It took me a bit to get my brain going on this project – sorry for a few obvious mistakes at the beginning of the discussion . . . .

Next we went to the computer to look at the approach to the word typing / coin flipping problems via Markov chains. Instead of the COVFEFE problem, we are looking at the expected number of coin flips required to see the sequence HTHT. The ideas here and the code are things I learned from Nassim Taleb – see the references in the project linked above:

Next we returned to the whiteboard to talk about the Martingale approach to the problem. The ideas here are things that I learned from Christopher Long and also from the paper linked above.

Here we take a quick look at the COVFEFE problem, the ABRACADABRA problem, and see why the HTHT problem takes on average 20 flips.

Finally, we computed the expected number of flips required to see each of the 16 different combinations of 4 coin flip sequences -> HHHH, HHHT, HHTH, and etc. The calculation for all 16 cases took a little longer than I usually want one of these videos to run, but I wanted to do all of the cases to help the boys understand the ideas that go into the calculations:

A detailed discussion of the concepts of both Markov Chains and Martingales are above what anyone could reasonably expect a 10th grader and 8th grader to understand. But the ideas are so neat that I thought showing these fun examples would make a great project for kids.