# Random walk where walk automatically ends at a certain position

A walker decides to move up or down using an unfair coin. The coin tells the walker to move up 1 step with probability 0.6 and down 1 step with probability 0.4. The walker tosses the coin prior each step. The walk stops when the walker reaches 5 steps above or 2 steps below his start.

What is the probability that the walker ends on exactly the 6th step?

I'm confused on the ending criteria. I can do this by hand for small steps: the probability of the walk ending on the 1st step is zero (because you need more than 1 step to get to -2 or 5), on the 2nd step is $(0.4)^2$, on the 3rd step 0 (I think) because if the walker moves to the left first, then it must move right immediately after, and then it can't reach -2 from the origin. It's similar if it moves to the right first, since then it won't be able to reach -2 with only two steps left.

I encountered this in my elementary probability class. Is there a way to do this that does not involve counting many thing manually?

We can set up a state machine for the state after each step where the finished states are removed: $$\begin{bmatrix} p_{-2}(n+1)\\ p_{-1}(n+1)\\ p_0(n+1)\\ p_1(n+1)\\ p_2(n+1)\\ p_3(n+1)\\ p_4(n+1)\\ p_5(n+1) \end{bmatrix}= \underbrace{\begin{bmatrix} 0&2/5&0&0&0&0&0&0\\ 0&0&2/5&0&0&0&0&0\\ 0&3/5&0&2/5&0&0&0&0\\ 0&0&3/5&0&2/5&0&0&0\\ 0&0&0&3/5&0&2/5&0&0\\ 0&0&0&0&3/5&0&2/5&0\\ 0&0&0&0&0&3/5&0&0\\ 0&0&0&0&0&0&3/5&0 \end{bmatrix}}_{\large M} \begin{bmatrix} p_{-2}(n)\\ p_{-1}(n)\\ p_0(n)\\ p_1(n)\\ p_2(n)\\ p_3(n)\\ p_4(n)\\ p_5(n) \end{bmatrix}$$ Computing $$M^6\begin{bmatrix}0\\0\\1\\0\\0\\0\\0\\0\end{bmatrix}= \begin{bmatrix}\color{#C00}{\frac{144}{3125}}\\0\\\frac{3024}{15625}\\0\\\frac{4536}{15625}\\0\\\frac{486}{3125}\\\color{#C00}{0}\end{bmatrix}$$ tells us that there is a $\frac{144}{3125}$ probability of ending on the $6^\text{th}$ step at the $-2$ position and a $0$ probability of ending on the $6^\text{th}$ step at the $5$ position.

If the walk ends after exactly $k$ steps, then it must have ended at a point with the same parity as $k,$ so if $k$ is odd the only possibility is that it reached $+5$, but if $k$ is even the only possibility is that it ended at $-2$.

Now for $k=6$ it must end at $-2$, so it must take $2$ steps up and $4$ down, without stopping earlier. I can't see a neater way of doing the question than just counting the ways to do this, then multiplying by $0.6^2\times0.4^4$ (which is the probability of a specific sequence of $2$ up and $4$ down).

One possibility is to go up in the first two steps. If you don't do this then you must take exactly one step up out of the first two (otherwise you reach $-2$ after two steps), and one step up out of the third or fourth (otherwise you reach $-2$ after four steps). There are $4$ ways to do this ($2$ for first/second times $2$ for third/fourth), so there are $5$ ways in total.

Hint:

Assuming that the walker starts at position $0$, the only way to end after exactly $6$ steps is to end at $-2$. This would involve $2$ up steps and $4$ down steps, but with some restrictions since you don't want to get to $-2$ before the sixth step. (You don't have to worry about getting to position $5$ with these available steps).

• Could I do something like calculate the probability of getting to $-2$ on the sixth step (without restrictions) and subtract the probability of getting to $-2$ on the 4th step and the probability of getting to $-2$ on the 2nd step? – Dave Sep 8 '17 at 15:29
• @Dave that's a good idea, but not quite right because you only want to subtract probability for the times when you get to $-2$ earlier and are still at $-2$ after six steps. – Especially Lime Sep 8 '17 at 15:32
• That would certainly be possible. There really aren't that many cases (you have to avoid sequences that start DD or UDDD or DUDD). – paw88789 Sep 8 '17 at 15:32
• @EspeciallyLime@paw88789 Thanks so much! I'm really struggling in my class so I appreciate the hints! – Dave Sep 8 '17 at 15:33