# The 9 step problem

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.

• Our teacher said if u feel this question to be easy do it for 'n' steps. – STK Oct 27 '16 at 13:53
• Solve first with just forward and backwards and see what you can pick up from there – Simply Beautiful Art Oct 27 '16 at 14:08
• He has to take an even number of steps in one axis and an odd number of steps in the other. Success comes only when the even number is split evenly between the directions and the odd number is as even as possible. You don't care which axis is even and which is odd, so just assume left/right is odd and sum the cases. – Ross Millikan Oct 27 '16 at 14:15
• Might clarify things to note that your answer is $4$ times the probability that he gets home in $10$ steps (after all, to get home in $10$ steps, he must be standing one step away after $9$ and then he must take the right step). – lulu Oct 27 '16 at 14:21

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

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

• We both improved ourselves ;) – drhab Oct 27 '16 at 18:56
• @drhab - that's right! – Hypergeometricx Oct 27 '16 at 18:57
• You can also approach this without thinking combinatorially, with a generating function. All of the 9-step paths can be generated by the polynomial $\left(L+R+U+D\right)^9$. Since $L$ and $R$ cancel, as do $U$ and $D$, the number of paths that terminate at $(m,n)$ is the coefficient of $R^mU^n$ in $\left(R^{-1}+R+U+U^{-1}\right)^9$. The number $15786$ @hypergeometric found is the number of paths that terminate at $(1,0)$, or the coefficient of $R$ in $\left(R^{-1}+R+U+U^{-1}\right)^9$. It’s no easier to finish the calculation, but it avoids needing to think about rearrangements of sequences. – Steve Kass Oct 27 '16 at 21:40
• Can u tell how did you came to that closed form, that is, how did you solved summation. – STK Oct 27 '16 at 23:40
• @SteveKass - Thanks! That's a very useful approach. (+1) You should post it as a solution. – Hypergeometricx Oct 28 '16 at 14:04

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.

• Nice way to approach the problem. (+1) – Hypergeometricx Oct 29 '16 at 3:48
• Of course I fully agree with @hypergeometric. – drhab Oct 29 '16 at 15:50
• Very nice approach great – Ekaveera Gouribhatla Oct 19 '18 at 16:32
• @EkaveeraKumarSharma Thanks for your comment! Looking back at this two-year-old question, I just now saw @hypergeometric’s closed-form solution, and I was able to come up with a combinatorial proof, which I’ve posted as a new answer. – Steve Kass Oct 20 '18 at 5:20

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.

• Got that. Thnx for the general part as well. I don't think a closed form is needed, that would definitely suffice. – STK Oct 27 '16 at 19:10
• You are welcome. – drhab Oct 27 '16 at 19:11
• There is a closed form! See my edited solution :) – Hypergeometricx Oct 27 '16 at 19:24

Here's a new combinatorial approach.

Assume that there are $$2n+1$$ steps.

Denote directions $$H$$ (Horizontal) and $$V$$ (Vertical) and polarities $$+$$ and $$-$$,
(ie. $$H+$$ is right, $$H-$$ left, $$V+$$ forward, $$V-$$ backward).

Of the $$2n+1$$ steps, choose any $$\color{red}{n}$$ steps. Number of ways: $$\binom {2n+1}n$$.

• For the chosen steps, assign polarity "$$+$$".
• For the remaining $$n+1$$ steps, assign polarity "$$-$$".

$$\begin{array}{&c|&c &c &c | &c} \hline & &+ &- &\text{Total} \\ \hline H& &? &?\\ V& &? &?\\ \hline & &\color{red}{n} &n+1 &2n+1\\ \hline\end{array}$$

Again, of the $$2n+1$$ steps, choose any $$\color{orange}{n}$$ steps. Number of ways: $$\binom {2n+1}n$$.

• For these $$n$$ steps, mark $$H$$ for those with polarity "$$+$$" and mark $$V$$ for those with polarity "$$-$$".

• For the remaining $$n+1$$ steps, do the opposite, i.e. mark $$V$$ for those with polarity "$$+$$" and mark $$H$$ for those with polarity "$$-$$".

$$\begin{array}{&c|&c &c &c | &c} \hline & &+ &- &\text{Total} \\ \hline H& &\color{orange}{r} &?\\ V& &? &\color{orange}{n-r}\\ \hline & &\color{red}{n} &n+1 &2n+1\\ \hline\end{array} \hspace{3cm} \begin{array}{&c|&c &c &c | &c} \hline & &+ &- &\text{Total} \\ \hline H& &\color{orange}{r} &r+1 & 2r+1\\ V& &n-r &\color{orange}{n-r} & 2n-2r\\ \hline & &\color{red}{n} &n+1 &2n+1\\ \hline\end{array}$$

This ensures that $$n$$ matched polarity step-pairs, with one unmatched step, in this case $$H-$$.

Multiply by $$4$$ for all four directions $$(H+, H-, V+, V-)$$

This gives total number of combinations as $$4\large\binom {2n+1}n^2$$.
Hence probability of ending up one step away from original position is $$\frac {4\large{\binom {2n+1}n} ^2}{4^{2n+1}}=\frac {\large\binom {2n+1}n ^2}{4^{2n}}$$

