バーンスタイン不等式（確率論）

確率論では、ベルンシュタイン不等式は、ランダム変数の合計がその平均から逸脱する確率に上限を与えます。最も単純なケースでは、X ₁、...、  X _nを、確率 1/2 で +1 と -1 の値を取る独立したベルヌーイランダム変数とします (この分布はラデマッハー分布としても知られています)。すると、任意の正の に対して、 ${\displaystyle \epsilon }$

${\displaystyle \mathbb {P} \left(\left|{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\right|>\varepsilon \right)\leq 2\exp \left(-{\frac {n\varepsilon ^{2}}{2(1+{\frac {\varepsilon }{3}})}}\right).}$

ベルンシュタイン不等式は、1920年代から1930年代にかけてセルゲイ・ベルンシュタインによって証明され、発表されました。 ^{[1] [2] [3] [4]}その後、これらの不等式はさまざまな形で何度も再発見されました。そのため、ベルンシュタイン不等式の特殊なケースは、チェルノフ境界、ホエフディングの不等式、東の不等式としても知られています。ベルンシュタイン不等式のマルチンゲールケースはフリードマンの不等式として知られており、 ^[5]その改良版はホエフディングの不等式として知られています。^[6]

1.を平均ゼロの独立したランダム変数とする。ほぼ確実に、すべての に対して であるとする。すると、すべての正の に対して、 ${\displaystyle X_{1},\ldots ,X_{n}}$${\displaystyle |X_{i}|\leq M}$${\displaystyle i.}$${\displaystyle t}$

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq t\right)\leq \exp \left(-{\frac {{\tfrac {1}{2}}t^{2}}{\sum _{i=1}^{n}\mathbb {E} \left[X_{i}^{2}\right]+{\tfrac {1}{3}}Mt}}\right).}$

2. を平均0の独立したランダム変数とする。ある正の実数と任意の整数に対して、 ${\displaystyle X_{1},\ldots ,X_{n}}$${\displaystyle L}$${\displaystyle k\geq 2}$

${\displaystyle \mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {1}{2}}\mathbb {E} \left[X_{i}^{2}\right]L^{k-2}k!}$

それから

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq 2t{\sqrt {\sum \mathbb {E} \left[X_{i}^{2}\right]}}\right)<\exp(-t^{2}),\qquad {\text{for}}\quad 0\leq t\leq {\frac {1}{2L}}{\sqrt {\sum \mathbb {E} \left[X_{j}^{2}\right]}}.}$

3.を平均0の独立したランダム変数とする。 ${\displaystyle X_{1},\ldots ,X_{n}}$

${\displaystyle \mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {k!}{4!}}\left({\frac {L}{5}}\right)^{k-4}}$

すべての整数 について、${\displaystyle k\geq 4.}$

${\displaystyle A_{k}=\sum \mathbb {E} \left[X_{i}^{k}\right].}$

それから、

${\displaystyle \mathbb {P} \left(\left|\sum _{j=1}^{n}X_{j}-{\frac {A_{3}t^{2}}{3A_{2}}}\right|\geq {\sqrt {2A_{2}}}\,t\left[1+{\frac {A_{4}t^{2}}{6A_{2}^{2}}}\right]\right)<2\exp(-t^{2}),\qquad {\text{for}}\quad 0<t\leq {\frac {5{\sqrt {2A_{2}}}}{4L}}.}$

4. バーンスタインは、上記の不等式の弱従属確率変数への一般化も証明した。例えば、不等式(2)は次のように拡張できる。 はおそらく独立でない確率変数とする。すべての整数 に対して、 ${\displaystyle X_{1},\ldots ,X_{n}}$${\displaystyle i>0}$

${\displaystyle {\begin{aligned}\mathbb {E} \left.\left[X_{i}\right|X_{1},\ldots ,X_{i-1}\right]&=0,\\\mathbb {E} \left.\left[X_{i}^{2}\right|X_{1},\ldots ,X_{i-1}\right]&\leq R_{i}\mathbb {E} \left[X_{i}^{2}\right],\\\mathbb {E} \left.\left[X_{i}^{k}\right|X_{1},\ldots ,X_{i-1}\right]&\leq {\tfrac {1}{2}}\mathbb {E} \left.\left[X_{i}^{2}\right|X_{1},\ldots ,X_{i-1}\right]L^{k-2}k!\end{aligned}}}$

それから

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq 2t{\sqrt {\sum _{i=1}^{n}R_{i}\mathbb {E} \left[X_{i}^{2}\right]}}\right)<\exp(-t^{2}),\qquad {\text{for}}\quad 0<t\leq {\frac {1}{2L}}{\sqrt {\sum _{i=1}^{n}R_{i}\mathbb {E} \left[X_{i}^{2}\right]}}.}$

マルチンゲールのより一般的な結果はFan et al. (2015)に記載されています。^[7]

証明はマルコフの不等式をランダム変数に 適用することに基づいている。

${\displaystyle \exp \left(\lambda \sum _{j=1}^{n}X_{j}\right),}$

パラメータを適切に選択するには、 ${\displaystyle \lambda >0}$

ベルンシュタイン不等式はガウスランダム行列に一般化できます。をスカラーとし、 を複素エルミート行列、 をサイズ の複素ベクトルとします。 ベクトル はサイズ のガウスベクトルです。 すると、任意の に対して、次式が成り立ちます。 ${\displaystyle G=g^{H}Ag+2\operatorname {Re} (g^{H}a)}$${\displaystyle A}$${\displaystyle a}$${\displaystyle N}$${\displaystyle g\sim {\mathcal {CN}}(0,I)}$${\displaystyle N}$${\displaystyle \sigma \geq 0}$

${\displaystyle \mathbb {P} \left(G\leq \operatorname {tr} (A)-{\sqrt {2\sigma }}{\sqrt {\Vert \operatorname {vec} (A)\Vert ^{2}+2\Vert a\Vert ^{2}}}-\sigma s^{-}(A)\right)<\exp(-\sigma ),}$

ここで はベクトル化演算であり、はの最大固有値である。証明はここで詳述されている。^[8]同様の不等式は次のように定式化される 。${\displaystyle \operatorname {vec} }$${\displaystyle s^{-}(A)=\max(-\lambda _{\max }(A),0)}$${\displaystyle \lambda _{\max }(A)}$${\displaystyle A}$

${\displaystyle \mathbb {P} \left(G\geq \operatorname {tr} (A)+{\sqrt {2\sigma }}{\sqrt {\Vert \operatorname {vec} (A)\Vert ^{2}+2\Vert a\Vert ^{2}}}+\sigma s^{+}(A)\right)<\exp(-\sigma ),}$

どこ 。 ${\displaystyle s^{+}(A)=\max(\lambda _{\max }(A),0)}$

• 濃度不等式- ランダム変数の裾の境界の概要。
• ホーフディングの不等式

（SNBernstein著、Collected Works、Nauka、1964年より）

これらの結果のいくつかの現代訳は、Prokhorov, AV; Korneichuk, NP; Motornyi, VP (2001) [1994]、「Bernstein inequality」、Encyclopedia of Mathematics、EMS Pressにも掲載されています。