STA Chapter2 part1 - nsasakiの勉強メモ

Sublinear Time Algorithms Lecture2

やる内容

Chernoff bound
Estimating the number of connected components
Estimating the weight of the minimum spanning tree

Chernoff bound

Let $X_{1},X_{2},\ldots,X_{m}$ be m independent identically distributed random variables such that $X_{i} \in \left[ 0,1 \right]$ .
$\mathrm{Let} \;\; S = \sum_{i=1}^{m} X_{i}\;\; \mathrm{and} \;\; p = E\left[ X_{i} \right] = \frac{E \left[ S \right]}{m}.$
Then,
$Pr \left( |{\frac{s}{m} - p| \geq \delta p \right) \leq e^{-\Omega\big( m p \delta^2\big)} .$

ってわかるか！と、
もとの資料がさくっとしか書いていなかったので、調べた事を。

Chernoff bound

確率論における確率の上限を与える不等式
前述の式はm個のサンプリングの点をとったとき、それが本当の平均とδ以上割合ずれる確率が指数関数で抑えられるという話。
確率の上限を与える不等式として、

Marcovの不等式
Chevyshefの不等式
Chernoff bound

の三つの話をする。

Marcovの不等式

Xを非負の確率変数とする。任意のa>0に対し、
$Pr \left( X \ge a \right) \le \frac{E \left[ X \right]}{a}$
が成り立つ。

証明

a>0に対し、
$I = \left{ 1 \;\; X \ge a \\ 0 \;\; else$
$X \ge a, a> 0$ より
$I \le \frac{X}{a}$
$E \left[ I \right] = Pr \left( I = 1 \right) = Pr \left( X \ge a \right)$
平均をとると
$Pr \left( X \ge a \right) = E\left[ I \right] \le E \left[ \frac{X}{a} \right] = \frac{ E\left[ X \right]}{a}$

Chebyshevの不等式

任意のa>0に対し
$Pr \left( | X - E\left[ X \right] | \right) \le \frac{Var \left[ X \right]}{a^{2}}$
が成り立つ。

証明

$Pr \left( | X - E\left[ X \right] | \ge a \right) = Pr \left( | X - E\left[ X \right] |^{2} \ge a^{2} \right)$
Marcovの不等式より
$Pr \left( | X - E\left[ X \right] |^{2} \ge a^{2} \right) \le \frac{E\left[ \left( X - E\left[ X \right] \right)^{2} \right]}{a^{2}} = \frac{Var \left[ X \right]}{a^{2}}$

ちなみにこの不等式から大数の法則が導ける.(大雑把に言うと、サンプルの数を増やせば増やす程サンプルの平均は理論上の平均に近くなるという話)

Chernoff bound

確率変数Xの積率母関数
$M_{X}(t) = E \left[ exp{tX} \right]$
を定義する。

Xの生じる確率をpとすると
$\begin{align} M_{X}(t) & = & E \left[ exp{tX} \right] \\ & = & p exp{t} + \left( 1 - p \right) \\ & = & 1 + p \left( exp{t} - 1 \right)\\ & \le & e^{p \left( e^{t} - 1 \right) } \end{align}$
任意のt > 0 に対して、
$Pr \left( X \ge a \right) = Pr \left( exp{tX} \ge exp{ta} \right) \le \frac{E \left[ exp{tX} \right]}{exp{a}}$
任意のt<0に対して、
$Pr \left( X \le a \right) = Pr \left( exp{tX} \ge exp{ta} \right) \le \frac{E \left[ exp{tX} \right]}{exp{a}}$
ここで、
$X_{1},X_{2},\ldots,X_{m}$ を互いに独立で同一の分布に従うランダムに選んだm個のサンプルとする。 $X_{i} \in \left[ 0,1 \right]$ .
$Pr \left( X_{i} = 1 \right) = p_{i}$ とし、 $S = \sum_{i=1}^{m} X_{i}\;\; \mathrm{and} \;\; p = E\left[ X_{i} \right] = \frac{E \left[ S \right]}{m}$ . とする。
任意のδ>0に対して、
$\begin{align} Pr \left( \frac{S}{m} \ge \left( 1 + \delta \right) p \right) & = & Pr \left( S \ge \left( 1 + \delta \right) mp \right) \\ & = & Pr \left( exp{tS} \ge exp{ \left( 1 + \delta \right) mtp} \right) \\ & \le & \frac{E \left[ exp{tS} \right] }{exp{\left( 1 + \delta \right) mtp}} \\ & \le & \frac{exp{\left( e^{t} - 1 \right) mp}}{exp{\left( 1 + \delta \right) mtp}} \end{align}$
$t= \log{\left( 1 + \delta \right) } > 0$ と設定し、式を整理すると
$Pr \left( \frac{S}{m} \ge \left( 1 + \delta \right) p \right) \le \left( \frac{exp{\delta}}{\left( 1 + \delta \right)^{\left( 1 + \delta \right)}} \right)^{mp}$
特に $0 < \delta \le 1$ について、
$\frac{exp{\delta}}{\left( 1 + \delta \right)^{\left( 1 + \delta \right)}} \le exp{-\frac{\delta^{2}}{3}}$
が成立する。(対数とって右辺引く左辺をして微分をしたら確かめられる)
ここから、
$Pr \left( \frac{S}{m} \ge \left( 1 + \delta \right) p \right) \le exp{ - \frac{m\delta^{2}p}{3}$
が成立する。
$Pr \left( \frac{S}{m} \le \left( 1 - \delta \right) p \right)$ についても同様に考えると、
$Pr \left( \frac{S}{m} \le \left( 1 - \delta \right) p \right) \le \left( \frac{exp{\delta}}{\left( 1 - \delta \right)^{\left( 1 - \delta \right)}} \right)^{mp} \le exp{ - \frac{m\delta^{2}p}{2} }$
以上より、
$Pr \left( | \frac{S}{m} - p | \ge \delta p \right) \le exp{ - \Omega \left( m\delta^{2}p \right) }$
となる。