NOTE also that the total number of ways to end up one step away from the original position after $$2n+1(=2N-1)$$ steps is the same as the total number of ways to end up back at the original position after $$2n+2(=2N)$$ steps, where $$N=n+1$$.

Assume that there are $$2N$$ steps.

Denote directions $$H$$ (Horizontal) and $$V$$ (Vertical) and polarities $$+$$ and $$-$$,
(ie. $$H+$$ is right, $$H-$$ left, $$V+$$ forward, $$V-$$ backward).

Of the $$2N$$ steps, choose any $$\color{red}{N}$$ steps. Number of ways: $$\binom {2N}N$$.

• For the chosen steps, assign polarity "$$+$$".
• For the remaining $$N$$ steps, assign polarity "$$-$$".

$$\begin{array}{&c|&c &c &c | &c} \hline & &+ &- &\text{Total} \\ \hline H& &? &?\\ V& &? &?\\ \hline & &\color{red}{N} &N &2N\\ \hline\end{array}$$

Again, of the $$2N$$ steps, choose any $$\color{orange}{N}$$ steps. Number of ways: $$\binom {2N}N$$.

• For these $$N$$ steps, mark $$H$$ for those with polarity "$$+$$" and mark $$V$$ for those with polarity "$$-$$".

• For the remaining $$N$$ steps, do the opposite, i.e. mark $$V$$ for those with polarity "$$+$$" and mark $$H$$ for those with polarity "$$-$$".

$$\begin{array}{&c|&c &c &c | &c} \hline & &+ &- &\text{Total} \\ \hline H& &\color{orange}{r} &?\\ V& &? &\color{orange}{N-r}\\ \hline & &\color{red}{N} &N &2N\\ \hline\end{array} \hspace{3cm} \begin{array}{&c|&c &c &c | &c} \hline & &+ &- &\text{Total} \\ \hline H& &\color{orange}{r} &r & 2r\\ V& &n-r &\color{orange}{N-r} & 2N-2r\\ \hline & &\color{red}{N} &N &2N\\ \hline\end{array}$$

Total number of combinations is $$\binom {2N}N\cdot \binom {2N}N=\binom {2N}N^2$$ Note that this equal to $$\binom {2n+2}{n+1}^2=4\binom {2n+1}n^2$$

In another answer, @hypergeometric provides a closed-form solution. I’m posting a second answer to provide a combinatorial argument for that closed-form solution. (I wouldn’t have come up with it had I not seen the closed-form solution!)

Proposition: The number of length-$$(2n+1)$$ paths that begin at the origin and end at the point $$(1,0)$$ (call these the “admissible paths”), where each step of the path moves one unit right, left, up, or down (R, L, U, or D), is $$\displaystyle{2n+1\choose n}^2$$.

Combinatorial proof strategy: Note that $$\displaystyle{2n+1\choose n}^2$$ is the number of ordered pairs $$(A,B)$$, where $$A$$ and $$B$$ are cardinality-$$n$$ subsets of $$\{1,2,\dots,2n+1\}$$. I will show that there is a one-to-one correspondence between the set of such pairs $$(A,B)$$ and the set of admissible paths.

Proof: Given an admissible path, note that the number of steps that increase the walker’s $$x$$- or $$y$$-coordinate (R’s and U’s) must exceed the number of steps that decrease either coordinate by exactly one, because the net effect of the path changes the coordinate sum $$x+y$$ of the walker’s position from $$0$$ to $$1$$. Thus there are $$n+1$$ R or U steps and $$n$$ L or D steps. Write $$0$$ above each R and U in the path and write $$1$$ above each L and D. Let $$A$$ be the subset of positions where a $$1$$ was written above a step of the path.

By a similar observation, there must be $$n+1$$ steps of type R or D (which increase the coordinate difference $$x-y$$ by one), and $$n$$ steps of type L or U (which decrease $$x-y$$ by one. Write $$0$$ below every R and D and $$1$$ below every L and U. Let $$B$$ be the subset of positions where a $$1$$ was written below a step of the path.

Different paths will yield different set pairs $$(A,B)$$, so this construction yields a distinct $$(A,B)$$ from each admissible path.

Now, given $$(A,B)$$, where $$A$$ and $$B$$ are cardinality-$$n$$ subsets of $$\{1,2,\dots,2n+1\}$$, create a path of steps L, R, U, and D as follows: Let $$A$$ be the set of positions in the path that are L or D, and $$B$$ the set of positions in the path that are L or U. Step $$k$$ of the path constructed from $$(A,B)$$ will be L if $$k$$ is in both $$A$$ and $$B$$; D if $$k$$ is in $$A$$, but not $$B$$; $$U$$ if $$k$$ is in $$B$$ but not $$A$$; $$R$$ if $$k$$ is in neither $$A$$ nor $$B$$.

The path created in this way contains $$n+1$$ steps that increase $$x+y$$ by one and $$n$$ that decrease $$x+y$$ by 1, and it contains $$n+1$$ steps that increase $$x-y$$ by one and $$n$$ that decrease $$x-y$$ by 1. Thus the path increases $$x$$ by one and leaves $$y$$ unchanged and is an admissible path. Different pairs $$(A,B)$$ yield different paths, and this completes the construction of bijection between the pairs $$(A,B)$$ and the admissible paths.