McDiarmidの不等式(小記事)

確率集中不等式の文脈でよく知られているMcDiarmidの不等式について解説します. 

準備: 集中不等式でよくある設定

$S$を集合として$X_1,\dots,X_n\in S$を$S$に値をとる独立な確率変数とします (同一分布に従うとは限らない). 関数 $f\colon S^n\to\mathbb{R}$に対し, 確率変数$Y=f(X_1,\dots,X_n)$を考えます. 例として$S=[0,1]$, $f(x_1,\dots,x_n)=x_1+\dots+x_n$とすると, Hoeffdingの不等式より$Y$はその期待値に集中します. つまり, 任意の$t>0$に対して

$$\Pr[|Y-\mathrm{E}[Y]|>t] \leq 2\exp\left(-\frac{2t^2}{n}\right)$$

が成り立ちます.

これを一般化して次のresearch questionを考えます:

関数$f$がどのような性質を持てば$Y$は集中性が成り立つのか?

結論から言うと, 次の法則が知られています.

$f$が"滑らか"ならば$Y$は集中する.

"滑らか"とはどういうことか, については色んな定義が考えられますが, ひとまずこの法則の根拠となる不等式の一つとしてMcDiarmidの不等式という便利な不等式があります.

McDiarmidの不等式

この不等式では関数の滑らかさをハミング距離に関するリプシッツ性と捉えます. $x,y\in S^n$に対してそのハミング距離$d_{\mathrm{ham}}(x,y)$を異なる要素の個数, すなわち$d_{\mathrm{ham}}(x,y)=|\{i\in[n]\colon x_i\neq y_i\}|$と定義します. 

定理 (McDiarmidの不等式)

関数$f\colon S^n\to \mathbb{R}$が, $d_{\mathrm{ham}}(x,y)=1$を満たす任意の$x,y\in S^n$に対し$|f(x)-f(y)|\leq L$を満たすとする. $X_1,\dots,X_n\in S$を独立な確率変数とし, $Y=f(X_1,\dots,X_n)$とする. このとき,

$$\Pr[|Y-\mathrm{E}[Y]|>t] \leq 2\exp\left( -\frac{2t^2}{nL^2} \right).$$

つまり, $f(x_1,\dots,x_n)$に対して一つの要素$x_i$を別の値に置き換えてもその時の$f$の値がほとんど変わらない(i.e., $L$が小さい)ならば$Y$はその期待値に集中するということを主張する定理です. 例えば冒頭で見た例 $S=[0,1]$, $f(x_1,\dots,x_n)=x_1+\dots+x_n$ ならば, 一つの要素$x_i\in [0,1]$を別の要素 $x'_i\in [0,1]$に置き換えたとしても関数値は高々$1$しか変化しないので, $L=1$としてMcDiarmidの不等式を適用するとHoeffdingの不等式が得られます (より一般に$S=[a,b]$という設定でも得られます).

McDiarmidの不等式の証明は関数$f(x_1,\dots,x_n)$に対するDoobのマルチンゲールを考え, それにAzuma--Hoeffdingの不等式を適用させるだけで得られるので, それほど難しくはありません.