The 9 step problem

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

  • $8$ steps comprising (i) $r$ steps each of R,L; and (ii) $(4-r)$ steps each of U,D, where $0\le r\le 4$; and
  • $1$ additional step of either one or R,L,U,D.

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$$


The original poster suggested I turn my comment into a solution, so here it is.

All possible 9-step paths (there are $4^9$ of them) can be generated by the polynomial $\left(L+R+U+D\right)^9$.

Since $L$ and $R$ cancel each other out, as do $U$ and $D$, the number of paths that terminate at the point $(m,n)$ is the coefficient of $R^mU^n$ in $\left(R^{-1}+R+U+U^{-1}\right)^9$.

$$\mbox{Let } P(R,U)=\left(R^{-1}+R+U+U^{-1}\right)^9=\sum_{m,n}p_{m,n}R^mU^n.$$

Also note that by the multinomial theorem, $$P(R,U)=\left(R^{-1}+R+U+U^{-1}\right)^9=\sum_{i+j+k+\ell=9}\binom{9}{i,j,k,\ell}R^{\,j-i}U^{k-\ell}\mbox{, with }i,j,k,\ell\in\mathbb{Z}^+\cup\{0\}.$$

By symmetry, the number of paths that terminate one step from home is $4$ times the number of paths that terminate at $(1,0)$, or $4p_{1,\,0}$, where $p_{1,\,0}$ is the coefficient of $R^1U^0$. Using the multinomial theorem equation above, $$p_{1,0}=\sum_{i+j+k+\ell=9\\j=i+1, k=\ell}\binom{9}{i,j,k,\ell}=\sum_{2i+1+2k=9}\binom{9}{i,j,k,\ell}=\sum_{2i+2k=8}\binom{9}{i,i+1,k,k}.$$

The sum $\displaystyle\sum_{2i+2k=8}\binom{9}{i,i+1,k,k}$ equals $\displaystyle\sum_{i=0}^4 \binom{9}{i,i+1,4-i,4-i}=\\$

$$\binom{9}{0,1,4,4}+\binom{9}{1,2,3,3}+\binom{9}{2,3,2,2}+\binom{9}{3,4,1,1}+\binom{9}{4,5,0,0}$$ $$= 630+5040+7560+2520+126=15876.$$

The desired probability is therefore $\dfrac{4\cdot15876}{4^9}=\dfrac{3969}{16384}$.

This is no less work than the answers already given, but it avoids combinatorial arguments, and it generalizes nicely to answer similar questions.


Think of the man starting at $(0,0)$.

Pick out one of the $4$ points $1$ step away from $(0,0)$. For instance $(1,0)$.

In order to arrive there after the $9$-th step the number of "horizontal" (parallel to the $x$-as) steps must be odd and the number of "vertical" (parallel to the $y$-as) steps must be even.

Secondly the number of steps to the right (horizontal) must exceed the number of steps to the left with $1$, and the number of steps forward (vertical) must equalize the number of steps backwards.

So we get the splitups:

  • $9=1+8$ resulting in $\binom9{0,1,4,4}=630$ routes
  • $9=3+6$ resulting in $\binom9{1,2,3,3}=5040$ routes
  • $9=5+4$ resulting in $\binom9{2,3,2,2}=7560$ routes
  • $9=7+2$ resulting in $\binom9{3,4,1,1}=2520$ routes
  • $9=9+0$ resulting in $\binom9{4,5,0,0}=126$ routes

The summation of these numbers is $15876$ and is the total number of routes to $(1,0)$.

Multiplying this with $4$ we find a total number of $63504$ routes to one of the elements of $\{(0,-1),(0,1),(1,0),(-1,0)\}$

The routes are equiprobable so in order to find the probability it remains to divide by the total number of routes, wich is $4^9=262144$.

End result:$$p=\frac{63504}{262144}\simeq0.2422$$

A general solution with $2n+1$ steps will take the form:$$4\sum_{k=0}^n\binom{2n+1}{k,k+1,n-k,n-k}$$

Maybe there is a closed form for that, but uptil now I don't know.

Tags:

Combinatorics

Probability

Summation

Recent Posts