Recursive (Counting) Bijection Harvard-MIT Challenging
2019


Problem - 4485

Contessa is taking a random lattice walk in the plane, starting at $(1, 1)$. (In a random lattice walk, one moves up, down, left, or right $1$ unit with equal probability at each step.) If she lands on a point of the form $(6m, 6n)$ for $m$, $n\in\mathbb{Z}$, she ascends to heaven, but if she lands on a point of the form $(6m+ 3, 6n+ 3)$ for $m,\ n\in\mathbb{Z}$, she descends to hell. What is the probability that she ascends to heaven? 


Let $P(x,\ y)$ be the probability that she ascends to the heaven from point $(x,\ y)$. Then $P(6x,\ 6y)=1$ and $P(6x+3,\ 6y+3)=0$ hold for all integers $x$ and $y$. Our target is to compute $P(1,\ 1)$.

The given information leads to $$P(x,\ y)=\frac{1}{4}P(x,\ y+1)+\frac{1}{4}P(x,\ y-1)+\frac{1}{4}P(x+1,\ y)+\frac{1}{4}P(x-1,\ y)$$

By symmetry, the following relationships should hold $$P(x,\ y)=P(y,\ x),\quad P(x,\ y)=P(-x,\ y),\quad P(x,\ y)=P(x,\ -y)$$

The first relation holds is because all the "heaven points" $(6x,\ 6y)$ and "hell points" $(6x+3,\ 6y+3)$ locate symmetric to line $y=x$. This mean that the distance and direction from the point $(x,\ y)$ to its nearest "heaven/hell points to are exactly the same as those from $(y,\ x)$ to its nearest "heaven/hell" points. The next two relations hold is because all the "heaven/hell points also locate symmetric to $y$ and $x$ axes, respectively. Combining the last two gives $$P(x,\ y)=P(-x,\ -y)$$

Meanwhile, for any integers $a$ and $b$ we should also have $$P(x,\ y)=P(x+6a,\ y+6b)$$

because this is equivalent to pane shift the coordinate system by a multiple of $6$ which will not change the direction and distance from point $(x,\ y)$ to its nearest "heaven/hell" points. Finally, we shall have $$P(x,\ y) = 1- P(x+3,\ y+3)$$

This is because applying a movement from point $(x,\ y)$ to a hell point onto $(x+3,\ y+3)$ will lead to a heaven point, vice versa.

Now let's consider the four points adjacent to $(1,\ 1)$. Applying the above symmetry rule, we find $P(1,\ 2)=P(2,\ 1)$ and $P(1,\ 0)=P(0,\ 1)$. Therefore, it is sufficient to just compute $P(1,\ 2)$ and $P(0,\ 1)$.

$$P(1,\ 2)=P(-1,\ -2)=1-P(2,\ 1)=1-P(1,\ 2)\implies P(1,\ 2)=\frac{1}{2}$$

Now we have (multiplying $4$ on both sides to eliminate fraction coefficients) $$\left\{ \begin{array}{l} 4P(1,\ 1)=2P(0,\ 1) + 2P(1,\ 2)=2P(0,\ 1) + 1\\4P(0,\ 1)=P(0,\ 2) + P(1,\ 1) + P(-1,\ 1) + P(0,\ 0) = P(0,\ 2) + 2 P(1,\ 1) + 1\\4P(0,\ 2)=P(0,\ 1) + P(1,\ 2) + P(-1,\ 2) + P(0,\ 3) = P(0,\ 1) + \frac{3}{2} \end{array}\right.$$

The above system also utilizes the facts that $P(0,\ 0)=1$ and $$P(0,\ 3)=1-P(-3,\ 0)=1-P(3,\ 0) = 1-P(0,\ 3)\implies P(0,\ 3)=\frac{1}{2}$$

Solving this above system yields $$P(1, \ 1)=\boxed{\frac{13}{22}}$$

report an error