集中度の不平等

確率論では、集中不等式は、ランダム変数がある値（通常はその期待値）から逸脱する確率の数学的境界を提供します。ランダム変数の偏差またはその他の関数は、二次ランダム変数と考えることができます。このような二次ランダム変数の集中の最も単純な例は、確率を 1 に集中させる最初のランダム変数の CDF です。CDF の解析形式が利用できる場合は、集中の確率を正確に示す集中等式が得られます。CDF の計算が難しい場合や、最初のランダム変数の正確な形式が不明な場合に、適用可能な集中不等式が役立つ洞察を提供します。

二次ランダム変数のほぼ普遍的な例としては、古典的な確率論の大数の法則が挙げられます。これは、穏やかな条件下では、独立したランダム変数の合計が、高い確率で期待値の周囲に集中するというものです。このような合計は、ランダム変数が平均の周囲に集中する最も基本的な例です。

濃度不等式は、それを使用するためにランダム変数についてどれだけの情報が必要かによって分類することができます。^[要出典]

を非負（ほぼ確実に）のランダム変数とする。すると、任意の定数に対して、 ${\displaystyle X}$${\displaystyle a>0}$

${\displaystyle \Pr(X\geq a)\leq {\frac {\operatorname {E} (X)}{a}}.}$

マルコフの不等式の次の拡張に注意:が正に増加する非負関数である場合、 ${\displaystyle \Phi}$

${\displaystyle \Pr(X\geq a)=\Pr(\Phi (X)\geq \Phi (a))\leq {\frac {\operatorname {E} (\Phi (X))}{\Phi (a)}}.}$

チェビシェフの不等式では、ランダム変数に関する次の情報が必要です。 ${\displaystyle X}$

• 期待値は有限です。${\displaystyle \operatorname {E} [X]}$
• 分散は 有限です。${\displaystyle \operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]}$

そして、すべての定数に対して、 ${\displaystyle a>0}$

${\displaystyle \Pr(|X-\operatorname {E} [X]|\geq a)\leq {\frac {\operatorname {Var} [X]}{a^{2}}},}$

または同等に、

${\displaystyle \Pr(|X-\オペレーター名 {E} [X]|\geq a\cdot \オペレーター名 {Std} [X])\leq {\frac {1}{a^{2}}},}$

ここで はの標準偏差です。 ${\displaystyle \operatorname {Std} [X]}$${\displaystyle X}$

チェビシェフの不等式は、のランダム変数に適用された一般化マルコフの不等式の特殊なケースとして考えることができます。 ${\displaystyle |X-\operatorname {E} [X]|}$${\displaystyle \ファイ (x)=x^{2}}$

Xを単峰分布、平均μ、有限非ゼロ分散σ2^のランダム変数とする。すると、任意の${\textstyle \lambda >{\sqrt {\frac {8}{3}}}=1.63299\ldots ,}$

${\displaystyle {\text{Pr}}(\left|X-\mu \right|\geq \lambda \sigma )\leq {\frac {4}{9\lambda ^{2}}}.}$

（比較的初歩的な証明については例えば^[1]を参照）。

単峰性確率変数およびに対して、片側ヴィソチャンスキー-ペチュニン不等式^[2]は次のように成り立ちます。 ${\displaystyle X}$${\displaystyle r\geq 0}$

${\displaystyle {\text{Pr}}(X-E[X]\geq r)\leq {\begin{cases}{\dfrac {4}{9}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}&{\text{for }}r^{2}\geq {\dfrac {5}{3}}\operatorname {Var} (X),\\[5pt]{\dfrac {4}{3}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}-{\dfrac {1}{3}}&{\text{otherwise.}}\end{cases}}}$

最も一般的に使用される集中不等式とは対照的に、Paley-Zygmund 不等式は偏差確率の下限を 提供します。

一般的なチェルノフ境界^{[3] :63–65は、}次のように定義されるのモーメント生成関数を必要とする。 は常に存在するが、無限大になることもある。 マルコフの不等式から、任意の に対して: ${\displaystyle X}$${\displaystyle M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right].}$${\displaystyle t>0}$

${\displaystyle \Pr(X\geq a)\leq {\frac {\operatorname {E} [e^{tX}]}{e^{ta}}},}$

そして、すべての に対して: ${\displaystyle t<0}$

${\displaystyle \Pr(X\leq a)\leq {\frac {\operatorname {E} [e^{tX}]}{e^{ta}}}.}$

異なる分布とパラメータの異なる値に対しては様々なチェルノフ境界が存在する。より多くの濃度不等式をまとめたものについては ^{[4] :5–7 を参照。}${\displaystyle t}$

