Expected time to reach the end of the line

Question

Imagine we have six nodes, labeled 0 through 5. One can transition from node $i$ to $i+1$ with probability $p$ or can remain at node $i$ with probability $1-p$. Note that once one transitions to a node, it cannot backtrack. See the following figure for an illustration.

I want to know the expected time it takes to reach node 5 assuming you start at node 0. I started to write down the following outcomes below:

• 5 transitions, 0 stops (5 time-steps)
• 5 transitions, 1 stop (6 time-steps)
• 5 transitions, 2 stops (7 time-steps)
• and so on...

where "stop" means no transition was made. Once we list all of the cases then it's just a matter of computing the probabilities. Problem is, I don't know how to write out all of the cases (infinitely many?). Is this the right way of thinking about it?

Answer 1

The easier way to approach this problem is to take advantage of linearity of expectation by expressing the transit time as a sum of i.i.d. geometrically-distributed random variables, as in Daniel Xiang’s answer, but it can certainly be attacked the way you propose: by computing the probability that it takes a given number of time steps to reach the end and then finding the sum of the infinite series that directly results from the definition of expectation.

Let $Y$ count the number of time steps to transit the chain. Since every transit takes at least five steps, we’ll focus on the probabilities of extra time being taken—of there being $k$ stops during the transit. Let the random variable $X=Y-5$ count these extra steps. As you’ve already determined, $\Pr(X=k)$ is equal to $p^5(1-p)^k$ times a coefficient that counts the number of ways that the stops can be distributed throughout the transit. This is a typical stars-and-bars problem, from which we can easily work out this coefficient: $$\Pr(X=k)=\binom{4+k}4p^5(1-p)^k$$ so $$E[X]=\sum_{k=0}^\infty k\Pr(X=k)=p^5\sum_{k=0}^\infty k\binom{4+k}4(1-p)^k=p^5{5-5p\over p^6}=5{1-p\over p}$$ and $$E[Y]=5+E[X]=\frac5p.$$

Answer 2

Let $T_i$ be the time it takes to reach node $i$ for $i = 1, ..., 5$.

Then the total time $T$ it takes for one to reach node 6 from node 0 can be written as a sum \begin{align*} T = T_1 + \dots + T_5 \end{align*} So the expected value of $T$ is \begin{align*} ET = \sum_1^5 ET_i \stackrel{(*)}{=} \sum_1^5 \frac{1}{p} = \frac{5}{p} \end{align*}

$(*)$ Since each $T_i$ is distributed $\sim$ Geom($p$)

Answer 3

You can model the number of steps to reach the destination as a Negative Binomial random variable $X$ with parameters $r=5$ (number of successes) and $p$. The success is moving to the right (with probability $p$ and the failure is staying in the same position.

The expectation of a Negative Binomial random variable is:

$$E[X]=\frac{r}{p}=\frac{5}{p}$$