October | 2010 | Spin Foam

(Follow-up to Expected value.)

This problem is known as the St. Petersburg paradox, and it was studied in the 18th century by Daniel Bernoulli and other mathematicians. In this post we will do a simple expected value analysis, but any kind of realistic analysis must consider the phenomenon of risk aversion.

Expected value

Let’s call H_i the event where a head appears at the i-th toss, and H_i the event where a tail appears at the same toss number. If we call P_n the probability that n tosses are required to get a head, we have:

$\displaystyle P_1 = P(H_1) = \frac{1}{2}$

$\displaystyle P_2 = P(T_1) P(H_2) = \frac{1}{2}\frac{1}{2} = \frac{1}{4}$

$\displaystyle P_3 = P(T_1) P(T_2) P(H_3) = \frac{1}{2}\frac{1}{2} \frac{1}{2} = \frac{1}{8}$

and, generalizing,

$\displaystyle P_n = P(T_1) P(T_2) \hdots P(T_{n-1}) P(H_n) = \left(\frac{1}{2}\right)^n = \frac{1}{2^n}$

As the bettor receives $ 2ⁿ from the house if n tosses are required, the expected balance is

$\displaystyle E[H] = \sum_{n=1}^\infty P_n 2^n - 100 = \sum_{n=1}^\infty \frac{2^n}{2^n} - 100 = \sum_{n=1}^\infty 1 - 100 = \infty$ .

So it would seem a perfect bet to make: what can be better than a bet with “infinite expected value”? 😀

Simulation

Let’s make a simulation to check if this result is reasonable:

import random

N = 10000

def get_tosses_until_head():
    tosses = 0
    while True:
        coin = random.randint(0, 1)
        tosses += 1
        if coin == 0:
            break
    return tosses

def get_balance():
    balance = -100
    tosses = get_tosses_until_head()
    balance += 2 ** tosses
    return balance

def main():
    random.seed(0)
    min_balance = max_balance = accum_balance = get_balance()
    for i in xrange(1, N):
        balance = get_balance()
        if balance < min_balance:
            min_balance = balance
        if balance > max_balance:
            max_balance = balance
        accum_balance += balance
    print 'Statistics after %d tries:' % N
    print '  Minimum balance: %d' % min_balance
    print '  Average balance: %d' % (float(accum_balance) / N)
    print '  Maximum balance: %d' % max_balance

if __name__ == '__main__':
    main()

Running the simulation we get:

Statistics after 10000 tries:
  Minimum balance: -98
  Average balance: -75
  Maximum balance: 32668

The average seems quite negative, how can we reconcile this with an “infinite expected value”? The answer is the same as in the case of the martingale: low probability events with huge returns skew the expected balance.

Let’s see how the normal expected value estimator works with a random variable $X$ , with finite expected value $\bar{x}$ and finite variance $\sigma^2_X$ :

$\displaystyle \widehat{x} = \frac{1}{N}\sum_{i=0}^N X_i$

$\displaystyle E[\widehat{x}] = E[\frac{1}{N}\sum_{i=0}^N X_i]$

$\displaystyle E[\widehat{x}] = \frac{1}{N}\sum_{i=0}^N E[X_i]$ (linearity of expectation)

$\displaystyle E[\widehat{x}] = \frac{1}{N}\sum_{i=0}^N \bar{x}$ ( $X_i$ are identically distributed)

$\displaystyle E[\widehat{x}] = \bar{x}$ (the estimator is unbiased)

$\displaystyle \sigma^2(\widehat{x}) = E[\widehat{x}^2 - E[\widehat{x}]^2]$

$\displaystyle \sigma^2(\widehat{x}) = E[\widehat{x}^2 - \bar{x}^2]$ ( $\bar{x}$ is an unbiased estimator)

$\displaystyle \sigma^2(\widehat{x}) = E[\widehat{x}^2] - \bar{x}^2$ (linearity of expectation; $\bar{x}$ is a number)

Replacing $\widehat{x}$ by its definition and focusing in $E[\widehat{x}^2]$ :

$\displaystyle E[\widehat{x}^2] = E\left[\left(\frac{1}{N}\sum_{i=0}^N X_i\right)^2\right]$

$\displaystyle E[\widehat{x}^2] = \frac{1}{N^2}E\left[\left(\sum_{i=0}^N X_i\right)^2\right]$ (linearity of expectation)

$\displaystyle E[\widehat{x}^2] = \frac{1}{N^2}E\left[\sum_{i=0}^N\sum_{j=0}^N X_i X_j\right]$ (square of a multinomial)

$\displaystyle E[\widehat{x}^2] = \frac{1}{N^2}\sum_{i=0}^N\sum_{j=0}^N E[X_i X_j]$ (linearity of expectation)

$\displaystyle N^2 E[\widehat{x}^2] = \sum_i E[X_i^2] + \sum_{\substack{i, j \\ j \ne i}} E[X_i] E[X_j]$ ( $X_i$ is independent of $X_j$ if $i \ne j$ )

$\displaystyle N^2 E[\widehat{x}^2] = N E[X_i^2] + (N^2 - N) \bar{x}^2$ ( $X_i$ are identically distributed)

Integrating this result in the $\sigma^2(\widehat{x})$ expression:

$\displaystyle \sigma^2(\widehat{x}) = \frac{N}{N^2} E[X_i^2] + \frac{N^2 - N}{N^2} \bar{x}^2 - \bar{x}^2$

$\displaystyle \sigma^2(\widehat{x}) = \frac{N}{N^2} E[X_i^2] - \frac{N}{N^2} \bar{x}^2$

$\displaystyle \sigma^2(\widehat{x}) = \frac{1}{N} \sigma^2_X$

This guarantees the convergence of the estimator to the expected value. But in our case there is no expected value (“it’s infinite”) and, consequently, we cannot even define the variance. Then the simulation is not very useful to get the expected value, as the estimator doesn’t need to converge to the expected value.

House without unbounded wealth

One (very realistic) situation where even the expected balance is negative is when the house has reasonably bounded wealth. For example, if we are betting against an agent whose possessions are merely equal to the entire world (!), the amounts we can be paid are bounded by ~$ 200·10¹², giving a very different expected value:

$\displaystyle E[H] = \sum_{n=1}^\infty P_n \min(2^n, 200\cdot10^{12}) - 100$