確率論 II – ランダム・ウォーク 5

確率論 II – _{ランダム・ウォーク} 5

2011 _年 , _西岡

http://c-faculty.chuo-u.ac.jp/˜nishioka/

2 _号館 11 _階 21131 _号室 オフィスアワー : _水曜 4 _限

目次

9 _母関数 1

9.1 _{数列の母関数} . . . 2 9.2 _{重畳と母関数} . . . 7

10 母関数の確率論への応用 11

10.1 いろいろな確率分布の母関数 . . . 11 10.2 待ち時間と負の二項分布 . . . 14 10.3 ランダム・ウォークの初回到達時間 . . . 17

9 _母関数

離散的な値をとる確率変数にたいして, ‘_母関数(generating function)’_の 方法は有効.

定義 9.1. _数列 {ak, k= 0,1,2,· · · }にたいし, (9.1) A(s)≡a0+a1s+a2s²+· · ·

が 有る区間α< s <β _{で収束するとき},A(s)_を{ak}の母関数という. 注意 9.2. _もし {ak}が有界なら, (9.1) _は−1< s <1_{で収束する}.

例題 9.3. (i) _すべてのkにたいしak= 1_なら,A(s) = 1 1−s. (ii) {ak}={0,0,1,1,1,· · · }のときは,A(s) = s²

1−s.

– 1 –

9.1 _{数列の母関数}

確率変数X _は

P[X=k] =pk, k= 0,1,2,· · ·, とする. _すると

P[X > j] =qj≡pj+1+pj+2+· · ·, j= 0,1,2,· · · このとき,{pk},{qj} それぞれの母関数P(s), Q(s)_は

P(s) =p0+p1s+p2s²+· · ·=!^∞

k=0

pks^k, −1≤s≤1 Q(s) =q0+q1s+q2s²+· · ·=

!∞ j=0

qjs^j, −1< s <1.

– 2 –

定理 9.4. −1< s <1 _にたいし, Q(s) = 1−P(s) 1−s . [証明] (1−s)Q(s)_{を計算する}.

Q(s) =q0+q1s+q2s²+q3s³+· · · s Q(s) = +q0s+q1s²+q2s³+· · · ここで,p0+p1+p2+· · ·= 1_{に注意すると}

qk+1−qk=−pk

q0=p1+p2+· · ·= 1−p0.

つまり

(1−s)Q(s) =q0−p1s−p2s²−· · ·

= 1−p0−p1s−p2s²−· · ·= 1−P(s). !

– 3 –

(∗) _{次に 母関数}P(s)_{の微分を調べる}:

P^"(s) =!^∞

k=0

k pks^k−1, −1< s <1.

この級数は−1< s <1_{で収束する}. 1. _もしX _の平均E[X]_{が存在するなら},

slim→1P^"(s) =!^∞

k=0

k pk=E[X].

2. _もしX _の平均E[X]_が発散(=∞)_なら,

slim→1P^"(s) =!^∞

k=0

k pk=∞=E[X].

命題 9.5. X _の平均E[X]_は

E[X] =P^"(1) =Q(1).

[証明] P(1) = 1だから 平均値の定理より,あるs < t <1_があり Q(s) = 1−P(s)

1−s =P^"(t)

つまり Q(1) = lim

s→1Q(s) = lim

s→1P^"(t) =P^"(1) =E[X]. ! 命題 9.6. X の分散σ²[X]≡E[X²]−"

E[X]# 2_は σ²[X] =P^""(1) +P^"(1)−"

P^"(1)#2

= 2Q^"(1) +Q(1)−"

Q(1)#2

.

– 5 –

[_証明] _まず

E[X(X−1)] = X∞ k=1

k(k−1)pk=P^""(1).

定理9.4_の式Q(s) =1−P(s)

1−s ^{を微分して}, Q^"(s) =−P^"(s) (1−s) + 1−P(s)

(1−s)² = −P^"(s) +Q[s]

1−s

⇒P^"(s) =Q(s)−(1−s)Q^"(s)

⇒P^""(s) = 2Q^"(s)−(1−s)Q^""(s).

これより

σ²[X] =P^""(1) +P^"(1)−` P^"(1)´2

= 2Q^"(1) +Q(1)−` Q(1)´2

. !

9.2 _{重畳と母関数}

確率変数X, Y が非負整数値をとるとする. _すると|s|<1_にたいし, E[s^X] =!^∞

k=0

s^k P[X=k] =P(s), |s|<1.

命題 9.7. X とY が独立なら

E[s^X+Y] = !^∞

j,k=0

s^j+k P[X=k, Y =j]

= !^∞

j,k=0

s^j s^k P[X=k]P[Y =j] =E[s^X]E[s^Y] =PX(s)PY(s).

