xxiii. St. Petersburg Paradox

Problem (N. Bernoulli, 1713). Toss a fair coin until the first head; if that takes $K$ tosses you win $2^K$. How much should you pay to play? $P(K=k)=2^{-k}$, so $\mathbb{E}[2^K]={\sum }_k{2}^{-k}{2}^k=1+1+\cdots =\infty$, yet nobody would pay more than a few dollars.

Resolution	Value of the game
expected value	$\infty$
banker with finite wealth $W$ ($2^m\le W<2^{m+1}$) pays $\min (2^K,W)$	$m+W/2^m\approx {\log }_{2}W+1$ (a billion-dollar bank: about 31)
logarithmic utility (D. Bernoulli, 1738), no wealth	$\mathbb{E}[{\log }_2{2}^K]=2$: certainty equivalent $2^2=4$
log utility with wealth $w$, fair entry price $c$ solving $\mathbb{E}[\ln (w-c+2^K)]=\ln w$	grows like ${\log }_{2}w$: about $3.35$ at $w=2$, $20.87$ at $w=10^6$
playing $n$ times (Feller)	total winnings $\approx n{\log }_{2}n$: the fair price per game grows like ${\log }_{2}n$

Fair entry price under log utility, from the code below: $w=2\to 3.35$ (you must borrow $1.35$), $w=10\to 4.97$, $w=100\to 7.79$, $w=1000\to 10.95$, $w=10^6\to 20.87$.

double cappedValue(double W) {                      // E[min(2^K, W)], K = number of tosses until the first head
    double s = 0;
    for (int k = 1; k < 2000; k++) s += ldexp(min(ldexp(1.0, k), W), -k);
    return s;
}
 
double logUtilityPrice(double w) {                  // largest entry price c with E[ln(w - c + 2^K)] >= ln w
    auto f = [&](double c) { double s = 0; for (int k = 1; k < 200; k++) s += ldexp(log(w - c + ldexp(1.0, k)), -k); return s - log(w); };
    double lo = 0, hi = w + 2;                      // c < w + 2 keeps the worst outcome (K = 1) positive
    for (int it = 0; it < 200; it++) { double mid = (lo + hi) / 2; (f(mid) >= 0 ? lo : hi) = mid; }
    return lo;
}
 
double averagePayout(int n, mt19937_64& rng) {      // average over n games (grows like log2 n)
    double s = 0;
    for (int i = 0; i < n; i++) { int k = 1; while (rng() & 1) k++; s += ldexp(1.0, k); }
    return s / n;
}

Proof: capped value, log utility and Feller's law

Capped game. With $2^m\le W<2^{m+1}$, the payout is $2^k$ for $k\le m$ and $W$ for $k>m$:
${\sum }_{k=1}^m{2}^{-k}{2}^k+W{\sum }_{k>m}{2}^{-k}=m+W{2}^{-m}$. For $W=2^m$ this is $m+1$. So a bank worth $10^9\approx 2^{29.9}$ makes the game worth about 31.

Log utility. $\mathbb{E}[{\log }_2{2}^K]={\sum }_{k}k{2}^{-k}=2$ (differentiate $\sum x^k=\frac{x}{1-x}$, so $\sum k{x}^k=\frac{x}{(1-x{)}^2}$, at $x=\frac{1}{2}$). The certain amount with the same utility is $2^2=4$. With wealth $w$, $f(c)=\mathbb{E}[\ln (w-c+2^K)]-\ln w$ is decreasing in $c$, so bisection finds the fair price.

Feller’s weak law. Let $S_n$ be the total of $n$ games and $b_n=n{\log }_{2}n$. Truncate: $Y_i=X_i[X_i\le b_n]$. Since $P(X>b)={\sum }_{2^k>b}{2}^{-k}\le 2/b$, $P(\exists i:X_i\ne Y_i)\le n\cdot 2/b_n=2/{\log }_{2}n\to 0$. Next $\mathbb{E}[Y]=\#\{k\ge 1:2^k\le b_n\}=\lfloor {\log }_2{b}_n\rfloor ={\log }_{2}n+O(\log \log n)$ and $\mathrm{Var}Y\le \mathbb{E}[Y^2]={\sum }_{2^k\le b_n}{2}^k\le 2b_n$. By Chebyshev, $P(|\sum Y_i-n\mathbb{E}Y|>\epsilon b_n)\le \frac{n\cdot 2b_n}{{\epsilon }^2{b}_n^2}=\frac{2}{{\epsilon }^2{\log }_{2}n}\to 0$. Hence $S_n/(n{\log }_{2}n)\to 1$ in probability: the fair price for $n$ games is about ${\log }_{2}n$ per game. All three functions were checked (capped value against $m+W/2^m$, prices against the bisection identity, averages against ${\log }_{2}n$ within a constant factor).

Related notes

• Probability and Expectation
• Two Envelopes Paradox
• Gambler’s Ruin