しましょう。すると${\displaystyle Z\sim N(0,1)}$$${\displaystyle \operatorname {P} (|Z|>t)\leq {\sqrt {\frac {2}{\pi }}}{\frac {\exp(-t^{2}/2)}{t}}}$$

を、すべてのiに対して次の条件を満たす独立した確率変数とします。 ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$

${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$ ほぼ確実に。

${\displaystyle c_{i}:=b_{i}-a_{i}}$

${\displaystyle \forall i:c_{i}\leq C}$

をそれらの合計、その期待値、およびその分散 とします。${\displaystyle S_{n}}$${\displaystyle E_{n}}$${\displaystyle V_{n}}$

${\displaystyle S_{n}:=\sum _{i=1}^{n}X_{i}}$

${\displaystyle E_{n}:=\operatorname {E} [S_{n}]=\sum _{i=1}^{n}\operatorname {E} [X_{i}]}$

${\displaystyle V_{n}:=\operatorname {Var} [S_{n}]=\sum _{i=1}^{n}\operatorname {Var} [X_{i}]}$

合計とその期待値の差を制限することは、多くの場合興味深いことです。いくつかの不等式を使用できます。

1.ホーフディングの不等式は次のようになります。

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)\leq 2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}$

2. ランダム変数はマルチンゲールの特殊なケースであり、 です。したがって、東の不等式の一般形も使用でき、同様の境界が得られます。 ${\displaystyle S_{n}-E_{n}}$${\displaystyle S_{0}-E_{0}=0}$

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}$

これは、スーパーマルチンゲールやサブマルチンゲールだけでなく、他の種類のマルチンゲールも扱えるため、Hoeffdingの一般化です。Fan et al. (2015)を参照してください。^[5] Azumaの不等式のより単純な形式を使用すると、境界の指数が4倍悪くなることに注意してください。

3. 和関数 は、n変数関数の特殊なケースです。この関数は制限付きで変化します。つまり、変数iが変更されると、 fの値は最大 だけ変化します。したがって、マクダーミッドの不等式も使用でき、同様の制限が得られます。 ${\displaystyle S_{n}=f(X_{1},\dots ,X_{n})}$${\displaystyle b_{i}-a_{i}<C}$

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}$

これは、制限された方法で変化する限り、合計関数以外の他の関数も処理できるため、Hoeffding の別の一般化です。

4.ベネットの不等式は、被加数の分散がほぼ確実な境界Cに比べて小さい場合、ホフディングの不等式よりもいくらか改善されています。

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left[-{\frac {V_{n}}{C^{2}}}h\left({\frac {Ct}{V_{n}}}\right)\right],}$どこ${\displaystyle h(u)=(1+u)\log(1+u)-u}$

5.ベルンシュタインの不等式の最初のものは、次のことを述べています。

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {t^{2}/2}{V_{n}+C\cdot t/3}}\right)}$

これは、ほぼ確実な境界だけでなく、ほぼ確実な境界と分散境界の両方を持つランダム変数を処理できるため、Hoeffding の一般化です。

6. チェルノフ境界は、独立変数の和の場合に特に単純な形になります。 ${\displaystyle \operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}}$

例えば、^[6]変数がに対してを満たすと仮定します。このとき下裾不等式が得られます。 ${\displaystyle X_{i}}$${\displaystyle X_{i}\geq E(X_{i})-a_{i}-M}$${\displaystyle 1\leq i\leq n}$

${\displaystyle \Pr[S_{n}-E_{n}<-\lambda ]\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)}$

が を満たす場合、上裾不等式が成り立ちます。 ${\displaystyle X_{i}}$${\displaystyle X_{i}\leq E(X_{i})+a_{i}+M}$

${\displaystyle \Pr[S_{n}-E_{n}>\lambda ]\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)}$

が iid で、がの分散である場合、チェルノフの不等式の典型的なバージョンは次のようになります。 ${\displaystyle X_{i}}$${\displaystyle |X_{i}|\leq 1}$${\displaystyle \sigma ^{2}}$${\displaystyle X_{i}}$

${\displaystyle \Pr[|S_{n}|\geq k\sigma ]\leq 2e^{-k^{2}/4n}{\text{ for }}0\leq k\leq 2\sigma .}$

7. 同様の境界は、ラデマッハ分布#和の境界にも記載されています。

エフロン・スタイン不等式（または影響不等式、分散の MG 境界）は、一般関数の分散を制限します。

