確率変数の正確な分布が分からなくても、期待値や分散がわかっていれば「極端な値が出る確率」の上限を見積もることができます。たとえば、平均100点、標準偏差10点のテストで、130点以上（平均+3σ）を取る確率はどの程度でしょうか。分布の形を知らなくても、チェビシェフの不等式は「1/9 以下」という上限を教えてくれます。
このような確率の不等式（probability inequalities）は、確率論と統計学の理論を支える基盤的な道具です。特に近年の機械学習理論では、集中不等式（concentration inequalities）と呼ばれるより精密な不等式が中心的な役割を果たしています。
確率の不等式を理解すると、以下のような応用が可能になります。
- 大数の法則の証明: チェビシェフの不等式による弱法則の証明
- 機械学習の汎化誤差評価: ヘフディングの不等式によるPAC学習の理論
- 仮説検定の理論: 検定統計量の裾確率の評価
- 信頼区間の構成: 有限サンプルに対する非漸近的な信頼区間
- バンディットアルゴリズム: UCBアルゴリズムの設計と解析
本記事では、4つの基本不等式を弱いものから強いものへ順に導出し、それぞれの適用場面と精度の違いをPythonで比較します。
本記事の内容
- マルコフの不等式（最も基本的な不等式）
- チェビシェフの不等式（分散を使った改善）
- ヘフディングの不等式（有界確率変数に対する指数型の集中不等式）
- ベルンシュタインの不等式（分散情報を活用した精密化）
- チェルノフ法（指数的不等式の統一的な導出法）
- Pythonによる比較と応用例
前提知識
マルコフの不等式
直感
マルコフの不等式は「非負の確率変数が大きな値を取る確率は、期待値で制限される」という最も基本的な不等式です。
日常的なアナロジーで考えましょう。ある会社の社員の平均年収が500万円だとします。すると、年収5000万円以上の社員は全体の何パーセント以上いることは絶対にありません。もし社員の10%が5000万円以上もらっていたら、残り90%の平均は $(500 – 0.1 \times 5000) / 0.9 < 0$ となり、年収が非負であることに矛盾します。マルコフの不等式は、年収5000万円以上の社員は最大でも $500/5000 = 10\%$ であることを保証します。
定理
$X \geq 0$ かつ $E[X] < \infty$ のとき、任意の $a > 0$ に対して
$$ \begin{equation} P(X \geq a) \leq \frac{E[X]}{a} \end{equation} $$
証明
証明は驚くほどシンプルです。$\mathbb{1}(X \geq a)$ を $X \geq a$ のとき1、そうでないとき0とする指示関数とします。
$X \geq 0$ なので、$X \geq a$ のとき $X \geq a \cdot 1 = a \cdot \mathbb{1}(X \geq a)$ が成り立ち、$X < a$ のとき $X \geq 0 \geq a \cdot 0 = a \cdot \mathbb{1}(X \geq a)$ も成り立ちます。
したがって常に $X \geq a \cdot \mathbb{1}(X \geq a)$ です。両辺の期待値をとると、
$$ E[X] \geq a \cdot E[\mathbb{1}(X \geq a)] = a \cdot P(X \geq a) $$
両辺を $a > 0$ で割ると結果が得られます。$\square$
マルコフの不等式の性質
長所: 仮定が最小限（非負性と期待値の存在のみ）であるため、適用範囲が最も広いです。分散が存在しない場合（たとえばパレート分布でテール指数 $\alpha \leq 2$ の場合）でも使えます。
短所: 上限が非常に粗いです。たとえば $E[X] = 1$ のとき、$P(X \geq 10) \leq 0.1$ という上限が得られますが、$X$ が正規分布 $N(1, 1)$ に従うなら実際の確率は $P(X \geq 10) \approx 4 \times 10^{-19}$ と桁違いに小さいです。
タイトネス: マルコフの不等式は「最悪の場合」の上限としてはタイト（達成可能）です。$P(X = a) = E[X]/a$、$P(X = 0) = 1 – E[X]/a$ という2点分布を考えれば、等号が成立します。
マルコフの不等式は基礎的すぎて実用的でないように見えるかもしれませんが、後述するすべての不等式の出発点になる極めて重要な結果です。
次に、分散の情報を使ってより精密な上限を得ましょう。
チェビシェフの不等式
直感
チェビシェフの不等式は「分散が小さければ、期待値から大きく外れる確率は小さい」ことを定量化します。
マルコフの不等式は期待値しか使いませんでしたが、分散の情報も活用すれば、もっと精密な上限が得られるはずです。テストの平均が100点で標準偏差が10点の場合と、標準偏差が50点の場合では、130点以上を取る確率は大きく異なるはずだからです。
定理
$E[X] = \mu$, $\text{Var}(X) = \sigma^2 < \infty$ のとき、任意の $k > 0$ に対して
$$ \begin{equation} P(|X – \mu| \geq k\sigma) \leq \frac{1}{k^2} \end{equation} $$
あるいは同値な形で、任意の $\epsilon > 0$ に対して
$$ P(|X – \mu| \geq \epsilon) \leq \frac{\sigma^2}{\epsilon^2} $$
証明
$(X – \mu)^2$ は非負確率変数なので、マルコフの不等式を適用します。
$$ P(|X – \mu| \geq \epsilon) = P((X – \mu)^2 \geq \epsilon^2) \leq \frac{E[(X-\mu)^2]}{\epsilon^2} = \frac{\sigma^2}{\epsilon^2} $$
$\epsilon = k\sigma$ と置くと $P(|X – \mu| \geq k\sigma) \leq 1/k^2$ が得られます。$\square$
証明のポイントは、マルコフの不等式を $X$ ではなく $(X – \mu)^2$ に適用することです。この「関数を噛ませてからマルコフの不等式を適用する」テクニックは、後述するチェルノフ法の特殊ケースです。
具体的な上限
| $k$（σの倍数） | 上限 $1/k^2$ | 備考 |
|---|---|---|
| 1 | 100% | 自明（常に成立） |
| 2 | 25% | 分布によらず25%以内 |
| 3 | 11.1% | 正規分布なら実際は0.27% |
| 4 | 6.25% | |
| 10 | 1% |
正規分布の場合と比較すると、チェビシェフの上限は非常に保守的です。しかし、分布の形が不明な場合にも使えるという点で強力です。
大数の弱法則への応用
$X_1, \dots, X_n$ が i.i.d. で $E[X_i] = \mu$, $\text{Var}(X_i) = \sigma^2$ のとき、$\bar{X}_n = \frac{1}{n}\sum X_i$ に対して $\text{Var}(\bar{X}_n) = \sigma^2/n$。チェビシェフの不等式より、
$$ P(|\bar{X}_n – \mu| \geq \epsilon) \leq \frac{\sigma^2}{n\epsilon^2} \to 0 \quad (n \to \infty) $$
これが大数の弱法則の最も簡単な証明です。任意の $\epsilon > 0$ に対して $P(|\bar{X}_n – \mu| \geq \epsilon) \to 0$ なので、$\bar{X}_n$ は $\mu$ に確率収束します。
しかし、$1/(n\epsilon^2)$ という減衰は非常に遅い（$n$ の1乗でしか減衰しない）です。たとえば、$P(|\bar{X}_n – \mu| \geq 0.1) \leq 0.01$ を保証するには $n \geq \sigma^2/(0.01 \times 0.01) = 10000\sigma^2$ が必要です。もっと速い減衰が得られないでしょうか。
チェルノフ法 — 指数的不等式の統一的な導出
ヘフディングやベルンシュタインの不等式に進む前に、それらの証明で共通して使われるチェルノフ法（Chernoff bounding method）を紹介しましょう。
基本的なアイデア
チェルノフ法は、マルコフの不等式を指数関数 $e^{sX}$ に適用することで、裾確率の指数的な上限を得る手法です。
任意の $s > 0$ に対して、
$$ P(X \geq a) = P(e^{sX} \geq e^{sa}) \leq \frac{E[e^{sX}]}{e^{sa}} $$
最後の不等式はマルコフの不等式です。$e^{sX}$ は非負なので適用可能です。
この上限は $s$ の値に依存するので、$s$ を最適化して最もタイトな上限を得ます。
$$ P(X \geq a) \leq \inf_{s > 0} e^{-sa} E[e^{sX}] = \inf_{s > 0} e^{-sa + \ln M_X(s)} $$
ここで $M_X(s) = E[e^{sX}]$ はモーメント母関数です。
チェルノフ法のポイントは、マルコフの不等式を $X$ ではなく $e^{sX}$ に適用し、$s$ を最適化するところにあります。指数関数を「噛ませる」ことで、多項式的な上限（チェビシェフ）から指数的な上限への飛躍が可能になります。
チェビシェフの不等式との関係
チェビシェフの不等式は、マルコフの不等式を $(X-\mu)^2$ に適用したものでした。一方、チェルノフ法は $e^{s(X-\mu)}$ に適用します。$e^x$ は $x^2$ よりも速く増大するので、チェルノフ法はチェビシェフの不等式よりも鋭い上限を与えます。
では、チェルノフ法を使って具体的な不等式を導出しましょう。
ヘフディングの不等式
直感
チェビシェフの不等式が $1/n$ のレートで裾確率を抑えるのに対し、ヘフディングの不等式は指数関数のレートで抑えます。代わりに、確率変数が有界であるという追加の仮定を必要とします。
有界性は多くの実用的な状況で成り立ちます。コインの表裏（0か1）、テストの点数（0点から100点）、機械学習の0-1損失（0か1）など、値域が限られた確率変数は多いです。
定理
$X_1, \dots, X_n$ が独立で $a_i \leq X_i \leq b_i$ a.s. のとき、$\bar{X}_n = \frac{1}{n}\sum X_i$ に対して
$$ \begin{equation} P\left(\bar{X}_n – E[\bar{X}_n] \geq t\right) \leq \exp\left(-\frac{2n^2t^2}{\sum_{i=1}^n (b_i – a_i)^2}\right) \end{equation} $$
特に $a_i = a$, $b_i = b$ の場合、両側の不等式として
$$ \begin{equation} P\left(|\bar{X}_n – \mu| \geq t\right) \leq 2\exp\left(-\frac{2nt^2}{(b-a)^2}\right) \end{equation} $$
証明の概略
ヘフディングの不等式の証明はチェルノフ法に基づきます。3つのステップからなります。
ステップ1（チェルノフ法）: 任意の $s > 0$ に対して、
$$ P(\bar{X}_n – \mu \geq t) = P\left(e^{s\sum(X_i – \mu_i)} \geq e^{snt}\right) \leq \frac{E[e^{s\sum(X_i – \mu_i)}]}{e^{snt}} $$
$X_i$ の独立性から期待値は積に分解できます。
$$ E[e^{s\sum(X_i – \mu_i)}] = \prod_{i=1}^n E[e^{s(X_i – \mu_i)}] $$
ステップ2（ヘフディングの補題）: $a \leq X \leq b$, $E[X] = 0$ のとき、
$$ E[e^{sX}] \leq \exp\left(\frac{s^2(b-a)^2}{8}\right) $$
この補題の証明には、$e^{sX}$ の凸性と $X$ の有界性から来る不等式を使います。$X \in [a, b]$ なので $X = (1-\lambda)a + \lambda b$（$\lambda = (X-a)/(b-a)$）と書け、$e^{sX}$ の凸性から $e^{sX} \leq (1-\lambda)e^{sa} + \lambda e^{sb}$ が成り立ちます。期待値を取り、$E[X] = 0$ を使って整理すると、$\ln E[e^{sX}] \leq s^2(b-a)^2/8$ が得られます。
ステップ3（$s$ の最適化）: 各因子にヘフディングの補題を適用すると、
$$ P(\bar{X}_n – \mu \geq t) \leq \exp\left(-snt + \frac{s^2}{8}\sum(b_i-a_i)^2\right) $$
$s$ について微分し、最適な $s^* = 4nt/\sum(b_i-a_i)^2$ を代入すると最終結果が得られます。
チェビシェフとの比較
$n$ 個の i.i.d. 変数（$[0, 1]$ 上）の場合の裾確率の減衰率を比較すると、
- チェビシェフ: $P(|\bar{X}_n – \mu| \geq t) \leq \sigma^2/(nt^2) = O(1/n)$（多項式的減衰）
- ヘフディング: $P(|\bar{X}_n – \mu| \geq t) \leq 2e^{-2nt^2} = O(e^{-cn})$（指数的減衰）
指数的減衰は桁違いに速いです。たとえば $t = 0.1$ のとき、$P(|\bar{X}_n – \mu| \geq 0.1) \leq 0.01$ を保証するためには、チェビシェフでは $n \geq 25\sigma^2/0.01 = 2500\sigma^2$ が必要ですが、ヘフディングでは $n \geq \ln(200)/(2 \times 0.01) \approx 265$ で十分です。
信頼区間への応用
ヘフディングの不等式は、分布形を仮定しないノンパラメトリックな信頼区間の構成に使えます。$P(|\bar{X}_n – \mu| \geq t) \leq 2e^{-2nt^2/(b-a)^2}$ において、右辺を $\alpha$ とおいて $t$ について解くと、
$$ t = (b-a)\sqrt{\frac{\ln(2/\alpha)}{2n}} $$
したがって、少なくとも確率 $1 – \alpha$ で
$$ \mu \in \left[\bar{X}_n – (b-a)\sqrt{\frac{\ln(2/\alpha)}{2n}},\; \bar{X}_n + (b-a)\sqrt{\frac{\ln(2/\alpha)}{2n}}\right] $$
が成り立ちます。これは中心極限定理に基づく信頼区間とは異なり、有限サンプルで厳密に成り立つ保証付きの信頼区間です。
ヘフディングの不等式は有界性しか使いませんが、分散の情報も活用すればさらに精密な上限が得られます。
ベルンシュタインの不等式
直感
ヘフディングの不等式は値域の幅 $(b-a)$ で上限が決まりますが、分散が小さい場合にはもっと鋭い上限が得られるはずです。たとえば、$X \in [0, 1]$ で $\text{Var}(X) = 0.01$ の場合と $\text{Var}(X) = 0.25$ の場合では、極端な値が出る確率は大きく異なるはずです。ベルンシュタインの不等式は、この分散情報を活用します。
定理
$X_1, \dots, X_n$ が独立、$E[X_i] = 0$, $|X_i| \leq M$ a.s. のとき、
$$ \begin{equation} P\left(\sum_{i=1}^n X_i \geq t\right) \leq \exp\left(-\frac{t^2/2}{\sum_{i=1}^n E[X_i^2] + Mt/3}\right) \end{equation} $$
ヘフディングとの違い
ベルンシュタインの不等式の分母には $\sum E[X_i^2]$（分散の情報）が含まれています。分母の2つの項の大小関係により、2つのレジームに分かれます。
-
$t$ が小さい領域（$\sum E[X_i^2]$ が支配的）: 指数の中身は $\approx -t^2/(2\sum E[X_i^2])$ となり、サブガウシアン的な振る舞い（$t^2$ で減衰）を示します。分散が小さいほど集中が強くなります。
-
$t$ が大きい領域（$Mt/3$ が支配的）: 指数の中身は $\approx -3t/(2M)$ となり、サブ指数的な振る舞い（$t$ で線形に減衰）を示します。
ヘフディングの不等式は分散情報を使わないため、常にサブガウシアン的な上限しか与えません。分散が小さい場合、ベルンシュタインはヘフディングよりもはるかに鋭い上限を与えます。
具体的な比較
$X_i \in [0, 1]$, $E[X_i] = 0.5$, $\text{Var}(X_i) = 0.01$（分散が非常に小さい場合）を考えます。$Y_i = X_i – 0.5$ として $|Y_i| \leq 0.5$, $E[Y_i] = 0$, $E[Y_i^2] = 0.01$ です。
$P(\bar{X}_n – 0.5 \geq t)$ の上限として、
- ヘフディング: $\exp(-2nt^2)$ — 分散に無関係
- ベルンシュタイン: $\exp(-nt^2/(2 \cdot 0.01 + t/3))$ — $t$ が小さいとき $\approx \exp(-nt^2/0.02)$
$t = 0.05$ のとき、ヘフディングは $\exp(-0.005n)$ で、ベルンシュタインは $\approx \exp(-0.125n)$。ベルンシュタインの方が25倍速く減衰します。
Pythonによる4つの不等式の比較
import numpy as np
import matplotlib.pyplot as plt
from scipy import stats
np.random.seed(42)
n = 100
p = 0.5 # ベルヌーイ分布のパラメータ
mu = p
sigma2 = p * (1 - p)
fig, axes = plt.subplots(1, 2, figsize=(14, 5.5))
# (a) 裾確率の上限比較
ax = axes[0]
t_range = np.linspace(0.01, 0.45, 200)
# 真の裾確率（二項分布で計算）
exact_prob = [1 - stats.binom.cdf(int(n * (mu + t)), n, p) +
stats.binom.cdf(int(n * (mu - t)) - 1, n, p)
if int(n * (mu + t)) < n else 0
for t in t_range]
exact_prob = np.array(exact_prob)
exact_prob = np.maximum(exact_prob, 1e-15)
# チェビシェフ
chebyshev = sigma2 / (n * t_range**2)
chebyshev = np.minimum(chebyshev, 1)
# ヘフディング
hoeffding = 2 * np.exp(-2 * n * t_range**2)
# ベルンシュタイン
bernstein = 2 * np.exp(-n * t_range**2 / (2 * sigma2 + 2 * t_range / 3))
ax.semilogy(t_range, exact_prob, "k-", linewidth=2.5, label="Exact (Binomial)")
ax.semilogy(t_range, chebyshev, "b--", linewidth=2, label="Chebyshev")
ax.semilogy(t_range, hoeffding, "r-.", linewidth=2, label="Hoeffding")
ax.semilogy(t_range, bernstein, "g:", linewidth=2, label="Bernstein")
ax.set_xlabel(r"$t$", fontsize=12)
ax.set_ylabel(r"$P(|\bar{X}_n - \mu| \geq t)$", fontsize=12)
ax.set_title(f"Tail probability bounds (n={n}, Bernoulli({p}))", fontsize=13)
ax.legend(fontsize=10)
ax.set_ylim(1e-10, 2)
ax.grid(True, alpha=0.3, which="both")
# (b) 信頼区間の幅の比較
ax = axes[1]
n_range = np.arange(10, 501)
alpha = 0.05 # 信頼水準 95%
# チェビシェフ: σ²/(nε²) ≤ α → ε = σ/√(nα)
width_cheb = 2 * np.sqrt(sigma2 / (n_range * alpha))
# ヘフディング: 2exp(-2nt²) ≤ α → t = √(ln(2/α)/(2n))
width_hoeff = 2 * np.sqrt(np.log(2 / alpha) / (2 * n_range))
# 正規近似（CLT）
width_clt = 2 * stats.norm.ppf(1 - alpha/2) * np.sqrt(sigma2 / n_range)
ax.plot(n_range, width_cheb, "b--", linewidth=2, label="Chebyshev")
ax.plot(n_range, width_hoeff, "r-.", linewidth=2, label="Hoeffding")
ax.plot(n_range, width_clt, "k-", linewidth=2, label="CLT (asymptotic)")
ax.set_xlabel("Sample size n", fontsize=12)
ax.set_ylabel("95% confidence interval width", fontsize=12)
ax.set_title("Confidence interval width comparison", fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig("probability_inequalities.png", dpi=150, bbox_inches="tight")
plt.show()
この比較から、以下の知見が得られます。
-
左図: チェビシェフ → ヘフディング → ベルンシュタインの順に上限が精密になる 。チェビシェフの上限（青）はかなり粗く、真の確率（黒）から数桁離れています。ヘフディング（赤）は指数的減衰により大幅に改善され、ベルンシュタイン（緑）は分散情報を活用してさらに精密です。$t = 0.2$ のとき、真の確率は $10^{-4}$ 程度ですが、チェビシェフの上限は1に近く、ヘフディングは $10^{-3}$ 程度、ベルンシュタインは $10^{-3}$ 程度と、精度に大きな差があります。
-
右図: 信頼区間の幅はヘフディングの方がチェビシェフより狭い 。$n = 100$ でチェビシェフの信頼区間幅は約0.65ですが、ヘフディングは約0.27、CLTは約0.20です。ヘフディングの信頼区間はCLTに比べて約35%広いですが、CLTが漸近的な近似であるのに対し、ヘフディングは有限サンプルで厳密な保証を持つ点が大きな利点です。
次に、分散が小さい場合にベルンシュタインの優位性がより顕著になることを確認しましょう。
低分散でのベルンシュタインの優位性
import numpy as np
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 2, figsize=(14, 5.5))
# (a) 分散が異なる場合の比較
ax = axes[0]
n = 100
t_range = np.linspace(0.01, 0.3, 200)
for var_val in [0.01, 0.05, 0.1, 0.25]:
# ベルンシュタイン
bernstein = 2 * np.exp(-n * t_range**2 / (2 * var_val + 2 * t_range / 3))
ax.semilogy(t_range, bernstein, linewidth=2,
label=rf"Bernstein ($\sigma^2 = {var_val}$)")
# ヘフディング（分散に無依存）
hoeffding = 2 * np.exp(-2 * n * t_range**2)
ax.semilogy(t_range, hoeffding, "k--", linewidth=2.5,
label="Hoeffding (any variance)")
ax.set_xlabel(r"$t$", fontsize=12)
ax.set_ylabel("Upper bound", fontsize=12)
ax.set_title(f"Bernstein vs Hoeffding (n={n})", fontsize=13)
ax.legend(fontsize=9)
ax.set_ylim(1e-12, 2)
ax.grid(True, alpha=0.3, which="both")
# (b) 必要サンプルサイズの比較
ax = axes[1]
epsilon = 0.05 # 精度
delta_range = np.logspace(-4, -0.3, 100) # 許容失敗確率
# チェビシェフ
sigma2 = 0.05
n_cheb = sigma2 / (delta_range * epsilon**2)
# ヘフディング
n_hoeff = np.log(2 / delta_range) / (2 * epsilon**2)
# ベルンシュタイン（近似）
n_bern = (2 * sigma2 * np.log(2 / delta_range) +
2/3 * epsilon * np.log(2 / delta_range)) / epsilon**2
ax.loglog(delta_range, n_cheb, "b--", linewidth=2, label="Chebyshev")
ax.loglog(delta_range, n_hoeff, "r-.", linewidth=2, label="Hoeffding")
ax.loglog(delta_range, n_bern, "g:", linewidth=2, label="Bernstein")
ax.set_xlabel(r"Failure probability $\delta$", fontsize=12)
ax.set_ylabel("Required sample size n", fontsize=12)
ax.set_title(rf"Sample complexity ($\epsilon={epsilon}$, $\sigma^2={sigma2}$)", fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3, which="both")
plt.tight_layout()
plt.savefig("bernstein_advantage.png", dpi=150, bbox_inches="tight")
plt.show()
この分析から、以下のことが明らかになります。
-
左図: 分散が小さいほどベルンシュタインの上限がヘフディングよりも鋭くなる 。$\sigma^2 = 0.01$ のとき、ベルンシュタインの上限はヘフディングよりも数桁小さいです。分散が$\sigma^2 = 0.25$（最大値）に近い場合は両者の差はわずかです。分散情報を活用できるベルンシュタインの利点は、まさに低分散の状況で発揮されるのです。
-
右図: 所与の精度 $\epsilon$ と信頼水準 $1-\delta$ を達成するために必要なサンプルサイズ 。ベルンシュタインが最も少ないサンプル数で済み、チェビシェフが最も多くのサンプルを要求します。$\delta = 0.01$（99%信頼）のとき、チェビシェフは約20,000サンプルを要求するのに対し、ヘフディングは約2,000、ベルンシュタインは約1,000で済みます。
機械学習への応用: PAC学習
ヘフディングの不等式とPAC学習
確率の不等式は機械学習理論、特にPAC学習（Probably Approximately Correct learning）の理論的基盤です。
訓練データの経験リスク $\hat{R}(h) = \frac{1}{n}\sum_{i=1}^n \ell(h(x_i), y_i)$ と真のリスク $R(h) = E[\ell(h(X), Y)]$ の差を評価したいとします。損失関数 $\ell$ が $[0, 1]$ の値を取るとき、ヘフディングの不等式より、
$$ P(|R(h) – \hat{R}(h)| \geq \epsilon) \leq 2\exp(-2n\epsilon^2) $$
有限個の仮説 $h_1, \dots, h_M$ を考える場合、合併上限（union bound）を使って、
$$ P\left(\exists h \in \mathcal{H}: |R(h) – \hat{R}(h)| \geq \epsilon\right) \leq 2M\exp(-2n\epsilon^2) $$
右辺を $\delta$ とおくと、少なくとも確率 $1-\delta$ で、すべての $h \in \mathcal{H}$ に対して
$$ |R(h) – \hat{R}(h)| \leq \sqrt{\frac{\ln(2M/\delta)}{2n}} $$
が成り立ちます。これが有限仮説空間に対するPAC学習の基本的な汎化界です。必要サンプルサイズは $n = O(\ln(M/\delta)/\epsilon^2)$ であり、仮説空間の大きさ $M$ の対数にしか依存しません。
UCBアルゴリズムとヘフディングの不等式
多腕バンディット問題のUCB（Upper Confidence Bound）アルゴリズムは、ヘフディングの不等式を直接利用しています。各腕 $i$ の報酬の平均を $\hat{\mu}_i$ とし、ヘフディングの信頼区間 $\hat{\mu}_i + \sqrt{\frac{2\ln t}{n_i}}$ を上限として使うことで、探索と活用のバランスを取ります。
不等式間の関係のまとめ
4つの不等式の関係を整理しましょう。
| 不等式 | 仮定 | 上限の型 | 減衰率 | 精度 |
|---|---|---|---|---|
| マルコフ | $X \geq 0$, $E[X] < \infty$ | $E[X]/a$ | — | 最も粗い |
| チェビシェフ | $\text{Var}(X) < \infty$ | $\sigma^2/\epsilon^2$ | $O(1/n)$ | 粗い |
| ヘフディング | 独立, 有界 | $e^{-2nt^2/(b-a)^2}$ | $O(e^{-cn})$ | 精密 |
| ベルンシュタイン | 独立, 有界 | $e^{-t^2/(2\sigma^2 + Mt/3)}$ | $O(e^{-cn})$ | 最も精密 |
仮定が強くなるほど、より精密な上限が得られます。実用的には、確率変数が有界ならヘフディングまたはベルンシュタインを使い、分散の情報があるならベルンシュタインを優先するのが良い選択です。
まとめ
本記事では、確率の4つの基本不等式を証明し、比較しました。
- マルコフ: $P(X \geq a) \leq E[X]/a$ — 最も基本的で、仮定は非負性のみ。他のすべての不等式の出発点
- チェビシェフ: $P(|X-\mu| \geq \epsilon) \leq \sigma^2/\epsilon^2$ — 分散を使った改善、多項式的減衰（$O(1/n)$）。大数の弱法則の証明に使用
- ヘフディング: $P(|\bar{X}-\mu| \geq t) \leq 2e^{-2nt^2/(b-a)^2}$ — 有界変数に対する指数的減衰。PAC学習理論とUCBアルゴリズムの基盤
- ベルンシュタイン: 分散情報を活用してヘフディングをさらに精密化。低分散の場合に特に有効
- チェルノフ法: 指数関数を噛ませてマルコフの不等式を適用し、$s$ を最適化する統一的な手法。ヘフディングとベルンシュタインの証明の基礎
次のステップとして、以下の記事も参考にしてください。
- 大数の法則 — チェビシェフの不等式による弱法則の証明
- ボレル・カンテリの補題 — 不等式と組み合わせた概収束の証明
- 確率変数の収束 — 不等式が収束の証明にどう使われるか
- PAC学習 — 機械学習理論におけるヘフディングの不等式の応用