The hunter and the rabbit

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 t \geq 0 the hunter (respectively the rabbit) is at a certain vertex H_t (respectively at R_t) in the cycle C_n (with vertices labeled \{0, \hdots, n-1\}). We impose the constraint that H_{t+1} and H_t 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 \tau = \min \{t \geq 0 : R_t = H_t \} 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 R_t and H_t 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 \mathbb{E} \tau \leq c_1 n \log n and the rabbit can always ensure \mathbb{E} \tau \geq c_2 n \log n.

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 \mathbb{P}(\tau < n) \leq c_1' / \log n, and respectively that there exists a strategy for the rabbit that ensures for any deterministic hunter \mathbb{P}(\tau < n ) \geq c_2' / \log n (see Lemma 2.2. here for a formal proof of this).

The hunter’s strategy

Let a, b be independent uniform random variables on [0,1]. The location of the hunter at time t is H_t = \lceil a n + b t \rceil \ \mathrm{mod} \ n. In some sense this hunter moves at a random speed determined by b and in a random direction determined by a. The key idea to analyze this strategy is to consider the number of collisions before time K_n = \sum_{t=0}^{n-1} \mathbf{1}\{R_t = H_t\}. Clearly

    \[\mathbb{P}( \tau < n ) = \mathbb{P}(K_n > 0) \geq \frac{(\mathbb{E} (K_n) )^2}{\mathbb{E} (K_n^2)},\]

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 \mathbb{P}(K_n = 0) \leq \mathbb{P}(|K_n - \mathbb{E} (K_n)| \geq |\mathbb{E} (K_n)|) \leq \mathrm{Var}(K_n) / (\mathbb{E} (K_n))^2):

    \[(\mathbb{E} (K_n))^2 = (\mathbb{E} (\mathbf{1}\{K_n \neq 0\} K_n))^2 \leq \mathbb{E}(\mathbf{1}\{K_n \neq 0\}^2) \mathbb{E} (K_n^2) = \mathbb{P}(K_n \neq 0) \mathbb{E} (K_n^2) .\]

Now it is just a matter of computing \mathbb{E} K_n and \mathbb{E} K_n^2 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:

    \[\mathbb{P}( \tau < n) = \mathbb{P}(K_n > 0) \leq \frac{\mathbb{E}(K_{2 n})}{\mathbb{E} (K_{2 n} | K_n > 0)} .\]

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 2 (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 U be a random variable uniformly distributed in \{0, \hdots, n-1\} and Z=(X,Y) be a simple random walk (independent of U) in \mathbb{Z}^2. Let T_0 = 0 and for k \geq 0,

    \[T_{k+1} = \inf\{ t \geq T_k : Y_t = k+1\} .\]

The rabbit is then defined by R_t = (X_{T_t} + U) \ \mathrm{mod} \ n (with R_0 = U). Using basic properties of the simple random walk in 2 dimensions one can analyze the term \mathbb{E} (K_{2 n} | K_n > 0) 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.

This entry was posted in Probability theory. Bookmark the permalink.

2 Responses to "The hunter and the rabbit"

    • Sebastien Bubeck

Leave a reply