§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であることを意味します。

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

5 演習

問題 5.1. 位置0と10で停止する対称ランダムウォークが位置3から出発するとき、10へ先に到達する確率と、0または10へ吸収されるまでの歩数の期待値を求めよ。

解答.

定理 2.1をN=10N=10、k=3k=3として用いると、10へ先に到達する確率はq3=3/10q_3=3/10である。定理 3.2により、吸収されるまでの歩数の期待値はt3=3⋅(10−3)=21t_3=3\cdot(10-3)=21歩である。▨

問題 5.2.tk=k(N−k)t_k=k(N-k)が境界条件t0=tN=0t_0=t_N=0と、1≤k≤N−11\le k\le N-1での漸化式tk=1+12tk−1+12tk+1t_k=1+\frac12t_{k-1}+\frac12t_{k+1}を満たすことを、代入して確かめよ。

解答.

t0=0⋅N=0t_0=0\cdot N=0、tN=N⋅0=0t_N=N\cdot0=0なので、境界条件を満たす。1≤k≤N−11\le k\le N-1とする。

(k−1)(N−k+1)=kN−k2+2k−N−1,(k+1)(N−k−1)=kN−k2−2k+N−1(k-1)(N-k+1)=kN-k^2+2k-N-1,\qquad(k+1)(N-k-1)=kN-k^2-2k+N-1

であり、二つの式の和は2kN−2k2−22kN-2k^2-2である。したがって、

1+12(k−1)(N−k+1)+12(k+1)(N−k−1)=1+(kN−k2−1)=k(N−k)1+\frac12(k-1)(N-k+1)+\frac12(k+1)(N-k-1)=1+(kN-k^2-1)=k(N-k)

が成り立ち、tk=k(N−k)t_k=k(N-k)は漸化式を満たす。▨

問題 5.3. 位置0とNNで停止する対称ランダムウォークについて、「確率1で吸収される」と「すべての無限列が有限時間で吸収される」の違いを説明せよ。

解答.

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

N≥3N\ge3の場合には、二つの主張は実際に異なる。位置kk（1≤k≤N−21\le k\le N-2）から出発し、右、左、右、左、…と交互に動く無限列は、位置kkとk+1k+1だけを往復するので、0にもNNにも到達しない。k=N−1k=N-1から出発する場合は、左、右、左、右、…と交互に動く無限列が、位置N−1N-1とN−2N-2だけを往復する。したがって、吸収されない無限列の集合は空でない。一方、定理 3.2の証明で示したP(T>mN)≤(1−2−N)mP(T>mN)\le(1-2^{-N})^mはm→∞m\to\inftyのとき0に近づくので、吸収されない確率は0である。すなわち、ランダムウォークは確率1で吸収されるが、すべての無限列が有限時間で吸収されるわけではない（注意 4.1）。▨

レベル3 — ランダムウォークと漸化式

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

解法の型n 歩後の位置は二項係数で数える（+1 が a 回、−1 が n−a 回で S_n==2a − n）。到達確率は1歩先で場合分けして p_i==p·p_(i+1) + q·p_(i−1) を立て、特性方程式 pt² − t + q==0 の解 1, q/p から一般解を作り、境界条件で定数を決める

問題 5.4. 1歩ごとに確率 1/2 で +1、確率 1/2 で −1 動く点が原点を出発する。位置 2 に到達するか位置 −2 に到達した時点で止まる。位置 −2 より先に位置 2 に到達する確率と、止まるまでの平均歩数を求めよ。

p=q=12,S0=0,位置 2 または位置 −2 に到達したら停止,P( 2 に先に到達 )= ?,E[ 止まるまでの歩数 ]= ?p = q = \dfrac{1}{2},\quad S_0 = 0,\quad \text{位置 } 2 \ \text{または位置 } {-2} \ \text{に到達したら停止},\qquad P(\,2 \ \text{に先に到達}\,) = \ ?,\quad E[\,\text{止まるまでの歩数}\,] = \ ?
解答.

答

P( 2 に先に到達 )=24=12E[ 歩数 ]=2×2=4\begin{array}{ll} P(\,2 \ \text{に先に到達}\,) &= \dfrac{2}{4} = \dfrac{1}{2} \\[6pt] E[\,\text{歩数}\,] &= 2 \times 2 = 4 \end{array}

