チェルノフ行き

Exponentially decreasing bounds on tail distributions of random variables

確率論において、チェルノフ境界とは、確率変数のモーメント生成関数に基づく、指数関数的に減少する裾の上限である。このような指数境界の最小値はチェルノフ境界またはチェルノフ・クラマー境界を形成し、これは指数関数よりも速く減少する可能性がある（例えば、ガウス分布以下）。^{[1] [2]これは、}ベルヌーイ確率変数の和など、独立確率変数の和に特に有用である。^{[3] [4]}

この境界は、1952年の論文でこの方法を説明したヘルマン・チェルノフにちなんで名付けられることが多いが、 ^[5]チェルノフ自身はヘルマン・ルービンに帰属させている。^[6] 1938年にハラルド・クラメールは、現在クラメールの定理として知られているほぼ同じ概念を発表した。

これは、マルコフの不等式やチェビシェフの不等式といった、裾の減衰に関してべき乗則的な境界しか与えない一次モーメントまたは二次モーメントに基づく裾の境界よりも、より厳しい境界である。しかし、和に適用する場合、チェルノフ境界は確率変数が独立であることを要求するが、これはマルコフの不等式やチェビシェフの不等式では要求されない条件である。

チェルノフ上界は、ベルンシュタイン不等式と関連しています。また、ホエフディングの不等式、ベネットの不等式、マクダーミドの不等式を証明するためにも用いられます。

一般的なチェルノフ境界

カイ二乗確率変数の両側チェルノフ境界

確率変数に対する一般的なチェルノフ境界は、マルコフ不等式を に適用することで得られる（そのため、指数マルコフ境界または指数モーメント境界と呼ばれることもある）。 が正の値の場合、これは の右裾におけるモーメント生成関数を用いた境界を与える。 ${\displaystyle X}$ ${\displaystyle e^{tX}}$ ${\displaystyle t}$ ${\displaystyle X}$ ${\displaystyle M(t)=\operatorname {E} (e^{tX})}$

${\displaystyle \operatorname {P} \left(X\geq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t>0)}$

この境界はすべての正の に対して成り立つので、最小値を取ることができます。 ${\displaystyle t}$

${\displaystyle \operatorname {P} \left(X\geq a\right)\leq \inf _{t>0}M(t)e^{-ta}}$

同じ分析を負の値で実行すると、左裾に同様の境界が得られます。 ${\displaystyle t}$

${\displaystyle \operatorname {P} \left(X\leq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t<0)}$

そして

${\displaystyle \operatorname {P} \left(X\leq a\right)\leq \inf _{t<0}M(t)e^{-ta}}$

量は期待値、あるいはそれと同等の として表すことができます。 ${\displaystyle M(t)e^{-ta}}$ ${\displaystyle \operatorname {E} (e^{tX})e^{-ta}}$ ${\displaystyle \operatorname {E} (e^{t(X-a)})}$

プロパティ

指数関数は凸関数であるため、ジェンセンの不等式 により となる。したがって、 のとき、右側の裾の境界は1以上となり、したがって自明となる。同様に、 のとき、左側の境界は自明となる。したがって、2つの最小値を組み合わせて、両側チェルノフ境界を定義できる。これは、（中央値ではなく平均値で折り畳まれた）の折り畳まれた累積分布関数の上限となる。 ${\displaystyle \operatorname {E} (e^{tX})\geq e^{t\operatorname {E} (X)}}$ ${\displaystyle a\leq \operatorname {E} (X)}$ ${\displaystyle a\geq \operatorname {E} (X)}$ $${\displaystyle C(a)=\inf _{t}M(t)e^{-ta}}$$ ${\displaystyle X}$

両側チェルノフ境界の対数は、速度関数（またはクラメール変換）として知られています。これは、キュムラント生成関数 のルジャンドル・フェンシェル変換または凸共役に相当し、次のように定義されます。モーメント生成関数は対数凸 であるため、凸共役の性質により、チェルノフ境界は対数凹でなければなりません。チェルノフ境界は平均 で最大値に達し、平行移動に対して不変です。 ${\displaystyle I=-\log C}$ ${\displaystyle K=\log M}$ $${\displaystyle I(a)=\sup _{t}at-K(t)}$$ ${\displaystyle C(\operatorname {E} (X))=1}$ ${\textstyle C_{X+k}(a)=C_{X}(a-k)}$

