Random Robot Roaming 2

We need the key binomial identities: $\begin{aligned} \sum_{a=0}^n \binom{n}{a}^2 & = \; \binom{2n}{n} \\ \sum_{a=0}^n \binom{n}{a}\binom{n+k}{a+k} & = \; \binom{2n+k}{n} \\ \sum_{a=0}^n \binom{n}{a}\binom{n+k+1}{a+k} & = \; \binom{2n+k+1}{n+1} \end{aligned}$ for $n,k \in \mathbb{N}$ . We can prove these identities by considering the coefficient of $X^n$ in $(1+X)^{2n} = (1+X)^n(1+X)^n$ , the coefficient of $X^n$ in $(1+X)^{2n+k} = (1+X)^n(1+X)^{n+k}$ and the coefficient of $X^{n+1}$ in $(1+X)^{2n+k+1} = (1+X)^n(1+X)^{n+k+1}$ respectively.

If the robot starts at $(0,0)$ , we want to know the probabiltiy of it landing on one of $(0,0)$ , $(2,0)$ , $(0,2)$ , $(0,-2)$ , $(0,-2)$ , $(1,1)$ , $(-1,1)$ , $(-1,-1)$ , $(1.-1)$ after 20 moves.

The robot will land on $(0,0)$ if it has made an equal number of "up" and "down" moves, and an equal number of "left" and "right" moves. There are $a_1 \; = \; \sum_{a=0}^{10} \frac{20!}{a! a! (10-a)! (10-a)!} \; = \; \sum_{a=0}^{10} \binom{20}{10} \binom{10}{a}^2 \; = \; \binom{20}{10}^2$ ways in which it can do this.

The robot will land on $(2,0)$ if it has made an equal number of "up" and "down" moves, and two more "right" moves than "left" moves. There are $a_2 \; = \; \sum_{a=0}^9 \frac{20!}{(a+2)! a! (9-a)! (9-a)!} \; = \; \sum_{a=0}^9 \binom{9}{a}\binom{11}{a}\binom{20}{11} \; = \; \binom{20}{9}\binom{20}{11}$ ways in which it can do this.

The robot will land on $(1,1)$ if it has made one more "up" move than "down" moves, and one more "right" move than "left" moves. There are $a_3 \; = \; \sum_{a=0}^9 \frac{20!}{(a+1)! a! (10-a)! (9-a)!} \; = \; \sum_{a=0}^9 \binom{9}{a}\binom{11}{a+1}\binom{20}{11} \; = \; \binom{20}{10}\binom{20}{11}$ ways in which it can do this.

---

An alternative argument goes as follows. Suppose that the robot tosses two distinct coins. If it tosses HH, it moves right. If it tosses HT, it moves up. If it tosses TH it moves down. If it tosses TT it moves left.

If the robot is to land on $(0,0)$ , the first coin must toss an equal number of heads and tails ( $10$ of each) and the second coin must also toss an equal number of heads and tails. Thus there are $a_1 \; = \; \binom{20}{10}^2$ ways for this to happen.

If the robot is to land on $(2,0)$ , the first coin must toss two more heads than tails, and the second coin must also toss two more heads than tails. Thus there are $a_2 \; = \; \binom{20}{11}\binom{20}{11}$ ways for this to happen.

If the robot is to land on $(1,1)$ , the first coin must toss two more heads than tails, while the second coin must toss an equal number of heads and tails. Thus there are $a_3 \; = \; \binom{20}{11}\binom{20}{10}$ ways for this to happen.

---