注意 左端を 0 に揃えて座標を k==位置 + 2 と読み替える（出発点は k==2、吸収壁は k==0 と k==4）。k から右端 4 に先に到達する確率を q_k とすると、1歩先で場合分けして q_k==(1/2)q_(k+1) + (1/2)q_(k−1)、境界は q_0==0、q_4==1。 この式は q_(k+1) − q_k==q_k − q_(k−1)（階差が一定）を意味するので q_k は等差数列。境界条件から q_k==k/4。出発点 k==2 を入れて確率は 2/4==1/2。 平均歩数 E_k は E_k==1 + (1/2)E_(k+1) + (1/2)E_(k−1)、境界 E_0==E_4==0。整理すると E_(k+1) − 2E_k + E_(k−1)==−2 で、2階階差が −2 の2次式 E_k==k(4 − k) が境界条件も満たすのでこれが解。k==2 を入れて 2 × 2==4 歩。 特性方程式 (1/2)t² − t + (1/2)==0 は t==1 の重解なので、斉次解は A + Bk（等差数列）になる、という見方でもよい。到達確率が距離の比になるのが対称ウォークの特徴。▨

問題 5.5. 数直線上の点が位置 2 を出発し、1歩ごとに確率 1/2 で +1、確率 1/2 で −1 動く。位置 0 に到達した時点で止まる（0 が吸収壁）。6 歩以内に位置 0 に到達する確率を求めよ。

S0=2,p=q=12 （位置 0 に着いたら停止: 吸収壁）,P( 6 歩以内に 0 に到達 )= ?S_0 = 2,\quad p = q = \dfrac{1}{2}\ \text{（位置 } 0 \text{ に着いたら停止: 吸収壁）},\qquad P(\,6 \ \text{歩以内に } 0 \ \text{に到達}\,) = \ ?
解答.

答2964\dfrac{29}{64}

注意 位置ごとの確率を1歩ずつ更新する漸化式を回す: 位置 j≥\ge1 からは確率 1/2 ずつ j+1 と j−1 へ配り、0 に着いた分はそこで打ち切って（吸収して）足し上げる。 出発点 2 から始めて 6 歩ぶん更新し、各歩で新たに 0 に到達した確率を合計すると 29/64。 パリティに注意: 位置 2 から 0 に着くには 偶数歩かかるので、0 に到達しうるのは 2, 4, … 歩目だけ。歩数を増やせばこの確率は 1 に近づく（対称ウォークは確率 1 でいつか原点に戻る）。▨

問題 5.6. 1回の賭けごとに確率 3/4 で持ち金が 1 増え、確率 1/4 で 1 減る。持ち金が 0 になる（破産）か 5 になる（目標達成）と勝負は終わる。持ち金 i（0≤\lei≤\le5）から始めて目標 5 に到達する確率を p_i とする。漸化式 p_i==p·p_(i+1) + q·p_(i−1) の特性方程式を書き、p_i を i の式で表せ。また p_1 の値を求めよ。

pi=34 pi+1+14 pi−1(1≤i≤4),p0=0,p5=1,pi= ?,p1= ?p_i = \dfrac{3}{4}\,p_{i+1} + \dfrac{1}{4}\,p_{i-1} \quad (1 \le i \le 4),\quad p_0 = 0,\quad p_{5} = 1,\qquad p_i = \ ?,\quad p_{1} = \ ?
解答.

答

特性方程式34t2−t+14=0⟹t=1, 13pi=1−(13) i1−(13) 5p1=81121\begin{array}{ll} \text{特性方程式} & \dfrac{3}{4}t^2 - t + \dfrac{1}{4} = 0 \quad \Longrightarrow\quad t = 1,\ \dfrac{1}{3} \\[4pt] p_i &= \dfrac{1 - \left(\dfrac{1}{3}\right)^{\,i}}{1 - \left(\dfrac{1}{3}\right)^{\,5}} \\[6pt] p_{1} &= \dfrac{81}{121} \end{array}

注意 p_i==p·p_(i+1) + q·p_(i−1) に p_i=ti= t^iを代入してtit^iで割ると、特性方程式 p·t² − t + q==0 が出る。p + q==1 なので p·t² − t + q==(t − 1)(p·t − q) と因数分解でき、解は t==1 と t==q/p==(1/3)。 2解が相異なるので一般解は p_i==A·1^i + B·(q/p)^i==A + B·(1/3)^i。境界条件 p_0==0 から A + B==0、p_5==1 から A + B·(1/3)^5==1。 これを解いて B==1/((1/3)^5 − 1)、A==−B。よって p_i==(1 − (1/3)^i)/(1 − (1/3)^5)。 i==1 とすると p_1==(1 − 1/3)/(1 − 1/243)==81/121。検算: この式は p_0==0、p_5==1 を満たす。有利な賭け（p > 1/2）なので、到達確率 81/121 は持ち金の割合 1/5 より大きい（対称な賭けなら到達確率はちょうど持ち金の割合になる）。▨

前提記事