I've been self-studying Markov Chains and came across a problem online here: http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf

I'm not asking for anything too formal (I'm still a newbie on the subject), but I would appreciate an intuitive explanation.

I'll summarize the problem as follows:

I draw 100 digits uniformly at random, with replacement, from the set of numbers {1, 2, . . . , 9, 0}, and list them in the order in which they were drawn. Then, two players A and B each follow these set of rules:

  1. Randomly choose one of the first 10 digits.
  2. Move forward as many digits as the number that is hit, except move forward 10 digits when a 0 is hit. For example, if a player randomly chooses the digit 3, move 3 steps to the right, and observe the digit at that spot.
  3. Repeat.
  4. Stop when the next move would go beyond the 100th digit, and record the last digit that you stopped at.

It turns out that the probability that the two players record the same last digit is approximately 0.974. Why is this probability so close to 1?

So obviously this problem is about coupling. I have a couple questions about it:

1) I can see that the longer this game goes on, it becomes more likely for players A and B to eventually converge to the same digit, after which they are in lock-step. Even at the very beginning, the probability that A and B both randomly happen to choose the same digit is >= 1/10, and the probability can only increase from there. However I don't know how one could actually compute the probability of convergence in this case or even to put a reasonable lower bound on it. Perhaps someone could give a more detailed (albeit informal) explanation?

2) I wonder if, for a particular list of 100 randomly chosen digits, it is possible to simply observe this list and somehow figure out with some high confidence which number you're likely to end up at, given the above rules. I suspect it should be possible (without running a bunch of brute-force simulated trials), but is it as simple as, say, just playing the game yourself (once) and choosing the last digit you ended up at?

  • 1
    $\begingroup$ Build a Markov model, where the state of the Markov model indicates how far A is ahead of B? There can be only 10 states to this Markov model, so you should be able to find the limiting distribution of it fairly easily. $\endgroup$ – D.W. Sep 18 '17 at 6:18
  • $\begingroup$ The normal rule is one question per post. So let me answer your second question in a comment. You can simulate all 10 possible runs and record the 10 last digits. Given that, it is easy to calculate the convergence probability for this particular choice of 100 random digits. $\endgroup$ – Yuval Filmus Sep 18 '17 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.