농도 부등식

확률론에서, 농도 부등식은 랜덤 변수가 어떤 값(일반적으로 기대값)에서 어떻게 벗어나는지에 대한 경계를 제공합니다.고전 확률론의 대수의 법칙은 독립 랜덤 변수의 합계가 매우 가벼운 조건에서 큰 확률로 기대치에 가깝다고 말합니다.이러한 합계는 평균 주위에 집중된 랜덤 변수의 가장 기본적인 예입니다.최근의 결과는 그러한 동작이 독립적인 랜덤 변수의 다른 함수에 의해 공유된다는 것을 보여준다.

농도 부등식은 랜덤 변수를 사용하기 위해 필요한 정보의 양에 따라 분류할 수 있다.

마르코프 부등식

$X를$ 음이 아닌 랜덤 변수(거의 확실하게 $)$ 로 합니다.다음으로 $a>0$ a $a>0$ > $a>0$ { $style$ a > $0$ 에 대해

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

마르코프 부등식에 대한 다음의 확장에 주목하라: 만약 $\Phi$ (\ $displaystyle \Phi)$ 가 $\Phi$ 엄밀하게 증가하고 음이 아닌 함수라면,

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

체비셰프 부등식

체비셰프의 부등식에는 랜덤 $변수$ X $(\displaystyle$ X $X$ 에 대한 다음 정보가 필요합니다.

$\operatorname {E} [X]$ E $\operatorname {E} [X]$ [ $]$ \ $displaystyle \operatorname$ { $E$ } [ X $]$ 는 $\operatorname {E} [X]$ 유한합니다.
$\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ 변수 $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ [ $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ ] $=$ $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ [ ( $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ - E $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ [ $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ ) $]{$ $displaystyle \operatorname {Var$ } [X]=\ $operatorname {E} [X])$ $^{2}]}$ 은 $\operatorname{Var}[X] = \operatorname{E}[(X - \operatorname{E}[X] )^2]$ (는) 유한합니다.

다음으로 $a>0$ a $a>0$ > $a>0$ { $style$ a > $0$ 에 대해

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

또는 동등하게

\displaystyle \Pr( X-\operatorname {E} [X]\geq a\cdot \operatorname {Std} [X])\leq {frac {1}{a^{2}}}}

$\operatorname {Std} [X]$ 서 Std $\operatorname {Std} [X]$ [ $]{$ $displaystyle$ $\operatorname$ { $Std }$ [ $X$ $]$ 는 $\operatorname {Std} [X]$ X의 $표준$ 편차입니다 $X$

체비셰프의 부등식은 $\Phi (x)=x^{2}$ ( $\Phi (x)=x^{2}$ $\Phi (x)=x^{2}$ $\Phi (x)=x^{2}$ ( $x)$ = $\Phi (x)=x^{2}$ x { $2$ 인 랜덤 $|X-\operatorname {E} [X]|$ X - $|X-\operatorname {E} [X]|$ $|X-\operatorname {E} [X]|$ [ $|X-\operatorname {E} [X]|$ $|X-\operatorname {E} [X]|$ { $style X-\operatorname {E}$ [ $X] }$ 에 $|X-\operatorname {E} [X]|$ 적용되는 일반화 마르코프 부등식의 특별한 경우로 볼 수 있다.

비소찬스키-페투닌 부등식

X를 단일 분포, 평균 μ 및 유한, 0이 아닌 분산 θ를² 갖는 랜덤 변수라고 가정합니다.다음으로 ${\textstyle \lambda >{\sqrt {\frac {8}{3}}}=1.63299...,}$ > 8 3 ${\textstyle \lambda >{\sqrt {\frac {8}{3}}}=1.63299...,}$ 1.63299 $...$ 에 대해 {\ $textstyle \taxda$ > {\ $taxrt {8}$ {3} $= 1.63299...,}$

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

(상대적인 기본적인 증명에 대해서는 예를 참조해 주세요).

일방 비소찬스키-페투닌 부등식

$유니모달$ 랜덤 $변수$ X(\ $displaystyle$ $r\geq 0$ ) $r\geq 0$ r ${\$ 0(\ $displaystyle$ r $\geq$ 0 $r\geq 0$ 의 경우 단측 Vysochanskij-Petunin 부등식은^[2] 다음과 같습니다.

$\displaystyle \mathbb {P}(X-E[X]\geq r)\leq {\begin{cases}{\dfrac {4}{9}} {\dfrac {Var(X)} {r^{2}+Var(X)}} {\mbox{2\geq} {3frac} {9}}}\end {case}}$

팔레-지그문트 부등식

칸텔리의 부등식

가우스 부등식

체르노프 경계

일반적인 체르노프^[3]^{: 63–65} 바운드에는 $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ 과 같이 $X$ 된X(\ $displaystyle$ X $X$ E [ e t $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ ]( $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ X ( $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ ) : $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ E [ $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ X $]$ \ $displaystyle M$ _ { $X$ } ( $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ ) : $=\operatorname$ { $E} \!\left[$ e^{ $tX}\$ right $M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]$ 존재하는 경우).마르코프 부등식을 바탕으로 t $t>0$ > $t>0$ { $displaystyle$ t > $0$ }마다 다음과 같이 계산됩니다.

\displaystyle \Pr(X\geq a)\leq {frac {operatorname {E} [e^{t\cdot X}} {e^{t\cdot a}}}

및 $t<0$ t $t<0$ < $t<0$ { $displaystyle t$ < 0 $t<0$ }마다:

\displaystyle \Pr(X\leq a)\leq {frac {operatorname {E} [e^{t\cdot X}} {e^{t\cdot a}}}.}

$모수$ t\ $displaystyle$ t의 분포와 값에는 다양한 체르노프 경계가 있습니다. 더 많은 농도 부등식의 집계에 대해서는 을 참조하십시오.

독립 변수의 합계에 대한 한계

$X_{1},X_{2},\dots ,X_{n}$ 1, $X_{1},X_{2},\dots ,X_{n}$ 2, $X_{1},X_{2},\dots ,X_{n}$ $X_{1},X_{2},\dots ,X_{n}$ n(\ $displaystyle X_{1$ }, $X_{$ 2},\ $dots,X_{n})$ 을 $X_{1},X_{2},\dots ,X_{n}$ 다음과 같은 독립된 랜덤 변수로 $X_{1},X_{2},\dots ,X_{n}$ .

a_{i}\leq X_{i}\leq b_{i}

a i

a_{i}\leq X_{i}\leq b_{i}

i

a_{i}\leq X_{i}\leq b_{i}

i i i i i i i i i i

a_{i}\leq X_{i}\leq b_{i}

displaystyle a

_

{

i

}

leq

X

_

{ i } leq b

_

{

a_{i}\leq X_{i}\leq b_{i}

i

a_{i}\leq X_{i}\leq b_{i}

} 。

c_{i}:=b_{i}-a_{i}

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

$(\$ 을 $S_{n}$ 합계, $(\$ 을 $E_{n}$ $V_{n}$ , $(\$ })을 $V_{n}$ 분산값으로 $S_{n}$ .

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

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

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

합계와 기대치 사이의 차이를 제한하는 것은 종종 흥미롭다.몇 가지 부등식을 사용할 수 있다.

1. 호핑의 부등식은 다음과 같다.

\displaystyle \Pr \left [ S _ { n } - E _ { n } > t \ right ]< 2 \ exp \ exp \ frac { 2 t ^ { 2 } { \ sum _ { i = n } c _ { i } { i } } { n } } } { right } < 2 }

2. 랜덤 $S_{n}-E_{n}$ S $S_{n}-E_{n}$ - $S_{n}-E_{n}$ n \ $displaystyle$ S _ { $n$ } - $E$ _ { $n$ }는 $S_{n}-E_{n}$ 마티게일의 특수한 경우이며, $S_{0}-E_{0}=0$ 0 - $S_{0}-E_{0}=0$ 0 $S_{0}-E_{0}=0$ \ $displaystyle S_{0}$ - $E_{0$ $=$ 0 입니다.따라서, 아즈마 부등식의 일반적인 형태도 사용할 수 있으며, 이는 유사한 경계를 산출한다.

\displaystyle \Pr \left [ S _ { n } - E _ { n } > t \ right ]< 2 \ exp \ exp \ frac { 2 t ^ { 2 } { \ sum _ { i = n } c _ { i } { i } } { n } } } { right } < 2 }

이것은 슈퍼마틴갈레와 서브마틴갈레뿐만 아니라 다른 종류의 마틴갈레도 다룰 수 있기 때문에 Hooffding's의 일반화이다.더 단순한 형태의 아즈마 부등식을 사용하면 경계에 있는 지수가 4배 더 나빠집니다.

3. S $S_{n}=f(X_{1},\dots ,X_{n})$ $S_{n}=f(X_{1},\dots ,X_{n})$ ( $S_{n}=f(X_{1},\dots ,X_{n})$ 1 $S_{n}=f(X_{1},\dots ,X_{n})$ , $S_{n}=f(X_{1},\dots ,X_{n})$ , $S_{n}=f(X_{1},\dots ,X_{n})$ n $S_{n}=f(X_{1},\dots ,X_{n})$ ) { $displaystyle$ S _ { n } $=$ f ( $X _$ { $1}$ , \ $dots$ , X _ { n $S_{n}=f(X_{1},\dots ,X_{n})$ } $S_{n}=f(X_{1},\dots ,X_{n})$ )는 n 변수 함수의 특수한 경우이다.이 함수는 제한적으로 변화한다.변수 i가 변경되면 f의 값은 $b_{i}-a_{i}<C$ b $b_{i}-a_{i}<C$ - $b_{i}-a_{i}<C$ < $i$ _ c \ $displaystyle b _$ { i $b_{i}-a_{i}<C$ } - a _ { $i$ } < C $b_{i}-a_{i}<C$ }만큼 변화한다.따라서 McDiarmid의 부등식을 사용할 수도 있고 다음과 같은 경계가 생성된다.

\displaystyle \Pr \left [ S _ { n } - E _ { n } > t \ right ]< 2 \ exp \ exp \ frac { 2 t ^ { 2 } { \ sum _ { i = n } c _ { i } { i } } { n } } } { right } < 2 }

이것은 합함수 이외의 다른 함수가 유계적으로 변화하기만 하면 처리할 수 있기 때문에 Hooffding의 다른 일반화입니다.

4. Bennett의 부등식은 Summands의 분산이 거의 확실한 경계 C에 비해 작을 때 Hoffding의 부등식보다 어느 정도 개선된다.다음과 같이 되어 있습니다.

\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],

[

\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],

-

\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],

n

\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],

>

\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],

]