この事実を一般化する.

– 7 –

定義 9.8. _数列{ak},{bk}にたいし,

ck≡a0bk+a1b_k−1+· · ·+a_k−1b1+akb0, k= 0,1,2,· · · と定義する. こうして出来た新しい数列{ck} を‘{ak}と{bk} の重畳 convolution’_といい,_{次で表記する}: {ck}={ak}∗{bk}.

重畳と母関数

! "

定理 9.9. _数列 {ck} が {ak} と {bk} の重畳. {ck} の母関数を C(s) =$_∞

k=0cks^k とする.

⇒ C(s) =A(s)B(s).

ここでA(s), B(s)_{は 数列}{ak},{bk}の母関数,

A(s) = X∞ k=0

aks^k B(s) = X∞ k=0

bks^k.

# $

– 8 –

[_定理 9.9_証明] C(s) =

X∞ k=0

cks^k= X∞ k=0

Xk j=0

ajb_k−js^k= X

0≤j≤k

ajb_k−js^k

= X∞ j=0

ajs^j X∞ k=j

bk−js^k−j= X∞ j=0

ajs^j X∞

!=0

b!s^!=A(s)B(s). !

j

j=0  → j=5    k k=2 → k= ∞

図9.1 _{縦に加えるか},_{横に加えるか}

– 9 –

例題9.10. (i) _すべてのk_にたいし,ak= 1 =bk. ⇒ ck=k+ 1.

A(s) = 1

1−s =B(s) ⇒ C(s) = 1 (1−s)². (ii) ak=k, bk= 1 ⇒ ck= 1 + 2 +· · ·+k=k(k+ 1)

2 .

A(s) = X∞ k=0

k s^k= s

(1−s)², B(s) = 1 1−s

⇒ C(s) = s (1−s)³ =

X∞ k=0

k(k+ 1) 2 s^k.

– 10 –

10 母関数の確率論への応用 10.1 いろいろな確率分布の母関数

Xn, n= 1,2,· · ·,を非負整数値をとる独立同分布の確率変数,

P[Xn=k] =pk, k= 0,1,· · · ⇒ A(s)≡ X∞ k=0

pks^k, |s|<1.

命題9.7_{から次が直ぐに判る}:

