Coin Flip Game Simulation
This program illustrates an amazing pattern-matching game discovered by Walter Penney (Jour. Recreational Mathematics, October 1969, p. 241). For a nice readable discussion, see the article "Nontransitive Paradoxes", in Martin Gardner's Time Travel and Other Mathematical Bewilderments, W. H. Freeman, 1988. For more technical details, see the article, "String Overlaps, Pattern Matching, and Nontransitive Games", by L.J. Guibas and A.M. Odlyzko, J. Combinatorial Theory 30 (1981), pp183-208.
The rules of the game are as described in the window above. The applet allows you to enter two target strings, or to enter one string and let the computer generate the other, or to let the computer generate strings. When two strings have been chosen, the predicted winning frequencies are displayed.
If you let the computer pick, it will always generate a string with the highest probability of winning against the string already chosen. If you click alternately on the GENERATE buttons, you will observe the game's amazing "nontransitivity": no matter which string you pick, I can always pick a string that will beat yours more than half the time.