The probability of a drunk person/random walk

Question

A drunk person wonders aimlessly along a path by going forward 1 step and backward 1 step with equal probabilities of $\frac12$.

a) After 10 steps, what is the probability that he has moved 2 steps forward?

b) What is the probability that he will make it to his front door within 20 steps before he collapses with the door being 6 steps in front of him.

My approach was to use Binomial in both cases:

a)${10\choose6} 0.5^{10}$. I can move 6 steps forward and 4 backwards and I will be in spot +2.

b)${20\choose6} 0.5^{20}$

I believe I have part a) correct but not b). I don't know how to handle the fact that in the spot 6+ is the house, a stop.

Can someone help me with part b)? I am seeing this wrong? I am thinking he is at zero but he can go -1 spot. Actually I am not sure if he can go from 0 to -1.

Answer 1

Negative binomial distribution is used if the events are DEPENDENT on each other. For example in your case, the event that the drunk man would take another step depends whether he has reached the front gate. Let's suppose he reaches the front gate in $13$ steps. Then the rest of the $7$ steps would be terminated, i.e., there is no need for them according to the problem. Hence number of steps are dependent.

The probability of $k$th success on $n$th trial with the probability of success being $p$ is given by the negative binomial distribution by the formula

$$\displaystyle P(X)=\binom {n-1}{k-1}p^{k}\left(1-p\right)^{\left(n-k\right)}$$

First we calculate the probability of there being at least $k$ backsteps in the first $6+k$ steps, i.e., $$\displaystyle P_X=1-\sum_{X=0}^{k-1}\binom {6+(k-1)}{X}(0.5)^{X}\left(1-0.5\right)^{\left(6+(k-1)-X\right)}=1-\sum_{X=0}^{k-1}\binom {5+k}{X}\left(0.5\right)^{\left(5+k\right)}$$ We will multiply this factor to probabilities of the respective cases whenever the number of forward steps exceeds $6$.

In $20$ steps, the possible ways the drunk man can reach the front gate $6$ steps in front of him where $p$ is $0.5$ are:

1) All $6$ steps are front steps. This means $6$th success on $6$th trial and hence becomes

$$\displaystyle P(X)=\binom {6-1}{6-1}(0.5)^{6}\left(1-0.5\right)^{\left(6-6\right)}=\left(\frac{1}{64}\right)$$

2) $1$ back step and $7$ front steps. This means $7$th success on $8$th trial and hence becomes

$$\displaystyle P(X)=P_1\binom {8-1}{7-1}(0.5)^{7}\left(1-0.5\right)^{\left(8-7\right)}=\left(\frac{63}{64}\right) \left(\frac{7}{256}\right)$$

3) $2$ back steps and $8$ front steps. This means $8$th success on $10$th trial and hence becomes

$$\displaystyle P(X)=P_2\binom {10-1}{8-1}(0.5)^{8}\left(1-0.5\right)^{\left(10-8\right)}=\left(\frac{15}{16}\right) \left(\frac{9}{256}\right)$$

4) $3$ back steps and $9$ front steps. This means $9$th success on $12$th trial and hence becomes

$$\displaystyle P(X)=P_3\binom {12-1}{9-1}(0.5)^{9}\left(1-0.5\right)^{\left(12-9\right)}=\left(\frac{219}{256}\right) \left(\frac{165}{4096}\right)$$

5) $4$ back steps and $10$ front steps. This means $10$th success on $14$th trial and hence becomes

$$\displaystyle P(X)=P_4\binom {14-1}{10-1}(0.5)^{10}\left(1-0.5\right)^{\left(14-10\right)}=\left(\frac{191}{256}\right) \left(\frac{715}{16384}\right)$$

6) $5$ back steps and $11$ front steps. This means $11$th success on $16$th trial and hence becomes

$$\displaystyle P(X)=P_5\binom {16-1}{11-1}(0.5)^{11}\left(1-0.5\right)^{\left(16-11\right)}=\left(\frac{319}{512}\right) \left(\frac{3003}{65536}\right)$$