チェルノフ境界は、 が単一の集中質量（退化分布）である場合に限り、厳密である。この境界は、有界確率変数の極限値またはその極限値を超える場合にのみ厳密であり、この場合、無限大に対して下限値に達する。非有界確率変数の場合、この境界はどこでも厳密ではないが、指数関数以下の因子までは漸近的に厳密である（「指数関数的に厳密」）。^[要出典]個々のモーメントは、解析の複雑さを増す代わりに、より厳密な境界値を提供することができる。^[7] ${\displaystyle X}$ ${\displaystyle t}$

実際には、正確なチェルノフ境界は扱いにくく、解析的に評価することが難しい場合があります。その場合、モーメント（またはキュムラント）生成関数の適切な上限を代わりに使用できます（例：サブガウス チェルノフ境界を与えるサブ放物線 CGF）。

一般的な分布に対する正確な速度関数とチェルノフ境界

分布	${\displaystyle \operatorname {E} (X)}$	${\displaystyle K(t)}$	${\displaystyle I(a)}$	${\displaystyle C(a)}$
正規分布	${\displaystyle 0}$	${\displaystyle {\frac {1}{2}}\sigma ^{2}t^{2}}$	${\displaystyle {\frac {1}{2}}\left({\frac {a}{\sigma }}\right)^{2}}$	${\displaystyle \exp \left({-{\frac {a^{2}}{2\sigma ^{2}}}}\right)}$
ベルヌーイ分布（詳細は下記）	${\displaystyle p}$	${\displaystyle \ln \left(1-p+pe^{t}\right)}$	${\displaystyle D_{KL}(a\parallel p)}$	${\displaystyle \left({\frac {p}{a}}\right)^{a}{\left({\frac {1-p}{1-a}}\right)}^{1-a}}$
標準ベルヌーイ （Hは2進エントロピー関数）	${\displaystyle {\frac {1}{2}}}$	${\displaystyle \ln \left(1+e^{t}\right)-\ln(2)}$	${\displaystyle \ln(2)-H(a)}$	${\displaystyle {\frac {1}{2}}a^{-a}(1-a)^{-(1-a)}}$
ラデマッハ分布	${\displaystyle 0}$	${\displaystyle \ln \cosh(t)}$	${\displaystyle \ln(2)-H\left({\frac {1+a}{2}}\right)}$	${\displaystyle {\sqrt {(1+a)^{-1-a}(1-a)^{-1+a}}}}$
ガンマ分布	${\displaystyle \theta k}$	${\displaystyle -k\ln(1-\theta t)}$	${\displaystyle -k\ln {\frac {a}{\theta k}}-k+{\frac {a}{\theta }}}$	${\displaystyle \left({\frac {a}{\theta k}}\right)^{k}e^{k-a/\theta }}$
カイ二乗分布	${\displaystyle k}$	${\displaystyle -{\frac {k}{2}}\ln(1-2t)}$	${\displaystyle {\frac {k}{2}}\left({\frac {a}{k}}-1-\ln {\frac {a}{k}}\right)}$[8]	${\displaystyle \left({\frac {a}{k}}\right)^{k/2}e^{k/2-a/2}}$
ポアソン分布	${\displaystyle \lambda }$	${\displaystyle \lambda (e^{t}-1)}$	${\displaystyle a\ln(a/\lambda )-a+\lambda }$	${\displaystyle (a/\lambda )^{-a}e^{a-\lambda }}$

MGFからの下からの境界

