chap4.1-4.2

Probabilistic Method
4章 The Second Moment
分散を扱います．
4.1 BASICS
定義
分散
また，以下では
u : 期待値
s2 : 分散
s : 標準偏差(分散の正の平方根)
とすることが多い．
チェビシェフの不等式
定理4.1.1[チェビシェフの不等式]
任意の正の数に対し，
(証明)
□
共分散
であるとき，varx
は次式で計算される．
ここで，cov
はYとZの共分散であり，
次式で定義される．
Y,Zが独立であるとき，covyz=0
である．
4.2 NUMBER THEORY
second moment method を数論に用いる．
nu(n): nを割り切る素数の数(重複は数えない)
e.g. nu(12) = nu(2^2 * 3) = 2
定理4.2.1
\omega arbitrarily slowly のとき，
をみたすx\in{1,…,n} の数はo(n)．
定理 4.2.1 の証明の流れ
1. Nux に近い値をとる確率変数Xを定義
2. E[x]=s^2=\ln\ln n+O(1) ，
var[x]=s^2=\ln\ln n+O(1) を計算
3. チェビシェフの不等式
を利用
定理4.2.1
\omega arbitrarily slowly のとき，
をみたすx\in{1,…,n} の数はo(n)．
定理4.2.1 – 確率変数の定義
(証明)nux に近い値をとる確率変数Xを定義する．
とし，以下のようにM,Xを定める．
(10は適当な(大きな)定数)
x<=nのMより大きい素因数は高々10個なので
以下では
の代わりにXを用いて計算
定理4.2.1 – 期待値の計算
(
“well-known fact”である
より)
を用いた．
定理4.2.1 – 分散の計算(1)
定義より，
まず，
を計算する．
定理4.2.1 – 分散の計算(2)
次に，
を計算する．
似たような計算により，
従って，
定理4.2.1 – チェビシェフの不等式
，
チェビシェフの不等式
，
より，
に対して，
また，
が成り立つ．
定理4.2.1
\omega arbitrarily slowly のとき，
をみたすx\in{1,…,n} の数はo(n)．
□
定理 4.2.2 の証明の流れ
1. \nuに近い値をとる確率変数Xを定義
2. 中心極限定理を利用するため，
Xを理想化した確率変数Yを定義
3. Yが正規分布に近づく
4. XがYに近づく
5. \nuも正規分布に近づく
定理4.2.2
が正または負または0のとき
X～N(μ,σ)のとき
定理4.2.2 – 確率変数の定義
(証明)ν(x)に近い値をとる確率変数Xを定義
後の計算の都合から，M,s(n)を次のようにおく
但し，
かつ
定理4.1.1の証明と同様に，
定理4.2.2 – 確率変数の理想化
Xは互いに独立でない確率変数の和
→中心極限定理が使えない
そこで，独立な確率変数の和からなるように
Xを理想化したYを定義
定理4.2.2 – 中心極限定理
Yは互いに独立な確率変数の和であるので，
とすると，中心極限定理より
はN(0,1)に近づき，
定理4.2.2 – モーメント(1)
は係数
のXの多項式であり，
を用いてさらに展開すると
より
個の
の形をした項が得られる．
と
であるので
より
．
定理4.2.2 – モーメント(2)
従って，
の各モーメント
が
であるので，
に近づき，
さらに
“a standard, though nontrivial, theorem in probability theory”
により，
はN(0,1)に近づく．よって
となる．
より
．但し，
□
定理4.2.2
が正または負または0のとき

Download Report