Thus, by symmetry, there are $\begin{aligned} a_1 + 4a_2 + 4a_3 & = \; \frac{(20!)^2}{(10!)^4(9!)^2(11!)^2}\left\{ (9!)^2(11!)^2 + 4(10!)^4 + 4(10!)^2 9! 11!\right\} \; = \; \frac{(20!)^2}{(10!)^4(9!)^2(11!)^2}\left( 2(10!)^2 + 9! 11!\right)^2 \\ & = \; \left[\frac{20!(2(10!)^2 + 9! 11!)}{(10!)^2 9! 11!}\right]^2 \; = \; \left[ \binom{20}{10} \frac{200 + 110}{110} \right]^2 \; = \; \left[\frac{31}{11}\binom{20}{10}\right]^2 \end{aligned}$ ways in which the robot can end up within $2$ units of its starting point, and so the probability that the robot ends up within $2$ units of its starting point is $\frac{a_1 + 4a_2 + 4a_3}{4^{20}} \; = \; \left[\frac{31}{11 \times 4^{10}}\binom{20}{10}\right]^2 \; = \; \frac{a^2}{b^2}$ where $\frac{a}{b} \; = \; \frac{31}{11 \times 4^{10}} \binom{20}{10} \; = \; \frac{130169}{262144}$ making the answer $130169 + 262144 = \boxed{392313}$ .

It's helpful to compare the possible positions of the robot after the first few moves to numbers in layers of a pyramid, as follows:

After $0$ moves, the robot is at the starting point with only $1$ way to get there. After $1$ move, the robot can be either up $1$ , right $1$ , down $1$ , or left $1$ from the starting point, all with only $1$ way to get there each time. After $2$ moves, the robot can move either up $1$ , right $1$ , down $1$ , or left $1$ after wherever the robot ended up after the first move. That means, for example, that there are $4$ ways to get back to the starting point (up $1$ down $1$ , down $1$ up $1$ , right $1$ left $1$ , or left $1$ right $1$ ). We can observe, then, that each block in the pyramid layer is the sum of the blocks that overlap it in the layer above .

With this rule we can also prove inductively that any block in the $x^{\text{th}}$ column and $y^{\text{th}}$ row in the layer after $m$ moves is ${m \choose x - 1}{m \choose y - 1}$ (see below for proof). For example, the number in the block in the $2^{\text{nd}}$ column and $2^{\text{nd}}$ row in the layer after $2$ moves is ${2 \choose 2 - 1}{2 \choose 2 - 1} = 4$ , which we already found.

If the robot starts at $(0, 0)$ on the grid, then it must stop on either $(0, 0)$ , $(\pm 1, \pm 1)$ , $(\pm 2, 0)$ , or $(0, \pm 2)$ to be $2$ units or less away from its starting point (note that $(\pm 1, 0)$ , or $(0, \pm 1)$ are not possible since they are all an odd distance away), and these coordinates correspond with the $10^{\text{th}}$ , $11^{\text{th}}$ , and $12^{\text{th}}$ columns and rows of the pyramid layer. This makes the probability:

$\displaystyle \frac{1}{4^{20}} \sum_{x = 10}^{12}{20 \choose x - 1} \sum_{y = 10}^{12} {20 \choose y - 1} = \frac{130169^2}{262144^2}$

so $a = 130169$ , $b = 262144$ , and $a + b = \boxed{392313}$ .

---

Proof by Induction:

For the first block, $(m, x, y) = (0, 1, 1)$ , so its value is ${0 \choose 1 - 1}{0 \choose 1 - 1} = 1$ .

The four blocks that overlap a $(m + 1, x, y)$ block from above are $(m, x, y)$ , $(m, x - 1, y)$ , $(m, x, y - 1)$ , and $(m, x - 1, y - 1)$ , and their values add up to ${m \choose x - 1}{m \choose y - 1} + {m \choose x - 2}{m \choose y - 1} + {m \choose x - 1}{m \choose y - 2} + {m \choose x - 2}{m \choose y - 2}$ , which is equivalent to ${m + 1 \choose x - 1}{m + 1 \choose y - 1}$ , the value of the $(m + 1, x, y)$ block.

Therefore, the value of any block is ${m \choose x - 1}{m \choose y - 1}$ .

This is an updated and more direct solution.

