The Second Moment (The Probabilistic Method, Chapter 4)
- 基本アイディア
- X の分布があまり大きくないので,ほとんどの場合 X≒Y,のようなことを証明
- どのようなときにそうなるのか?
- Chebyshev's Inequality
- 分散,標準偏差 $\sigma$
- $Pr[|X - E[X]| \geq \lambda \sigma] \leq \lambda^{-2}$
- これを使うことを,second moment method と言うらしい
- 共分散 Cov[X, Y] = E[XY] - E[X]E[Y]
- 独立なら 0
- 確率 $p_i$ で 0, 1 をとる $X_i$ の和 $X$
- $Var[X] \leq E[X] + \sum Cov[X_i, X_j]$
- 例 v(n):n を割る素数の数
- Theorem: ln ln n にとても近い
-
- 例 G(n, p) の clique number ω(G)
- k-clique の個数は簡単に計算できる
- ω(G) ≧ k0 (2 log n ぐらい)
- おまけ(今回の証明手法とは関係ない):Pr[ω(G) = k0 or k0+1] → 1