理論計算機科学を読むための数学・証明・アルゴリズム基礎

第10章 確率の基礎

章間ナビゲーション

この章で使う記号

記号 意味
Ω 標本空間
A ⊆ Ω 事象
Pr[A] 事象 A の確率
Pr[A | B] B が起きた条件での A の条件付き確率
X 確率変数
E[X] 期待値
Var(X) 分散
I_A 事象 A の指示変数

この章で解消する詰まりどころ

情報理論、暗号、ランダム化アルゴリズム、並行計算を読むと、次のような記法が頻繁に出ます。

Pr[A]
Pr[A | B]
E[X]
H(X) = - Σ_x p(x) log p(x)

これらは高度な統計学ではなく、有限集合上の確率として読めれば十分な場面が多いです。この章では、理論計算機科学で止まりやすい確率の最小セットを扱います。

本体教科書で使う箇所

  • 情報理論: 自己情報量、エントロピー、相互情報量、符号。
  • 暗号: 鍵生成、ランダム性、攻撃成功確率、確率的アルゴリズム。
  • 複雑性理論: ランダム化計算、確率的判定。
  • 並行計算: 非決定性と確率的選択の区別。

1. 標本空間と事象

確率では、起こり得る結果全体を標本空間 Ω と書きます。標本空間の部分集合を事象と呼びます。

例: コインを2回投げる。

Ω = {HH, HT, TH, TT}
A = {HH, HT}       1回目が H である事象
B = {HT, TH}       H と T が1回ずつ出る事象

この章では、基本的に有限の Ω だけを扱います。

2. 確率

各事象 A ⊆ Ω に対して、確率 Pr[A] を割り当てます。有限で一様な場合は、次で計算できます。

Pr[A] = |A| / |Ω|

例:

Ω = {HH, HT, TH, TT}
A = {HH, HT}
Pr[A] = 2/4 = 1/2

一般には、確率は次を満たします。

  1. 0 ≤ Pr[A] ≤ 1
  2. Pr[Ω] = 1
  3. A ∩ B = ∅ なら Pr[A ∪ B] = Pr[A] + Pr[B]

3. 補事象と和事象

補事象は「A が起きない」事象です。

Pr[A^c] = 1 - Pr[A]

2つの事象の和については、一般に次が成り立ちます。

Pr[A ∪ B] = Pr[A] + Pr[B] - Pr[A ∩ B]

A と B が排反なら A ∩ B = ∅ なので、最後の項は0です。

4. 条件付き確率

B が起きたと分かった後で A が起きる確率を、条件付き確率と呼びます。

Pr[A | B] = Pr[A ∩ B] / Pr[B]

ただし Pr[B] > 0 が必要です。

例: サイコロを1回振る。

A = 偶数が出る = {2,4,6}
B = 4以上が出る = {4,5,6}
A ∩ B = {4,6}
Pr[A | B] = |{4,6}| / |{4,5,6}| = 2/3

条件付き確率では、分母が Ω ではなく B に変わると考えるとよいです。

5. 独立性

事象 A と B が独立であるとは、片方が起きたという情報が、もう片方の確率を変えないことです。

Pr[A ∩ B] = Pr[A]Pr[B]

Pr[B] > 0 のとき、これは次と同値です。

Pr[A | B] = Pr[A]

排反との違い

排反は同時に起きないことです。

A ∩ B = ∅

独立は、互いに情報を与えないことです。排反と独立は別概念です。Pr[A]>0, Pr[B]>0 のとき、排反なら

Pr[A ∩ B] = 0
Pr[A]Pr[B] > 0

なので、独立ではありません。

6. ベイズの定理

条件付き確率の定義から、次が得られます。

Pr[A | B] = Pr[B | A] Pr[A] / Pr[B]

これはベイズの定理です。理論計算機科学では、確率的推論、情報理論、暗号の安全性議論、機械学習の基礎で使います。

7. 確率変数

確率変数は、結果に数値を対応させる関数です。

X: Ω -> R

例: コインを2回投げて、表の数を X とする。

X(HH)=2
X(HT)=1
X(TH)=1
X(TT)=0

確率変数は「変数」という名前ですが、数学的には関数です。