モーメント生成関数のみを用いると、ペイリー・ジグムント不等式を に適用することで裾確率の下側からの上界が得られ、次の式が得られます。 （ が負の場合、左裾の上界が得られます。）しかし、チェルノフの上界とは異なり、この結果は指数的に厳密ではありません。 ${\displaystyle e^{tX}}$ $${\displaystyle \operatorname {P} \left(X>a\right)\geq \sup _{t>0\land M(t)\geq e^{ta}}\left(1-{\frac {e^{ta}}{M(t)}}\right)^{2}{\frac {M(t)^{2}}{M(2t)}}}$$ ${\displaystyle t}$

テオドソプロス^[9]は指数傾斜法を用いて下からより厳密なMGFベースの境界を構築した。

特定の分布（二項分布など）の場合、チェルノフ境界と同じ指数順序の下からの境界が利用できる場合がよくあります。

独立確率変数の合計

X がn 個の独立した確率変数X ₁、...、X _{n の}合計である場合、 Xのモーメント生成関数は個々のモーメント生成関数の積となり、次のようになります。

${\displaystyle \Pr(X\geq a)\leq \inf _{t>0}{\frac {\operatorname {E} \left[\prod _{i}e^{t\cdot X_{i}}\right]}{e^{t\cdot a}}}=\inf _{t>0}e^{-t\cdot a}\prod _{i}\operatorname {E} \left[e^{t\cdot X_{i}}\right].}$

1

そして：

${\displaystyle \Pr(X\leq a)\leq \inf _{t<0}e^{-ta}\prod _{i}\operatorname {E} \left[e^{tX_{i}}\right]}$

特定のチェルノフ境界は、ランダム変数の特定のインスタンスのモーメント生成関数を計算することによって達成されます。 ${\displaystyle \operatorname {E} \left[e^{-t\cdot X_{i}}\right]}$ ${\displaystyle X_{i}}$

確率変数も同一分布に従う場合（iid）、和のチェルノフ境界は、単変数チェルノフ境界の単純な再スケーリングに帰着する。つまり、n個のiid変数の平均のチェルノフ境界は、単変数チェルノフ境界のn乗に等しい（クラメールの定理を参照）。

独立した有界確率変数の和

チェルノフ境界は、分布に関わらず、独立かつ有界な確率変数の一般的な和にも適用できます。これはヘフディングの不等式として知られています。証明は他のチェルノフ境界と同様のアプローチに従いますが、ヘフディングの補題をモーメント生成関数に適用します（ヘフディングの不等式を参照）。

ヘフディングの不等式。X 1 _, ..., X _{n が}[a,b]の範囲の値を取る独立確率変数であるとする。Xをそれらの和とし、μ = E[ X ]をその和の期待値とする。すると、任意のに対して、 ${\displaystyle t>0}$

${\displaystyle \Pr(X\leq \mu -t)<e^{-2t^{2}/(n(b-a)^{2})},}$

${\displaystyle \Pr(X\geq \mu +t)<e^{-2t^{2}/(n(b-a)^{2})}.}$

独立したベルヌーイ確率変数の和

以下のセクションにおけるベルヌーイ確率変数の境界は、確率pが1に等しいベルヌーイ確率変数に対して、 ${\displaystyle X_{i}}$

${\displaystyle \operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p)e^{0}+pe^{t}=1+p(e^{t}-1)\leq e^{p(e^{t}-1)}.}$

チェルノフ境界には、元の加法形式（絶対誤差に境界を与える）や、より実用的な乗法形式（平均に対する誤差に境界を与える）など、さまざまな種類があります。

乗法形式（相対誤差）

乗法的チェルノフ境界。X 1 _, ..., X _{n が}{0, 1}の範囲の値をとる独立確率変数であるとする。Xをそれらの和とし、μ = E[ X ]をその和の期待値とする。すると、任意のδ > 0に対して、

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq \left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right)^{\mu }.}$

同様の証明戦略を用いて、0 < δ < 1のとき、

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq \left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right)^{\mu }.}$

