Sen(Qian)’s Memo

参考: https://ludu-vorton.hatenablog.com/entry/2019/06/06/073000#チェルノフ上界Chernoff-bounds

モーメント母関数によって、定義されている。

確率変数$Z$について、$M_Z(\lambda) = \mathbb{E}[e^{\lambda Z}]$であること。$\lambda$で1階微分すると期待値、2階微分すると分散が得られる。ここでは$\lambda$だが、よく$t$ともかかれる。

ここで、$M_{Z - \mathbb{E}[Z]}$とは、モーメント母関数の確率変数が$Z$ではなく代わりに$Z-\mathbb{E}[Z]$であるということであり、$\mathbb{E}[e ^ {\lambda(Z - \mathbb{E}[Z])}]$である。

$\exist \lambda \geq 0$を取る。すると、指数関数は単調増加なので、同様に$Z \geq \mathbb{E}[Z] + t \Leftrightarrow \exp(\lambda Z) \leq \exp(\lambda (\mathbb{E}[Z] + t))$が成り立つ。

次に両辺を、$\exp(\lambda \mathbb{E}[Z])$で割ると、これ自体は正なので不等号の向きが変わらず以下のようになる。

最後、マルコフの不等式を使った。ここでは、$Pr[Z \geq t] \leq \frac{\mathbb{E}[Z]}{t}$である。

$X_i \in [0, 1]$で互いに独立であり、$X = \sum_{i=1}^n X_i$である。この時、以下が成り立つ。

ここで、$Z$は確率変数であり、$m_Z(s)$はモーメント母関数。

$X_i$がベルヌーイ分布、$X$がガウシアンと仮定する。

$\mathbb{R}$上の分布$D$について、$F: \mathbb{R} \to [0,1]$を$D$の累積分布関数だとする。そこで、$F(a)=1/2$となる中央値$a$を知りたい。

$\forall \epsilon, \delta > 0$であり、$s = O(\frac{\log (1/\delta)}{\epsilon^2})$個のサンプルが得られるとする。この時、サンプルからの経験的な中央値は、少なくとも$1 - \delta$以上の確率で$[F^{-1}(1/2 - \epsilon), F^{-1}(1/2 + \epsilon)]$が成り立つ。

気持ちとして、累積分布関数の値域で、$1/2 \pm \epsilon$となる確率を評価している感じ。

$X_i$という確率変数を、$i$番目のサンプルが$F^{-1}(1/2 - \epsilon)$より小さいならば1、それ以外ならば0とする。$X=\sum X_i$とする。

この時、$\mathbb{E}[X_i] = 1/2 - \epsilon$となる(それはそう)。これがサンプル$s$個あるとなっているので、全体では、$\mathbb{E}[X] = \sum (1/2 - \epsilon) = (1/2-\epsilon)s$である。

ここで、チェルノフ上界を用いて、$1/2-\epsilon$より小さい値=理想的な中央値から外れるサンプルの数の上界を抑える。

そして、$(1 + \epsilon)\mathbb{E}[X] = (1 + \epsilon)(1/2-\epsilon) \leq s/2$であるから、上のチェルノフ上界での評価は以下のようになる。

これはまさに経験中央値が越える確率を抑えるというもので、同様に及ばないのも$\frac{\delta}{2}$未満であるので、これで示せた。

Boostingという、成功確率が$1/2 + \epsilon$となるアルゴリズムを、$1 - \delta$以上の確率で成功するまで上げていく運用法がある。

ある確率変数$X$が$2/3$以上の確率で、$X \in I$を満たすとする。

この時、$X$を$O(\log(1 / \delta))$回サンプリングしたときの経験中央値は$1-\delta$以上の確率で$I$に含まれる。

まず、$\forall k>1$について、乱択クイックソートの比較回数は$32 k n\log n$回以下である確率は、$1-\frac{1}{n^{k-1}}$以上である。つまり、$k$回アルゴリズムを走らせたら、すごい速度でソートが失敗する確率が下がっていく。

$X_i$を、A[i]の深さを示す確率変数だとする。クイックソートでいう比較回数は深さに依存している。pivotに選ばれるのが遅いとどんどん深さが増えていくし、深さがその値が他のpivotとの比較された回数である。

よって、この時比較回数は$\sum_{i=1}^n X_i$である。

再帰呼び出しを考える。pivotは$t \in [0, |A_j|)$から一様に選んでいる。

「バランスが取れている」をpivotがAをソートした後に、真ん中の1/3に入っている$\frac{1}{3}|A_j| \leq t \leq \frac{2}{3} |A_j|$であるということ。これの確率は$1/3$以上である。

バランスしていると、次の再帰を考えるとき、真ん中の$1/3$に入っているので、どう悪くても文カチした両方のうち大きい方でも2/3以下なので、$|A_{j+1}| \leq \frac{2}{3} |A_j|$である。

次に、$Y_i$を$A_j$において「バランスが取れている」なら1、それ以外なら0とする。

$\mathbb{E}[Y_i] \geq 1/3$で、$Y_i$はそれぞれ独立である。

$d=32 k \log n, Y = \sum_{j=1}^d Y_j$として、$\mathbb{E}[y] \geq d/3$である。