確率・統計（電子2年） 第15講 23. 確率過程のさわり

確率・統計（電子２年）
第 15 講
• 期末試験解説
• 確率過程の例（離散時間最適停止，連続時間確率過程）
23. 確率過程のさわり
離散時間最適停止問題の例
離散時間最適停止問題は，賭けをどこで止めると儲かりやすいか？の問題から
発生したと言われる．例として，秘書採用問題（Secretary Problem）を考える．
見掛けは以前出てきた確率変数の列である（有限個の場合は確率変数ベクトル
とも言える）が，時間の進行（順番）と共に一般に知りえる情報が増えていく．本
質的には確率過程（後述）として扱う．
例：秘書採用，あるいはお見合い問題 秘書採用問題とは，n 人の候補者を順次面談して，1 名を選ぶ時に，
「取り消し」
や「後戻り」はできないとして，どういう戦術を取ればよい秘書を採用できるか？
という問題であり，お見合いの戦術とも考えられる．
古典的秘書採用問題を正確に記述すると以下のようなものである．
• n 人の応募者に対して 1 名づつ面談をし，必ず 1 名（だけ）採用する．
（n が
既知であることが大きな仮定である）．面談の評価値によって順位を付ける
が，評価値が同点の人はいないと仮定する．
• 面談の順番は無作為．つまり，n! 通りの順番が等確率で出現する．
• ある人を面談したら，その場で採用・不採用を決める．つまり，採用を決め
たら，それ以降の人は面談・採用できないし，逆に一旦不採用にした人を，
それ以降の人を面談した後でやっぱり採用する，というのも禁止．また，採
用したが，相手に断られる，というのもないものと仮定する．
• k 番目の人の面談が終わった時点でその人を採用するかどうかの判定基準（戦
術）には，暫定相対順位（今まで面談が終わった人の中で何位か？），およ
び，k, n だけしか利用できない．もちろん，必ず誰か 1 名を採用する必要が
あるので，n 番目の人まで行ってしまったら（それまでの (n − 1) 人を不採
用にしたら）その人を採用する．
注：面談の「絶対評価」は用いない点に注意．同じ相対順位「1 位」でも，世
間水準的にみて極めて優秀な人と，どんぐりの背比べで結果的に 1 位になっ
た人とでは，現実には区別するかも知れない．しかし，ここでは，そのよう
な「付加的情報」を利用できないモデルで考えている．
1
この問題での最も単純な（古典的な）目標は，
1. 「採用する人の真の順位（最終順位）が 1 位である確率」を最大にする戦術：
最良選択問題 (best-choice problem)
2. 「採用する人の最終順位の期待値」を最小（順位は小さい方がいいので）に
する戦術：期待順位最小化問題 (rank minimization problem)
3. 少し一般化して，最終順位 x に関する利得関数 Un (x) が与えられるとして，採
用する人の最終順位を確率変数 X とし，Un (X) の期待値を最大にする戦術．
1 x=1
．
例えば，best-choice 問題に対応する利得関数：Un (x) =
0 otherwise
などが知られている．上の仮定で，目標の 1 つ目の，best-choice 問題を調べよう．
• Rk を k 番目の応募者の（面談直後の）暫定相対順位，
• Lk を k 番目の応募者の最終順位，
「面談の順番は無作為」という上の仮定より，
と置く（k = 1, 2, . . . , n）．
1
, s = 1, 2, . . . , k
k
• R1 , R2 , . . . , Rn は独立（自明ではない）．
1
• P (Lk = s) = , s = 1, 2, . . . , n
n
もちろんこれは「無条件」（面談を行う前）の確率である．
• P (Rk = s) =
「n 人中でベスト（1 位）の人を採用する」確率を最大化する戦術では，相対順
位が 2 以下の人は（最後以外は）採用しないはずである．よって必ず相対順位が
1 になった時に採用を決定するが，どのタイミングでの相対 1 位かが問題である．
そこで，r = 1, 2, . . . , n を戦術のパラメタとして（最適な r を後で検討する），
• 戦術 σ(r)：
「最初の (r −1) 人は相対順位が 1 位でも採用せず，r 番目以降（残っ
てるのは (n − r + 1) 人）で初めて相対順位が 1 位となった人を採用する．た
だし，r = n の場合は，n 番目の人を無条件に採用する」
を定義する．
• この戦術で採用される人の面談順序を確率変数 Z(r) とすると，
• P (LZ(r) = 1) を最大にする r = r ∗ を使った戦術 σ(r ∗ ) が「最適」．
ここで，
• r = 1, = n では，Z(r) = k ⇔ Rr = 1, Rr+1 = 1, · · · , Rk−1 = 1, Rk = 1
• r = 1 では，R1 = 1 より，Z(1) = 1．よって，P (LZ(1) = 1) = P (L1 = 1) =
2
1
n
• r = n では，Z(n) = n．よって，P (LZ(n) = 1) = P (Ln = 1) =
1
n
def
そこで，r = 1, = n の時の，fn (r) = P (LZ(r) = 1) を計算しよう．
fn (r) =
=
n
k=r
n
k=r
=
=
n
n
k=r
P (Lk = 1, Rk = 1, Rk−1 ≥ 2, . . . , Rr ≥ 2)
P (Lk = 1|Rk = 1, Rk−1 ≥ 2, . . . , Rr ≥ 2)P (Rk = 1)
⎛
⎝
n
k=r i=k+1
n
k=r
=
P (Lk = 1, Z(r) = k) =
⎞
P (Ri ≥
2)⎠ P (Rk
k
k+1
n−1
·
···
k+1 k+2
n
= 1)
1
k
r
j=k−1
r
j=k−1
P (Rj ≥ 2)
P (Rj ≥ 2)
k−2 k−3
r−1
·
···
k−1 k−2
r
n
1
r−1 n k=r k − 1
ただし，３行目の変形には，
• 「k 番目の人の相対順位が 1 位」という条件下で，
『その人の最終順位も１位
になる』確率は，
『それ以降の k + 1, k + 2, . . . , n 番目の人は全員相対順位が
２位以上になる』確率と等しい
という関係を使った．すなわち以下の等式が成立する．
P (Lk = 1|Rk = 1, Rk−1 ≥ 2, . . . , Rr ≥ 2)
= P (Rk+1 ≥ 2)P (Rk+2 ≥ 2) · · · P (Rn ≥ 2) =
n
i=k+1
P (Ri ≥ 2)
n
1
1
r−1 (r = 1, = n); (r = 1, n) を最大にする r
n k=r k − 1
n
∗
を見つければよい．例えば，n = 3 のときは，r = 2．なぜなら，
最適な r ∗ は，fn (r) =
1
1
1
1
1
f3 (1) = , f3 (2) =
1+
= , f3 (3) =
3
3
2
2
3
n
+ 1 で近似できる（最初の
e
面談者以降の「応募者数の約 37 ％分」をスキップするのがベスト）．この時，1
1
位を採用できる確率は，fn (r ∗ ) ≈ ≈ 0.368 . . .．なぜなら，
e
実は，n が十分大きいときは，最適な r ∗ は，r ∗ ≈
n
n
r−1 1
1 1
r−1
r−1 =
k−1 ≈
n k=r k − 1
n k=r n n
n
1
(r−1)/n
1
r−1
r−1
dx = −
log
x
n
n
ここで，g(x) = −x log x と置くと，g (x) = −(log x + 1) より，g(x) は
3
1
1
1
• x = で最大になり，その時，g
= ．
e
e
e
r−1
r−1
よって，
「採用する人の真の順位（最終順位）が 1 位である」確率 −
log
n
n
1
r−1
n
≈ （つまり r ≈ + 1）で最大になる．
は，
n
e
e
連続時間確率過程の例と時間平均
時刻 t をパラメタに持つ確率変数の集合 {X(t)}t∈T を確率過程と呼ぶ．
ただし， X(t, ω) : T × Ω → R で，T は時刻の動く範囲．
• T が離散値（例えば，T = {0, 1, 2, . . .}）の場合が離散時間確率過程
• T が連続値（例えば，T = [0, ∞)）の場合が離散時間確率過程
ある運命 ω を固定した時の，t の関数 X(·, ω) を標本路 (Sample Path) と呼ぶ．
確率過程というモデル化によって調べたいことは例えば，
• 初期状態（X(0, ω) の値）から出発して確率的に変化（発展）していく現象
の将来（X の値の，ある時点での分布，あるいは複数の時点での結合分布）．
• 初期状態から十分時間が経って，
「定常的」になっている確率現象の，任意の
時点での状態（値）の分布．
「定常過程」とは，簡単にいえば，一定時間ずら
しても（結合）分布が変化しない確率過程．
連続時間確率過程 {X(t, ·)} を考える．
• 標本路の時間平均：以下の右辺が確率 1 で定義（有限確定値，∞，または
−∞）できる場合，確率変数：
1
X(ω) = lim
t→∞ t
def
t
X(s, ω)ds
0
を，確率過程 {X(t)}t∈[0,∞) の「時間平均」と呼ぶ．
例：X(t) がある地点の気温の時間変化なら，X は気温の無限長期間平均．
• {X(t)} が「エルゴード的定常過程」と呼ばれる条件を満たす場合，任意の
時刻 t での X(t) の「期待値」E[X(t)] と，
「時間平均」が等しい（確率 1 で）．
この事実は実は大数の強法則の一般化になっている．
• 標本路の事象平均：特定の事象の発生に対応する時刻の（昇順の）列を表す確
率変数列 N = {T1 , T2 , . . .} を与えた時 (0 < T1 (ω) < T2 (ω) < · · ·)，以下の
右辺が確率 1 で定義（有限確定値，∞，または −∞）できる場合，確率変数：
def
n
1
X(Ti (ω), ω)
n→∞ n
i=1
X N (ω) = lim
4
を，確率過程 {X(t)}t∈[0,∞) の事象列 N に関する「事象平均」と呼ぶ．
例：X(t) がある地点の気温の時間変化， N がその地点での雷発生という事
象列の時，X N は雷がなった時刻の気温だけに着目した加算無限個の平均．
例：バス停での待ち時間のパラドックス 停留所にバスとそれに乗りたい客が次々に到着する状況を想定する．
• Tn (ω)：n 台目のバスの到着（＝出発）時刻．
バスは到着するとその時に待っていた客を瞬時に全員乗せて出発する．ただ
し，その同時刻にバス停に来た客は待ち時間なしでそのバスに乗るものとす
る．また，T0 (ω) = 0 (∀ω) とする．
• X(t, ω)：時刻 t にバス停に来た客がバスに乗るまでに待つ時間．バスの到着
という確率現象に応じて，X(t, ω) が確定する．
X(t, ω) =
0
t=0
Tn (ω) − t Tn−1 (ω) < t ≤ Tn (ω) (n = 1, 2, . . .)
さて，バスの到着に関する確率モデル（分布）を与えて，待ち時間 {X(t)}t∈[0,∞)
の時間平均と，バスの到着（＝出発）直後に限定した事象平均を計算してみよう．
ここで，最初のバスの出発 (t = 0）から十分時間が経過した後は，上の確率過程
は「定常過程」で近似できる．さらにエルゴード的と仮定できる場合は，
• 「時間平均」は，定常状態で「無作為（ランダム）な時刻にバス停にやって
来る客」の待ち時間の期待値に等しく，
• 「事象平均」は，定常状態で「バスの出発直後に来てバスの背中を見て悔し
い思いをする客」の待ち時間の期待値に等しい．
簡単のために，バスの到着時間間隔
def
Yn (ω) = Tn (ω) − Tn−1 (ω) (n = 1, 2, . . .)
は互いに独立で期待値／分散が有限な同一分布に従うとし，
• m1 = E[Yn ], m2 = E[Yn2 ]
と置く．また，A(t, ω) を時刻 t までに到着したバスの台数（時刻 0 に到着したバ
スは除く）とする．
＜１＞ 時間平均は
m2
2m1
5
一見，
「無作為な時刻にバス停にやって来る客」の待ち時間の時間平均は，バス
m1
の平均到着間隔の半分の
のように思える．しかし，これは直感が「平均」と
2
いう言葉に惑わされた例である．例えば，
「平均到着間隔」が同じ 30 分であっても，
バスが毎回 59 分 59 秒待つと２台続けてくる場合（バス到着間隔として 59 分 59 秒
と 1 秒を交互に取る）と，正確に 30 分間隔で来る場合とでは，
「無作為な時刻にバ
ス停にやって来る客」の待ち時間は，後者に比べて前者が長いと考えられる．な
ぜなら，多くの客は 59 分 59 秒の長い方の到着間隔中にバス停に来るから．
そこで定義に基づいた厳密な計算による理解が必要になる．以下の計算より，時
間平均 X(ω) は，確率 1 で「バスの平均到着間隔の半分よりは長い」ことがわかる．
1
X = lim
t→∞ t
t
0
⎛
A(t) T
i
1 X(s)ds = lim ⎝
t→∞ t
i=1
Ti−1
X(s)ds +
⎞
t
TA(t)
X(s)ds⎠
A(t) 1 Yi
1 t
m2
(Yi − s)ds + lim
X(s)ds =
+0
t→∞ t
t→∞ t TA(t)
2m1
i=1 0
= lim
=
V [Yn ] m1
m1
m2 − m21 m1
=
≥
+
+
2m1
2
2m1
2
2
(a.s.)
• （第２項）= 0 a.s. は，t → ∞ なので，t に比べて， t − TA(t) (ω) や X(s, ω)
が十分小さくなるから．厳密な証明は省くが，直感的には自明な結果．
• （第１項）= m2 /2m1 a.s. は，大数の強法則から導かれる．
Yi
Yi2
1 m2
m2
1 A(t)
A(t) 1 A(t)
=
=
(Yi − s)ds = lim
·
t→∞ t
t→∞
t A(t) i=1 2
m1 2
2m1
i=1 0
lim
途中の等式は以下の計算に依る：
1
A(t)
．なぜなら TA(t) (ω) ≤ t < TA(t)+1 (ω) より，
=
t→∞
t
m1
• lim
A(t, ω)
A(t, ω)
A(t, ω)
≥
≥
TA(t) (ω)
t
TA(t)+1 (ω)
A(t, ω)
n
= lim
=
lim
n→∞ T (ω)
t→∞ TA(t) (ω)
n
A(t, ω)
n
lim
= lim
=
n→∞ Tn+1 (ω)
t→∞ TA(t)+1 (ω)
の両側で大数の強法則を使い，
n
1
lim
Yi (ω)
n→∞ n
i=1
−1
=
1
(a.s.)
m1
n+1
1 n+1
lim
Yi (ω)
·
n→∞
n
n + 1 i=1
−1
=
1
(a.s.)
m1
A(t)
n
m2
1 Yi2
1 1
Yi2 =
（大数の強法則より）
= n→∞
lim ·
t→∞ A(t)
2 n i=1
2
i=1 2
• lim
＜２＞ 「バスが出た直後」という事象に関する事象平均は m1
6
一方，バスの到着時刻を表す確率変数列 N = {T1 , T2 , . . .} を与えて，
def
X + (t, ω) = lim X(t + ε, ω)
ε→+0
の N に関する事象平均を考える．X + (Ti (ω), ω) は，i 番目のバスの出発直後に来
た客の待ち時間であり，それは Yi (ω) に等しいので，
n
1 n−1
1
X + (Ti (ω), ω) = lim
Yi (ω) = m1
n→∞ n
n→∞ n
i=0
i=1
X + N (ω) = lim
(a.s.)
• 待ち時間のパラドックス
上の例で， X(ω) ＝
m2
, X + N (ω) = m1
2m1
X(ω) − X + N (ω) =
(a.s.) なので，
1
1
(m2 − 2m21 ) =
(V [Yn ] − E[Yn ]2 ) (a.s.)
2m1
2m1
よって， V [Yn ] > E[Yn ]2 （つまり， E[Yn2 ] > 2E[Yn ]2 ）の場合は，確率 1 で，
「無
作為に到着する客の待ち時間の時間平均」が「バスの出発直後に来る客の待ち時間
の時間平均」より長くなることを意味し，
「待ち時間のパラドックス」と呼ばれる．
しかし，これはよく考えると矛盾ではない．上の条件からバス到着間隔の分散
が大きい（到着時間間隔が大きく変動する）場合を対象としているので，
• 時間平均（X ）の計算では，長い到着間隔の発生に対し，その間に沢山の客
が来て，
「（個々の）客の待ち時間」が多重に「平均」へ寄与し，短い到着間
隔の発生に対しては，その間の客数が少ないので「平均」への寄与が少ない．
• 一方，事象平均（X + N ）の計算では，到着間隔の長さに依らずに 1 回の到着
が 1 回だけ（その時間間隔の長さ分）「平均」へ寄与する．
「無作為に到着する客の平均待ち時間」X と「バスの出発直後に来る客の平
均待ち時間」X + N の大小を，バスの到着時間間隔 Yn に具体的な分布を与え
て考えると，
• Yn が互いに独立な同一の指数分布に従う場合： X =
（無記憶性）．
m2
= m1 = X + N
2m1
• Yn が 互 い に 独 立 な 同 一 の（ 非 負 値 を 取 る ）一 様 分 布 に 従 う 場 合：
m2
2m1
< m1 = X + N ．
X=
<
2m1
3
• バスが必ず３台連続で来る（つまり，Yn が約 3m1 , 0, 0 を繰り返す）場合：
3
X ≈ m1 > m1 = X + N ．これがパラドックスの起きる例であるが，特
2
殊な状況と言える．
7
24. まとめ
本講義（半期）で学んだことは，大別すると，
• 確率の数学モデルと計算法の基本∼事象，確率分布，独立性，条件付確率，
結合分布，確率変数，確率変数の関数，期待値，分散，共分散
• 確率変数列の収束∼概収束・確率収束・法則収束，大数の法則，中心極限定理
• 統計的推定・検定∼標本平均，不偏分散，最尤推定，信頼区間，統計的検定
• 確率過程のさわり
確率空間 (Ω, F , P ) を定義して確率現象一般を数学的に矛盾なくモデル化し，そ
の上で積分論（測度論）での極限の性質を解析する手法を用いて無限回の試行を
含む現象を調べた．例えば，
「大数の法則」を証明することで「どの目も出やすさ
が等しいサイコロを振り続けて行くとき，5 という目が出る相対頻度は，5 の目が
出る確率（つまり 1/6）に近づく」という現象を説明した．
ただし，サイコロで「5 の目が出る確率が 1/6」であるのは「どの目も等確率で
出る」という仮定の帰結であり，その仮定は確率論の帰結（結果）ではない．ま
た，無限や連続が絡む領域で確率に関する「仮定」を置くのは自明でないことは，
ベルトランのパラドックスの例でも見た．
実際の問題の記述は，
「確率空間」を構成（意識）する必要はなく，確率変数と
その分布を与えればよい．この時，
「現象に即して与える仮定」と「論理的帰結
（確率論に基づく計算）」の境界を明確に意識する必要がある．
「仮定」が現実
問題を正しく捉えていなければ，計算した確率は意味がない．
一方，観測したデータから背景にある確率分布に関する「推定」を行う方法も
少し学んだ．サイコロを振り続けて出目を観測することで，
「どの目も等確率で出
る」という仮定（仮説）の妥当性を検定できる．確率論の応用としての「統計的
推定・検定」は実用上も非常に重要であるが，仮定／前提を理解しないで「統計
ソフト」などを盲目的・機械的に使うと，誤った結論を導くこともある．
回想：第１回の例題 最後に初回の講義の例題が，どのように解けるようになったかを確認してみる．
• 問い：乱数 X, Y は，互いに「独立」で，どちらも実数区間 [1, 2] の範囲から
無作為に１つの「実数」を出力する．一回の実験で X と Y の値を各々一個出
力し，i 回目の実験での出力値を Xi , Yi と置く．実験を繰り返すとして，Xi
n
1
Xi
と Yi の比の相加平均：
という値は，n の増加に伴い収束するか？
n i=1 Yi
X
• 答え：ほとんどの運命（確率 1）で，E
= 1.5 log 2 ≈ 1.035 に収束する．
Y
8