Test Your Intuition 50. Two-Player Random Walk; Can You Detect Who Did Not Follow the Rules?

Ruth and Ron start together at the origin and take a walk on the integers. Every day they make a move. They take turns in flipping a coin and they move together right or left according to the outcome. Their coin flips create a simple random walk starting at the origin on the integers.

We know for sure that they we will return to the origin infinitely many times. However, their random walk never comes back to the origin, so we know for sure that one of them did not follow the rules!

Test your intuition: Is it possible to figure out from the walk whether it was Ruth or Ron who did not follow the coin-flipping rule?


This entry was posted in Probability, Test your intuition and tagged , . Bookmark the permalink.

13 Responses to Test Your Intuition 50. Two-Player Random Walk; Can You Detect Who Did Not Follow the Rules?

  1. Ilan says:

    My intuition says yes, but it would be more interesting if the answer is no, which I suspect is the reason you asked it.

  2. Separate into two separate walks, by taking every other flip. The cheater’s private walk will not obey recurrence.

    • Ian D-B says:

      Suppose the cheater’s strategy is simply to do the opposite of whatever the non-cheater does on every move after the combined walk gets up to +2 or -2, so that the walk stays permanently above zero. Then the cheater’s walk alone is the mirror image of the non-cheater’s and will recur infinitely often.

      (to make sure it gets to +/-2, the cheater just does the same as the non-cheater on the first step, i.e. if the non-cheater goes +1, then so does the cheater. Ever after, the cheater always does the opposite).

  3. Ilan says:

    What if the cheater knew in advance the sequence of coin tosses of the non-cheater. Would this change the answer?

  4. Ilan says:

    I wonder what would happen if the cheater moved to the right with probability 0.5 + 2^{-k}, assuming he was k steps right of the origin?

  5. Ian D-B says:

    When the cheater starts their turn at +1 (or -1, if on that side), they always have to play +1. Suppose the cheater is truly random except at +1. Then you’ll be able to tell by their behavior there, since you’ll get to +1 infinitely often.

    Now obviously they could try to avoid ever getting to +1, but that just shifts the problem back a step.

    So those simple strategies fail.

    Alternatively, they could try to make the probability of getting to +1 very low, but not to zero, such that they don’t actually reach +1 infinitely often. The question is if they can do this in such a way as to be undetectable.

    That is, my intuition here is that a strategy for the cheater will always be one that is random when very far from the origin, and progressively less random as the walk gets closer. It’s just a question of whether the deviations from randomness can be small enough to stay undetectable.

    Another observation: it seems like it’s enough to check whether a player’s action is random conditional just on the current state of the walk. Conditioning on past values of the state seems irrelevant.

  6. Assume that the process is always positive. This raises suspicion that one of the players fakes “right” more often then “left”, to avoid hitting zero. This strategy probably could be “masked” by faking “left” more often when safely distant from the origin, so the “mean value” stays zero. Yet then one would be able to see that the right/left distribution of faked moves inevitably depends on the current position of the walkers, which I suspect can be statistically confirmed over a long enough interval.

    On the other hand, even if both walkers are honest and probability of never hitting the origin is nil, this does not mean that such event is impossible (a perfect coin in principle can produce an infinite series of tails-only). Thus maximum that one will be able to say is to indicate a possible culprit with an astronomic credibility, yet not prove the guilt.

  7. Rikhav says:

    Let x be the smallest absolute state that appears infinitely often (if it exists). Say Ron moves first, so he moves whenever the current state is even. Then if x is even, Ron is the cheater since he only moves toward the origin with probability 0 from x. And if x is odd, Ruth is the cheater by the same argument.
    So a competent cheater would ensure no state is visited infinitely often. But this requires the walk to drift. By separating the walk into just the moves that Ron makes and just the moves that Ruth makes, just the cheater’s walk will drift.

    • The last step in the proposed argument is problematic: You are assuming that if $X_n+Y_n$ tends to infinity and $Y_n$ is a simple random walk, then $x_n$ must tend to infinity. This fails, for instance, if $X_n=\log_2(n)-Y_n$. E.g. If Ron reverses Ruth’s last move at all times that are not a power of 2, and at the powers of 2 he steps right.

  8. I found this quite hard but very enjoyable. We can detect who broke the rules. I will sketch the reason soon.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s