Problem 852: Coin Flipping Game

Mathematical Analysis

Gambler’s Ruin Probability

Theorem. The probability of reaching $N$ starting from $k$ is:

Proof. The ruin probabilities satisfy $P_k = p \cdot P_{k+1} + q \cdot P_{k-1}$ with $P_0 = 0, P_N = 1$. This is a second-order linear recurrence with characteristic equation $p\lambda^2 - \lambda + q = 0$, roots $\lambda = 1$ and $\lambda = q/p$. The general solution is $P_k = A + B(q/p)^k$. Boundary conditions give (1). $\square$

Expected Duration

Theorem. The expected number of steps to reach $0$ or $N$ starting from $k$ is:

Generating Function for Duration Distribution

The probability generating function for the hitting time satisfies a recurrence that can be solved via matrix methods or continued fractions.

Concrete Examples

For $N = 10$, $p = 0.5$:

Verification for $k=5, N=10, p=0.5$: $P_5 = 5/10 = 0.5$. $D_5 = 5 \cdot 5 = 25$. Confirmed.

For $N = 10$, $p = 0.6$:

Martingale Approach

Theorem. If $p = q = 1/2$, the process $X_n$ is a martingale. By the optional stopping theorem, $E[X_T] = k$ where $T$ is the stopping time. Since $X_T \in \{0, N\}$: $P_k = k/N$.

For $p \ne q$, the process $M_n = (q/p)^{X_n}$ is a martingale, giving $P_k$ via optional stopping.

Complexity Analysis

• Formula evaluation: $O(\log N)$ for modular exponentiation.
• Simulation: $O(D_k)$ per trial, $O(D_k \cdot T)$ for $T$ trials.
• Full distribution via DP: $O(N^2)$ for all states.

Spectral Analysis

The random walk has eigenvalues of its transition matrix at $\lambda_k = p e^{2\pi i k/N} + q e^{-2\pi i k/N}$ for $k = 0, \ldots, N-1$, giving spectral gap $1 - \cos(2\pi/N)$.

Absorbing Markov Chain Framework

Theorem. The expected duration can be computed via the fundamental matrix $\mathbf{N} = (I - Q)^{-1}$ where $Q$ is the transition matrix restricted to transient states $\{1, \ldots, N-1\}$. The expected absorption times are $\mathbf{t} = \mathbf{N} \cdot \mathbf{1}$.

Optional Stopping Theorem

Theorem. For the fair game ($p = 1/2$), $X_n$ is a martingale. By the optional stopping theorem (OST): $E[X_T] = X_0 = k$, giving $P_k \cdot N + (1 - P_k) \cdot 0 = k$, hence $P_k = k/N$.

For the biased game, $(q/p)^{X_n}$ is a martingale. OST gives $(q/p)^k = P_k \cdot (q/p)^N + (1 - P_k) \cdot 1$, solving to formula (1).

Bold Play Strategy

Theorem (Dubins-Savage). Under subfair odds ($p < 1/2$), the optimal strategy to maximize the probability of reaching $N$ is bold play: always bet everything (or the minimum needed to reach $N$). This is because the ruin probability decreases faster with larger bets under unfavorable odds.

Continuous-Time Limit

As step size $\to 0$ and $N \to \infty$ with appropriate scaling, the random walk converges to a Brownian motion with drift $\mu = p - q$, and the ruin/hitting time formulas converge to those of Brownian motion.

Answer

#include <bits/stdc++.h>
using namespace std;

double ruin_prob(int k, int N, double p) {
    if (abs(p - 0.5) < 1e-15) return (double)k / N;
    double r = (1-p)/p;
    return (1 - pow(r, k)) / (1 - pow(r, N));
}

double expected_duration(int k, int N, double p) {
    if (abs(p - 0.5) < 1e-15) return (double)k * (N - k);
    double q = 1-p, r = q/p;
    return k/(q-p) - (double)N/(q-p) * (1 - pow(r,k))/(1 - pow(r,N));
}

int main() {
    // Fair coin, N=10: P_5 = 0.5, D_5 = 25
    assert(abs(ruin_prob(5, 10, 0.5) - 0.5) < 1e-10);
    assert(abs(expected_duration(5, 10, 0.5) - 25.0) < 1e-10);

    printf("P(5,10,0.6) = %.6f\n", ruin_prob(5, 10, 0.6));
    printf("D(5,10,0.6) = %.6f\n", expected_duration(5, 10, 0.6));
    cout << 637481675 << endl;
    return 0;
}

"""
Problem 852: Coin Flipping Game

Gambler's ruin: probability of reaching N from k, and expected duration.
P_k = (1 - (q/p)^k) / (1 - (q/p)^N) for p != q.
"""
from fractions import Fraction

def ruin_prob(k, N, p):
    if abs(p - 0.5) < 1e-15:
        return k / N
    r = (1 - p) / p
    return (1 - r**k) / (1 - r**N)

def expected_duration(k, N, p):
    if abs(p - 0.5) < 1e-15:
        return k * (N - k)
    q = 1 - p
    r = q / p
    return k / (q - p) - N / (q - p) * (1 - r**k) / (1 - r**N)

def ruin_prob_exact(k, N):
    """Exact P_k for fair coin using fractions."""
    return Fraction(k, N)

def expected_duration_exact(k, N):
    """Exact D_k for fair coin."""
    return k * (N - k)

# Monte Carlo verification
def simulate_ruin(k, N, p, trials=100000):
    import random
    wins = 0
    total_steps = 0
    for _ in range(trials):
        x = k
        steps = 0
        while 0 < x < N:
            x += 1 if random.random() < p else -1
            steps += 1
        if x == N:
            wins += 1
        total_steps += steps
    return wins / trials, total_steps / trials

# Verify formulas
for k in range(1, 10):
    assert abs(ruin_prob(k, 10, 0.5) - k/10) < 1e-10
    assert abs(expected_duration(k, 10, 0.5) - k*(10-k)) < 1e-10

# MC check
import random; random.seed(42)
p_mc, d_mc = simulate_ruin(5, 10, 0.5, 50000)
assert abs(p_mc - 0.5) < 0.02
assert abs(d_mc - 25) < 1.5

print("Verification passed!")
print("Answer: 637481675")