Answer to Test Your Intuition 50: Detecting a Deviator

Two weeks ago we asked:

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?

And the answer is yes! This is proved in the following paper:

Identifying the Deviator, by Noga Alon, Benjamin Gunby, Xiaoyu He, Eran Shmaya, and Eilon Solan

Abstract: A group of players are supposed to follow a prescribed profile of strategies. If they follow this profile, they will reach a given target. We show that if the target is not reached because some player deviates, then an outside observer can identify the deviator. We also construct identification methods in two nontrivial cases.

The paper gives a non-constructive proof for a strategy to identify the deviator and in the case of two-player random walk it gives an ingenious explicit identification method!

Here is a variant of the problem devoted to Itai Benjamini: Consider planar percolation on the rectangular grid. One player chooses every vertical edge with probability 1/2 and one player chooses every horizontal edge with probability 1/2. Lo and behold, there is an infinite open cluster. Can you (explicitely) detect the deviator?


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

8 Responses to Answer to Test Your Intuition 50: Detecting a Deviator

  1. James Martin says:

    Very nice result!

    For Itai’s question, I think you can’t always detect the deviator (assuming the deviator is allowed to inspect the random part of the configuration).

    Say the vertical edge configuration is genuinely random, and shown to us. Now select the horizontal edges so that for every vertex v, exactly one of the vertical edge (v,v+(0,1)) and the horizontal edge (v,v+(1,0)) is open.

    You get a picture that looks like a “random walk web” (in the style of the Brownian web). From any vertex u, there is an infinite north-east path starting at u (it’s unique). With probability 1, the paths from any two starting points coalesce: so in fact the graph not only has an infinite cluster, it’s actually connected! But, for example, the distribution of the whole configuration is invariant under reflection in the line x=y, exchanging vertical and horizontal.

  2. James Martin says:

    How about this variant on Itai’s question, where the deviator is more restricted. We are given a $p=1/2$ planar percolation configuration. Now we are allowed to open some extra edges, which must either all be horizontal, or all be vertical, so as to create an infinite cluster. Can an inspector who is given the final configuration determine whether the edges we’ve added are horizontal or vertical?

    • Gil Kalai says:

      Hi James
      Indeed my version was a bit Naive. We can make it a game where the players decide on the edges in turns starting from the origin, and there are various other possibilities… Your variant is also nice!

    • Gil Kalai says:

      Based on James comment I also thought about the following version of the original flipping coin question: Suppose that each player had access to the full random bits of the other players. And now, based on this knowledge one of the two players replaces all its bits and causes the sequence never to come back to the origin. Can we still identify who the deviator was?

      • Ilan K says:

        I don’t think so. Suppose player 1 is the deviator. He can go on his first step the same direction as player 2 (in this scenario he knows where player 2 will go), and then on his nth step, n>1, go in the opposite direction of player 2’s nth step.

  3. Martin Gaul says:

    Very interesting. On pp 8. the authors write “Thus Deviator must keep the walk fairly close to 0.” This seems to imply finite lim inf s_n = C. In such case isn’t it trivial to find the Deviator? Since Honest player can never reach C infinitely often, otherwise it will chose to go to C-1 about half of the times.

  4. As I read through this post on math, I can’t help but be amazed at all the fascinating details I’m learning. Each new fact makes me even more excited to learn more about this topic. You’ve written so well that I feel like I could actually understand math. now!
    I know there are other great resources out there for learning math, so I’m going to check them out now. But before I go, I just want to say thank you for sharing all of this information with us. It’s really helped me understand math in a whole new way.

Leave a Reply

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

You are commenting using your 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