\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],

\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],

exp

\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],

[ -

\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],

n

\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],

2

\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],

( C

\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],

\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],

n )

\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],

,

\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

\

Pr

\ left [ S

_

{

n

} - E

_

{

n

} >

t

\

right

} \

leq 2

\

exp

\ [ - { - { \

frac

{

V

_ n } {

n

} } } } {

c } (

{

h

}

5. 번스타인의 첫 번째 불평등은 다음과 같다.

\displaystyle \Pr \left [ S _ { n } - E _ { n } > t \ right ]< 2 \ exp \ left ( - \ frac { t^ {2} / 2) { V _ { n } + C \ cdot t/3} \ right }

이것은 거의 확실한 한계뿐만 아니라 거의 확실한 한계와 분산 한계를 가진 랜덤 변수를 처리할 수 있기 때문에 Hooffding의 일반화입니다.

6. 체르노프 경계는 독립 변수의 합계의 경우 E $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ [ $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ t $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ S $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ ] $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ E $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ [ $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ i $]$ \ $display \operatorname { E$ } [ $e$ ^ { $t$ \ $cdot$ S $_$ { n } = $prod$ { $n$ }^{ n } ^{ n } } $\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}$ 특히 $단순$ 한 형태를 가진다 $.$

예를 ^[5]들어 변수 $X_{i}$ i (\ $displaystyle X_{i$ })가 $X_{i}$ $X_{i}\geq E(X_{i})-a_{i}-M$ i $X_{i}\geq E(X_{i})-a_{i}-M$ ( $X_{i}\geq E(X_{i})-a_{i}-M$ i $X_{i}\geq E(X_{i})-a_{i}-M$ )를 $X_{i}\geq E(X_{i})-a_{i}-M$ 한다고 가정합니다 $X_{i}\geq E(X_{i})-a_{i}-M$ - $X_{i}\geq E(X_{i})-a_{i}-M$ M ( \ $displaystyle$ X _ { $i$ } \ $geq E$ ( X _ { i } ) - a _ { i $X_{i}\geq E(X_{i})-a_{i}-M$ } - $X_{i}\geq E(X_{i})-a_{i}-M$ $1\leq i\leq n$ 、 $1\leq i\leq n$ 1 $1\leq i\leq n$ i $1\leq i\leq n$ n $1\leq i\leq n$ \ $displaystyleq$ then $then then$ then then then then then then $1\leq i\leq n$ 。

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

$(\$ X_ ${i})$ 가 $X_{i}$ $X_{i}\leq E(X_{i})+a_{i}+M$ E( $X_{i}\leq E(X_{i})+a_{i}+M$ + $X_{i}\leq E(X_{i})+a_{i}+M$ + $X_{i}\leq E(X_{i})+a_{i}+M$ (\ $displaystyle X_{i}\leq$ E $(X_{i})$ + $a_{i}+M$ 를 $X_{i}\leq E(X_{i})+a_{i}+M$ 하는 $X_{i}$ 상단 꼬리 부등식이 있습니다.

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

$(\$ 가 $X_{i}$ i.i.d, $X_{i}$ $|X_{i}|\leq 1$ 1 $(\displaystyle X_$ ${i$ $및$ $\sigma ^{2}$ 2 $(\$ ^{ $2})$ 인 $\sigma ^{2}$ $X_{i}$ 체르노 부등식의 $일반적$ 인 버전은 $다음$ 과 같습니다.

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

7. Rademacher distribution #Bounds on sums에서도 같은 경계를 찾을 수 있습니다.

에프론-스타인 부등식

Efron-Stein 부등식(또는 영향 부등식 또는 분산에 대한 MG 한계)은 일반 함수의 분산을 제한합니다.

$X_{1}\dots X_{n}$ 1 $X_{1}\dots X_{n}$ $X_{1}\dots X_{n}$ \ $display style$ X_ ${1$ } \ $dots X_{n$ , $X_{1}'\dots X_{n}'$ $X_{1}'\dots X_{n}'$ ... X $X_{1}'\dots X_{n}'$ ${\$ \ $display X_{1}$ ' \ $dots X_{n}'$ 은 $X_{1}'\dots X_{n}'$ $X_{i}'$ i $X_{i}'$ {\ \ $display style X_{$ i $X_{i}'$ } $X_{i}$ X $X_{i}$ i { $display$ X_n $}$ 에서 $X_{i}$ $X_{i}'$ 되어 $X_{1}\dots X_{n}$ 가정합니다.

$X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ ( $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ 1 , $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ , $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ ) , $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ ( $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ ) $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ ( $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ 1 $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ , $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ , $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ i - $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ , X $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ , $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ i + $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ 1, $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ , $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ n ) $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$ . { $display$ X = ( $X _$ { $1$ , \ $dots$ , X _ { $n$ } , $X^$ { i } \ $DOTs$ = { 1 } ) 。 $}$ 그럼 $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).$

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

브르타놀레휴버-카롤 부등식

브르타놀레Huber-Carol 부등식은 다원적으로 분포된 랜덤 변수의 벡터와 기대치의 벡터 사이의 차이를 제한합니다.^[6]^[7] 간단한 증거는 (부록 섹션)에 나와 있습니다.

랜덤 벡터 $(Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})$ 1, $(Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})$ , Z $(Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})$ , $(Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})$ $(Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})$ $)$ { $displaystyle (Z_{1}, Z_{2$ }, $Z_{3},\ldots$ $,$ $Z_{n})$ 가 $(Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})$ 파라미터( $(p_{1},p_{2},\ldots ,p_{n})$ 1, p $(p_{1},p_{2},\ldots ,p_{n})$ , $(p_{1},p_{2},\ldots ,p_{n})$ $(p_{1},p_{2},\ldots ,p_{n})$ n $)$ { $displaystyle (p_1},$ { $n2},$ \ $ldots$ }, \displaystyle ( $p_{n$ })와 함께 다원 분산되어 있는 경우 $그러면 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}}.}

이 부등식은 총 변동 거리를 제한하는 데 사용됩니다.

메이슨과 반즈벳의 부등식

다항 랜덤 벡터에 대한 Mason과 van Zwet 부등식은^[9] 고전적인 카이-제곱 통계량의 약간의 수정과 관련이 있습니다.

랜덤 벡터 $(N_{1},\ldots ,N_{k})$ 1, $(N_{1},\ldots ,N_{k})$ $(N_{1},\ldots ,N_{k})$ $)$ { $displaystyle (N_{1},\ldots,N_{k})$ { $displaystyle$ n $}$ $(p_{1},\ldots ,p_{k})$ 및 $n$ ( $(p_{1},\ldots ,p_{k})$ 1, $(p_{1},\ldots ,p_{k})$ p $)$ { $displaystyle (p_{1},\ldots,p_$ ${k$ $})$ {displaystyle $p_0}$ ( $i<k.$ $p_{i}>0$ 를 $(N_{1},\ldots ,N_{k})$ $(p_{1},\ldots ,p_{k})$ $p_{i}>0$ 사용하여 $p_{i}>0$ 으로 $분산$ 시킵니다.모든 C을}그리고 나서;0{\displaystyle C>0}과δ>0{\displaystyle \delta>0}모든 n≥ 1{\displaystyle n\geq 1}과 λ, p1,…, pk에 정수 a, b, c>;0,{\displaystyle a,b,c>0,}가 − 1{\displaystyle\lambda ,p_{1},\ldots ,p_{k-1}}을 만족시키 λ 존재합니다.>Cn분{p) $\lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}$ $\lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}$ $\lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}$ $\lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}$ - 1 $\lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}$ 、 { $display$ style \ $displayda > Cn$ \ $min$ \ { p $_$ p $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ { $i$ } 1 \ $leq$ $k$ - 1 $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ } $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ i i i i $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ i $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ i 、 $i$ i $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ - " $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ \ $displaystyle$ _ { i $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ = 1 }^{ k - $1$ p _ k - { i } p _ i } \ $leq$ 1 \ $leq$ 1 $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ } 、

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

드보레츠키-키퍼-울포위츠 부등식

드보레츠키-키퍼-울포위츠 부등식은 실제 누적분포함수와 경험적 누적분포함수의 차이를 제한한다.

$자연수$ n(\ $displaystyle$ n $n$ 을 $X_{1},X_{2},\dots ,X_{n}$ 하면 X $X_{1},X_{2},\dots ,X_{n}$ , $X_{1},X_{2},\dots ,X_{n}$ 2, $X_{1},X_{2},\dots ,X_{n}$ $X_{1},X_{2},\dots ,X_{n}$ (\ $displaystyle X_{1}, X_{2},\dots,X_{n})$ 은 $X_{1},X_{2},\dots ,X_{n}$ 누적분포함수 F(·)를 갖는 독립적이고 동일한 분포 랜덤 변수입니다. $F_{n}$ {\ $displaystyle F_{$ n $F_{n}$ }}은 다음과 같이 정의된 관련 경험적 분포 함수를 나타냅니다.

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

$F(x)$ F $)$ { $displaystyle$ F $(x)}$ 는 $F(x)$ 단일 랜덤 $변수$ X $(\$ $displaystyle$ X $)$ 가 $X$ x(\ $displaystyle$ x $x$ 보다 작을 $F_{n}(x)$ 이며 F( $)$ { $displaystyle F_{n}(x)$ 는 $F_n(x)$ x(\ $displaystyle$ x $x$ 보다 작은 평균 랜덤 변수 수입니다.

그리고나서

\displaystyle \Pr \left(\sup _{x\in \mathbb {R}} {\bigl (}F_{n}(x)-F(x){\bigr}}>\leq e^{-2n\varepsilon^{2}}{\text}}\arechqs\rtext}{\biglon {\}}}}\rtext}\biglon\rts\rts\rtext}{\rtext}{{\rt}}{\rt}}}

