ヘフディングの不等式（Hoeffding’s inequality）をグラフで【※制作途中】

ヘフディングの不等式（Hoeffding’s inequality）は、マルコフの不等式など集中不等式（concentration inequality）の一種です。

ヘフディングの不等式とは
便利さと歴史、利用例
ヘフディング不等式とグラフ

ヘフディングの不等式とは

独立な確率変数 $X_1\,,\cdots\,,X_n$ があり、それぞれが区間 $[a_i,b_i]$ の中に必ず収まるとします。このとき、標本平均 $\bar{X}_n=\frac{1}{n}\Sigma_i X_i$ が、その期待値 $\mu=E[\bar{X}_n]$ から $\epsilon$ 以上離れてしまう確率は、以下の式で抑えられます。

\begin{align}
P(\Abs{\bar{X}_n−\mu}\geq \epsilon)\leq 2\exp\Pare{− \dfrac{2n^2\epsilon^2}{\Sigma_i^n (b_i−a_i)^2}}\,.
\end{align}

特に、全ての確率変数が同じ区間 $[0,1]$ に収まる場合（コイン投げなど）は、よりシンプルな形になります。

\begin{align}
P(\Abs{\bar{X}_n−\mu}\geq \epsilon)\leq 2e^{-2n\epsilon^2}\,.
\end{align}

便利さと歴史、利用例

便利さ: この不等式の便利な点は、分布の具体的な形や分散を知らなくても使えることです。確率変数が独立で、値が特定の範囲に収まることさえわかっていれば、サンプルサイズ n と許容誤差 ϵ から、逸脱確率の上限を計算できます。この一般性と単純さが最大の利点です。
歴史的経緯: 1963年にワシリー・ヘフディング (Wassily Hoeffding) によって発表されました。セルゲイ・ベルンシュタイン (Sergei Bernstein) らによる有界な確率変数の和に関する研究の流れを汲み、集中不等式と呼ばれる分野の foundational な結果の一つとなっています。
現在の利用例:
- 統計学: 信頼区間の構成、仮説検定など。
- 機械学習: 学習アルゴリズムの汎化誤差（未知データに対する性能）の評価（PAC学習理論など）。
- ランダム化アルゴリズム: アルゴリズムの性能が確率的にどの範囲に収まるかの解析。
- その他、確率的な振る舞いをするシステムの解析全般。

ヘフディング不等式とグラフ

ベルヌーイ分布の擬似乱数が真の平均に集中していく様子

このグラフは、サンプルサイズ n (横軸) に対し、確率 1−δ (例: 95%) で標本平均（黒点）が収まるとヘフディングが保証する範囲（水色領域、赤/青破線）を示します。

$n$ が増えると、保証される範囲は狭まり、標本平均（黒点）は真の平均（オレンジ線）に近づきます。
黒点が水色領域内にほぼ収まることで、不等式が成り立つ様子がわかります。

ヘフディング不等式の成り立つ様子

(グラフ2: ベルヌーイ(0.5), ε=0.1に対する確率のグラフを想定)

このグラフは、標本平均が真の平均から固定の誤差 $\epsilon=0.1$ 以上離れる確率（縦軸、対数）を $n$ (横軸) に対して示しています。

$n$ が増えると、経験的な確率（青点）もヘフディングの上限（赤点）も指数的に減少します（対数グラフ上で直線的に下降）。
青点は常に赤点の下にあり、不等式の正しさが確認できます。同時に、赤点と青点のギャップは、ヘフディングが安全側（緩め）の評価を与えることを示唆します。

他の手法との比較

ヘフディングの不等式を他の手法と比較してみましょう。

手法/定理	主な仮定	結果の種類	評価の厳しさ（タイトさ）	特徴・使い所
ヘフディング (Hoeffding)	独立、有界	確率の上限 (有限$n$)	緩いが汎用的。	単純・汎用性高。有界のみ仮定。
バーンスタイン (Bernstein)	独立、有界、分散が既知か有界	確率の上限 (有限$n$)	分散が小さいとヘフディングよりタイト。	分散情報を利用して改善。
チェルノフ (Chernoff)	独立、積率母関数が存在	最適化された上限 (有限$n$)	特定の分布（和）に対してタイト。	特定の分布に特化。ベルヌーイ和などに強力。
中心極限定理 (CLT)	独立同分布 (i.i.d.)、分散が有限かつ正	分布形状の漸近近似 ($n\to\infty$)	有限の $n$ での誤差については不明。漸近的に正確。	独立なものの平均（や和）を取ると、元の分布が何であれ、結果は正規分布に。