Dániel Paulin (National University of Singapore)
Mcdiarmid koncentrációs egyenlőtlensége, és kapcsolata a Markov láncokkal.
<br><br>
Mcdiarmid koncentrációs egyenlőtlensége:
Legyenek X_1,...,X_n független valószínűségi változók, X=(X_1,...,X_n),
f: R^n ->R függvény amire teljesül hogy |f(x)-f(y)|<=c_i ha x és y csak az
i. koordinátában tér el, akkor
<br><br>

P(f(X)>E(f(X))+t)<=exp(-t^2/(sum c_i^2))
P(E(f(X))-t>f(X))<=exp(-t^2/(sum c_i^2))
<br><br>

Sourav Chatterjee bizonyítása felcserélhető valószínűségi változókra és
Markov láncokra épül, és általánosítható olyan esetekre is, amikor
X_1,...,X_n összefüggő.