The Blended Game
My PRIMES STEP students invented several variations of Penney’s game. We posted a paper about these new games at math.HO arxiv:2006.13002.
In Penney’s game, Alice selects a string of coin-flip outcomes of length n. Then Bob selects another string of outcomes of the same length. For example, Alice chooses HHT, and Bob chooses THH. Then a fair coin is tossed until Alice’s or Bob’s string appears. The player whose string appears first wins. In our example, Bob has a greater probability of winning, namely, 3/4. If the first two flips are HH, then Alice wins; otherwise, Bob wins.
The reader can check that HHT beats HTT with 2 to 1 odds. Thus, the game contains a non-transitive cycle it is famous for: THH beats HHT beats HTT beats TTH beats THH.
I already wrote about the No-Flippancy game that my students invented. It starts with Alice and Bob choosing different strings of tosses of the same length.
However, in the No-Flippancy game, they don’t flip a coin but select a flip outcome deterministically according to the following rule: Let i ≤ n be the maximal length of a suffix in the sequence of “flips” that coincides with a prefix of the current player’s string. The player then selects the element of their string with index i + 1 as the next “flip.” Alice goes first, and whoever’s string appears first in the sequence of choices wins.
My favorite game among the invented games is the Blended game, which mixes the No-Flippancy game and Penney’s game.
In the game, they sometimes flip a coin and sometimes don’t. Alice and Bob choose their strings as in Penney’s game and the No-Flippancy game. Before each coin flip, they decide what they want by the rule of the No-Flippancy game above. If they want the same outcome, they get it without flipping a coin. If they want different outcomes, they flip a coin. Whoever’s string appears first in the sequence of `flips’ wins.
For example, suppose Alice selects HHT, and Bob selects THH. Then Alice wants H and Bob wants T, so they flip a coin. If the flip is T, then they both want Hs, and Bob wins. If the first flip is H, they want different things again. I leave it to the reader to see that Bob wins with probability 3/4. For this particular choice of strings, the odds are the same as in Penney’s game, but they are not always the same.
This game has a lot of interesting properties. For example, similar to Penney’s game, it has a non-transitive cycle of choices. Surprisingly, the cycle is of length 6: THH beats HHT beats THT beats HTT beats TTH beast HTH beat THH.
Share:
Cristóbal Camarero:
I think you have copied the 6-cycle in reverse. You have actually said in the preceding paragraph that Bob with THH beats HHT thrice each four games, right?
10 July 2020, 6:55 amtanyakh:
Thank you, Cristobal,
You are right, I fixed it.
12 July 2020, 1:34 pmDivicius:
Hello, big fan of your blog from France here.
23 July 2020, 3:50 pmI teach 11 to 15 years old and this post make me think of something I encountered this year.
My question was : Alice wants to choose randomly an integer from 1 to 10 (both included). She only has one coin. Write a way for her to do it.
It was the first time I asked this question in years of teaching. Few found a valid answer and it was always a variation of four toss and ignore 6 possibilities.
I asked myself, is there a more elegant way but didn’t think of one.
If someone does, I’m going to elaborate on that question this year with various dices.
tanyakh:
Divicius, You might be able to prove that if you want to guarantee a finite number of throws, the probabilities should be p/q, where q is a power of 2. If you need 1/10, the number of tosses is not guaranteed to be finite.
23 July 2020, 5:13 pmYogendra Singh:
I read your blog and i think you have copied the 6-cycle in reversible order. You said in that paragraph Bob with THH beats HHT thrice every four games, ok?
24 August 2020, 12:37 pm