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.
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: