Monte Carlo Simulation of Penney’s Game

I’ve been doing riddles lately. I recently came across this post on Quora which told me about Penney’s Game, a fascinating logic problem that is somewhat counterintuitive.

penneysQuora.png

Naturally, I read his answers: https://www.quora.com/What-are-the-solutions-to-Penneys-game-and-what-is-the-explanation

I didn’t understand this trickery, and wanted to see the probabilities for myself. I’ve also been learning MATLAB, so I devised a simple form of Monte Carlo simulation to see how the probability of each pattern diverged over a number of trials.

I wrote a game which takes any number of players and any length of heads-tails sequences. For example, I could play a game with the following:

  • Player 1: TTHT
  • Player 2: HHHT
  • Player 3: THTH
  • Player 4: HHHH

(Players can also choose sequences of different lengths, but that usually makes the game significantly favor shorter sequences.)

Here are the results using the above sequences. Over 5000 games, it’s easy to see how the probabilities diverge.

penneysSim.png

The full game output looks like this:

penneysMAT.png

Note how HHHT and HHHH had almost identical win probabilities. This is because once the pattern H-H-H emerges, there is a 50% chance that the next flip will be H, and a 50% chance that it will be T.

Interestingly though, HHHT took an average of 16.17 flips to emerge, whereas HHHH took nearly twice that, with 30.32 flips. Why the discrepancy? Alon has a great explanation, also linked above: https://www.quora.com/What-are-the-solutions-to-Penneys-game-and-what-is-the-explanation

Check out my GitHub for the MATLAB files.

Also: a similar problem with a great explanation: https://mindyourdecisions.com/blog/2008/05/20/the-dice-brain-teaser-a-technical-interview-question-that-can-help-you-solve-problems-better/