6
$\begingroup$

This is an example in Durrett's book "Probability theory: theory and examples", it's about the coupling time in Markov chains, but I can't see the reason behind it.

The trick is played by two persons A and B. A writes 100 digits from 0-9 randomly, B choose one of the first 10 numbers and does not tell A. If B has chosen 7,say, he counts 7 places along the list, notes the digits at the location, and continue the process. If the digit is 0 he counts 10. A possible sequence is underlined in the list:

$$ 3\ 4\ \underline{7}\ 8\ 2\ 3\ 7\ 5\ 6\ \underline{1}\ \underline{6}\ 4\ 6\ 5\ 7\ 8\ \underline{3}\ 1\ 5\ \underline{3}\ 0\ 7\ \underline{9} \ 2\ 3\ ...$$

The trick is that, without knowing B's first digit, A can point to B's final stopping location. He just starts the process from any one of the first 10 places, and conclude that he's stopping location is the same as B's. The probability of making an error is less than 3%.

I'm puzzled by the reasoning behind the example, can anyone explain it to me ?

  • 3
    I do this with my class and they are mystified. It is possibly the least amazing card trick ever, but the coupling idea is that if by chance they ever hit the same card they hit all the same cards afterwards.2012-11-27
  • 0
    See page $22$ of http://www.yaroslavvb.com/papers/kovchegov-from.pdf for a rewording of @mike's comment2012-11-27
  • 0
    @mike:could you explain me further? I did not quite see how to view the process as a Markov process.2012-11-27
  • 0
    I don't think it illustrates the markov part , I think it's meant to illustrate the 'coupling' part. The only randomness (necessarily) in the card trick is the choice of initial card, it should work even with the deck in order. The idea for markov chains is to start one from its stationary distribution and the other from any state, and run them independently until they land in the same state, then you can push them forward together in exactly the same way.2012-11-27

1 Answers 1