5
$\begingroup$

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;
}
$\endgroup$
5
$\begingroup$

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))
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I understand the odd probability, but I have trouble seeing how you got to the formula for the even probability. I know it works, I just have trouble understanding it conceptually. How did you derive that expression? $\endgroup$ – Robert Jan 5 at 18:02
  • 1
    $\begingroup$ @Robert I used the symmetry in the rows of Pascal's triangle. Each row adds to $2^n$. For odd $n$, the is a clear left half and right half, both equal to each other so both equal to $2^{n-1}$. For even $n$ there is a middle term which makes things harder, but if you just split the middle term into halves and put them on each side, again you get two equal sides equal to $2^{n-1}$. So the sum of the terms we wanted is $2^{n-1}$ minus half the middle term. $\endgroup$ – Ragib Zaman Jan 5 at 18:16
  • 1
    $\begingroup$ Alternatively, you could think of it as $P(k < n/2) + P(k>n/2) = 1-P(k=n/2)$ (where $n$ is even and $k$ is the number of heads) and note the two terms of the left hand side are the same by symmetry. $\endgroup$ – Ragib Zaman Jan 5 at 18:24
  • 1
    $\begingroup$ Ah - gotcha; I wrote this out and now I can clearly see where the expression came from. Thank you so much for helping me understand it! $\endgroup$ – Robert Jan 5 at 18:27
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.