定理10.1. Sn≡X1+· · ·+Xnに対し,q_k⁽ⁿ⁾≡P[Sn=k_とおくと, {q⁽ⁿ⁾_k }={pk}∗{pk}∗· · ·∗{pk}

| {z }

n

`={pk}^n∗と記す´ .

Snの確率分布母関数Q⁽ⁿ⁾(s)≡E[s^Sn] =` A(s)´n

. %

– 11 –

例題10.2. (i) 0< p <1_とする. X _を

P[X= 1] =p, P[X= 0] = 1−p

である確率変数. _{この母関数は}

A(s) =s⁰ P[X= 0] +sP[X= 1] = 1−p+p s.

(ii) Xk, k= 1,2,· · ·,_を(i)の分布を持つ独立同分布の確率変数列.

Sn≡X1+· · ·+Xnは2_項分布

P[Sn=k] =nCk p^k(1−p)^n−k, k= 0,1,· · ·, n に従うが,_{その母関数}B(s)_は

B(s) = (1−p+p s)ⁿ= Xn k=0

nCkp^k (1−p)^n−ks^k.

(iii) _確率変数X _が経数λ_{のポアッソン分布に従うとは},

P[X=k] = λ^k

k! e^−λ, k= 0,1,· · · ポアッソン分布の母関数P(s)_は

P(s) = X∞ k=0

λ^k

k! e^−λs^k=e^−λ(1−s). %

– 13 –

10.2 待ち時間と負の二項分布

1. _{表が出る確率}p_{のコインを投げる}. Xを「このコインを投げて,_{初めて表が出} た回数」(=表がでるまでの待ち時間)_とすると,k+ 1回目に初めて表が出る確 率は

(10.1) P[X=k] =q^kp, q≡1−p, k= 0,1,· · ·. この確率分布の母関数ϕ1(s)_は

(10.2) ϕ1(s)≡

X∞ k=0

q^kp s^k= p 1−q s 命題9.5, 9.6_より E[X] = q

p, σ²[X] = q p².

2. Srを「r回表が出るまでの待ち時間」とする. Xj, j= 1,2,· · ·,_を(10.1)_と 同分布で互いに独立な確率変数とすると,

Sr=X1+X2+· · ·+Xr, r= 1,2,· · ·

命題9.7

! "

確率変数X, Y _{の母関数を}GX(s), GY(s)_とする. X _とY _{が独立なら}, 確率変数X+Y _の母関数GX+Y(s)_は

GX+Y(s)≡E[s^X+Y] =GX(s)GY(s), |s|<1. %

# $

を使うと,Srの母関数ϕr(s)_{が簡単に計算できる}.

(10.3) ϕr(s) =` p

1−q s

´r

= X∞ j=0

„ −r j

«

p^r(−q)^j s^j. 最後の等式は テイラー展開で,_{負の二項係数}

„ −r j

«

≡(−r) (−r−1)· · ·(−r−j+ 1)

j! , j= 0,1,· · ·

を使った.

命題10.3. P[Sr=j] = −r j

!

p^r (−q)^j, j= 0,1,· · ·. %

– 15 –

(∗) テイラー展開を使うと，r_{が整数でなくても}(10.3)_が成立: 一般の二項展開

! "

拡張された二項展開: _実数q,_実数r&= 0_にたいし,

(10.4) `

1−q s´r

= X∞ j=0

„ r j

«

(−q)^j s^j, |s|< 1

|q|. ここで

„ r j

«

≡(r) (r−1)· · ·(r−j+ 1)

j! , j= 0,1,· · ·

# $

– 16 –

10.3 ランダム・ウォークの初回到達時間

w(0) = 0であるランダム・ウォーク{w(k), k= 0,1,· · · }に対し,T1 を1_への 初回到達時間(the first passage time)_とする.i.e.

{T1=n}≡{w(1)≤0, w(2)≤0,· · ·, w(n−1)≤0, w(n) = 1} ただし{w(k), k= 0,1,· · · }には次の確率を導入する,

P[w(k+ 1) =w(k) + 1˛˛w(k)] =p, P[w(k+ 1) =w(k)−1˛˛w(k)] =q≡1−p

(∗) T1の分布の母関数を決定する: Φ(s)≡

X∞ n=0

ϕnsⁿ, |s|<1, ϕ0≡0, ϕn≡P[T1=n].

Step 1. _まずϕ1=P[T1= 1] =p.

– 17 –

Step 2. {T1=n}, n≥2_{にたいしては},_{下の図が成立する}:

1 O

-1 k n

k-1 n-k

1. w(1) =−1,ランダム・ウォークが最初に0_{に到達する時刻を}k_とする,i.e.

k≡min{j: w(j) = 0}.

ランダム・ウォークは(1,−1)→(k,0)_{と動くので},_{これが起こる確率は} {T1=k−1}と等しい.

2. 次にランダム・ウォークは(k,0)_{から再出発して},_時刻n_で初めて1_に到着す る. _{これが起こる確率は}{T1=n−k}に等しい.

– 18 –

3. つまり 図 が成立する確率は qϕk−1 ϕn−k. ここでk_は2≤k≤n−1 _{のどこでもいいので}, (10.5) ϕn=q"

ϕ1ϕ_n−2+ϕ3 ϕ_n−3+· · ·+ϕ_n−2 ϕ1

#, n≥2.

ϕ0≡0_として(10.5)_{を書き直す}, ϕn=q

Xn k=0

ϕk ϕ_n−k⇔{ϕn}=q{ϕn}∗{ϕn}

この両辺にsⁿ_を乗じて,n≥2_{で和をとる}: Φ(s)−p s=q s`

Φ(s)´2

⇒ Φ(s) =1±p

1−4p q s²

2q s .

ところが,Φ(0) =ϕ0= 0_なので,

(10.6) Φ(s) = 1−p

1−4p q s²

2q s .

– 19 –

Step 3. (10.4)_より

√1−a s= X∞ j=0

„ 1/2 j

«

a^j(−s)^j

= 1 + X∞ j=1

(1/2) (−1/2) (−3/2)· · ·(3/2−j)

j! a^j(−s)^j

よって,

Φ(s) =p s+ X∞ j=2

1 4q

(1/2) (3/2)· · ·(j−3/2)

j! (4p q)^js^2j−1

⇒ ϕ2j−1= (2j−2)!

j! (j−1)! p^jq^j−1, ϕ2j= 0, j= 1,2,· · ·.

注意10.4. (i) p+q= 1_だから1 = (p+q)². _よって p1−4p q=p

(p+q)²−4pq=p

(p−q)²=|p−q|.

これより

Φ(1) =X

ϕj=1−|p−q| 2q . つまり

Xϕj= 8<

:

p/q ifp < q 1 ifp≥q これは

1. p < qなら ランダム・ウォークがずっと負である確率は q−p p . 2. p≥q_{なら，上の確率は}0.

– 21 –

(ii) _とくにp=q= 1/2_なら,ランダム・ウォークがずっと負である確率は0.

では1に到達するまでの平均時間は? d

ds Φ(s) = 2p

p1−4p q s² −1−p

1−4p q s² 2q s² これより p=q= 1/2_なら Φ^"(1)→ ∞. !