Sannolikhet och datavetenskap koncept
Inom sannolikhetsteori och teoretisk datavetenskap är McDiarmids ojämlikhet en koncentrationsojämlikhet som begränsar avvikelsen mellan det samplade värdet och det förväntade värdet för vissa funktioner när de utvärderas på oberoende slumpvariabler . McDiarmids ojämlikhet gäller funktioner som uppfyller en bounded differences- egenskap, vilket innebär att att ersätta ett enda argument till funktionen samtidigt som alla andra argument lämnas oförändrade inte kan orsaka en för stor förändring av funktionens värde.
Påstående
En funktion
f :
X
1
×
X
2
× ⋯ ×
X
n
→
R
{\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \ gånger {\mathcal {X}}_{n}\rightarrow \mathbb {R} }
egenskapen bounded differences om värdet av
i
{\displaystyle i}:
x
i
{\displaystyle x_{i}}
f
{\displaystyle f}
c
i
{\displaystyle c_{i}}
c
1
,
c
2
, … ,
c
n
{\displaystyle c_{1},c_{2},\dots ,c_{n}}
i ∈ [ n ]
{\displaystyle i\in [n]}
x
1
∈
X
1
,
x
2
∈
X
2
, … ,
x
n
∈
X
n
{\displaystyle x_{1}\i {\mathcal {X}}_{1}, \,x_{2}\i {\mathcal {X}}_{2},\,\ldots ,\,x_{n}\i {\mathcal {X}}_{n}}
sup
x
i
′
∈
X
i
|
f (
x
1
, … ,
x
i − 1
,
x
i
,
x
i + 1
, … ,
x
n
) − f (
x
1
, … ,
x
i − 1
,
x
i
′
,
x
i + 1
, … ,
x
n
)
|
≤
c
i
.
{\displaystyle \sup _{x_{i}'\in {\mathcal {X}}_{i}}\left|f(x_{1},\dots ,x_{i-1},x_{i} ,x_{i+1},\ldots ,x_{n})-f(x_{1},\dots ,x_{i-1},x_{i}',x_{i+1},\ldots, x_{n})\right|\leq c_{i}.}
McDiarmid's Inequality — Låt
f :
X
1
×
X
2
× ⋯ ×
X
n
→
R
{\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \ cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} }
c
1
,
c
2
, … ,
c
n
{\displaystyle c_{1},c_{2 },\dots ,c_{n}}
Betrakta oberoende slumpvariabler
X
1
,
X
2
, … ,
X
n
{\displaystyle X_{1},X_{2},\dots ,X_{n}}
X
i
∈
X
i
{\displaystyle X_{i}\in {\mathcal {X}}_{i}}
i
{\displaystyle i}
ε >
0
{\displaystyle \varepsilon >0}
P
(
f (
X
1
,
X
2
, … ,
X
n
) −
E
[ f (
X
1
,
X
2
, … ,
X
n
) ] ≥ ε
)
≤ exp
(
−
2
ε
2
∑
i = 1
n
c
i
2
)
,
{\displaystyle {\text{P}}\left(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1}, X_{2},\ldots ,X_{n})]\geq \varepsilon \right)\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1} ^{n}c_{i}^{2}}}\höger),}
P
( f (
X
1
,
X
2
, … ,
X
n
) −
E
[ f (
X
1
,
X
2
, … ,
X
n
) ] ≤ − ε ) ≤ exp
(
−
2
ε
2
∑
i = 1
n
c
i
2
)
,
{\displaystyle {\text{P}}(f(X_{1},X_{2},\ldots ,X_ {n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\leq -\varepsilon )\leq \exp \left(-{\frac { 2\varepsilon ^{2}}{\summa _{i=1}^{n}c_{i}^{2}}}\höger),}
och som en omedelbar konsekvens,
P
(
|
f (
X
1
,
X
2
, … ,
X
n
) −
E
[ f (
X
1
,
X
2
, … ,
X
n
) ]
|
≥ ε ) ≤ 2 exp
(
−
2
ε
2
∑
i = 1
n
c
i
2
)
.
{\displaystyle {\text{P}}(|f(X_{1},X_{2},\ldots,X_{n})-\mathbb {E} [f(X_{1},X_{2} ,\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n} c_{i}^{2}}}\höger).}
Tillägg
Obalanserade fördelningar
En starkare gräns kan ges när argumenten till funktionen samplas från obalanserade distributioner, så att omsampling av ett enstaka argument sällan orsakar en stor förändring av funktionsvärdet.
McDiarmid's Inequality (obalanserad) — Låt
f :
X
n
→
R
{\displaystyle f:{\mathcal {X}}^{n}\rightarrow \mathbb {R} }
c
1
,
c
2
, … ,
c
n
{\displaystyle c_{1},c_{2},\dots ,c_{n}}
Betrakta oberoende slumpvariabler
X
1
,
X
2
, … ,
X
n
∈
X
{\displaystyle X_{1},X_{2},\ldots ,X_{n}\in {\mathcal {X}}}
χ
0
∈
X
{\displaystyle \chi _{0}\in {\mathcal {X}}}
1 − p
{\displaystyle 1-p}
ε >
0
{\displaystyle \varepsilon >0}
P
(
|
f (
X
1
, … ,
X
n
) −
E
[ f (
X
1
, … ,
X
n
) ]
|
≥ ε ) ≤ 2 exp
(
−
ε
2
2 p ( 2 − p )
∑
i = 1
n
c
i
2
+
2 3
e
max
i
c
i
)
.
{\displaystyle {\text{P}}(|f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})] |\geq \varepsilon )\leq 2\exp \left({\frac {-\varepsilon ^{2}}{2p(2-p)\summa _{i=1}^{n}c_{i}^ {2}+{\frac {2}{3}}\varepsilon \max _{i}c_{i}}}\right).}
Detta kan användas för att karakterisera till exempel värdet av en funktion på grafer när den utvärderas på glesa slumpmässiga grafer och hypergrafer , eftersom det i en gles slumpmässig graf är mycket mer sannolikt att någon speciell kant saknas än att den finns.
Skillnader avgränsade med hög sannolikhet
McDiarmids ojämlikhet kan utvidgas till det fall där funktionen som analyseras inte strikt uppfyller egenskapen bounded differences, men stora skillnader förblir mycket sällsynta.
McDiarmid's Inequality (Skillnader avgränsade med hög sannolikhet) — Låt
f :
X
1
×
X
2
× ⋯ ×
X
n
→
R
{\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}} _{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } vara
Y
⊆
X
1
×
X
2
× ⋯ ×
X
n
{\displaystyle {\ mathcal {Y}}\subseteq {\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}}
c
1
,
c
2
, … ,
c
n
≥
0
{\displaystyle c_{1},c_{2},\dots ,c_{n}\geq 0}
(
x
1
, … ,
x
n
) ∈
Y
{\displaystyle (x_{1},\ldots ,x_{n})\in {\mathcal {Y}}}
(
x
1
′
, … ,
x
n
′
) ∈
Y
{\displaystyle (x'_{1},\ldots ,x'_{n})\in {\mathcal {Y}}}
|
f (
x
1
, … ,
x
n
) − f (
x
1
′
, … ,
x
n
′
)
|
≤
∑
i :
x
i
≠
x
i
′
c
i
.
{\displaystyle \left|f(x_{1},\ldots,x_{n})-f(x'_{1},\ldots,x'_{n})\right|\leq \sum _{ i:x_{i}\neq x'_{i}}c_{i}.}
Betrakta oberoende slumpvariabler
X
1
,
X
2
, … ,
X
n
{\displaystyle X_{1},X_{2},\dots ,X_{n}}
X
i
∈
X
i
{\displaystyle X_{i}\in {\mathcal {X}}_{i}}
i
{\displaystyle i}
p = 1 −
P
( (
X
1
, … ,
X
n
) ∈
Y
)
{\displaystyle p=1-\mathrm {P} ((X_{1},\ldots ,X_{n})\in {\ mathcal {Y}})}
m =
E
[ f (
X
1
, … ,
X
n
) ∣ (
X
1
, … ,
X
n
) ∈
Y
]
{\displaystyle m=\mathbb {E} [f(X_ {1},\ldots ,X_{n})\mid (X_{1},\ldots,X_{n})\in {\mathcal {Y}}]}
ε >
0
{\displaystyle \varepsilon >0}
P
(
f (
X
1
, … ,
X
n
) − m ≥ ε
)
≤ p + exp
(
−
2 max
(
0
, ε − p
∑
i = 1
n
c
i
)
2
∑
i = 1
n
c
i
2
)
,
{\displaystyle {\text{P}}\left(f(X_{1},\ldots,X_{n})-m\geq \varepsilon \right)\leq p+\exp \left(-{\frac { 2\max \left(0,\varepsilon -p\sum _{i=1}^{n}c_{i}\right)^{2}}{\sum _{i=1}^{n}c_ {i}^{2}}}\höger),}
och som en omedelbar konsekvens,
P
(
|
f (
X
1
, … ,
X
n
) − m
|
≥ ε ) ≤ 2 p + 2 exp
(
−
2 max
(
0
, ε − p
∑
i = 1
n
c
i
)
2
∑
i = 1
n
c
i
2
)
.
{\displaystyle {\text{P}}(|f(X_{1},\ldots ,X_{n})-m|\geq \varepsilon )\leq 2p+2\exp \left(-{\frac { 2\max \left(0,\varepsilon -p\sum _{i=1}^{n}c_{i}\right)^{2}}{\sum _{i=1}^{n}c_ {i}^{2}}}\höger).}
Det finns starkare förbättringar av denna analys i vissa distributionsberoende scenarier, som de som uppstår i inlärningsteori .
Sub-Gaussiska och subexponentiella normer
Låt
k
{\displaystyle k}:
f
{\displaystyle f}
f
k
( X ) ( x ) := f (
x
1
, … ,
x
k − 1
,
X
k
,
x
k + 1
, … ,
x
n
) −
E
X
k
′
f (
x
1
, … ,
x
k − 1
,
X
k
′
,
x
k + 1
, … ,
x
n
) ,
{\displaystyle f_{k}(X)(x):=f(x_{1},\ldots ,x_{k-1},X_ {k},x_{k+1},\ldots ,x_{n})-\mathbb {E} _{X'_{k}}f(x_{1},\ldots ,x_{k-1} ,X'_{k},x_{k+1},\ldots ,x_{n}),}
så att
f
k
( X )
{\displaystyle f_{k}(X)}
x
1
, … ,
x
k − 1
,
x
k + 1
, … ,
x
n
{\displaystyle x_ {1},\ldots ,x_{k-1},x_{k+1},\ldots,x_{n}}
McDiarmid's Inequality (Sub-Gaussian norm) — Låt
f :
X
1
×
X
2
× ⋯ ×
X
n
→
R
{\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_ {2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} }
X = (
X
1
,
X
2
, … ,
X
n
)
{\displaystyle X=(X_{1},X_{2},\dots ,X_{n})}
X
i
∈
X
i
{ \displaystyle X_{i}\in {\mathcal {X}}_{i}}
i
{\displaystyle i}
Låt
f
k
( X )
{\displaystyle f_{k}(X)}
k
{\displaystyle k}:
f
{\displaystyle f}
‖ ⋅
‖
ψ
2
{\displaystyle \|\cdot \|_{\psi _{2}}}
sub-Gaussiska normen för en slumpvariabel.
Sedan, för alla
ε >
0
{\displaystyle \varepsilon >0}
P
(
f (
X
1
, … ,
X
n
) − m ≥ ε
)
≤ exp
(
−
ε
2
32 e
‖
∑
k ∈ [ n ]
‖
f
k
( X )
‖
ψ
2
2
‖
∞
‖
.
{\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq \exp \left({\frac {-\ varepsilon ^{2}}{32e\left\|\sum _{k\in [n]}\|f_{k}(X)\|_{\psi _{2}}^{2}\right\ |_{\infty }}}\right).}
McDiarmid's Inequality (Sub-exponentiell norm) — Låt
f :
X
1
×
X
2
× ⋯ ×
X
n
→
R
{\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_ {2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} }
X = (
X
1
,
X
2
, … ,
X
n
)
{\displaystyle X=(X_{1},X_{2},\dots ,X_{n})}
X
i
∈
X
i
{ \displaystyle X_{i}\in {\mathcal {X}}_{i}}
i
{\displaystyle i}
Låt
f
k
( X )
{\displaystyle f_{k}(X)}
k
{\displaystyle k}:
f
{\displaystyle f}
‖ ⋅
‖
ψ
1
{\displaystyle \|\cdot \|_{\psi _{1}}}
Sedan, för alla
ε >
0
{\displaystyle \varepsilon >0}
P
(
f (
X
1
, … ,
X
n
) − m ≥ ε
)
≤ exp
(
−
ε
2
4
e
2
‖
∑
k ∈ [ n ]
‖
f
k
( X )
‖
ψ
1
2
‖
2
‖ _ _ _
max
k ∈ [ n ]
‖
‖
f
k
( X )
‖
ψ
1
‖
∞
)
.
{\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq \exp \left({\frac {-\ varepsilon ^{2}}{4e^{2}\left\|\sum _{k\in [n]}\|f_{k}(X)\|_{\psi _{1}}^{2 }\right\|_{\infty }+2\varepsilon e\max _{k\in [n]}\left\|\|f_{k}(X)\|_{\psi _{1}} \right\|_{\infty }}}\right).}
Bennett och Bernstein bildar
Förfiningar av McDiarmids ojämlikhet i stil med Bennetts ojämlikhet och Bernstein-ojämlikheter möjliggörs genom att definiera en variansterm för varje funktionsargument. Låta
B
:=
max
k ∈ [ n ]
sup
x
1
, … ,
x
k − 1
,
x
k + 1
, … ,
x
n
|
f (
x
1
, … ,
x
k − 1
,
X
k
,
x
k + 1
, … ,
x
n
) −
E
X
k
f (
x
1
, … ,
x
k − 1
,
X
k
,
x
k + 1
, … ,
x
n
)
|
,
V
k
:=
sup
x
1
, … ,
x
k − 1
,
x
k + 1
, … ,
x
n
E
X
k
(
f (
x
1
, … ,
x
k − 1
,
X
k
,
x
k + 1
, … ,
x
n
) −
E
X
k
f (
x
1
, … ,
x
k − 1
,
X
k
,
x
k + 1
, … ,
x
n
)
)
2
,
σ ~
2
:=
∑
k = 1
n
V
k
.
{\displaystyle {\begin{aligned}B&:=\max _{k\in [n]}\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\ prickar ,x_{n}}\left|f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right| ,\\V_{k}&:=\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\mathbb {E} _ {X_{k}}\left(f(x_{1},\dots,x_{k-1},X_{k},x_{k+1},\dots,x_{n})-\mathbb { E} _{X_{k}}f(x_{1},\dots,x_{k-1},X_{k},x_{k+1},\dots,x_{n})\right)^ {2},\\{\tilde {\sigma }}^{2}&:=\summa _{k=1}^{n}V_{k}.\end{aligned}}}
McDiarmid's Inequality (Bennett-form) — Låt
f :
X
n
→
R
{\displaystyle f:{\mathcal {X}}^{n}\rightarrow \mathbb {R} }
c
1
,
c
2
, … ,
c
n
{\displaystyle c_{1},c_{2},\dots ,c_{n}}
X
1
,
X
2
, … ,
X
n
{\displaystyle X_{1},X_{2},\dots ,X_{n}}
X
i
∈
X
i
{\displaystyle X_{i}\in {\mathcal {X}}_{i}}
i
{\displaystyle i}
B
{\displaystyle B}
σ ~
2
{\displaystyle {\tilde {\sigma }}^{2}}
Sedan, för alla
ε >
0
{\displaystyle \varepsilon >0}
P
( f (
X1
,
… ,
Xn
−ε2Blog
) −E
[
f (
X1
,
… ,
Xn
≥ε
) ] ) ≤exp ( (
1
Bεσ
2
_
_ _
_
_ _
_ _
_ _
_
_
)
_
+ ~ ) . _ _
{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\ geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon }{2B}}\log \left(1+{\frac {B\varepsilon }{{\tilde {\sigma }}^{2 }}}\eller hur).}
McDiarmid's Inequality (Bernstein-form) — Låt
f :
X
n
→
R
{\displaystyle f:{\mathcal {X}}^{n}\rightarrow \mathbb {R} }
c
1
,
c
2
, … ,
c
n
{\displaystyle c_{1},c_{2},\dots ,c_{n}}
B
{\displaystyle B}
σ ~
2
{\displaystyle {\tilde {\sigma }}^{2}}
Sedan, för alla
ε >
0
{\displaystyle \varepsilon >0}
P
( f (
X1
,
… ,
Xn
−ε22
) −E
[
f (
X1
2
, … ,
Xn
(
) ] ≥ε ) ≤exp (
_
σ
_
_
_
_
_
_
+
_
Bε3
_
_
_
_
~ ) ) . _
{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\ geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon ^{2}}{2\left({\tilde {\sigma }}^{2}+{\frac {B\varepsilon }{ 3}}\right)}}\right).}
Bevis
Följande bevis på McDiarmids ojämlikhet konstruerar Doob-martingalen som spårar det villkorliga förväntade värdet av funktionen när fler och fler av dess argument samplas och betingas, och sedan tillämpar en martingalkoncentrationsojämlikhet ( Azumas ojämlikhet) . Ett alternativt argument som undviker användningen av martingaler finns också, som drar fördel av funktionsargumentens oberoende för att tillhandahålla ett Chernoff-bundet -liknande argument.
För bättre läsbarhet kommer vi att introducera en notationsstenografi:
z
i ⇁ j
{\displaystyle z_{i\rightharpoondown j}}
z
i
, … ,
z
j
{\displaystyle z_{i},\dots ,z_{j} }
z ∈
X
n
{\displaystyle z\in {\mathcal {X}}^{n}}
1 ≤ i ≤ j ≤ n
{\displaystyle 1\leq i\leq j\leq n} ,
f (
X1⇁
)
+
( i − 1 )
, y ,
x
( i
−
1 ) ⇁n
,
)
Xi
:
1
,
= f (
X1
xi
, … , y ,
xn
+ 1
_
, … . _
_
_
_ _
{\displaystyle f(X_{1\rightharpoondown (i-1)},y,x_{(i+1)\rightharpoondown n}):=f(X_{1},\ldots ,X_{i-1}, y,x_{i+1},\ldots ,x_{n}).}
Välj valfri
x
1
′
,
x
2
′
, … ,
x
n
′
{\displaystyle x_{1}',x_{2}',\ldots ,x_{n}'}
x
1
,
x
2
, … ,
x
n
{\displaystyle x_{1},x_{2},\ldots ,x_{n}} ,
triangelolikhet ,
|
f (
x
1 ⇁ n
) − f (
x
1 ⇁ n
′
)
|
≤
|
f (
x
1 ⇁ n
) − f (
x
1 ⇁ ( n − 1 )
′
,
x
n
)
|
+
cn
_
≤
|
f (
x
1 ⇁ n
) − f (
x
1 ⇁ ( n − 2 )
′
,
x
( n − 1 ) ⇁ n
)
|
+
c
n − 1
+
c
n
≤
…
≤
∑
i = 1
n
c
i
,
{\displaystyle {\begin{aligned}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown n})|\\[6pt]\leq {}&|f(x_{1\rightharpoondown \,n})-f(x'_{1\rightharpoondown (n-1)},x_{n})| +c_{n}\\\leq {}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown (n-2)},x_{(n-1)\rightharpoondown n })|+c_{n-1}+c_{n}\\\leq {}&\ldots \\\leq {}&\summa _{i=1}^{n}c_{i},\end {Justerat}}}
och därmed är
f
{\displaystyle f}
Eftersom
f
{\displaystyle f}
{
Z
i
}
{\displaystyle \{Z_{i}\}}
Z
i
{\displaystyle Z_{i}}
X
1
, … ,
X
i
{\displaystyle X_{1},\ldots ,X_{i}} )
Z
i
:=
E
[ f (
X
1 ⇁ n
) ∣
X
1 ⇁ i
]
{\displaystyle Z_{i}:=\mathbb {E} [f(X_{1\rightharpoondown n})\mid X_{1\ högerharpundown i}]}
för alla
i ≥ 1
{\displaystyle i\geq 1}
Z
0
:=
E
[ f (
X
1 ⇁ n
) ]
{\displaystyle Z_{0}:=\mathbb {E} [f(X_{1\rightharpoondown n })]}
Z
n
= f (
X
1 ⇁ n
)
{\displaystyle Z_{n}=f(X_{1\rightharpoondown n})}
Definiera nu de slumpmässiga variablerna för varje
i
{\displaystyle i}
U
i
:=
sup
x ∈
X
i
E
[ f (
X
1 ⇁ ( i − 1 )
, x ,
X
( i + 1 ) ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
,
X
i
= x ] −
[
f (
X
1 ⇁ ( i − 1 )
,
X
i ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
] ,
L
i
:=
inf
x ∈
X
i
E
[ f (
X
1 ⇁ ( i - 1 ) )
, x ,
X
( i + 1 ) ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
,
X
i
= x ] −
[
f (
X
1 ⇁ ( i − 1 )
,
X
i ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
] .
{\displaystyle {\begin{aligned}U_{i}&:=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i) -1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{ 1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&:=\inf _{x\in { \mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1 \rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\ rightharpoondown (i-1)}].\\\end{aligned}}}
Eftersom
X
i
, … ,
X
n
{\displaystyle X_{i},\ldots ,X_{n}}
X
i
= x
{\displaystyle X_{i}=x}
U
i
=
sup
x ∈
X
i
E
[ f (
X
1 ⇁ ( i − 1 )
, x ,
X
( i + 1 ) ⇁ n
) − f (
X
1 ⇁ ( i − 1 )
,
X
i ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
] ,
Li
=
inf
x ∈
X
i
E
[ f (
X
1 ⇁
n
i - 1 )
( , x ,
X
( i + 1 ) ⇁
⇁
) − f (
X
1
( i ) − 1 )
,
X
i ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
] .
{\displaystyle {\begin{aligned}U_{i}&=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i- 1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i) -1)}],\\L_{i}&=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1) )},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i- 1)}].\\\end{aligned}}}
Observera att
}
Li
≤
Z
i
−
Z
i − 1
≤
U
i
{\displaystyle L_{i}\leq Z_{i}-Z_{i-1}\leq U_{i}
U
i
−
L
i
=
sup
u ∈
X
i
, ℓ ∈
X
i
E
[ f (
X
1 ⇁ ( i − 1 )
, u ,
X
( i + 1 ) ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
] −
E
[ f (
X
1 ⇁ ( i − 1 )
, ℓ ,
X
( i + 1 ) ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
]
=
sup
u ∈
X
i
, ℓ ∈
X
i
E
[ f (
X
1 ⇁ ( i − 1 )
, u ,
X
( i + 1 ) ⇁ n
) − f (
X
1 ⇁ ( i − 1 )
, l ,
X
( i + 1 ) ⇁ n
) ∣
X
1 ⇁ ( i − 1 )
]
≤
sup
x
u
∈
X
i
,
x
l
∈
X
i
E
[
c
i
∣
X
1 ⇁ ( i − 1 )
]
≤
c
i
{\displaystyle {\begin{aligned}U_{i}-L_{i }&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\ rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]-\mathbb {E} [f(X_{1\rightharpoondown (i-1)},\ell ,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u, X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},l,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i) -1)}]\\&\leq \sup _{x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}} \mathbb {E} [c_{i}\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&\leq c_{i}\end{aligned}}}
Om vi sedan tillämpar den allmänna formen av Azumas ojämlikhet på
{
Z
i
}
{\displaystyle \left\{Z_{i}\right\}} ,
P
( f (
X
1
, … ,
X
n
) −
E
[ f (
X
1
, … ,
Xn
exp
) ] ≥ ε ) = P (
Zn
(
−
Z
0
≥ ε ) ≤
_
−
2
ε
2
∑
i
= 1nci2
_
_
_
_
)
_ .
{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\ geq \varepsilon )=\operatörsnamn {P} (Z_{n}-Z_{0}\geq \varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{ i=1}^{n}c_{i}^{2}}}\höger).}
Den ensidiga gränsen i den andra riktningen erhålls genom att tillämpa Azumas olikhet på
{
−
Z
i
}
{\displaystyle \left\{-Z_{i}\right\}}
unionsbunden .
◻
{\displaystyle \square }
Se även
![{\displaystyle i\in [n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b389a8f1ad8a43d2bcf5194acf34e934f806311)
![{\displaystyle {\text{P}}\left(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\geq \varepsilon \right)\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dcec32c891eaf7e6f8fb7c99d8749928ad1636e1)
![{\displaystyle {\text{P}}(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\leq -\varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e8acf5ba6be8dd3cf27f282bc328b17bfd23a93)
![{\displaystyle {\text{P}}(|f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a60a6951869cfdf72d6bf5c6f1f2f2b38abef530)
![{\displaystyle {\text{P}}(|f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left({\frac {-\varepsilon ^{2}}{2p(2-p)\sum _{i=1}^{n}c_{i}^{2}+{\frac {2}{3}}\varepsilon \max _{i}c_{i}}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/855bb934c5e7f34c95fa713da1fd5e828ad36d07)
![{\displaystyle m=\mathbb {E} [f(X_{1},\ldots ,X_{n})\mid (X_{1},\ldots ,X_{n})\in {\mathcal {Y}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c965758a80ff46edb71c1959ec2d13526340986b)
![{\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq \exp \left({\frac {-\varepsilon ^{2}}{32e\left\|\sum _{k\in [n]}\|f_{k}(X)\|_{\psi _{2}}^{2}\right\|_{\infty }}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40a7e2c7fc75956f303ed25c04ee7b1bf107ca93)
![{\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq \exp \left({\frac {-\varepsilon ^{2}}{4e^{2}\left\|\sum _{k\in [n]}\|f_{k}(X)\|_{\psi _{1}}^{2}\right\|_{\infty }+2\varepsilon e\max _{k\in [n]}\left\|\|f_{k}(X)\|_{\psi _{1}}\right\|_{\infty }}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70ee2d217ef648fe22a5cf860623582e53091c4c)
![{\displaystyle {\begin{aligned}B&:=\max _{k\in [n]}\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\left|f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right|,\\V_{k}&:=\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\mathbb {E} _{X_{k}}\left(f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right)^{2},\\{\tilde {\sigma }}^{2}&:=\sum _{k=1}^{n}V_{k}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/312deb5dc1b54e6b3c651089e825980a2443a6a6)
![{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon }{2B}}\log \left(1+{\frac {B\varepsilon }{{\tilde {\sigma }}^{2}}}\right)\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7704caf7a037657bf4a425383f9885ca8a7596e6)
![{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon ^{2}}{2\left({\tilde {\sigma }}^{2}+{\frac {B\varepsilon }{3}}\right)}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea6a82ec74188846989046b43328b95a5eaa0a12)
![{\displaystyle {\begin{aligned}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown n})|\\[6pt]\leq {}&|f(x_{1\rightharpoondown \,n})-f(x'_{1\rightharpoondown (n-1)},x_{n})|+c_{n}\\\leq {}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown (n-2)},x_{(n-1)\rightharpoondown n})|+c_{n-1}+c_{n}\\\leq {}&\ldots \\\leq {}&\sum _{i=1}^{n}c_{i},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8a3d4618dccde1175f60e840012985638c2eb28)
![{\displaystyle Z_{i}:=\mathbb {E} [f(X_{1\rightharpoondown n})\mid X_{1\rightharpoondown i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d282a3f3a353ad3afae9d483afcc6fbc0e62f27b)
![{\displaystyle Z_{0}:=\mathbb {E} [f(X_{1\rightharpoondown n})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cef2ef327bad57acbfa735e645bd71bab6461f01)
![{\displaystyle {\begin{aligned}U_{i}&:=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&:=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6308d303b73a83754d872be0edcc317e817bea53)
![{\displaystyle {\begin{aligned}U_{i}&=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b12e9453887e3a63e513cc3eb6d88641987f6fe0)
![{\displaystyle {\begin{aligned}U_{i}-L_{i}&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]-\mathbb {E} [f(X_{1\rightharpoondown (i-1)},\ell ,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},l,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\&\leq \sup _{x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}\mathbb {E} [c_{i}\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&\leq c_{i}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4575c944d2aa6f26072f96a149dac22fa66cf81)
![{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )=\operatorname {P} (Z_{n}-Z_{0}\geq \varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a5a67a03307a7983380121343d55e057618ac43)