上記の式は実際には扱いにくいことが多いため、対数不等式のリストから得られる不等式から導かれる、より緩いがより便利な境界^[10]がよく使用されます。 ${\displaystyle \textstyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )}$

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq e^{-\delta ^{2}\mu /(2+\delta )},\qquad 0\leq \delta ,}$

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq e^{-\delta ^{2}\mu /2},\qquad 0\leq \delta \leq 1,}$

${\displaystyle \Pr(|X-\mu |\geq \delta \mu )\leq 2e^{-\delta ^{2}\mu /3},\qquad 0\leq \delta \leq 1.}$

の境界は自明であることに注意してください。 ${\displaystyle \delta =0}$

さらに、ランバートW関数のテイラー展開に基づいて、^[11]

${\displaystyle \Pr(X\geq R)\leq 2^{-xR},\qquad x>0,\ \mu >0,\ R\geq (2^{x}e-1)\mu .}$

加法形式（絶対誤差）

次の定理はワシリー・ヘフディング^[12]によるもので、チェルノフ・ヘフディングの定理と呼ばれています。

チェルノフ・ヘフディング定理。X ₁ , ..., X _{n が}{0, 1}の範囲の値をとるiid確率変数であるとする。p = E[ X ₁ ]、ε > 0とする。

${\displaystyle {\begin{aligned}\Pr \left({\frac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq \left(\left({\frac {p}{p+\varepsilon }}\right)^{p+\varepsilon }{\left({\frac {1-p}{1-p-\varepsilon }}\right)}^{1-p-\varepsilon }\right)^{n}&=e^{-D(p+\varepsilon \parallel p)n}\\\Pr \left({\frac {1}{n}}\sum X_{i}\leq p-\varepsilon \right)\leq \left(\left({\frac {p}{p-\varepsilon }}\right)^{p-\varepsilon }{\left({\frac {1-p}{1-p+\varepsilon }}\right)}^{1-p+\varepsilon }\right)^{n}&=e^{-D(p-\varepsilon \parallel p)n}\end{aligned}}}$

どこ

${\displaystyle D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right)}$

は、それぞれパラメータxとyを持つベルヌーイ分布の確率変数間のカルバック・ライブラー距離である。p ≥ ⁠1/2⁠、つまり​ ${\displaystyle D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}}$

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}>p+x\right)\leq \exp \left(-{\frac {x^{2}n}{2p(1-p)}}\right).}$

より単純な境界は、 D ( p + ε || p ) ≥ 2 ε ²を用いて定理を緩和することによって得られる。これは、D ( p + ε || p )の凸性と、

${\displaystyle {\frac {d^{2}}{d\varepsilon ^{2}}}D(p+\varepsilon \parallel p)={\frac {1}{(p+\varepsilon )(1-p-\varepsilon )}}\geq 4={\frac {d^{2}}{d\varepsilon ^{2}}}(2\varepsilon ^{2}).}$

この結果は、ヘフディングの不等式の特別な場合である。

${\displaystyle {\begin{aligned}D((1+x)p\parallel p)\geq {\frac {1}{4}}x^{2}p,&&&{-{\tfrac {1}{2}}}\leq x\leq {\tfrac {1}{2}},\\[6pt]D(x\parallel y)\geq {\frac {3(x-y)^{2}}{2(2y+x)}},\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2y}},&&&x\leq y,\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2x}},&&&x\geq y\end{aligned}}}$

p < ⁠の場合に強い1/8⁠なども使用されます。

アプリケーション

チェルノフ境界は、スパースネットワークにおけるセットバランスやパケット ルーティングに非常に役立ちます。

集合バランス問題は、統計実験の設計時に発生します。通常、統計実験の設計においては、実験参加者の各特性を与えられた上で、各特性が2つのグループ間で可能な限りバランスが取れるように、参加者を2つの互いに素なグループに分割する方法を知る必要があります。^[13]

チェルノフ境界は、疎なネットワークでパケットをルーティングする際にネットワークの輻輳を軽減する順列ルーティング問題の厳密な境界を得るためにも使用されます。^[13]

チェルノフ境界は計算学習理論において、学習アルゴリズムがおそらく近似的に正しいことを証明するために用いられます。つまり、十分に大きな訓練データセットに対しては、高い確率でアルゴリズムの誤差は小さいということを証明するために用いられます。^[14]