TLDR : The furthest locations (edges) the robot can reach forms a diamond (actually a tilted square), of axes $u, v$ , say. The number of ways it can reach each point of the edges corresponds to $\binom {2n}{m}$ which is the $2n$ -th row of the Pascal triangle. The number of ways to reach a location in the interior is the product of the number of ways to reach each of its $u$ and $v$ coordinates on the edges (axes) respectively.

---

Full Solution :

1D version

This problem can be analysed as a 2D version of the original Random Robot question, which is a 1D version. Assume that the robot can only move along a straight line i.e. up or down, starting from the origin. We want to determine the number of ways to arrive at position $2m$ after $2n$ moves, where $0\le m\le n$ . The robot must make $n+m$ moves in the +ve direction and $n-m$ moves in the -ve direction, with moves taken in any order. Hence the total number of ways to end up at $2m$ is
$\displaystyle \binom {2n}{n+m}$ .
The number of ways to arrive at each position $2m$ (where $-n\le m\le n)$ are the numbers from the $2n$ -th row of the Pascal triangle. An illustration for the case $n=3$ is shown as part of the diagram above i.e. green boxes for the $u$ axis (or $v$ ).

---

2D version (Present problem)

Let $2n$ be the total number of steps taken. Refer to the diagram above (diagram shows the case for $n=3$ WLOG) and note axes $u, v$ . The robot starts at the centre position at $(u,v) = (0,0)$ . Robot steps are indicated in purple squares. Each time the robot takes a step (up/down/left/right), it is making a one move each in the $u$ and $v$ directions simultaneously. Hence the number of ways to arrive at at a location $(u,v) = (2i, 2j)$ ( where $0\le i,j\le n)$ after $2n$ moves is
$\binom {2n}{n+i}\binom {2n}{n+j}$ .

The number of ways to end up at a location no more than two units away from the origin is given by summing over all $i,j$ where $|2i, 2j| \le 2$ i.e. $0\le i,j\le 1$ , which gives
$S_{2n}= \sum_{i=-1}^1 \binom {2n}{n+i} \sum_{j=-1}^1 \binom {2n}{n+j} = \left(\sum_{i=-1}^1 \binom {2n}{n+i}\right)^2 = \left( \binom {2n}{n-1}+\binom{2n}n + \binom {2n}{n+1}\right).$

For the illustration given, this is $S_6 = \left( \binom 62+\binom 63+\binom 64\right)^2 =50^2 = 2500.$

In the given question, total number of moves is 20 i.e. $n=10$ , which gives $S_{20} = \left( \binom {20}9+\binom {20}{10}+\binom {20}{11}\right)^2.$

The total number of possible journeys is $4^{20}$ . Therefore the probability of ending at locations two units or less from the origin is given by
$\frac {A^2}{B^2} =\frac {S_{20}}{4^{20}}$

where

$\frac AB =\frac { \displaystyle\binom {20}9 + \binom {20}{10}+\binom {20}{11}}{4^{10}} =\frac {510676}{1048576} = \frac {130169}{262144} = \frac ab$

where $a=130169, b=262144$ and $a, b$ are co-prime.

Hence $a+b = 130169 + 262144 = \color{#D61F06}{392313}. \; \; \; \blacksquare$

---

General case : It is interesting to note that the number of ways of ending at locations 2p units or less from the origin is given by $\left (\binom {2n}{n-p}+ \cdots+\binom {2n}n +\cdots+\binom {2n}{n+p}\right )^2$ . When $p=n$ , this becomes $(2^{2n})^2 =4^{2n}$ , as expected.

---

NB: Alternatively, this can be solved using 2-dimensional convolution. This is similar to the solution posted by OP.

The solution is the same David Vreken. Calculate $C(20,k)$ by Excel - first green line. Second green line is $C(20,k)C(20,1$ ), next lines $C(20,k)C(20,2)$ , $C(20,k)C(20,3)$ and so on. Sum of Blue numbers give way to answer.