TITLE: Finding the expected value of coin flip experiment (Dark Souls problem)
QUESTION [13 upvotes]: I'm trying to find the formula for an expected value, but testing has shown that my formula is incorrect. Can you find either a closed form or recursive formula for the expected values in this experiment, and explain how you found that formula?
The Game
You have $n$ coins labelled $1$ through $n$. We will label the set of coins $[n]$. We have a function $f$ that maps coin $i$ to the probability coin $i$ lands heads. A coin landing heads is a success. A coin landing tails is a failure. 
We start with flipping coin $1$. If coin $1$ lands heads, we move on to coin $2$. If coin $1$ lands tails, we start over with coin 1.
On coin $i$, if coin $i$ lands heads, we move on to coin $i+1$. If coin $i$ lands tails, we return to coin $1$.
If we land heads on coin $n$, we win and the game ends.
The Variables and Counters
We will be keeping track of $n$ variables $\{ X_1, X_2, \ldots , X_n \}$. Each of these will count some, but not all, of the times we fail coin $n$. To make the explanation easier, we will treat these as counters in an algorithm, and their final values will be the random variables.
If we flip heads on coin $i$, we do nothing.
If we flip tails on coin $i$, one of two things happens.

If the last coin we failed, $j$, appeared later than $i$ (that is, $j > i$), then we reset all counters $\{ X_1, X_2, \ldots , X_n \}$ to $0$ and then set $X_i=1$.
If the last coin we failed, $j$, appeared earlier than or is equal to $i$ (that is, $j \leq i$), then we increment $X_i$ by $1$ and move back to coin $1$ as described in the rules.

Edit: If we have not failed a coin previously, then we do $(2)$ . That is, we increment $X_i$ by $1$ and move back to coin $1$ without changing any other counters.
The Problem
We want to find the expected value of each $X_i$ after successfully flipping heads on coin $n$.
My Solution
It's hard to put my solution in math terms, because my solution is wrong.
I write the expansion 
$$E(X_i) = 0*P(X_i = 0) + 1*P(X_i = 1) +  2*P(X_i = 2) + 3*P(X_i = 3) + \ldots \text{.}\tag{1}$$
My intuition then leads me to say 
$$P(X_i=k+1) = P(X_i=k)*(1-f(i))*\prod_{j = 1}^{j=i-1}f(j)\text{.}\tag{2}$$
The above, $(2)$, is probably wrong, but here is the intuition. $(1-f(i))$ represents the probability of an extra failed flip of coin $i$ at a particular point in the game followed by successful coin-flips on coins $1$ through $i-1$ represented by the term $\prod_{j = 1}^{j=i-1}f(j)$.
For notational convenience, we set $x=(1-f(i))*\prod_{j = 1}^{j=i-1}f(j)$. We can then use $P(X_i =0) + P(X_i=1) + P(X_i=2) +\ldots = 1$ to find that 
$$P(X_i=k)= (1-x)*x^{k} \tag{3}$$
and then
$$\mathbb{E}(X_i) = \frac{x}{1-x}\text{.}\tag{4}$$
Displays $(3)$ and $(4)$ are just algebra, and even if there is a typo, I'm fairly certain that is not where the problem lies.
Data
If $n=5$ and $f(i)=.5$ for all $i$, then some approximations of the expected values are $\mathbb{E}(X_1) = 1.56902$, $\mathbb{E}(X_2)= .4036$, $\mathbb{E}(X_3)= .15541$, $\mathbb{E}(X_4)= .06952$, and $\mathbb{E}(X_5)= .03185$. These were found by running experiments in C++. I provide these so you can test your formulas against the actual values. My formula in display $(4)$ will give you values $\mathbb{E}(X_2)= \frac{1}{3}$, $\mathbb{E}(X_3)= \frac{1}{7}$, $\mathbb{E}(X_4)= \frac{1}{15}$, and $\mathbb{E}(X_5)= \frac{1}{31}$.
Note
I really don't care about $\mathbb{E}(X_1)$, so my rules, formula, and data may not all match up for that case.

