Expected Value of a Coin Flipping Game with Variable Coins

Question

Main Question:

My game works as follows:

1. You start with 1 coin and flip it. When you move to the next round, you add another coin and repeat.
2. You move on to the next round if the majority of the coins flipped in the current round come up heads. Otherwise, you lose the game.

I've been trying to calculate the expected value of this game — the average round you get to before you lose.

I've calculated that, for a given round R:

$P(\text{win round R}) = \frac{1}{2^R}\sum^{R}_{k=floor(R/2)+1}{R \choose k}$

and with a simulation in Java, the expected value came out to be about $1.7229533856734633$, but I've no clue of a closed form for this value.

How would I find this expected value, analytically? Thank you!

Simulation Code, if there's discrepancy between the analytic expected value and the simulated one:

public static void main(String[] args) {
    int total = 0;
    double sim = Math.pow(2.0, 30.0);
    for (int i = 0; i < sim; i++) {
        total += game();
    }
    System.out.println((double) total / sim);
}

public static int flip(int coins) {
    int heads = 0;
    for (int i = 0; i < coins; i++) 
    {
        if (Math.random() >= 0.5) 
            heads++;
    }
    return heads;
}

public static int game() {
    int coins = 1;
    while (flip(coins) > coins/2) {
        coins++;
    }

    return coins;
}

Answer 1

Not quite a closed form but here is a simplification.

Let $X$ be a random variable denoting the number of rounds that the game lasts. First we use the fact that $$\mathbb{E}[X] = \sum_{n=0}^{\infty} \mathbb{P}(X > n) = 1 + \sum_{n=1}^{\infty} \mathbb{P}(X > n).$$

$X>n$ if and only if rounds $1,2,\ldots, n$ are won. The probability we win round $n$ is $1/2$ if $n$ is odd and $\frac{1}{2} \left( 1 - \frac{ \binom{n}{n/2} }{2^n} \right)$ if $n$ is even. Therefore we have

$$ \mathbb{E}[X] = 1 + \sum_{n=1}^{\infty} \frac{1}{2^n} \prod_{m=2,4,6,\ldots}^n \left(1 - \frac{ \binom{m}{m/2} }{2^m} \right)$$

Using the first $150$ terms of this series gives the value to $50$ correct decimal places:

$$\mathbb{E}[X] \approx 1.7229609314217239880589009988703907210042264264132$$

---

Here is the Python code I used to generate the value. It runs in about 0.6 milliseconds on my machine.

from scipy.special import comb
from decimal import *
getcontext().prec = 50 # Number of decimal places

def p(i): # Probability of winning round i
    if i % 2: return Decimal('0.5')
    return Decimal('0.5') - Decimal(comb(i, i//2)) / Decimal(2**(i+1))

def EV(n):
    S, P = 1, 1
    for i in range(1, n+1):
        P *= p(i)
        S += P
    return S

print(EV(150))

Answer 2

Let $p$ be the probability that a coin is heads. Let $\{X_n:n\geqslant 0\}$ be a Markov chain on the nonnegative integers with $X_0=1$ a.s. and transition probabilities $$ P_{ij} = \begin{cases} 1,& i=j=0\\ 1- p^i\sum_{k=\lfloor i/2\rfloor + 1}^i\binom ik,& i>0, j=0,\\\ p^i\sum_{k=\lfloor i/2\rfloor + 1}^i\binom ik,& i>0, j=i+1 \end{cases} $$ Let $\tau_j=\inf\{n>0:X_n=j\}$. Then the probability that you get to round $j$ before losing is \begin{align} \mathbb P(\tau_j<\infty) &= P_{j,0}\sum_{i=1}^j P_{i,i+1}\\ &= \left(1- p^j\sum_{k=\lfloor j/2\rfloor + 1}^j\binom jk\right)\sum_{i=1}^j\left(p^i\sum_{k=\lfloor i/2\rfloor + 1}^i\binom ik\right) . \end{align} Mathematica gives $$ P_{i,i+1} = \texttt{Binomial[i, 1 + Floor[i/2]] Hypergeometric2F1[1, 1 - i + Floor[i/2],}\\ \texttt{ 2 + Floor[i/2], -1]} $$ but does not even attemp to evaluate the sum. This is a hard problem.