"Back to square one" problem 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.
 A: 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. 
A: 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
A: 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$.
