Mathacadabra
Home > Discussions > Probability
Note: this page uses MathJax for formatting, so may take a few seconds to load.


Coupling
Bob Dobrow

Guess the number
One hundred random integers are written on the board, each uniformly distributed from one to nine. A volunteer is asked to pick one of the first few numbers on the list, but not tell anyone which number they choose. They are then told to select numbers as follows. If they are currently at $i$, they count down (in their head) $i$ positions to the next number. If the next number is $j$, they then count $j$ numbers to the next, etc., etc. They continue doing this until they get to a last number and can not move further.

For instance, if the first 20 numbers are
5 7 7 3 3 9 6 8 2 9 4 2 3 9 6 2 3 7 3 3 . . .
and the volunteer has chosen the first 3 as their initial number, then their successive numbers will be 3, 6, 3, 2 7.

The "magic" aspect of all this is that the magician is able to tell the volunteer what their last number is!

You do it! Here are 100 numbers chosen uniformly at random
8 6 1 1 4 3 8 9 7 8 7 1 2 8 3 5 5 8 7 1 2 2 1 9 4 9 2 4 9 9 9 4 9
1 5 8 7 9 1 7 3 6 6 3 2 6 9 6 5 5 1 2 5 6 5 3 5 4 6 2 6 7 5 4 7 7
7 4 4 2 7 8 5 2 1 2 9 7 5 1 1 9 9 6 3 4 1 1 2 2 4 1 2 7 9 8 5 1 5 7
Choose an initial number and count to the end. I claim that your last number is . . . 9.

The trick illustrates a powerful idea in probability called coupling. Suppose there were two volunteers to do the trick, and they chose different initial numbers. Observe that as each volunteer counts out their numbers, if at any point they both land on the same number, then they will continue to land on the same number for the rest of the process. We say that the two random processes (of selecting successive numbers) has been coupled.

The coupling time is the (random) time when the two processes are first coupled. And the trick is based on the fact that the coupling time for two independent processes with high probability will occur before the 100th number has been picked. In fact, it can be shown that for 50 numbers, the probability that two processes will be coupled is about 80%; and for 100 numbers it is about 94%. Thus all the magician has to do is choose any number from the first few numbers, do the selecting in their head, and report the final number as the volunteer's final position.

The trick can be done with a deck of cards (let face cards be equal to five). The chance that the magician will get it right is about 80%. With two decks of cards the success probability is about 95%.

     Bob Dobrow is a Professor of Mathematics at Carleton College in Minnesota.

For more information about this trick, see the following.
  1. Lagarias, J.C., E. Rains, and R.J. Vanderbei. Preprint. The Kruskal count. Available at http://xxx.lanl.gov/abs/math.PR/0110143.
  2. Gardner, Martin. 2000. Modeling mathematics with playing cards. College Mathematics Journal 31(May):173-177.