Randomized Steps on a Grid

The probability of reaching $(4,4)$ is the coefficient of $x^4y^4$ in the expansion of $f_n(x,y) = \left( \frac14 x + \frac14 x^{-1} + \frac14 y + \frac14 y^{-1} \right)^n.$ Well, $\begin{aligned} f_n(x,y) &= \left( \frac14 \right)^n (xy)^{-n} (x^2y + y + xy^2 + x)^n \\ &= \left( \frac14 \right)^n (xy)^{-n} (x+y)^n (xy+1)^n. \end{aligned}$ The coefficient of $x^4y^4$ in $f_n(x,y)$ is the coefficient of $x^{n+4}y^{n+4}$ in $\left( \frac14 \right)^n (x+y)^n (xy+1)^n.$ Looking at degrees of terms makes it clear that the only way to get $x^{n+4}y^{n+4}$ is by getting $x^{n/2} y^{n/2}$ in the first part and $(xy)^{n/2+4}$ in the second part. (It makes sense that $n$ has to be even; otherwise it's easy to see from the polynomial or from thinking about the problem that the probability will be 0.)

So the conclusion is: let $n=2k.$ Then the probability of getting to $(4,4)$ in $n$ steps is exactly $p_k = \left( \frac14 \right)^{2k} \binom{2k}{k} \binom{2k}{k+4}.$

Consider $p_k/p_{k+1}.$ The claim is that for $k \le 15$ this is less than 1, and for $k \ge 16$ it's greater than 1, which would mean that $p_k$ is maximized when $k=16.$ Let's write it down: $\begin{aligned} \frac{p_k}{p_{k+1}} &= 16 \frac{\binom{2k}{k} \binom{2k}{k+4}}{\binom{2k+2}{k+1} \binom{2k+2}{k+5}} \\ &= 16 \frac{(k+1)(k+1)(k+5)(k-3)}{(2k+2)(2k+1)(2k+2)(2k+1)} \\ &= 4 \frac{(k+5)(k-3)}{(2k+1)^2} \\ &= \frac{4k^2+8k-60}{4k^2+4k+1} \\ &= 1 + \frac{4k-61}{4k^2+4k+1}, \end{aligned}$ which is greater than $1$ for $k \ge 16$ and less than $1$ for $k \le 15$ . So the claim is proved, and $p_k$ is maximized when $k=16,$ or $n=\fbox{32}.$

Edit: For any point $(a,b),$ here is a partial proof that the probability of reaching $(a,b)$ in $n$ steps is maximized when $n=a^2+b^2.$

First note that the parity of $a^2+b^2$ is correct: if $a$ and $b$ are both even or both odd, it takes an even number of steps to reach $(a,b),$ and $a^2+b^2$ is even. Otherwise, it takes an odd number of steps to reach $(a,b)$ and $a^2+b^2$ is odd.

Now the same argument as above gives a value of $p_n,$ the probability of reaching $(a,b)$ in $n$ steps, as $p_n = \left( \frac14 \right)^n \binom{n}{\frac{n-a+b}2} \binom{n}{\frac{n+a+b}2},$ and, similar to the above, we get $\frac{p_n}{p_{n+2}} = \frac{(n+2+a+b)(n+2+a-b)(n+2-a+b)(n+2-a-b)}{(n+2)^2(n+1)^2}.$ Let $r_n$ be the top and $s_n$ be the bottom. Then I get $\begin{aligned} r_{a^2+b^2} - s_{a^2+b^2} &= 4a^4 + 4a^2b^2 + 12a^2 + 4b^4 + 12b^2 + 12 > 0 \\ r_{a^2+b^2-2} - s_{a^2+b^2-2} &= -4a^2b^2 \le 0. \end{aligned}$ This at least shows that $p_{a^2+b^2-2} \le p_{a^2+b^2} > p_{a^2+b^2+2}.$ But it is not quite so clear that this "local maximum" is a "global maximum" in general. The numerator of $\frac{p_n}{p_{n+2}}-1$ is a cubic, so it might have some other critical points...

Let us ask a simpler question: What if the expected value of $d$ , the distance to the origin, after $n$ steps are made. The answer is straightforward, one of the principal property of random walks, $d=\sqrt{n}$ . Using $d^2=4^2+4^2=32$ we get $n=32$ .

This happens to be the solution to the current problem. Is that a coincidence or is it always true?

To reach $(4,4)$ from $(0,0)$ , we need to take $a+2$ steps to the right, $a-2$ steps to the left, $b+2$ steps up, and $b-2$ steps down, for some integers $a,b \ge 2$ , which means that we have achieved our goal after a total of $2(a+b)$ steps. Thus the probability of reaching $(4,4)$ from $(0,0)$ after $2n$ steps is equal to $p_n \; = \; \frac{1}{4^{2n}}\sum_{a=2}^{n-2} \frac{(2n)!}{(a-2)!(a+2)!(n-a-2)!(n-a+2)!} \; = \; \frac{1}{4^{2n}} \times \frac{2^{4n} \Gamma(n+\frac12)^2}{\pi (n-4)!(n+4)!}$ After simplification, this is equal to $p_n \; = \; \frac{\big((2n)!\big)^2}{4^{2n}(n!)^2(n-4)!(n+4)!} \hspace{2cm} n \ge 4$ Thus we deduce that $\frac{p_{n+1}}{p_n} \; = \; \frac{(2n+2)^2(2n+1)^2}{16(n+1)^2(n-3)(n+5)} \; = \; \frac{(2n+1)^2}{4(n-3)(n+5)}$ and this implies that $p_n \le p_{n+1}$ provided that $4n \le 61$ . Hence we deduce that the largest value of $p_n$ is $p_{16}$ .

It is not possible to reach $(4,4)$ from $(0,0)$ after an odd number of steps, and hence the number $N$ of steps that maximizes the probability of getting from $(0,0)$ to $(4,4)$ in $N$ steps is $N = 2\times16 = \boxed{32}$ .

Here is a counting approach to this problem (that will require the assistance of a calculator to realistically solve):

Let's create a bijection. If we write out the steps of that path Richard takes, the number of ways to reach $(4,4)$ is the number of sequences of these steps. For example, $NNNEWEENENSE$ is one possible path, where each letter represents a cardinal direction (north, south, east, west).

In order to reach $(4,4)$ , we need a minimum of $8$ steps total. We also note that if we have an odd number of steps, we cannot possibly reach our destination. Let $s$ be the number of pairs of steps more than the minimum needed to reach $(4,4)$ . In other words, $s = \frac{1}{2}(n-8)$ . Let $k$ be the number of pairs of steps assigned to just the north and south directions. This makes $s-k$ represent the number of pairs of steps assigned to the east and west directions.

First, we find the number of ways to divide up the positions of the north/south letters versus the east/west letters, which is $\binom{8+2s}{4+2k}$ . Then we calculate the number of ways to select which letters are north/south, which is $\binom{4+2k}{k}$ , and the number of ways to select which letters are east/west, which is $\binom{4+2(s-k)}{s-k}$ , and multiply all of these values together. If we sum this expression for values of $k$ from $0$ to $s$ , we will be able to find the total number of ways to reach the point.

Let $P(s)$ be the number of ways to reach $(4,4)$ for a given $s$ . We now have that $P(s) = \sum\limits_{k=0}^{s} \binom{8+2s}{4+2k} \binom{4+2k}{k} \binom{4+2(s-k)}{s-k}$ Since each pair adds $2$ steps, each pair multiplies the total number of paths Richard can take by $4^2 = 16$ . To find where the probability is maximized, we find where the probability begins to first decrease. This occurs at the first non-negative integer $s$ such that $\frac{P(s+1)}{P(s)} < 16$ . We notice that $\frac{P(13)}{P(12)}=\frac{2165548674394987200}{135719648326407600} < 16$ so the probability is maximized where $n = 8+2\cdot{12} = \boxed{32}$ .

Additional comments: The particularly high numbers are a result of choosing a destination point that would make the answer difficult to simply guess. However, using recursion or some other more advanced techniques and identities, solving this problem is equivalent to finding the first non-negative $s$ such that: $\frac{ (9 + 2 s)^2} {4(1 + s) (9 + s)} < 1$ Can you figure out how to obtain this condition?

As we have to go from $(0,0)$ to $(4,4).$ Lets make a square with side 8 so we a giant square made of $8\times 8=64$ small squares of unit length. We can make use of half the small squares i.e, 32 to move from origin to $(4,4).$

I came up with this.To move from $(0,0)$ to $(r, r)$ make a square of side 2r with (0,0) as center and symmetric about the coordinate axes, thus giving you total number i.e, $4r^{2}$ small squares of unit length and using half of them i.e, $2r^{2}$ will give you maximum probability to reach the point $(r, r),$

So according to this Question, $r=4$

Maximum Steps $=2r^{2}=2\times4^{2}=2\times16=32.$

Therefore $N=\boxed{32 }$

You go forward 1 step (statistically) after taking four equally probable random steps in any one of the four cardinal directions. Therefore, you need 8×4=32 random walks to travel 8 steps to reach any one of the four points {(4,4), (-4,4), (-4,-4), ( 4,-4)} starting from origin at (0,0).

Answer=32

Since we're talking of random walks, the reference I learned when I was 12 mentioned that distance $d = \sqrt{steps}$ .

The location $(4,4)$ is $\sqrt{4^2+4^2}$ or $4\times\sqrt{2}$ steps from the start. Squaring that is $32$ .

N.b. : I'm not sure how programming or a calculator will help, since that reference is in my dad's bookshelf, next to the Table of Areas and Volumes of Items Used in Physics and Math Problems (Engineering Edition) . The table for Red Rubber Balls has been somewhat famously referenced elsewhere in cyberspace.

Another one I guesstimated right. It is known that the expected distance of a random walk is $\sqrt n$ . In this problem we have two independent random walks one East-West and one North-West. So to maximize the chance of being +4 on each axis then 16 steps are needed for each and so $\boxed{32}$ for the total.