プログラミング初心者の勉強日記

情報科学専攻です. 機械学習と競技プログラミングについて日々勉強しています.

MENU

確率論の大定理:大数の法則、チェビシェフの不等式

本記事は確率論の基本定理の一つである大数の法則 (law of large numbers) についての紹介記事です.

まず、大数の法則を説明するために必要な確率変数列の収束の概念をいくつか紹介して、そのあとに大数の法則の説明に入りたいと思います.

また、最後に大数の法則をシミュレーションしてみたのでその結果とソースコードも載せておきます.

1. 確率収束

  • 定義 : 確率変数列 X_1, X_2, \cdotsが確率変数X確率収束するとは、任意の\epsilon > 0に対して、

$$ \lim_{n \to \infty} P(|X - X_n| > \epsilon) = 0 $$

が成り立つことです. 確率変数をサンプルし続けると段々とある確率変数Xに近づいていき、外れ値を取りづらくなることを表しています. しかし、ある点を境にXと一致してそれ以降もXを取り続けることを表しているわけではないので、私たちが一般的に習う収束とは少し違った概念となっています.

 X_n \xrightarrow{P} X (n \rightarrow \infty) と表します.

2. 概収束

  • 定義 : 確率変数列X_1, X_2, \cdotsが確率変数X概収束 (または、確率1収束する)とは、

$$ P(\lim_{n \to \infty} X_n = X) = 1 $$

が成り立つことです.

確率収束はX_nが段々Xに近くことを表していましたが、X_nが同じ値を取り続ける保証はなく、わずかながら外れ値を取る可能性が常に存在しています. 一方概収束はそのようなX_nは次第にXと収束することを表しています.

 X_n \xrightarrow{a.s.} X (n \rightarrow \infty)と表します.

また、概収束の方が、確率収束よりも厳しい条件なので、概収束が成り立つならば、確率収束も成り立ちます. しかし、逆は必ずしも言えるわけではありません.

3. 確率収束と概収束の例

Wikipediaにわかりやすい例があったので引用させていただきます.

確率収束 人に弓を持たせて、的をめがけて矢を射させる作業を考えます. X_nn回までの成績とします. 何年もこの作業を繰り返し続ければ、その人の腕前は向上し、的の中心を射抜いて10点の成績を得ることも起こりやすくなるはずです. 逆にその人が10点以外の成績を取る可能性は低くなるはずです. したがってX_nX = 10確率収束します.
しかし、X_nX概収束はしません. その人がどんなに腕前を向上したからといって、失敗する可能性もわずかながら存在しているからです. したがって確率変数列は定常状態になることは決してありません.
概収束 動物が毎日に摂る食事の数量を記録します. この数量の列は予測不可能ですが、その値がゼロとなる日は「確かに必ず」訪れます. その後、その値は永遠にゼロを取り続けます. したがって、この食事の数量を表す列はX = 0概収束します.

4. チェビシェフの不等式

大数の弱法則を導くためにチェビシェフの不等式を導入します.

チェビシェフの不等式は、任意の確率変数の値の平均と分散との関係について表した次のような不等式のことを言います.

Xが平均\mu、分散\sigma^{2}の確率分布に従う時、任意の\epsilonに対して、

{\displaystyle
P(|X - E(X)| \geq \epsilon) \leq \frac{\sigma^{2}}{\epsilon^{2}}
}

簡単な証明

マルコフの不等式を用いた証明もありますが、今回は簡単な証明を紹介します.

今回は連続型の確率変数について考えますが、離散型についても同様の考え方ができます.

ここで、A = \{x_i \; |x_i - \mu| \geq \epsilon \}となる範囲Aを定義します. そうすると、

{\displaystyle \sigma^{2} = \int_{-\infty}^{\infty} (x - \mu)^{2} f(x) dx \geq  \int_{x \in A} (x - \mu)^{2} f(x) dx \geq \int_{x \in A} \epsilon^{2} f(x) dx }

{\displaystyle =\epsilon^{2} \int_{x \in A} f(x) dx = \epsilon^{2} P(|X - \mu| \geq \epsilon)}

となります.

この両辺を\epsilon^{2}で割るとチェビシェフの不等式が得られます.

5. 大数の弱法則および強法則

同じ条件の下で、独立に多数回の試行の結果としてえられる標本平均は、試行回数を増やすと一定の値 (母平均) に収束します. これを大数の法則と呼びます.

大数の法則を上で紹介した確率変数の収束を用いて表すと以下のようになります.

X_1, X_2 \cdotsが期待値 \mu = E(X_1) = E(X_2) = \cdotsを持つとします. この時、

$$ \frac{\sum_{i = 1}^{n} X_i}{n} \xrightarrow{a.s.} \mu (n\rightarrow \infty) $$

大数の強法則と呼び、

$$ \frac{\sum_{i = 1}^{n} X_i}{n} \xrightarrow{P} \mu (n \rightarrow \infty) $$