8. 期待値

確率変数 X の期待値は、値の重み付き平均です。

E[X] = Σ_x x Pr[X=x]

例: 公平なサイコロの出目 X。

E[X] = (1+2+3+4+5+6)/6 = 3.5

期待値の線形性

任意の確率変数 X, Y と定数 a, b について、次が成り立ちます。

E[aX + bY] = aE[X] + bE[Y]

重要なのは、X と Y が独立でなくても成り立つことです。

9. 指示変数

事象 A に対して、次の確率変数を定義します。

I_A = 1  if A が起きる
I_A = 0  otherwise

このとき、

E[I_A] = Pr[A]

指示変数は数え上げと確率を接続する道具です。

例: 長さ n のビット列をランダムに選ぶ。i 番目のビットが1である事象を A_i とし、I_i をその指示変数とする。1の個数を X とすると、

X = I_1 + I_2 + ... + I_n
E[X] = E[I_1] + ... + E[I_n] = n/2

10. 分散

分散は、期待値からのばらつきを表します。

Var[X] = E[(X - E[X])^2]

計算では次の形がよく使われます。

Var[X] = E[X^2] - E[X]^2

分散は、ランダム化アルゴリズムの実行時間や、ハッシュ表の衝突数の解析に出てきます。

11. 代表的な分布

Bernoulli分布

確率 p で1、確率 1-p で0を取る分布です。

Pr[X=1] = p
Pr[X=0] = 1-p
E[X] = p

二項分布

独立な Bernoulli 試行を n 回行い、成功回数を数える分布です。

Pr[X=k] = C(n,k) p^k (1-p)^(n-k)
E[X] = np

幾何分布

成功確率 p の試行を、初めて成功するまで繰り返すときの試行回数です。

Pr[X=k] = (1-p)^(k-1) p
E[X] = 1/p

12. Markov不等式と Chebyshev不等式

細かい証明より、まず用途を押さえます。

非負の確率変数 X について、Markov不等式は次を述べます。

Pr[X >= a] <= E[X] / a

分散が有限な確率変数 X について、Chebyshev不等式は次を述べます。

Pr[|X - E[X]| >= a] <= Var[X] / a^2

これらは、「期待値や分散だけから、極端な値を取る確率を上から抑える」道具です。

13. ランダム化アルゴリズム

アルゴリズムが乱数を使う場合、同じ入力でも実行ごとに挙動が変わります。

代表的な分類は次です。

種類 特徴
Las Vegas 常に正しい答えを返すが、実行時間が確率的に変わる
Monte Carlo 実行時間は制御しやすいが、一定確率で誤ることがある

確率的解析では、確率は通常「入力の分布」ではなく「アルゴリズム内部の乱数」に対して取ります。この区別が重要です。

14. エントロピーへの接続

情報理論で使うエントロピーは、確率分布の不確実性を測る量です。

H(X) = - Σ_x Pr[X=x] log Pr[X=x]

この式を読むには、少なくとも次が必要です。

  • 確率変数 X。
  • 値 x ごとの確率 Pr[X=x]。
  • 総和記号。
  • 対数。
  • 期待値の感覚。

この章は、エントロピーを深く学ぶ前の記法準備です。

15. よくある誤り

誤り1: 独立と排反を混同する

排反は同時に起きないことです。独立は片方の発生がもう片方の確率を変えないことです。

誤り2: 条件付き確率の分母を間違える

Pr[A | B] の分母は Pr[B] です。Pr[A] ではありません。

誤り3: 期待値を「最も起こりやすい値」と考える

期待値は平均です。最頻値とは限りません。

誤り4: 非決定性を確率と考える

NFAや並行モデルの非決定性は、確率分布を持つ選択とは限りません。どの遷移も「可能」として扱う形式化です。

16. 章末確認

次を説明できれば、この章の目的は達成です。

  1. Pr[A | B] を定義できる。
  2. 独立と排反を区別できる。
  3. 確率変数を関数として説明できる。
  4. 期待値の線形性を使える。
  5. 指示変数で個数の期待値を計算できる。
  6. 二項分布の形を読める。
  7. エントロピーの式に出る記法を読める。

次に読む章

Edit this page on GitHub