The game-theoretic vs measure-theoretic LLN

March 08, 2024

$\newcommand{\calF}{\mathcal{F}} \renewcommand{\Re}{\mathbb{R}} \newcommand{\E}{\mathbb{E}}$

When I first wrote about the game-theoretic law of large numbers I don’t think I fully appreciated its relationship to the measure-theoretic law of the large numbers. The game-theoretic LLN can be stated as a guarantee on a certain type of full information game (a “protocol”). In the first post we stated the game in terms of three players, but we’ll simplify it here for convenience.

• Bob has some initial capital, $$C_0 = 1$$
• For $$t=1,2,\dots$$
• Bob makes a bet $$M_t\in\Re$$
• The world reveals a value $$x_t\in [0,1]$$
• Bob updates his capital as $$C_t = C_{t-1} + M_t(1/2 - x_t)$$

The game stops if Bob goes broke (i.e., $$C_t<0$$). Translating the result from last time into a statement about this game, Bob has a strategy which ensures that either

$\label{eq:gt_slln} \lim_{t\to\infty}\frac{1}{t}\sum_{i\leq t} x_i = 1/2, \tag{1}$

or he becomes infinitely wealthy ($$\liminf_{t\to\infty}C_t = \infty$$). There’s nothing special about the constant 1/2 here. It could be replaced with any value between 0 and 1 and we’d simply change how Bob updates his capital. If you want to get all Bayesian about it, you might say that Bob has a belief that the average value of the observations $$x_t$$ is 1/2 and is betting accordingly. Or you don’t have to get Bayesian at all, and you can instead say that Bob is able force the world to act in a certain way if the world wants to prohibit him from getting infinitely wealthy.

Notice that there no probabilistic assumptions whatsoever in the statement of the game-theoretic LLN. There are no distributions, no probability measures, no sigma algebras, nothing. It makes a deterministic statement about every sequence of numbers $$(x_t)$$, namely that there exists a betting strategy such that either \eqref{eq:gt_slln} will happen, or Bob will become infinitely wealthy. It takes only a minor amount of mathematical background to understand this statement.

The measure-theoretic law of large numbers, on the other hand, requires graduate-level training in mathematics to fully understand. You need the notion of a probability measure, a sigma-algebra, and of almost-sure convergence (or convergence in probability for the weak law), which requires sophisticated tools from measure-theory to state, let alone understand.

It’s therefore somewhat remarkable that the game-theoretic LLN implies the measure-theoretic LLN (the strong LLN, in fact, which implies the weak LLN) for bounded observations. The game-theoretic LLN is therefore a stronger statement than its measure-theoretic counterpart.

To see that the game-theoretic LLN implies the measure-theoretic LLN, we add some distributional assumptions to the game above. Suppose the values $$x_t$$ are drawn iid from $$[0,1]$$ with mean $$1/2$$ (of course, $$[0,1]$$ can be replaced with any finite range). Let $$\calF_t$$ denote the $$\sigma$$-algebra of observations witnessed by the end of round $$t$$, i.e., $$\calF_t = \sigma(x_1,\dots,x_t)$$. Since $$M_t$$ is announced before witnessing $$x_t$$, it can only be based on the information in rounds $$1,2,\dots,t-1$$. That is, in measure-theoretic terms, $$M_t$$ is $$\calF_{t-1}$$-measurable. This implies that Bob’s wealth process, $$(C_t)_{t\geq 1}$$, is a martingale (with respect to the distribution over $$(x_t)$$):

$\E[C_t|\calF_{t-1}] = \E[C_{t-1} + M_t(1/2 - x_t)|\calF_{t-1}] = C_{t-1} + M_t\E[1/2 - x_t|\calF_{t-1}] = C_{t-1}.$

Moreover, Bob’s betting strategy ensures that $$C_t\geq 0$$ for all $$t$$, implying that $$(C_t)$$ is a nonnegative martingale. Nonnegative martingales starting at any finite value reach infinity with probability zero, i.e.,

$\Pr( \sup_{t} C_t = \infty) = 0.$

That is, Bob achieves infinite wealth with probability 0. Therefore, \eqref{eq:gt_slln} must happen with probability 1:

$\Pr\left(\lim_{t\to\infty} \frac{1}{t}\sum_{i=1}^t x_i = 1/2\right) = 1,$

which is precisely the (strong) law of large numbers.

# References

Back to all notes