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