A man can take a step forward, backward,left and right with equal probability. Find the probability that after 9 steps he will be just 1 step away from his initial point.
I have done similar questions with movement restricted to forward and backward only ,but this one just blows my mind.
Best Answer
NEW SOLUTION
(Apr 2020)
Consider a 1D walk along the $u$-axis with $2n-1$ steps, where he can only move $+1$ or $-1$ each step With an odd number of steps he can only end in an odd position. In order to end at, say position $(2m-1)$, he would have to take $(n+m-1)$ forward steps and $(n-m)$ backward steps (such that the sum of number of steps is $2n-1$ and the difference is $2m-1$)). The number of ways of doing this is $\dbinom {2n-1}{n+m-1} = \dbinom {2n-1}{n-m}$.
Now consider a 2D walk, as given in the present question. Taking the forward direction to be north, assume two perpendicular axes $u, v$ in the northeast and northwest directions respectively. Each step forward/backward/left/right respresents a simultaneous step in both the $u,v$ directions. Hence the number of ways of ending at $(u,v)=(2i-1, 2j-1)$ is $\dbinom {2n-1}{n-i}\dbinom{2n-1}{n-j}$.
In order to end up $1$ step in front, i.e. $(u,v)=(1,1)$ (where $i=j=1$), the number of ways is $\dbinom {2n-1}{n-1}\dbinom {2n-1}{n-1}=\dbinom {2n-1}{n-1}^2$. Since there are for such locations ($(u,v)=(\pm 1, \pm 1)$), the total number of ways is $$4\dbinom {2n-1}{n-1}^2=\left[2\dbinom {2n-1}{n-1}\right]^2=\left[\frac {2n}n\dbinom {2n-1}{n-1}\right]^2=\dbinom {2n}n^2$$
The total number of different journeys (combination of moves) is $4^{2n-1}$. Hence the probability of ending up one step away from the origin is $\dfrac{\dbinom {2n}n^2}{4^{2n-1}}$. Here $n=5$, so the probability is $$\dfrac{\dbinom {10}5}{4^9} = \dfrac {63504}{262144} = \color{red}{0.2422}$$
PREVIOUS SOLUTION
(2019) (See also solution using a combinatorial approach, posted separately)
Assume that possible steps are R,L,U,D, representing $1$ step Right, Left, Up and Down respectively.
In order to end up one step away from the initial point, the $9$ steps must include
If the $1$ additional step is an R, then total number of ways is equivalent to the number of ways of arranging $R\underbrace{R\cdots}_{r}\; \underbrace{L\cdots}_{r}\; \underbrace{U\cdots}_{(4-r)}\; \underbrace{D\cdots}_{(4-r)}$ which is given by $$\sum_{r=0}^4\binom 9{r+1,r,4-r,4-r}=\sum_{r=0}^4\frac {9!}{(r+1)!r!(4-r)!(4-r)!}=\binom 94^2=15876$$ By symmetry, the number would be the same if the additional step is either L, U or D.
Hence, total number of different ways to end up one step away from initial point is thus given by $$15876\cdot4=63504$$ Dividing this by the total number of different possible paths, $4^9=262144$, gives the probability of ending up one step away from initial point as $\color{red}{0.2422}$.
General Formula
If the total number of moves is $(2n+1)$, the total number of different ways is given by $$4\sum_{r=0}^n\binom {2n+1}{r+1,r,n-r,n-r}=4\sum_{r=0}^n \frac {(2n+1)!}{(r+1)!r!(n-r)!(n-r)!}=4\binom {2n+1}n^2$$ and the probability is given by $$\frac {4\binom {2n+1}n^2}{4^{2n+1}}=\frac {\binom {2n+1}n^2}{4^{2n}}$$
Summation
The analysis above makes use of the following summation result: $$\small\begin{align}\require{cancel} \sum_{r=0}^n\binom {2n+1}{r+1,r,n-r,n-r} &=\sum_{r=0}^n\binom {\color{magenta}{2n+1}}{\underbrace{r+1,n-r}_{\color{magenta}{n+1}},\underbrace{r,n-r}_\color{magenta}n}\\ &=\sum_{r=0}^n\left[\color{magenta}{\binom{2n+1}{n+1}}\binom {n+1}{r+1}\color{\lightgrey}{\binom {n-r}{n-r}}\right] \left[ \color{magenta}{\binom nn}\binom nr\color{\lightgrey}{\binom {n-r}{n-r} } \right]\\ &=\binom {2n+1}n\sum_{r=0}^n\binom {n+1}{r+1}\binom nr\\ &=\binom {2n+1}n\sum_{r=0}^n\binom {n+1}{r+1}\binom n{n-r}\\ &=\color{red}{\binom {2n+1}n^2}\qquad\blacksquare \end{align}$$
NOTE also that the total number of ways to end up one step away from the original position after $9$ steps is the same as the total number of ways to end up back at the original position after $10$ steps.
Using a similar approach as above, and putting $N=n+1$ gives
$$\begin{align} \sum_{r=0}^N \binom{2N}{r,r,N-r,N-r} &=\sum_{r=0}^N \binom {\color{magenta}{2N}}{\underbrace{r,N-r}_{\color{magenta}N},\underbrace{r,N-r}_{\color{magenta}N}}\\ &=\sum_{r=0}^N \left[\color{magenta}{\binom {2N}N}\binom Nr\color{\lightgrey}{\binom {N-r}{N-r}}\right] \left[\color{magenta}{\binom NN}\binom Nr\color{\lightgrey}{\binom {N-r}{N-r}}\right]\\ &=\binom {2N}N\sum_{r=0}^N \binom Nr^2\\ &=\color{red}{\binom {2N}N ^2}\qquad\blacksquare\end{align}$$
Putting $n=4$, i.e. $N=5$ gives the total number of ways required as $$\binom {10}5^2=252^2=63504\qquad\blacksquare$$ Note that $$\small\binom {2N}N^2 =\binom {2n+2}{n+1}^2 =\left[\frac {2n+2}{n+1}\binom {2n+1}n\right]^2 =\left[2\binom {2n+1}n\right]^2 =4\binom {2n+1}n^2\qquad\blacksquare$$