"Back to square one" problem

Question

There's a problem I've been stuck on in preparation for junior programming contest I'm going to participate in. It is as follows:

The "back to square one" problem is played on a board that has $n$ squares in a row and $n-1$ probabilities. Players take turns playing. On their first turn, a player advances to square $1$.After the first turn, if a player is on square $i$ , the player advances to square $i + 1$ with probability $p(i)$ , and returns to square 1 with probability $1-p(i)$ .The player is finished upon reaching square $n$. Compute the expected number of turns to complete the game.

$\textbf{My Attempt:}$ From the definition of expectation we know that

$$E[X] = \sum_{i=1}^{n-1}i\cdot P(i)= \sum_{i=1}^{n-1}i\cdot(1-p(i))\cdot p(i)$$

I'm not really sure what to do with this expression. Perhaps it follows a negative binomial distribution. But, the CDF for this is really ugly and I think it would be beyond the scope of this contest.

Answer 1

Let $f(i)$ be the expected number of turns when you are on square $i$. Then you have the recurrence for $i=1, 2,3,\dots n-1$: $$f(i) =1+ f(i+1)p(i)+f(1)(1-p(i)), \; f(n)=0$$ and we seek $f(0)=1+f(1)$. This gives you a linear system to solve.

Answer 2

Intuitively, you need to win $n-1$ in a row. The chance of doing that is $\prod_i p(i)$, so it takes $\frac 1{\prod_i p(i)}$ tries. You need to work out the average length of a failed try. It is $1\ \ 1-p(1)$ of the time, $2\ \ p(1)(1-p(2))$ of the time, and so on. Add those up, remembering that you must fail $n-2$ for this calculation. If the average length of a failure is $x$, you have $\frac x{\prod_i p(i)}+n-1$ for the expected time to success

Answer 3

This is a problem of knowing after how many iterations a transient markov state gets absorbed into the absorbing state.

Wikipedia helps!

Basically fill a matrix $A$ with the probabilities of the markov chain, remove the last column and last row that correspond to the absorbing state, you have $Q$.

Then $N = (I - Q)^{-1}$, and the answer is the sum of the first row of $N$.