、が と独立であり、すべての に対して同じ分布を持つと仮定します。 ${\displaystyle X_{1}\dots X_{n}}$${\displaystyle X_{1}'\dots X_{n}'}$${\displaystyle X_{i}'}$${\displaystyle X_{i}}$${\displaystyle i}$

それでは​ ${\displaystyle X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).}$

${\displaystyle \mathrm {Var} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E[(f(X)-f(X^{(i)}))^{2}].}$

^{証明は例えば[7]}に見られる。

ブルタニョール・フーバー・カロル不等式は、多項分布するランダム変数のベクトルと期待値のベクトルの差を制限します。 ^{[8] [9]} 簡単な証明は^[10]（付録セクション）にあります。

ランダムベクトル がパラメータを持つ多項分布 に従う 場合、 ${\displaystyle (Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})}$${\displaystyle (p_{1},p_{2},\ldots ,p_{n})}$${\displaystyle Z_{1}+Z_{2}+\dots +Z_{n}=M,}$

${\displaystyle \Pr \left(\sum _{i=1}^{n}|Z_{i}-Mp_{i}|\geq 2M\varepsilon \right)\leq 2^{n}e^{-2M\varepsilon ^{2}}.}$

この不等式は、総変動距離を制限するために使用されます。

多項式ランダムベクトルに対するメイソンとヴァン・ツヴェットの不等式^[11]は、古典的なカイ二乗統計量のわずかな修正に関係している。

ランダムベクトルがパラメータとを持つ多項分布であるとし、に対してとなると、任意のとに対して、すべての とに対してとなる 定数が存在し、を 満たすので 、${\displaystyle (N_{1},\ldots ,N_{k})}$${\displaystyle n}$${\displaystyle (p_{1},\ldots ,p_{k})}$${\displaystyle p_{i}>0}$${\displaystyle i<k.}$${\displaystyle C>0}$${\displaystyle \delta >0}$${\displaystyle a,b,c>0,}$${\displaystyle n\geq 1}$${\displaystyle \lambda ,p_{1},\ldots ,p_{k-1}}$${\displaystyle \lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}}$${\displaystyle \sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,}$

${\displaystyle \Pr \left(\sum _{i=1}^{k-1}{\frac {(N_{i}-np_{i})^{2}}{np_{i}}}>\lambda \right)\leq ae^{bk-c\lambda }.}$

ドヴォレツキー・キーファー・ウォルフォヴィッツの不等式は、実累積分布関数と経験累積分布関数の差を制限します。

自然数 が与えられたとき、を累積分布関数F (·)を持つ実数値の独立かつ同一分布の確率変数とする。 は、次式で定義される 関連する経験分布関数を表すものとする。${\displaystyle n}$${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ ${\displaystyle F_{n}}$

${\displaystyle F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{X_{i}\leq x\}},\qquad x\in \mathbb {R} .}$

したがって、は単一のランダム変数が より小さい確率であり、 はより小さいランダム変数の平均個数です。 ${\displaystyle F(x)}$${\displaystyle X}$${\displaystyle x}$${\displaystyle F_{n}(x)}$${\displaystyle x}$

それから

${\displaystyle \Pr \left(\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon \right)\leq e^{-2n\varepsilon ^{2}}{\text{ for every }}\varepsilon \geq {\sqrt {{\tfrac {1}{2n}}\ln 2}}.}$

一方、反集中不等式は、特定の値または値の範囲にランダム変数が集中できる量の上限を提供します。具体的な例としては、公平なコインを 回投げた場合、任意の数の表が出る確率は 未満になります。この考え方は大幅に一般化できます。たとえば、Rao と Yehudayoff ^[12]の結果は、任意の に対して が存在し、任意の に対して、少なくともの値に対して以下が真であることを意味します。 ${\displaystyle n}$${\displaystyle {\frac {1}{\sqrt {n}}}}$${\displaystyle \beta ,\delta >0}$${\displaystyle C>0}$${\displaystyle k}$${\displaystyle 2^{n(1-\delta )}}$${\displaystyle x\in \{\pm 1\}^{n}}$

${\displaystyle \Pr \left(\langle x,Y\rangle =k\right)\leq {\frac {C}{\sqrt {n}}},}$

ここで はから一様に描かれています。 ${\displaystyle Y}$${\displaystyle \{\pm 1\}^{n}}$

このような不等式は、通信複雑性（例えば、ギャップハミング問題^[13]の証明）やグラフ理論^[14]を含むいくつかの分野で重要です。

独立したラデマッハ確率変数の加重和に対する興味深い反集中不等式は、ペイリー・ジグムント不等式とヒンチン不等式を用いて得ることができる。^[15]

• カルティク・スリダラン、「集中不等式の簡単な入門」—コーネル大学