大数の弱法則と呼びます.

ここでは、チェビシェフの不等式を用いて大数の弱法則について証明します.

大数の弱法則の証明

X_1, X_2, \cdots X_nが同じ平均と分散を持つ独立な確率変数の時、\overline{X} = \sum_{i = 1}^{n} X_iの平均と分散はそれぞれ、\mu\frac{\sigma^{2}}{n}となります. このとき、チェビシェフの不等式より、

{\displaystyle
P(|\overline{X} - E(\overline{X}|) \geq \epsilon) = P(|\overline{X} - \mu | \geq \epsilon) \leq \frac{\sigma^{2}}{n \epsilon^{2}} } となります.

 n \rightarrow \inftyとすると右辺は0に収束します. 以上より大数の弱法則が成り立つことが証明できました.

したがって、標本平均はnを大きくしていくと母平均\muに近づくと言えます.

6. 実装例

pythonで大数の法則の可視化をしたので以下にソースコードと実行例を載せておきます.

今回、母数をp = 0.6のベルヌーイ分布に従う確率変数X_1, X_2, \cdots X_{10000}をサンプルします.

X_n = \frac{\sum_{i = 1}^{n} X_i}{n}とすると、大数の弱法則より、

$$ X_n \xrightarrow{P} E(X_1) = p $$

が成り立ちます.

したがって、X_k = \frac{\sum_{i = 1}^{k} X_i } {k}kを1から10000までだんだん大きくしていった時に、E(X_1) = p = 0.6に近づけば大数の弱法則が成り立っていることが確認できたことになります. (ベルヌーイ分布の期待値はE(X) = p. ベルヌーイ分布の記事も書いてるのでこちらも参照してください.)

www.tatsumiya-blog.tokyo

ベルヌーイ分布に従う確率変数は、一様乱数を生成し、その乱数x_ix_i \geq pの時x_i = 1にし、それ以外をx_i = 0とすることで、サンプルすることにします.

その確率変数のk回目までの試行での標本平均をX_kとし配列に格納します. (見やすくするために、試行100回間隔で配列に格納しています.)

最後にmatplotlibを用いて図示しています.

以下にp = 0.6の時とp = 0.2の時の結果をそれぞれ3つ載せておきます. (1回だけだと偶然近づいた可能性もあるので複数回行いました.)

f:id:linearml:20180928031445p:plainf:id:linearml:20180928031455p:plainf:id:linearml:20180928031505p:plain
p = 0.6

f:id:linearml:20180928031514p:plainf:id:linearml:20180928031523p:plainf:id:linearml:20180928031533p:plain
p = 0.2

いずれもp = 0.60.2に近づいているのがわかります.

今回確かめたのは大数の弱法則なので、標本平均はp確率収束します. したがって、ある点以降pに一致するということはなく、pの近傍にある確率が極めて高いことを表していて、そのことは上の図からも見てわかります.

import numpy as np
import matplotlib.pyplot as plt

p = 0.2
num = 10000
r = 0.0
dist = np.zeros(num / 100 + 1)
dist[0] = 0.0
j = 1
for i in range(num + 1):
    a = np.random.rand()
    if a <= p :
        r += 1
    p_hat = r / (1.0 + i)
    if i != 0 and i % 100 == 0 :
        print i
        dist[j] = p_hat
        j += 1

left = np.array([i * 100 for i in range(num / 100 + 1)])
height = dist
plt.plot(left, height)
h = np.array([p for i in range(num + 1)])
l = np.array([i for i in range(num + 1)])
plt.plot(l, h, color = 'red')
plt.show()

7. まとめ

  • 確率収束 \lim_{n \to \infty} P(|X - X_n| > \epsilon) = 0

    X_nXに近づいていくがある点を境に完全に一致し、以後Xを取り続けるということを表していない. X_nXの近傍にいる確率が極めて高い.

  • 概収束  P(\lim_{n \to \infty} X_n = X) = 1

    確率収束と違って、ある点を境にXを取り続ける. 確率収束より条件が厳しいため、概収束が成り立つならば確率収束も成り立つ. 逆は必ずしも言えるわけではない.

  • チェビシェフの不等式 P(|X - E(X)| \geq \epsilon) \leq \frac{\sigma^{2}}{\epsilon^{2}}

    確率変数の平均と分散との関係について表した不等式.

  • 大数の強法則 : 標本平均が母平均に概収束する.

     X_1, X_2, \cdotsが独立であり、平均\muの同一分布に従うとき、

     \frac{\sum_{i = 1}^{n} X_i}{n} \xrightarrow{a.s.} \mu (n \rightarrow \infty)

  • 大数の弱法則 : 標本平均が母平均に確率収束する.

     X_1, X_2, \cdotsが独立であり、平均\muの同一分布に従うとき、

     \frac{\sum_{i = 1}^{n} X_i}{n} \xrightarrow{P} \mu (n \rightarrow \infty)