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.

Technical notes:

  1. You can choose to play individual trials with the NEXT TRIAL button, or check the CONTINUOUS button to play repeated trials.
  2. Clicking RESTART clears the target strings. Click NEXT twice to enter new strings.
  3. Java 1.1 or later is required.
  4. This applet was specially  commissioned for Math 390b, and was written by Michael Chen. It is still a  beta version, and we would be interested to hear of any bugs or incompatibilities. Please email me if you encounter problems.