Source-linked AI summary
Hoeffding's inequality in game-theoretic probability
Vladimir Vovk
TL;DR
The note addresses the absence of large-deviation inequalities in a book presenting game-theoretic probability results. It applies Hoeffding’s original proof in a forecasting game, deriving a supermartingale and using it to state a game-theoretic Hoeffding inequality.
Problem
A recent book on game-theoretic probability contains versions of several probability results but no large-deviation inequalities.
Source: §1 · p. 1Method
The note adapts Hoeffding’s proof by constructing a non-negative supermartingale in a bounded-variable forecasting game.
Source: §2 · pp. 1–3Results
The constructed supermartingale yields a game-theoretic version of Hoeffding’s inequality for upper probability in the forecasting game.
Source: §3 · p. 4Takeaways & Limitations
Hoeffding’s original proof remains valid in the game-theoretic framework.
Source: §1 · p. 1, §2 · p. 1, §3 · p. 4The forecasting protocol is a perfect-information game with no randomness.
Source: §2 · p. 2
Abstract
from arXiv · showhide
This note makes the obvious observation that Hoeffding's original proof of his inequality remains valid in the game-theoretic framework. All details are spelled out for the convenience of future reference.
1 Introduction
The note fills a gap in game-theoretic probability by stating a game-theoretic version of Hoeffding’s inequality.
1 Introduction
- The note states a game-theoretic version of Hoeffding’s inequality, whose original result is cited as, Theorem 2.The cited book presents game-theoretic versions of several probability results but contains no large-deviation inequalities.Source: §1 · p. 1
2 Hoeffding’s supermartingale
The section constructs a non-negative supermartingale starting from 1, then uses it to obtain Hoeffding’s inequality. It presents the forecasting protocol and the argument bounding the supermartingale’s one-step growth.
2 Hoeffding’s supermartingale
- A non-negative supermartingale starting from 1 is the central product of Hoeffding’s method and is used to obtain the inequality.The section says its theorem is essentially inequality (4.16) in.Source: §2 · pp. 1–2
- The protocol has Forecaster announce bounds and an expectation, Reality choose a bounded observation, and Sceptic trade tickets and update capital.Sceptic may choose initial capital and discard money at round ends; the protocol is perfect-information, with no randomness.Source: §2 · pp. 1–2
- The proof shifts all bounds and expectations by the same constant so that μ_n = 0, without changing Sceptic’s position.It then assumes a_n < 0 < b_n.Source: §2 · p. 2
- The one-step construction reduces to an exponential inequality, which the proof establishes using convexity and a second-order Taylor expansion.The second derivative is bounded by (b_n - a_n)^2/4.Source: §2 · p. 3
- The section relates game-theoretic and measure-theoretic probability and notes that many measure-theoretic proofs carry over straightforwardly.The protocol asks Forecaster only for the interval and expectation needed for the result, rather than a full probability forecast.Source: §2 · p. 3
3 Hoeffding’s inequality
The section defines upper probability through non-negative supermartingales and uses the constructed supermartingale to state Hoeffding’s inequality in the forecasting game. The resulting corollary concerns a fixed-round event when bounds are known in advance.
3 Hoeffding’s inequality
- Upper probability is the infimum initial value of non-negative supermartingales that reach at least 1 on the event.The passage identifies this as a game-theoretic counterpart of measure-theoretic probability.Source: §3 · p. 4
- The corollary gives a game-theoretic Hoeffding bound on upper probability for an event over a fixed number of rounds, with bounds known in advance and t > 0.The proof maximizes the bound’s right-hand side at h = 4Nt/C; the supplied passages do not state the resulting bound’s formula.Source: §3 · p. 4
- Sceptic needs to know only C at the game’s start, not the individual bounds a_n and b_n.The corollary assumes the bounds are given in advance.Source: §3 · p. 4
- The measure-theoretic counterpart is sometimes called the Hoeffding–Azuma inequality, while the martingale version also appears in Hoeffding’s paper.The note attributes the name’s Azuma reference to.Source: §3 · p. 4