Department of Mathematics --- College of Science --- University of Utah

To Be Unpredictable

The Applet on this page let's you try your skill at being unpredictable. After clicking on the Applet you'll see a new window pop up. There are a number of text fields and buttons. In particular, on the left there are two buttons labeled HEADS and TAILS. Clicking on the two buttons creates a sequence of Heads and Tails akin to a sequence of coin tosses. (We'll use the word toss and click interchangeably.)

Your task is to create a sequence that is unexpected. You will probably find this a very difficult thing to do.

What does unexpected mean? The code considers the last few tosses in the current sequence and sees if that sequence has occurred before. If so it predicts that you will click on the same button as you did the last time. The size of the last subsequence is is as large as possible, but no larger than the number $ m$ listed in the second text field of the control panel. The maximum possible value of $ m$ is 15. A smaller value may be more effective, and you may want to pick a very small value, like $ m=1$ for experimental purposes. Regardless of your choice of $ m$, the system keeps track of your key clicks for all subsequences of length up to $ 15$. Thus you can change $ m$ as you go along, and if you increase its value past information will already be present.

If no past information is available, for example before your first choice of Heads or Tails, the system guesses that you'll choose Heads. So you'll get off to a good start by clicking on TAILS.

The large text field in the control panel lists the current score, for example:

$\displaystyle \hbox{ :) 10: player: 6 / comp: 4 score 0.6 }$

The smiley face indicates that the computer guessed wrong at the last toss, there have been a total of 10 tosses, in 4 cases the computer guessed right, and in 6 it guessed wrong. The score is the difference between the player's score and the mean (half the number of guesses), divided by the standard deviation. A positive score means the player is ahead, a negative the opposite. If the score exceeds $ 3$ the text field turns green, if it is less than $ -3$ it turns red. These color changes can be construed as a win by the player or computer, respectively. It is unlikely that a deviation from the mean by three standard deviations is by chance.

The reset button resets the computer memory and lets you start over. Clicking on the applet or the Quit Button exists the code.

You can see the computer's upcoming guess by clicking on Next. Let $ n$ be the number in the text field to the right of that button. If $ n=0$ the computer's guess is printed to standard output. It is also indicated in the title of the control panel. If $ n>0$ the next $ n$ optimal player tosses are applied and listed to standard output.

The behavior of the computer is entirely deterministic and thus it is possible, by careful bookkeeping, to obtain a perfect score against it. The following table lists the beginning of the optimal sequence of tosses (with $ m=15)$ that give rise to that score.

  Toss  Computer Player Why?
  1   H   T   Initial computer guess H, no history. Player plays T.
  2   H   T   past history is T, never occurred before.
  3   T   H   toss 2 was T after T, computer guess will be T again, player plays H
  4   H   T   past history is H, never occurred before.
  5   H   T   toss 3 was H after T, guess will be H again.
  6   H   T   toss 3 was H after TT, guess will be H again.
  7   T   H   toss 6 was T after TT, guess will be T again.
  8   T   H   toss 4 was T after TTH, guess will be T again.
  9   H   T   toss 8 was H after H.
  10   T   H   toss 9 was T after H.
  11   H   T   toss 8 was H after TH.
  12   T   H   toss 5 was T after THT.
  13   T   H   toss 11 was T after HTH.
  14   T   H   toss 9 was T after THH.
  15   H   T   toss 14 was H after HH.
  16   H   T   toss 10 was H after HHT.
  17   T   H   toss 6 was T after HTT.
  18   H   T   toss 8 was H after TTH.
  19   T   H   toss 5 was T after TTHT.
  20   H   T   toss 14 was H after THTH.

The first 1000 tosses in the optimal sequence (given above in red letters ) are:

TTHTTTHHTHTHHHTTHTHTTHHHHTHHTTTTHTTHTTTTTHHHTHTTTH
THHTHHHHHTTTHHHHHHTHTHTHHTTHHTTTHTTTHTTHHTHHTHTTHT
HHHHTTHHHTTTTTTHTHTHTTTTHHTTHTTHTHTHHHHHHHTTHTTTHH
HTTHHTHTTTTTTTHHTHHHTHHHHTHTTHHTTHHHHHTHHHTTTHTHTT
THHTTTTTHTTTTHTHHHTHTHHTHTHTTHTTHHHTHHTHHTTHTHHTTT
HHTHHTTTHTHHHHHTHTTTTHTTTHHTTHHTHHHHTTTTHHHHTTHTHH
HTTTTHTHTTHTHTTTTTHTHHTTHTTTTHHHTTTHHTTTHHHTHHHTHT
THTTTHTHTHHTHHTHHHTTHHHHTTTHTTHTHHTHTTTHHHHTHTHHHH
THHHHHHTTTTTHHTTTTHHTHTTHHHTTHTTHHTTTTTTTTHTTHHHHH
HHHTHHTHTHHTTTTTHHHHHTTHHTTHTHTHTHTTHHTHTHTHTHHHTH
HTTHHHTHTHTTTHTTTTTTHHHTTHTHHTHHTTTTTTHHTTHHHTTHHH
THHHHHTHHTTHTTHHHHTTHHTHHTTHHTHTHHTHHHTHTHTHTTTHHH
THTHHHTHTTTTTHHTHTHTTTTTTHTTTHTHHHTTHHTTTTHTHHTHTH
HHHHTTHTHTHHTTTHTTHHHTTTHTTTTHHTHHTHHTHTHTHHHHTTTH
HTHTTTHTTHTTHTTTHHTHHHHHHHHHTTTHTHHTTTTHHHTHHTTTHH
HHTTTTTTTHTHHHHTHTHTTHHHTHTTHHHHHTTTTHTTTTTHTTHTHT
THTTTTHTTHHTTHTTTHTTTHHHHHTHTHHTTHTHTTTHTHTTHHTTTH
HTTHTHHHHHHTHHHHTTHTTHTTHHTHTTHTTHTHHHTHHHTTHTTTTT
TTTTHHHHTHHHTHHTHTTTTHHHHHHHTHTTHTHTHTTHTHHTTHHHHT
HTTTHHTHTTHTHTTHHTHHHTTTTTHTHTTTTHTHTHHHTTTHHHTTTT

Of course, the challenge is to win against the code unaided, depending only on your memory and intuition. On the other hand, you don't have to get a perfect score, just work your way up to three standard deviations. Good luck!

Winning Sequences

You can make your life easier by reducing the value of $ m$. For example, it's pretty easy to see that if $ m=1$ the optimal sequence starts with T T H T T H H and from then on keeps repeating T T H H. The following table lists the repeating parts of optimal sequences for small values of $ m$.
m repeating part
1 T T H H
2 T T T H H H T H
3 T T T T H H T H T H H H H T T H
4 T T T T T H T T T H H T H T H H H T T H T H T T H H H H H T H H

If you set the value of $ m$ accordingly and keep entering the above mentioned sequence of tosses you will win. There is an obvious structure in those sequences that you may want to investigate. If one starts some way, and then plays optimally, the sequences of tosses will become periodic. Let's define a winning period to be a sequence of coin tosses which is such that if we start with it, and keep repeating it, eventually the computer will cease scoring at all. (Of course a winning period depends on $ m$ .) Here are some possible questions to ask:

  1. Are there other winning periods?
  2. Are there winning periods of length different from 2m+1?
  3. If not, for a given $ m$ what are the lengths of the shortest and longest winning periods?

Alternative Input

You can also enter your guesses as a string in the scoring text field as a string containing (upper case) T and H for tails and heads. Type or paste your input, and hit the ENTER key. All other characters are ignored, including any output that may still be in the text field. If you download the code (see below) you can similarly enter the sequence through standard input. In a Unix environment you can pipe the output from another program into the code described here. It's particularly interesting to pipe the output from the program (obtained with the Next button into another instant of the program, and to see the effect of different values of $ m$.

Downloading the code

You can download the code and run it in without a browser or being connected to the internet. Call the file coins.class. On a Unix System you can invoke it with the command java coins. On a PC the command jview coins may work.