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.

2 Responses to "The hunter and the rabbit"

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).

2 Responses to "The hunter and the rabbit"

By Bob Vanderbei November 30, 2013 - 6:06 am

By Sebastien Bubeck November 30, 2013 - 10:45 am

Categories

Recent Posts

Archives

Blogroll