반농축 불평등

반면, 반농도 부등식은 랜덤 변수가 양 주위에 얼마나 집중될 수 있는지에 대한 상한을 제공한다.

예를 들어 Rao 및 Yehudayoff는^[10] $x\in \{\pm 1\}^{n}$ $x\in \{\pm 1\}^{n}$ { ± $x\in \{\pm 1\}^{n}$ $(\$ x $\in \{\pm$ 1 $\}^n$ 의 대부분의 방향에 대해 다음과 같은 C $C>0$ > $C>0$ (\ $displaystyle$ C> $0)$ 이 $C>0$ 존재함을 나타냅니다.

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

$Y$ 서 Y $(\$ $displaystyle$ Y $)$ 는 $Y$ 충분한 크기의 하위 $B\subseteq \{\pm 1\}^{n}$ B $B\subseteq \{\pm 1\}^{n}$ { $B\subseteq \{\pm 1\}^{n}$ { ± $B\subseteq \{\pm 1\}^{n}$ n $(\displaystyle$ B\subseteq \{\ $pm$ 1 $\}^{$ n $})$ 에서 균일하게 그려집니다.

그러한 불평등은 통신 복잡성(예: 격차 해밍^[11] 문제의 증거)과 그래프 ^[12]이론을 포함한 여러 분야에서 중요하다.

독립 Rademacher 랜덤 변수의 가중치 합계에 대한 흥미로운 반농도 부등식은 Paley-Zygmund 및 Kintchine ^[13]부등식을 사용하여 얻을 수 있다.

레퍼런스

^ Pukelsheim, F., 1994.스리 시그마 룰미국 통계학자, 48(2), 페이지 88-91
^ Mercadier, Mathieu; Strobel, Frank (2021-11-16). "A one-sided Vysochanskii-Petunin inequality with financial applications". European Journal of Operational Research. 295 (1): 374–377. doi:10.1016/j.ejor.2021.02.041. ISSN 0377-2217.
^ Mitzenmacher, Michael; Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2.
^ Slagle, N.P. (2012). "One Hundred Statistics and Probability Inequalities".
^ Chung, Fan; Lu, Linyuan (2010). "Old and new concentration inequalities" (PDF). Complex Graphs and Networks. American Mathematical Society. Retrieved August 14, 2018.
^ Bretagnolle, Jean; Huber, Catherine (1978). "Lois empiriques et distance de Prokhorov". Lecture Notes in Mathematics. 649: 332--341.
^ van der Vaart, A.W.; Wellner, J.A. (1996). Weak convergence and empirical processes: With applications to statistics. Springer Science & Business Media.
^ Yuto Ushioda; Masato Tanaka; Tomomi Matsui (2022). "Monte Carlo Methods for the Shapley–Shubik Power Index". Games. 13 (3): 44. doi:10.3390/g13030044.
^ Mason, David M.; Willem R. Van Zwet (1987). "A Refinement of the KMT Inequality for the Uniform Empirical Process". The Annals of Probability. 15 (3): 871–884.
^ Rao, Anup; Yehudayoff, Amir (2018). "Anti-concentration in most directions". Electronic Colloquium on Computational Complexity.
^ Sherstov, Alexander A. (2012). "The Communication Complexity of Gap Hamming Distance". Theory of Computing.
^ Matthew Kwan; Benny Sudakov; Tuan Tran (2018). "Anticoncentration for subgraph statistics". Journal of the London Mathematical Society. 99 (3): 757–777. arXiv:1807.05202. Bibcode:2018arXiv180705202K. doi:10.1112/jlms.12192. S2CID 54065186.
^ Veraar, Mark (2009). "On Khintchine inequalities with a weight". arXiv:0909.2586v1 [math.PR].

외부 링크

Karthik Sridharan, "집중력 불평등에 대한 부드러운 입문" - Cornell 대학교

[1] Pukelsheim, F., 1994.스리 시그마 룰미국 통계학자, 48(2), 페이지 88-91

[2] Mercadier, Mathieu; Strobel, Frank (2021-11-16). "A one-sided Vysochanskii-Petunin inequality with financial applications". European Journal of Operational Research. 295 (1): 374–377. doi:10.1016/j.ejor.2021.02.041. ISSN 0377-2217.

[MitzenmacherUpfal-3] Mitzenmacher, Michael; Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2.

[OneHundredNPS-4] Slagle, N.P. (2012). "One Hundred Statistics and Probability Inequalities".

[ChungChernoff-5] Chung, Fan; Lu, Linyuan (2010). "Old and new concentration inequalities" (PDF). Complex Graphs and Networks. American Mathematical Society. Retrieved August 14, 2018.

[Bretagnolle-6] Bretagnolle, Jean; Huber, Catherine (1978). "Lois empiriques et distance de Prokhorov". Lecture Notes in Mathematics. 649: 332--341.

[Vaart-7] van der Vaart, A.W.; Wellner, J.A. (1996). Weak convergence and empirical processes: With applications to statistics. Springer Science & Business Media.

[Ushioda-8] Yuto Ushioda; Masato Tanaka; Tomomi Matsui (2022). "Monte Carlo Methods for the Shapley–Shubik Power Index". Games. 13 (3): 44. doi:10.3390/g13030044.

[Mason-9] Mason, David M.; Willem R. Van Zwet (1987). "A Refinement of the KMT Inequality for the Uniform Empirical Process". The Annals of Probability. 15 (3): 871–884.

[RaoYehudayoff-10] Rao, Anup; Yehudayoff, Amir (2018). "Anti-concentration in most directions". Electronic Colloquium on Computational Complexity.

[Sherstov-11] Sherstov, Alexander A. (2012). "The Communication Complexity of Gap Hamming Distance". Theory of Computing.

[Kwan-12] Matthew Kwan; Benny Sudakov; Tuan Tran (2018). "Anticoncentration for subgraph statistics". Journal of the London Mathematical Society. 99 (3): 757–777. arXiv:1807.05202. Bibcode:2018arXiv180705202K. doi:10.1112/jlms.12192. S2CID 54065186.

[Veraar-13] Veraar, Mark (2009). "On Khintchine inequalities with a weight". arXiv:0909.2586v1 [math.PR].

[2]

[3]

[5]

[6]

[7]

[9]

[10]

[11]

[12]

[13]

Search