チェルノフ境界は、ランダム化を用いて摂動空間を探索することにより、アプリケーション／アルゴリズムの「堅牢性レベル」を評価するために効果的に用いることができる。^[15]チェルノフ境界を用いることで、強い（そして概して非現実的な）小さな摂動仮説（摂動の規模が小さい）を放棄することができる。そして、この堅牢性レベルは、特定のアルゴリズムの選択、ハードウェア実装、あるいは構造パラメータが不確実性の影響を受けるソリューションの妥当性を検証または拒否するために用いることができる。

チェルノフ境界の単純かつ一般的な用途は、ランダム化アルゴリズムの「ブースティング」である。確率p > 1/2で目的の答えとなる推測を出力するアルゴリズムがある場合、そのアルゴリズムをn /2回以上実行し、 n /2回以上実行した時に出力される推測を出力することで、より高い成功率を得ることができる。（このような推測は複数回発生することはない。）これらのアルゴリズム実行が独立していると仮定すると、n /2回以上の推測が正しい確率は、確率pで1となる独立したベルヌーイ確率変数X _kの合計がn /2を超える確率に等しい。これは、乗法チェルノフ境界（シンクレアの授業ノートの系13.3、μ = np）によって少なくとも証明できる。 ^[16] ${\displaystyle n=\log(1/\delta )2p/(p-1/2)^{2}}$ ${\displaystyle 1-\delta }$

${\displaystyle \Pr \left[X>{n \over 2}\right]\geq 1-e^{-n\left(p-1/2\right)^{2}/(2p)}\geq 1-\delta }$

行列チェルノフ境界

ルドルフ・アールスヴェーデとアンドレアス・ウィンターは、行列値確率変数に対するチェルノフ境界を導入した。^[17]この不等式の次のバージョンは、トロップの研究で見ることができる。^[18]

M ₁ , ..., M _tを、および となるような独立な行列値確率変数とする。行列 の演算子ノルムを と表記する。がすべての に対してほぼ確実に成立する場合、任意のε > 0に対して成立する。 ${\displaystyle M_{i}\in \mathbb {C} ^{d_{1}\times d_{2}}}$ ${\displaystyle \mathbb {E} [M_{i}]=0}$ ${\displaystyle \lVert M\rVert }$ ${\displaystyle M}$ ${\displaystyle \lVert M_{i}\rVert \leq \gamma }$ ${\displaystyle i\in \{1,\ldots ,t\}}$

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}\right\|>\varepsilon \right)\leq (d_{1}+d_{2})\exp \left(-{\frac {3\varepsilon ^{2}t}{8\gamma ^{2}}}\right).}$

0からの偏差がεによって高い確率で制限されると結論付けるためには、の対数に比例するサンプル数を選択する必要があることに注意してください。一般に、残念ながら への依存は 避けられません。例えば、 次元の対角ランダム符号行列を考えてみましょう。t個の独立したサンプルの合計の演算子ノルムは、長さtのd個の独立したランダムウォークの最大偏差とまったく同じです。一定確率で最大偏差の固定された境界を達成するためには、このシナリオではtがdとともに対数的に増加する必要があることは容易にわかります。^[19] ${\displaystyle t}$ ${\displaystyle d_{1}+d_{2}}$ ${\displaystyle \log(\min(d_{1},d_{2}))}$ ${\displaystyle d\times d}$

次元への依存を避けるために、 M のランクが低いと仮定すると、次の定理が得られます。

次元に依存しない定理

0 < ε < 1で、M をランダム対称実数行列とし、ほぼ確実に とする。Mの台上の各要素の階数は最大でもrであるとする。 ${\displaystyle \|\operatorname {E} [M]\|\leq 1}$ ${\displaystyle \|M\|\leq \gamma }$

${\displaystyle t=\Omega \left({\frac {\gamma \log(\gamma /\varepsilon ^{2})}{\varepsilon ^{2}}}\right).}$

