In this post I will tell you the story of the hunter and the rabbit. To keep you interested let me say that in the story we will see a powerful (yet trivial) inequality that I learned today from Yuval Peres, which he calls a reversed second moment method (we will also review the basic second moment method).
We consider a sequential game between a hunter and a rabbit. At each time step the hunter (respectively the rabbit) is at a certain vertex (respectively at ) in the cycle (with vertices labeled ). We impose the constraint that and must be neighbors, that is the hunter can only move one step at a time. We impose no restriction on the rabbit (he can jump around like a real rabbit). Let be the capture time. We allow for randomized strategies for the two players.Of course the hunter wants to minimize the expected capture time while the rabbit wants to maximize it.
December 3rd clarification: the processes and are independent, in other words the hunter does not see the rabbit and vice versa (the game would be trivial otherwise!).
Theorem [Adler et al., 2003]: The hunter can always ensure and the rabbit can always ensure .
We will now sketch the proof of this beautiful theorem following the method of [Babichenko et al. 2012]. Quite intuitively it is enough to show that there exists a strategy for the hunter that ensures for any deterministic rabbit , and respectively that there exists a strategy for the rabbit that ensures for any deterministic hunter (see Lemma 2.2. here for a formal proof of this).
The hunter’s strategy
Let be independent uniform random variables on . The location of the hunter at time is . In some sense this hunter moves at a random speed determined by and in a random direction determined by . The key idea to analyze this strategy is to consider the number of collisions before time . Clearly
where the inequality is a ‘strong’ form of the second moment method which can be proved with Cauchy-Schwarz as follows (recall that the basic second moment simply says ):
Now it is just a matter of computing and which can be done very easily, see page 9 here.
The rabbit’s strategy
The rabbit’s strategy is an order of magnitude more complicated/more beautiful. The basic intuition to design a good rabbit’s strategy is the reversed second moment method which is the following trivial inequality:
Let us look into this last term in more details. Of course the rabbit’s location at a given time step should be uniformly distributed, thus the numerator will be equal to (recall that here the hunter is deterministic). Thus we want to maximize the denominator, in other words once the rabbit has collided with the hunter, he should try to collide as much as possible after that! This is in my opinion a truly beautiful intuition. The way to achieve this proposed in [Babichenko et al. 2012] goes as follows. Let be a random variable uniformly distributed in and be a simple random walk (independent of ) in . Let and for ,
The rabbit is then defined by (with ). Using basic properties of the simple random walk in 2 dimensions one can analyze the term in a few lines, see page 7 here. I suspect that one could come up with other rabbit strategies that achieve the same excepted capture time.
By Bob Vanderbei November 30, 2013 - 6:06 am
It looks like you have assumed that both the hunter and the rabbit are blind. At first, I was imagining otherwise. Of course, the not-blind game is trivial—the rabbit will always jump to a state more than one step away from where the hunter currently is.
By Sebastien Bubeck November 30, 2013 - 10:45 am
You’re absolutely right Bob, sorry for not making this precise. I’m wondering what happens if they can see each other AND if the hunter can also jump (it could be that the game is still trivial, I don’t know).