game-theoretic concentration inequalities

We can recover many of the classical concentration inequalities of measure-theoretic probabilities in game-theoretic form (see game-theoretic probability).

Fix a gamble space $(\Omega ,\mathcal{Z})$ (game-theoretic probability:Gamble spaces, prices, and probabilities).

Markov’s inequality

Let $X:\Omega \to [0,\infty )$ and $\alpha >0$. If the gamble space is arbitrage-free and positive-linear, then

$$\overline{\mathbb{P}}(X\ge \alpha )\le \frac{\overline{\mathbb{E}}[X]}{\alpha }.$$

The proof even mimics the proof of the usual Markov’s inequality (basic inequalities:Markov’s inequality). Notice that $X/(\alpha \overline{\mathbb{E}}[X])\ge 1(X\ge \alpha \overline{\mathbb{E}}[X])$ by case analysis. So

$$\overline{\mathbb{P}}(X\ge \alpha \overline{\mathbb{E}}[X])=\overline{\mathbb{E}}1(X\ge \alpha \overline{\mathbb{E}}X)\le \overline{\mathbb{E}}\left[\frac{X}{\alpha \overline{\mathbb{E}}[X]}\right]=\frac{1}{\alpha \overline{\mathbb{E}}[X]}\overline{\mathbb{E}}[X]=\frac{1}{\alpha },$$

where we’ve used the monotonicity and scaling properties of game-theoretic expectations.

Chebyshev’s inequality

The usual Chebyshev’s inequality (basic inequalities:Chebyshev’s inequality) bounds the concentration of a random variable in terms of its means variance. Since there’s no natural notion of mean or variance in GTP, we need to introduce it explicitly.

Let $(\Omega ,\mathcal{Z})$ be positive-linear. Suppose there exist $\mu ,\sigma$ such that $\overline{\mathbb{E}}(X-\mu {)}^2\le {\sigma }^2$. Then

$$\overline{\mathbb{P}}(|X-\mu |\ge \alpha \sigma )\le \frac{1}{{\alpha }^2}.$$