ほぼ確実に成り立つならば、 ${\displaystyle r\leq t}$

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\operatorname {E} [M]\right\|>\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t)}}}$

ここで、M ₁、...、M _tはMのiidコピーです。

サンプリングバリアント

チェルノフの限界値の次の変形は、母集団内の多数派が標本内の少数派になる確率、あるいはその逆の確率を制限するために使用できます。^[20]

一般集団Aと部分集団B  ⊆  Aがあるとします。部分集団の相対的な大きさ (| B |/| A |) を rで表します。

整数kと、サイズkのランダム標本S  ⊂  Aを選んだとします。標本内の部分母集団の相対的なサイズ (| B ∩ S |/| S |) をr _Sで表します。

そして、すべての分数d∈  [0,1]について：

${\displaystyle \Pr \left(r_{S}<(1-d)\cdot r\right)<\exp \left(-r\cdot d^{2}\cdot {\frac {k}{2}}\right)}$

特に、BがAで多数派（すなわちr > 0.5）である場合、 BがSで多数派を維持する 確率（r _S  > 0.5）は次のように制限できる：d  = 1 − 1 /（2 r）：^[21]

${\displaystyle \Pr \left(r_{S}>0.5\right)>1-\exp \left(-r\cdot \left(1-{\frac {1}{2r}}\right)^{2}\cdot {\frac {k}{2}}\right)}$

もちろん、この境界値は全く厳密ではありません。例えば、r  = 0.5 の場合には、Prob > 0 という自明な境界値が得られます。

証明

乗法形式

乗法チェルノフ境界の条件に従って、X ₁、...、X _nを独立したベルヌーイ確率変数とし、その和がXで、それぞれの確率が1になる確率はp _iであるとします。ベルヌーイ変数の場合:

${\displaystyle \operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p_{i})e^{0}+p_{i}e^{t}=1+p_{i}(e^{t}-1)\leq e^{p_{i}(e^{t}-1)}}$

そこで、任意の とをとして( 1 )を用いると、 ${\displaystyle a=(1+\delta )\mu }$ ${\displaystyle \delta >0}$ ${\displaystyle \mu =\operatorname {E} [X]=\textstyle \sum _{i=1}^{n}p_{i}}$

${\displaystyle {\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \inf _{t\geq 0}\exp(-t(1+\delta )\mu )\prod _{i=1}^{n}\operatorname {E} [\exp(tX_{i})]\\[4pt]&\leq \inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +\sum _{i=1}^{n}p_{i}(e^{t}-1){\Big )}\\[4pt]&=\inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}.\end{aligned}}}$

t = log(1 + δ )と置くだけで、 δ > 0のときにt > 0となり、代入して次のように求めることができる。

