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 ?

  • 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

1

The Markovian part goes something like this: Once you are in a state (being on a specific position), it does not matter how you got there (how far was the last number), for you to know where you are going to go next. Thus even without any memories you can still continues through the chain.

As you can see on

page 22 of yaroslavvb.com/papers/kovchegov-from.pdf

  • if start on the same number as player B, you will get to the same result with probability 1 (the probability of you guessing right is 1/10)
  • if you get it wrong, you have expected number of tries to land on the some of B's numbers of around 20, from which point you will get the same result.

So, you need to miss on the first try and not step on any of the numbers that B stepped to get a different end result.