REPLY [4 votes]: Let's reformulate the problem in an equivalent and simpler way:
We have a sequence of independent realizations of a discrete random variable $Y$, taking values on $1, 2 \cdots, n , n+1$, with a given pmf $q_i = P(Y=i)$. We win a round each time $Y=n+1$.
( In the original formulation $Y$ corresponds to the first coin that "failed" (tail), or either $Y={n+1}$ if we won. Hence
$$
q_i = \begin{cases} 
(1-f_i)\prod_{j=1}^{i-1}{f_j} & \quad 1\le i \le n \\
1 - \sum_{i=1}^n (1-f_i)\prod_{j=1}^{i-1}{f_j} & \quad i = n+1
\end{cases} \tag1
$$
gives the relationship between $q_i$ and $f_i$. Moreover, $q_i$ corresponds to $x$ in OP's attempt).
For each round, we mark the longest immediately previous non-decreasing subsequence (perhaps empty), and count each value of $Y$.
Take for example, $n=5$, and a particular sequence: $$\cdots 4 \, \color{green}{2 \, 3 \,4 \,4} \,\color{red}{6} \,5\, 3\, \color{green}{1\, 1\, 5} \,\color{red}{6} \, \color{red}{6}\, 3\, 4 \cdots \tag2$$
Each red number signals a finished round, and each inmediate previous non-decreasing sequence (in green) denotes the counted values (coins).
Hence, in the three completed round here: we have ${\bf x}=(x_1,x_2,x_3,x_4,x_5)= (0,1,1,2,0)$ for the first round, ${\bf x}=(2,0,0,0,1)$ for the second and ${\bf x}=(0,0,0,0,0)$ for the last one (empty counters). We want to calculate  $E[x_i]$.

( Edit - see below for a simpler and better proof)
Imagine a long sequence of length $m$. In average we'll have $q_6 m$ completed rounds.
Let $\alpha_{k,5}$ count the number of rounds with $x_5=k$ ($0\le k < \infty$). Again, in average we'll have $$\alpha_{k,5} = m \, q_6 \, q_5^k(1-q_5) \tag3$$
Hence the approximation (asympotically exact, I conjecture) $p(x_5 = k) = q_5^k (1-q_5)$ and $$E[x_5]= \frac{q_5}{1-q_5} \tag4$$
Similarly, for  $\alpha_{k,4}$ we can sum over $j$, the number of intermediate $5's$ and
$$\alpha_{k,4} = \sum_j m \, q_6 \, q_5^j q_4^k(1-q_4) \tag5$$
and $$E[x_4]= \frac{q_4}{(1-q_5)(1-q_4)}$$
Then, in general
$$E[x_i]= \frac{q_i}{\prod_{j=i}^n(1-q_j)} \tag6$$

Edit: Another proof: Let's compute, for example, $p(x_3) = P(x_3 = x_3)$ , i.e., the probability that the most recent non-decreasing sequence before a given $6$ (and excluding the previous $6$) includes $x_3$ $3$'s. For $x_3 \ge 1$ this is given by
$$ p(x_3) = \sum_{x_5, x_4} (1-q_3)  q_3^{x_3} q_4^{x_4} q_5^{x_5}= \frac{(1-q_3)}{(1-q_4)(1-q_5)}  q_3^{x_3}  \tag7$$
Now, because $\sum_{k=0}^{\infty} k a^k=\sum_{k=1}^{\infty} k a^k=a (1-a)^{-2}$, the expected value is:
$$E[x_3]=  \frac{q_3}{(1-q_5)(1-q_4)(1-q_3)} \tag 8$$
in agreement with $(6)$.

Some values, in agreement with numerical simulation:
 i       1       2       3       4       5
   
 f      0.5     0.5     0.5     0.5     0.5
 q    0.50000 0.25000 0.12500 0.06250 0.03125
E[x]  1.67783 0.41946 0.15730 0.06882 0.03226
   
 f      0.9     0.7     0.5     0.3     0.1
 q    0.10000 0.27000 0.31500 0.22050 0.08505
E[x]  0.31155 0.75707 0.64477 0.30917 0.09296
   
 f       0.1     0.3     0.5     0.7     0.9
 q     0.90000 0.07000 0.01500 0.00450 0.00105
E[X]   9.87958 0.07684 0.01531 0.00453 0.00105
{"set_name": "stack_exchange", "score": 13, "question_id": 3686625}