${\displaystyle \exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}={\frac {\exp((1+\delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }.}$

これは望ましい結果であることを証明します。

チェルノフ・ヘフディング定理（加法形式）

q = p + εとする。 ( 1 )においてa = nqとすると、次式を得る。

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}\geq q\right)\leq \inf _{t>0}{\frac {E\left[\prod e^{tX_{i}}\right]}{e^{tnq}}}=\inf _{t>0}\left({\frac {E\left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}.}$

ここで、Pr( X _i = 1) = p、 Pr( X _i = 0) = 1 − pとすると、

${\displaystyle \left({\frac {\operatorname {E} \left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}=\left({\frac {pe^{t}+(1-p)}{e^{tq}}}\right)^{n}=\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)^{n}.}$

したがって、微積分を使って簡単に最小値を計算することが可能です。

${\displaystyle {\frac {d}{dt}}\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)=(1-q)pe^{(1-q)t}-q(1-p)e^{-qt}}$

方程式をゼロにして解くと、

${\displaystyle {\begin{aligned}(1-q)pe^{(1-q)t}&=q(1-p)e^{-qt}\\(1-q)pe^{t}&=q(1-p)\end{aligned}}}$

となることによって

${\displaystyle e^{t}={\frac {(1-p)q}{(1-q)p}}.}$

したがって、

${\displaystyle t=\log \left({\frac {(1-p)q}{(1-q)p}}\right).}$

q = p + ε > pなので、 t > 0となり、 tについての上界が満たされます。 tについて解いた後、上の式に代入すると、

${\displaystyle {\begin{aligned}\log \left(pe^{(1-q)t}+(1-p)e^{-qt}\right)&=\log \left(e^{-qt}(1-p+pe^{t})\right)\\&=\log \left(e^{-q\log \left({\frac {(1-p)q}{(1-q)p}}\right)}\right)+\log \left(1-p+pe^{\log \left({\frac {1-p}{1-q}}\right)}e^{\log {\frac {q}{p}}}\right)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left(1-p+p\left({\frac {1-p}{1-q}}\right){\frac {q}{p}}\right)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left({\frac {(1-p)(1-q)}{1-q}}+{\frac {(1-p)q}{1-q}}\right)\\&=-q\log {\frac {q}{p}}+\left(-q\log {\frac {1-p}{1-q}}+\log {\frac {1-p}{1-q}}\right)\\&=-q\log {\frac {q}{p}}+(1-q)\log {\frac {1-p}{1-q}}\\&=-D(q\parallel p).\end{aligned}}}$

我々は今、望んでいた結果を得ました。

${\displaystyle \Pr \left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq e^{-D(p+\varepsilon \parallel p)n}.}$

対称的なケースの証明を完了するには、ランダム変数Y _i = 1 − X _iを定義し、同じ証明を適用して、それを境界に代入するだけです。

参照

• バーンスタイン不等式
• 集中不等式− ランダム変数の裾の境界の要約。
• クラメールの定理
• エントロピー値が危険にさらされている
• ホーフディングの不等式
• 行列チェルノフ境界
• モーメント生成関数

参考文献

1. ブシュロン、ステファン (2013).集中不等式：独立性の非漸近理論. ガボール・ルゴシ、パスカル・マサート. オックスフォード: オックスフォード大学出版局. p. 21. ISBN 978-0-19-953525-5. OCLC  837517674。
2. Wainwright, M. (2015年1月22日). 「Basic tail and concentration bounds」（PDF） . 2016年5月8日時点のオリジナルよりアーカイブ（PDF） 。
3. Vershynin, Roman (2018).高次元確率：データサイエンスへの応用入門. ケンブリッジ, イギリス. p. 19. ISBN 978-1-108-41519-4. OCLC  1029247498.{{cite book}}: CS1 maint: location missing publisher (link)
4. Tropp, Joel A. (2015-05-26). 「行列集中不等式入門」.機械学習の基礎と動向. 8 ( 1–2 ): 60. arXiv : 1501.01571 . doi :10.1561/2200000048. ISSN  1935-8237. S2CID  5679583.
5. チェルノフ、ハーマン (1952). 「観測値の合計に基づく仮説検定の漸近的効率性の尺度」.数理統計年報. 23 (4): 493– 507. doi : 10.1214/aoms/1177729330 . ISSN  0003-4851. JSTOR  2236576.
6. チェルノフ、ハーマン (2014). 「統計学のキャリア」(PDF) . リン、シーホン、ジェネスト、クリスチャン、デイビッド・L.バンクス、ギアート・モレンバーグス、デイビッド・W.スコット、ジェーン・リン・ワン（編）. 『統計学の過去、現在、そして未来』CRC Press. p. 35. ISBN 9781482204964. 2015年2月11日時点のオリジナル（PDF）からアーカイブ。
7. Philips, Thomas K.; Nelson, Randolph (1995). 「正の裾の確率に対するモーメント境界はチェルノフの境界よりも厳しい」. The American Statistician . 49 (2): 175– 178. doi :10.2307/2684633. ISSN  0003-1305. JSTOR  2684633.
8. Ghosh, Malay (2021-03-04). 「カイ二乗確率変数の指数関数的裾野境界」. Journal of Statistical Theory and Practice . 15 (2) 35. doi : 10.1007/s42519-020-00156-x . ISSN  1559-8616. S2CID  233546315.
9. Theodosopoulos, Ted (2007-03-01). 「チェルノフ境界の逆転」. Statistics & Probability Letters . 77 (5): 558– 565. arXiv : math/0501360 . doi :10.1016/j.spl.2006.09.003. ISSN  0167-7152. S2CID  16139953.
10. ミッツェンマッハー、マイケル、アップファル、イーライ（2005年）『確率とコンピューティング：ランダム化アルゴリズムと確率解析』ケンブリッジ大学出版局、ISBN 978-0-521-83540-4。
11. Dillencourt, Michael; Goodrich, Michael; Mitzenmacher, Michael (2024). 「簡略化されたアルゴリズム解析のためのパラメータ化されたチェルノフ境界の活用」. Information Processing Letters . 187 (106516) 106516. doi : 10.1016/j.ipl.2024.106516 .
12. Hoeffding, W. (1963). 「有界確率変数の和に対する確率不等式」(PDF) .アメリカ統計学会誌. 58 (301): 13– 30. doi :10.2307/2282952. JSTOR  2282952.
13. 問題の詳細についてはこの本のセクションを参照してください。
14. Kearns, M.; Vazirani, U. (1994).計算学習理論入門. MIT Press. 第9章（付録）, 190–192ページ. ISBN 0-262-11193-4。
15. Alippi, C. (2014). 「ランダム化アルゴリズム」.組み込みシステムのためのインテリジェンス. Springer. ISBN 978-3-319-05278-6。
16. Sinclair, Alistair (2011年秋). 「「ランダム性と計算」コースの授業ノート」(PDF) . 2014年10月31日時点のオリジナル(PDF)からアーカイブ。 2014年10月30日閲覧。
17. Ahlswede, R.; Winter, A. (2003). 「量子チャネルによる識別のための強い逆」. IEEE Transactions on Information Theory . 48 (3): 569– 579. arXiv : quant-ph/0012127 . doi :10.1109/18.985947. S2CID  523176.
18. Tropp, J. (2010). 「ランダム行列の和に対するユーザーフレンドリーな末尾境界」.計算数学の基礎. 12 (4): 389– 434. arXiv : 1004.4389 . doi :10.1007/s10208-011-9099-z. S2CID  17735965.
19. Magen, A. ; Zouzias, A. (2011). 「低ランク行列値チェルノフ境界と近似行列乗算」. arXiv : 1005.2724 [cs.DM].
20. Goldberg, AV; Hartline, JD (2001). 「複数のデジタル商品のための競争オークション」. Algorithms — ESA 2001 . Lecture Notes in Computer Science. Vol. 2161. p. 416. CiteSeerX 10.1.1.8.5115 . doi :10.1007/3-540-44676-1_35. ISBN  978-3-540-42493-2。; 補題6.1
21. k が変化したときの r の関数としての上界と r が変化したときの k の関数としての上界のグラフを参照してください。

さらに読む

• チェルノフ, H. (1952). 「観測値の総和に基づく仮説検定の漸近的効率性の尺度」Annals of Mathematical Statistics . 23 (4): 493– 507. doi : 10.1214/aoms/1177729330 . JSTOR  2236576. MR  0057518. Zbl  0048.11804.
• チェルノフ, H. (1981). 「正規分布を含む不等式に関するノート」Annals of Probability . 9 (3): 533– 535. doi : 10.1214/aop/1176994428 . JSTOR  2243541. MR  0614640. Zbl  0457.60014.
• Hagerup, T.; Rüb, C. (1990). 「チェルノフ境界のガイドツアー」.情報処理レター. 33 (6): 305. doi :10.1016/0020-0190(90)90214-I.
• Nielsen, F. (2011). 「チェルノフ情報の情報幾何学的特徴づけ」. IEEE Signal Processing Letters . 20 (3): 269– 272. arXiv : 1102.2684 . doi :10.1109/LSP.2013.2243726. S2CID  15034953.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Chernoff_bound&oldid=1319888840"