7) $6$ back steps and $12$ front steps. This means $12$th success on $18$th trial and hence becomes

$$\displaystyle P(X)=P_6\binom {18-1}{12-1}(0.5)^{12}\left(1-0.5\right)^{\left(18-12\right)}=\left(\frac{1}{2}\right) \left(\frac{1547}{32768}\right)$$

8) $7$ back steps and $13$ front steps. This means $13$th success on $20$th trial and hence becomes

$$\displaystyle P(X)=P_7\binom {20-1}{13-1}(0.5)^{13}\left(1-0.5\right)^{\left(20-13\right)}=\left(\frac{793}{2048}\right) \left(\frac{12597}{262144}\right)$$

Adding all the probabilities yields $0.213283$.

Answer 2

Consider Pascal's triangle for a moment.

$$ \begin{matrix} & & & & & & 1 \\ & & & & & 1 & & 1\\ & & & & 1 & & 2 & & 1 \\ & & & 1 & & 3 & & 3 & & 1 \\ & & 1 & & 4 & & 6 & & 4 & & 1 \\ & 1 & & 5 & & 10 & & 10 & & 5 & & 1\\ 1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1\end{matrix} $$ Now, each number is the number of paths from the initial $1$ at the top to the respective point, such that each step is downwards.

What we seek is the number of paths that reach the sixth column to the right (or left) of centre. Let us look at the case of going two columns to the right in four steps. In this case, there are ${4\choose 3}=4$ paths that end in the second column. Then there's one path directly to the second column, from which two do not then finish in the second column, giving a total of $6$.

Now consider the case of two and six. In this case, we have 15 paths finishing in the second column, then there are 4 paths to the second column in four steps with two paths from there that do not then finish in the second column, and there is one path to the second column in two steps and then six paths from there that do not touch the second column again. This produces a total of $15\cdot1+4\cdot2+1\cdot6=29$. For confirmation, here are the 29 possible paths of length six reaching position 2:

$$\begin{matrix}++++++,& +++++-,& ++++-+,& \color{red}{++++--},& +++-++,\\ +++-+-,& \color{red}{+++--+}, &+++---,& ++-+++,& \color{red}{++-++-},\\ \color{red}{++-+-+},& ++-+--,& \color{red}{++--++},& ++--+-,& ++---+,\\ ++----,& +-++++,& \color{red}{+-+++-},& \color{red}{+-++-+},& +-++--,\\ \color{red}{+-+-++},& \color{red}{+--+++},& +--++-,& \color{red}{-++++-},& \color{red}{-+++-+},\\ -+++--,& \color{red}{-++-++},& \color{red}{-+-+++},& \color{red}{--++++}\end{matrix}$$ I have coloured the ones that end in position two in red. Now we can express the sum itself in the form $$ {6\choose4}\cdot1+{4\choose3}\cdot2+{2\choose2}\cdot6 $$

We can generalise this without too much trouble (we'll restrict it to even position targets). We can express the summation in the form $$ S_{M,N} = \sum_{k=N}^{M} {2k\choose k+N}{2(M-k)\choose M-k} $$ where $N=n/2$ is half the distance to the door (as the distance is even) and $M=m/2$ is half the total number of steps. Why the second combinatorial? Because if you work it out, the number of paths of length $2n$ that don't return to the centre column happens to be $2n\choose n$.

Now, just to demonstrate it working, notice that $$ S_{2,1} = 6\\ S_{3,1} = 29\\ S_{3,2} = 8 $$ Also note that, as expected, $S_{n,n}=1$.

Now, we're looking at $n=6$ and $m=20$, so $N=3$ and $M=10$, giving $$ S_{10,3} = 198440 $$ And of course, the total number of paths over 20 steps is $2^{20}$, so the probability works out to be $$ P = \frac{198440}{2^{20}} = \frac{198440}{1048576} \approx 0.189 $$ So there's roughly a 19% chance of the drunk reaching the door.