§B4.18ランダムウォークと漸化式の応用

最終更新

各歩で位置が確率的に変わる過程を、位置を状態、一歩の動きを遷移として扱います。

1 対称ランダムウォークの広がり

定義 1.1 (一次元単純対称ランダムウォーク).X1,X2,…X_1,X_2,\ldotsを、11と−1-1をそれぞれ確率1/21/2でとる互いに独立な確率変数とします。S0=0S_0=0、

Sn=X1+⋯+XnS_n=X_1+\cdots+X_n

で定める過程を一次元単純対称ランダムウォークといいます。

定理 1.2 (位置の期待値と分散). 上のランダムウォークについて、

E[Sn]=0,V[Sn]=nE[S_n]=0,\qquad V[S_n]=n

が成り立ちます。したがってSnS_nの標準偏差はn\sqrt nです。

証明. 各XiX_iについてE[Xi]=0E[X_i]=0、V[Xi]=1V[X_i]=1です。期待値の線形性と、独立な確率変数の分散の加法性を用いると結論を得ます。▨

2 吸収される位置へ到達する確率

位置0とNNで停止する対称ランダムウォークを考えます。位置kkから出発してNNへ先に到達する確率をqkq_kとします。

定理 2.1 (上端へ到達する確率).0≤k≤N0\le k\le Nについて、

qk=kNq_k=\frac{k}{N}

が成り立ちます。

証明. 境界条件はq0=0,qN=1q_0=0,q_N=1です。1≤k≤N−11\le k\le N-1では一歩先で場合分けして

qk=12qk−1+12qk+1q_k=\frac12q_{k-1}+\frac12q_{k+1}

を得ます。したがってqk+1−qk=qk−qk−1q_{k+1}-q_k=q_k-q_{k-1}であり、(qk)(q_k)は等差数列です。境界条件からqk=k/Nq_k=k/Nを得ます。▨

3 吸収までの歩数の期待値

位置kkから0またはNNへ到達するまでの歩数の期待値をtkt_kとします。

定理 3.1 (非負整数値確率変数の裾確率和公式).TTを非負整数値または無限大をとる確率変数とし、TL=min⁡(T,L)T_L=\min(T,L)とします。このとき、正の整数LLについて

E[TL]=∑r=0L−1P(T>r)E[T_L]=\sum_{r=0}^{L-1}P(T>r)

が成り立ちます。右辺をL→∞L\to\inftyとした和が有限ならば、E[T]E[T]も有限であり、

E[T]=∑r=0∞P(T>r)E[T]=\sum_{r=0}^{\infty}P(T>r)

が成り立ちます。

証明. 各結果について

TL=∑r=0L−11{T>r}T_L=\sum_{r=0}^{L-1}\boldsymbol{1}_{\{T>r\}}

が成り立ちます。有限和の期待値を取ると最初の式を得ます。非負確率変数の期待値を、切り詰めた確率変数の期待値の上限

E[T]=sup⁡L≥1E[TL]E[T]=\sup_{L\ge1}E[T_L]

として定めると、右辺の部分和が有限な極限をもつ場合には、二つ目の式とE[T]<∞E[T]<\inftyを得ます。▨

定理 3.2 (吸収時間の期待値).0≤k≤N0\le k\le Nについて、

tk=k(N−k)t_k=k(N-k)

が成り立ちます。

証明. 境界ではすでに停止しているのでt0=tN=0t_0=t_N=0です。内部では最初の一歩を数えた後の期待値を場合分けして

tk=1+12tk−1+12tk+1t_k=1+\frac12t_{k-1}+\frac12t_{k+1}

を得ます。この期待値が有限であることも確認します。吸収されていない任意の位置から、次のNN歩をすべて左へ進めば0へ到達するので、次のNN歩以内に吸収される条件付き確率は少なくとも2−N2^{-N}です。吸収時刻をTTとすると、

P(T>mN)≤(1−2−N)mP(T>mN)\le(1-2^{-N})^m

です。確率の単調性から、

∑r=0∞P(T>r)≤N∑m=0∞P(T>mN)≤N∑m=0∞(1−2−N)m=N2N\begin{aligned} \sum_{r=0}^{\infty}P(T>r) &\le N\sum_{m=0}^{\infty}P(T>mN)\\ &\le N\sum_{m=0}^{\infty}(1-2^{-N})^m =N2^N \end{aligned}

です。裾確率和公式により、E[T]E[T]は有限であり、E[T]≤N2NE[T]\le N2^Nです。

候補uk=k(N−k)u_k=k(N-k)は境界条件を満たし、

1+12uk−1+12uk+1=uk1+\frac12u_{k-1}+\frac12u_{k+1}=u_k

も満たします。二つの解の差は境界値0の等差数列になるので0であり、解は一意です。したがってtk=ukt_k=u_kです。▨

4 確率1と例外なく起こること

注意 4.1 (almost sure と certain の区別). 有限区間の対称ランダムウォークは確率1で境界へ吸収されます。しかし、左右の動きが永遠に特定の列をなす個々の無限列も標本空間上では考えることができます。確率1で起こることは、例外となる結果が集合として存在しないことを意味しません。例外集合の確率が0であることを意味します。

本記事では有限区間の境界値問題だけを扱います。一般のランダムウォークと確率過程の理論は「確率過程」が扱います。

5 演習

  1. N=10,k=3N=10,k=3のとき、10へ先に到達する確率と、0または10へ吸収されるまでの歩数の期待値を求めます。
  2. tk=k(N−k)t_k=k(N-k)を漸化式へ代入して確認します。
  3. 「確率1で吸収される」と「すべての無限列が有限時間で吸収される」の違いを説明します。

1の答えは3/103/10と21歩です。2では

1+12(k−1)(N−k+1)+12(k+1)(N−k−1)=k(N−k)1+\frac12(k-1)(N-k+1)+\frac12(k+1)(N-k-1)=k(N-k)

となります。3では前者は吸収されない無限列全体の確率が0であるという主張であり、その集合が空であるという主張ではありません。後者は例外となる無限列が一つも存在しないという、より強い主張です。

演習

問題を解いてから「解答・解説」を開けます。

数直線上を1歩ごとに確率 p で +1、確率 q == 1 − p で −1 動く点を考える（1次元単純ランダムウォーク）。S_n は n 歩後の位置、S_0 は出発点とする。

演習を読み込み中…

前提記事