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

(1)

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

2011 _年 , _西岡

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

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

0 _{確率モデル}

0.1 何故モデルが必要か

(∗)

何かを詳しく調べるとき

,⇒

モデルが必要となる

.

例題

0.1 (

_{地震波の伝搬}

).

_{地球の内部構造モデル}

(

_左

)

_を使って

,

_地震波が伝搬する様子を調べる

.

図

0.1

_{左＝地球の構造}

, 1:

_内核

, 2:

_外核

, 3:

_{下部マントル}

, 4:

_{上部マント} ル

, 5:

_地殻

, 6:

_地表

,

_右

=

_{地震波の伝搬}

,

_外核

,

_{内核で屈折する}

.

例題

0.2 (

地震の発生

).

_{プレートテクトニクス}

-

モデル

:

地球の表面

(

地殻

)

は十数枚の硬いプレートに覆われている

.

プレートは相互に移動していて

,

地震や火山などの活動はそのプレートの境界で起きているプレート同士の相互作用が

,

地震・火山という現象を引き起こしている

.

図

0.2

_{プレートの動き}

このモデルを使って

,

_{地震警報をだし}

,

地震後はそのマグニチュードを調べる

.

図

0.3

地震の発生

(2)

例題

0.3 (

原子模型

).

原子核の周りを電子が周回している

‘

原子模型

’

を使って

,

電磁波や光を受けたときの原子の挙動が計算出来る

.

図

0.4

_原子模型

0.2 確率現象のモデル

ブラウン運動

! "

•

では

,

ランダムな現象のモデルは

?

•

ランダムな事象のモデルとして最も有力なものがブラウン運動

.

# $

ブラウン運動

:

水面に浮かべたケシの花粉の不規

則な運動

,

花粉に水分子が衝突して不規則に動く

.

この軌跡をブラウン運動と呼ぶ

.

•

ケシの花粉の軌跡を上から見ると

図

0.5

_{ブラウン運動}

図

0.6

花粉の位置と時間のグラフ

:

_{ブラウン運動の軌跡}

•

このブラウン運動の特徴は

, (i)

ランダムに変化

,

(ii)

_{軌跡は連続}

,

(iii)

_{至る所微分不可能}

=

_{ギザギザになっている}

.

(3)

•

自然

/

社会の両方で

,

ブラウン運動をモデルとする現象は非常に多い

.

例題

0.4. (i)

_株価

, USA

_{流通業の中堅２社}

,

ホームデポとロウズの株

価の推移

, 2009

年

7

月から

2010

年

7

月

図

0.7

_青

=

_{ホームデポ，赤}

=

_ロウズ

⇒

まるでブラウン運動のような挙動

.

(ii)

_{人や動物の移動}

,⇒

クラゲ

:

_{太陽の光を追い}

,

_午前は東

,

_{午後は西に} 移動する

.

海流の影響で動きがランダム

=

_{ブラウン運動になる}

.

(iii)

煙や液体の拡散運動

. ⇒

煙分子のブラウン運動

0.3 ランダム・ウォークの導入

ランダム・ウォーク

! "

(i)

_{時間が連続なため}

,

ブラウン運動の数学的な取り扱いは大変難しい

.

(ii)

ランダムな運動が方向を変る時間を

,t = 1,2,· · ·

と

,

飛び飛びにしたものがランダム・ウォーク

.

(iii)

ランダム・ウォークは数学的に扱いやすい

.

(iv)

この挙動を調べることが

,

_{本講義の目的}

.

# $

図

0.8

ランダム・ウォークの軌跡

•

ランダム・ウォークの特徴は

, (i)

_{ランダムに変化}

,

_{軌跡は折れ線}

,

(ii)

「変化する時間」の間隔を短くすれば

,

ブラウン運動になる

.

(4)

例題

0.5. (i)

ランダム・ウォークは株式

/

相場のモデルに使われる

. ⇒

「相場はランダム・ウォークか

?

」

!!"#$%&'()*+,-*..." /01 "2,345647,689..."::

!!""""##$$""%%&&""''(())&&**

!

!""##$$%%&&''(())**++,,--!!""##$$%%&&''(())**

;&<=&>?@ABCDEFGHIJKLMNO%P&QRST&UV&WXAYZ[\]^_`$\L;

K?abcde$fghH

!"#$%&'()*+

,-./01*2

ijK?abcde$f9klIJKmfno%Tpqrsmc\t$OuvwNxy&9zG{&z|}

DL\t$~a>&ÄÅuÇÉyÑÖghH

++,,--..//--00112233

345667$849

:; < = > ?@ A 5 B C D 8 E 7 FA6 AA A5 ABAC AD A8 AE A7AF56 5A 55 5B 5C5D58 5E 57 5F B64 4 4 4 4 4

4556677((88 9 9::;;<<

!""#$%&'()*+,-./01 23456789:;<=>'(?

@/AB)*CD-E345FGB H/0127IJ+KLMNO:/

0123456+PQRSTUVW XYOE-7Z[+\]YO^

_:

=

=>>??@@??

,-./01*2G,-./+H*I JKL l

l

Ads by Google システム売買為替相場予想為替相場トレード建築模型

基礎から学ぶシステムトレード相場はランダムウォーク？ http://system-trading.jp/toyoshima/index.php?ID=10

1 / 3 11/04/19 0:41

(ii)

_{クラックの進行}

. ⇒

これもランダム・ウォークに類似

.

図

0.9

_左

:

_{建物のひび割れ}

,

_右

:

_{地震の地割れ}

1 ランダム・ウォークの定義

(

_参考書

: W.

_フェラー

,

_{確率論とその応用}

, 1,

_紀伊国屋

, 1980,

_￥

3,150. )

• ρ1,ρ2,· · ·

を

{1,−1}

どちらかの値をとる数列とする

.

実数

a

_{と自然数}

n

_にたいし

,

新しい数列

(1.1) w(n)≡

! a, n= 0

a+ρ1+ρ2+· · ·+ρn, n= 1,2,· · ·

を考える

.

定義

1.1. 2

次元平面で

,

次の各点を結ぶ折れ線

( path

と呼ぶ

)

をランダム・ウォーク

W

_と呼ぶ

:

W : (0, w(0))→(1, w(1))→(2, w(2))→· · ·→(n, w(n))→· · ·

(1,w(1)) (2,w(2))

(3,w(3)) (4,w(4))

(5,w(5)) (0,a)

図

1.1

_{ランダム・ウォーク}

W

_の

path,x

_{軸を時刻と考える}

(i) ρ₁, ρ₂,· · ·

は

±1

_{どちらかの値をとる}

.

→

時刻

n

までのランダム・ウォークには

,2ⁿ

_個の

paths

がある

.

(5)

(ii) (0, a)→(n, b)

なるランダム・ウォーク

W

_にたいし

,











u≡w(1)−a, w(2)−w(1),· · ·, w(n)−w(n−1)

のなかで

,1

_{の値をとるものの総数}

v≡w(1)−a, w(2)−w(1),· · · , w(n)−w(n−1)

のなかで

,−1

_{の値をとるものの数}

(0,a)

(n,b) v

u

n b-a

とすると

,

_次が成立

:

u−v=b−a, u+v=n → u= n+b−a

2 , v= n−b+a

2 .

!

重要な式

"

(iii) (0, a)→(n, b)

なるランダム・ウォーク

W

_は

,

すべて

(ii)

を満たしている

.

よってその

path

の個数

N(n)

_は

N(n) =nC_u= n!

(n+b−a

2 )! (n−b+a 2 )!

=nC_(n+b₋_a)/2.

n≥|b−a|. (1.2)

# $

2 _反射原理

2.1 _{数の数え方} ( _基礎数学 I)

(i)

男子学生

a, b,· · · ,

_{から数人を選び}

,

集合

X

_を

X ≡{a, b, c, d, e,}

と定義する

. X

_の人数は

5

と直ぐに数えられるが

,

ここで数えるとは次を意味する

:

U

_{を自然数の部分集合}

U ≡{1,2,3,4,5}

とすると

X

_と

U

_とに

1 : 1

_{関係がある}

=X

_{の元に番号をつける}

.

定義

2.1.

_ある集合

A

_と

B

_とに

1 : 1

_{関係があるとは}

,

_{以下の条件をみた}

す関係式

h:B →A

_{が存在することである}

:

x∈B

_にたいし

h(x)∈A

_かつ

h(B) =A, x, y∈B

_かつ

x&=y⇒h(x)&=h(y).

(2.1)

(

この

(2.1)

をみたす関係式を全単射とよぶ

.) (

(ii) Step 1.

_{女子学生の集合}

Y ≡{α,β,γ,δ,&}

がある

.

_いま

X

_と

Y

が同数であることを確認するには

,

_「

Y

_と

U

＝{1,2,· · · ,5}

とに

1:1

の関係がある」ことを確かめるより

,

_{もっと簡単}

な方法がある

.

(6)

Step 2.

簡単な方法

=

「男女が

1:1

で互いに手をつなぐ」

.

全員が手をつなげれば

, X

_と

Y

_は同数

.

つまり

h:X↔Y

という全単射が存在した

.

(∗)

_以後

,

この考え方を使う

.

2.2 特別なランダム・ウォーク

ランダム・ウォークの応用を考えるとき

,

定数

c

_にたいしある

0< k≤n

_があり

,Sk > c

_{となる確率} を調べる必要がしばしば生じる

^*1.

c

*1

例えば

,{w(n)}

が株価だとして

,

_それが

1

_ヶ月内に

c

_{円を超える確率}

.

Step 1.

簡単のため

,a >0, b >0

_として

,

ランダム・ウォーク

W : (0, a)→(1, w(1))→· · ·→(n, b)

にたいし

,

_途中で

w(t)≤0

_となる

0< t < n

_がある

path

_の個数を

,

次の手順で数える

.

(i) W

_は

,

_途中で

x

_{軸と交差するので}

,

_{それが最初に}

x

_{軸と交わる時刻} を

t

_とする

.

t= min{k:w(k)≤0}. (ii) W

_にたいし

,

新しい

pathW^†

_{を次で定義する}

:

W^† : (0,−a)→(1,−w(1))→· · ·(t,0)→

→(t+ 1, w(t+ 1))→· · ·→(n, w(n)).

(2.2)

(t, 0) (0,a)

(n,b)

(0,-a)

W^†

の

path (

_赤

)

_は

,

_時刻

t

までは

W

と

x

軸に関して対称

,

_時刻

t

以降は

W

と同じ

path.

Step 2.

つまり

,

対応が有ることが判った

.

• (0, a)→(n, b)

_{かつ途中で}

x

_{軸と交差する}

path

⇒ (0,−a)→(n, b)

_なる

path

_のなかで

,

_唯一つの

path

_が対応

.

• (0,−a)→(n, b)

_なる

path ⇒ (0, a)→(n, b)

_{かつ途中で}

x

_軸と

交差する

path

のなかで

,

唯一つの

path

が対応

.

(7)

(t, 0) (0,a)

(n,b)

(0,-a)

図

2.1 (0, a)→(n, b)

_で

x

_{軸と交差する}

path

(0,a)

(n,b)

(0,-a)

(t, 0)

図

2.2 (0,−a)→(n, b)

_の

path

これより次の補題が得られる

重要な補題

! "

補題

2.2. (i) (0, a)→(n, b)

なるランダム・ウォーク

W

_にたいし

, W

_{のなかで途中で}

x

_{軸と交差する}

path

_の個数

=

(0,−a)→(n, b)

なるランダム・ウォーク

W^†

_の

path

の個数

. (ii)

前者の個数を数えることは難しいが

, (1.2)

_により

,

_{後者の個数は} 簡単に計算でき

,

(2.3) n!

(n+b+a

2 )! (n−b−a 2 )!

=nC(n+b+a)/2 (

( (1.2)

で

a→ −a

_{と置き換える}

.)

# $

(∗)

_{前の補題から}

,

「反射原理」が得られる

.

反射原理の定理

! "

定理

2.3 (

_反射原理

). b >0

_とする

. (0,0)→ (n, b)

_である

path

_のなかで

,

(2.4) w(1)>0, w(2)>0,· · · , w(n) =b >0

であるものの個数は

(2.5) b

n·ⁿC_(n+b)/2. (

# $

[

証明

] w(1)>0

_だから

, (2.4)

の

path

は点

(1,1)

_を通る

.

つまり

(1,1)→(n−1, b)

_という

path

_で

(2.4)

をみたすものの個数がも求める数

. (1.2) +

_補題

[

_反射法則

]

_より

,

(i) (1,1)→(n, b)

_という

path

_の個数

=n−1C_(n+b)/2₋₁.

(ii) x

_{軸と交わる}

path

_の個数

= (1,−1)→(n, b)

_という

path

_の個数

=n−1C(n+b)/2.

これより

求める数

=n−1C_(n+b)/2₋₁−n−1C_(n+b)/2

= (n−1)!

&

(n+b)/2−1'

!&

(n−b)/2'

!− (n−1)!

&

(n+b)/2'

!&

(n−b)/2−1'

!

= n!

&

(n+b)/2'

!&

(n−b)/2'

!

((n+b)/2

n −(n−b)/2 n

)

=nC_(n+b)/2· b n. !

(8)

3 _双対原理

pathW :w(0) = 0, w(1), w(2),· · · , w(n) (

_黒

)

_にたいし

y(k)≡w(k)−w(k−1) =±1, k= 1,· · · , n

とおく

.

_{そして新しい}

pathW^∗ (

_赤

)

_{を次で定義する}

:

W^∗:w^∗(0) = 0, w^∗(1)≡y(n), w^∗(2)≡y(n) +y(n−1),

· · · , w^∗(n)≡y(n) +· · ·+y(1).

(3.1)

Step1. pathW

_{から新しい}

pathW^∗

_を

(3.1)

_で作った

. W^∗

_は

,W

_から次の操作で得られる

:

1.

左右反転

,→ 2.

上下反転

,→ 3.

出発点を原点に移動こうして得られた

W^∗

_は

w(k)>0, k = 1,2,· · · , n

_{を満たしている}

.

ここが最大値

path W

n

ここが最大値

左右反転した path

ここが最小値

上下反転した path

ここが最小値

出発点を原点に移動した path

つまり

pathW

_と

path W^∗

_は合同

.

しかも

w^∗(n) =w(n)−w(n−1)+w(n−1)−w(n−2)+· · ·w(1)−w(0) =w(n).

Step 2.

逆に

*W : (0,0)→(n, b), w(k)+ >0 for k= 1,2,· · · , n.

なる

pathW*

_{が与えられた}

. (3.1)

_により

,W*

_{からつくられた}

path *W^∗

は

(3.2)

_{を満たすことを示す}

.

(9)

W*^∗

_は

,W*

から次の操作で得られる

:

1.

左右反転

,→ 2.

上下反転

,→ 3.

出発点を原点に移動

.

ここが最小値

w(k)>0, k= 1, 2, ,n の path

ここが最小値左右反転した path

n

ここが最高値上下反転した path

n

ここが最高値出発点を原点に移動した path

n

結局

,

原点から出発し

,

w(n)> w(k) for allk= 1,· · · , n−1 (

⇔

右端が最高値

)

という

path

_{が得られた}

.

この

W ↔W^∗

の関係を利用すると次が判る

.

!

双対原理

"

定理

3.1. b >0

_とする

. (0,0)→(n, b)

_という

path

で

(3.2) w(n)> w(k) for allk= 1,· · · , n−1 (

⇔

右端が最高値

)

となるものの個数は

b

n ⁿC_(n+b)/2. (

# $

[

証明

] Step 1. (0,0)→(n, b)

_という

path

で

(3.2)

をみたすもの

W : (0,0)→(n, b), w(n)> w(k) for k= 1,2,· · · , n

を考える

.

つぎにこの

pahtW

_にたいし

(3.1)

の

W^∗

_{を考えると}

(10)

W^∗: (0,0)→(n, b)

w^∗(k) =w(n)−w(n−1) +· · ·w(k)−w(k−1)

=w(n)−w(k−1)>0

つまり

W^∗

_は

(3.3) W^∗: (0,0)→(n, b), w(k)>0 for k= 1,2,· · ·, n.

Step 2.

_逆に

W* : (0,0)→(n, b), w(k)+ >0 for k= 1,2,· · · , n.

なる

path *W

_{が与えられた}

. (3.1)

により

,W*

_{からつくられた}

pathW*^∗

は

(3.2)

_を満たす

.

実際

,

y(k)≡W*(k)−*W(k−1), k= 1,2,· · ·n

だから

,

b

w^∗(n) =y(n) +y(n−1) +· · ·+y(1) =w(n)b −w(0) =b w(n),b b

w^∗(k) =y(n) +· · ·y(k) =w(n)b −w(kb −1)

だから

+

w^∗(n)−w+^∗(k) =w(n)+ −(

w(n)+ −w(k+ −1))

=w(k+ −1)>0.

つまり

*W^∗

_は

(3.2)

を満たしている

.

Step 3.

つまり

Step 1, 2

より

(3.2)

を満たす

path

の個数

=(3.3)

を満たす

path

の個数が示された

.

_後者の

path

_{の個数は定理}

2.3

_より

b

n ·nC(n+b)/2. !

注意

3.2.

公平なコインでコイントスを繰り返し

,

表なら

+1,

_裏なら

−1

という賭を

n

_回行う

.

累積の損得が「最終回で最高値

b

_{」となる確率は}

1

2ⁿ · b

n ·nC_(n+b)/2. (

公平なコインで

n

_{回トスを行うと}

, path 1

_{個に確率}

1/2ⁿ

_がある

.

(11)

4 _{反射原理の応用例}

!

投票問題

"

例題

4.1 (

投票問題

).

選挙の結果

A

_の得票

=j, B

_の得票

=k, j > k

となった

.

開票作業中

,A

_が

B

_{を常にリードし続ける}

”

確率

= j−k j+k. (

# $

[

_解答

]

_{横軸に投票数}

”,

_縦軸に

A

_の得票

- B

_{の得票をとり}

,

_ランダム・ウォーク

X

_{を走らせる}

.

開票作業中

,A

_が

B

_{を常にリードし続ける} ので

,

_最初の

1

_票目は

A

に入らなければならない

.

(1,1)

(j+k,j-k)

1 j+k

j+k-1

j-k-1

よって

,X

_の

path

は

(0,0)→(1,1)

_となる

.

投票総数は

j+k

_票で

,A

が

j

_票

,B

_が

k

_{票となったので}

,

X

_{の通るべき点}

: (0,0)→(1,1)→(j+k, j−k),

「開票作業中

,A

_が

B

を常にリードし続ける」

= (1,1)→(j+k, j−k)

_という

path

_が

x

_{軸に交わらない}

.

ここで

,

_「

(1,1)→(j+k, j−k)

_という

path

_が

x

_{軸に交わらない」に反} 射原理を使う

.

_この

path

_の個数は

j+k−1Cj−1−j+k−1Cj = (j+k−1)!

(j−1)!k! −(j+k−1)!

j! (k−1)!

= (j+k−1)!

(j−1)! (k−1)!

“1 k −1

j

”

= (j+k−1)!

(j−1)! (k−1)!· j−k j k

= (j+k)!

j!k! · j k

j+k ·j−k

j k =j+kCj·j−k j+k.

一方

,(0,0)→(j+k, j−k)

_という

path

_の個数は

j+kCj

だから

,

開票作業中

,A

_が

B

_{を常にリードし続ける}

”

_確率

=j+kCj ·j−k j+k

,

j+kCj = j−k j+k. !

(12)

5 _再帰時間

原点から出発し

,

_時刻

2n

_で

x

_{軸上にいる}

path

_を考える

.

(5.1) W : (0,0)→(2n,0).

•

この

path

_は「時刻

2n

に出発点に帰還した」もので

,

_時刻

2n

_を _再帰時間と呼ぶ

.

• (5.1)

となる

path

の個数は

2nCn

である

.

•

そのなかでずっと

x

_{軸より上にいる}

path

の個数を調べる

.

定理

5.1

! "

定理

5.1. (i) (5.1)

のなかで

,

(5.2) w(1)>0, w(2)>0, · · ·, w(2n−1)>0, w(2n) = 0

である

path

の個数は

1

n·²ⁿ−2Cn−1

個

. (ii) (5.1)

のなかで

,

(5.3) w(1)≥0, w(2)≥0, · · ·, w(2n−1)≥0, w(2n) = 0

である

path

_の個数は

1

n+ 1·²ⁿCn

個

. $

# $

[

証明

] (i) (5.1) + (5.2)

である

path

は

,

どれも

(2n−1,1)

_を通る

.

(2n-1,1) (1,1)

図

5.1 (5.2)

_の

path

つまり

(5.1) + (5.2)

である

path

は

,

W : (0,0)→(2n−1,1)

_かつ

(5.2)

を満たす

ものの個数と等しい

.

_ところが

,

_{この個数は既に}

§2

_定理

2.2 [

_反射原理

]

_で判っている

.

!

反射原理

"

b >0

_とする

. (0,0)→(n, b)

_である

path

_のなかで

,

「

w(1)>0, w(2)>0,· · ·, w(n) =b >0

」であるものの個数は

(b/n)nC(n+b)/2. "

# $

これから

(5.1) + (5.2)

である

path

の個数

= 1

2n−1 ²ⁿ⁻¹Cn

= 1

2n−1

(2n−1)!

n! (n−1)! = 1 n

(2n−2)!

(n−1)! (n−1)! = 1

n ²ⁿ⁻²Cn−1.

(13)

(ii)

図

5.1

より

, (i)

の

path

は

W : (1,1)→(2n−1,1)

_かつ

(5.3)

を満たす

.

つまり

,

(5.4) (1,1)→(0,0), (2n−1,0)→(2n,0)

とすると

, (5.1)+(5.3)

_の

path

_{が得られる}

. (5.4)

_は

,n→n+ 1

_と置き換えれば良いので

,

(5.1) + (5.3)

である

path

の個数

= 1

n+ 1 ²ⁿCn. !

6 ランダム・ウォークとコイントス

我々は

,

ランダム・ウォークを次で定義した

.

ランダム・ウォーク

! "

ρ₁,ρ₂,· · ·

を

{1,−1}

どちらかの値をとる数列とする

.

実数

a

_{と自然数}

n

_にたいし

,

_{新しい数列}

w(n)≡

! a, n= 0

a+ρ₁+ρ₂+· · ·+ρ_n, n= 1,2,· · ·

を考える

.

ここで

, 2

次元平面で

,

以下の各点を結ぶ折れ線

( path

と呼ぶ

)

をランダム・ウォーク

W

_と呼ぶ

:

W : (0, w(0))→(1, w(1))→(2, w(2))→· · ·→(n, w(n))→· · ·

# $

(∗)

_ここで

,ρ1,ρ2,· · ·

の値に確率を導入する

.

つまり

,

公平なコインを投げ

, k

_{回目のコイントスで}

!

表が出る

⇒ρk = 1,

確率

1/2

裏が出る

⇒ρk =−1,

_確率

1/2

とする

. a= 0

_とおき

,

w(n) =

! 0"n n= 0

k=1ρk n≥1

は

n

回のコイントスで得られた累積損得額となる

.

また

ランダム・ウォークの性質

! "

• W : (0,0)→(n, w(n)

_という

path

は

2ⁿ

_個

,

•

一つ一つの

path

が

1/2ⁿ

_{の確率を持つ}

.

# $

(∗) W : (0,0)→(1, w(1))→· · ·→(n, w(n))→· · ·

という

path

_に対し

,

_{次の用語を定義する}

.

!

用語

"

(i)

_時刻

n

_{で原点に帰還する}

⇔ w(n) = 0, (ii)

_時刻

n

_で

0

_{に初め帰還する}

⇔ w(1))= 0,· · · , w(n−1))= 0,w(n) = 0,

(iii)

時刻

n

_{で点}

r >0

_{に初めて到達する}

⇔ w(1)< r, · · · , w(n−1)< r, w(n) =r.

# $

以下の議論で

,

これらの確率を調べる

.

(14)

定理

6.1

! "

定理

6.1. w(0) = 0

であるランダム・ウォークを考える

. u_2n≡ 1

2²ⁿ ²ⁿC_n, n= 1,2,· · ·

とおくと

,

以下の確率は全て

u2n

に等しい

.

(i) P[w(2n) = 0], (ii) P[w(1))= 0, w(2))= 0,· · · , w(2n))= 0],

(iii) P[w(1)≥0, w(2)≥0,· · · , w(2n)≥0]. $

# $

[

証明

] (i) (0,0)→(2n,0)

_を結ぶ

path

の個数は

2nCn

個

.

一方

,

時刻

2n

_までの

path

_の総数は

2²ⁿ

_個だから

, (i)

_{が導かれる}

.

(ii) Step 1.

_{前述の定理}

5.1

_を使う

.

定理

5.1 (i)

! "

W : (0,0)→(2n,0)

_のなかで

,

w(1)>0. w(2)>0, · · ·, w(2n−1)>0, w(2n) = 0

である

path

_の個数は

1

n ·2n−2C_n−1

_個

.

# $

これより「

w(1)>0, w(2)>0,· · ·, w(2k−1)>0, w(2k) = 0

_」である

path

の個数は

1

2k−1 ^2k⁻¹Ck == 1 2k−1

(2k−1)!

k! (k−1)! = 1

k ^2k⁻²Ck−1.

よって「

w(0) = 0, w(1)$= 0, w(2)$= 0,· · ·, w(2k−1)$= 0, w(2k) = 0

」である

path

_の個数は

,

_上の

2

_倍

, 2

k ^2k⁻²C_k₋₁

_個

.

⇒ P[w(0) = 0, w(1)$= 0, w(2)$= 0,· · ·, w(2k−1)$= 0, w(2k) = 0]

= 1 2^2k

2

k ^2k−2C_k−1= 1

2k u_2k−2. (6.1)

ここで「原点に戻る時刻は常に偶数」に注意し

,

{

時刻

2n

以下では原点に戻らない

}={

全体

}−{

時刻

2

で初めて原点に戻る

}

−{

時刻

4

で初めて原点に戻る

}−· · ·−{

時刻

2n

で初めて原点に戻る

}

だから

,

P[w(0) = 0, w(1)$= 0, w(2)$= 0,· · ·, w(2n)$= 0]

= 1−P[w(1)$= 0, w(2) = 0]−P[w(1)$= 0, w(2)$= 0, w(4) = 0]

−· · ·−P[w(1)$= 0,· · ·, w(2n)$= 0]

= 1−1 2u0−1

4u2−· · ·− 1

2nu2n−2. (6.2)

Step 2.

_次に

!

恒等式

"

u_2k₋₂−u_2k = 1

2^2(k⁻^{1) 2}^k⁻²C_k₋₁− 1 2^2k ^2kC_k

= 1

2^2(k⁻¹⁾

(2k−2)!

(k−1)! (k−1)!

#1−1 4

(2k−1) 2k k·k

$= 1

2k u2k−2

# $

となるから

,

これを

(6.2)

に代入して

,

P[w(0) = 0, w(1))= 0, w(2))= 0,· · · , w(2n))= 0]

= 1−1

2u₀−1

4u₂−· · ·− 1

2nu_2n₋₂

= 1−#

u0−u2

$−#

u2−u4

$−· · ·−#

u2n−2−u2n

$

= 1−u0+u2n =u2n. (ii)

が得られた

.

(15)

(iii) Step 1.

前述の定理

5.1

を使う

.

定理

5.1 (ii)

! "

W : (0,0)→(2n,0)

のなかで

,

w(1)≥0, w(2)≥0, · · ·, w(2n−1)≥0, w(2n) = 0

である

path

_の個数は

1

n+ 1·2nCn

個

.

# $

まず

{w(0) = 0, w(1)≥1, w(2)≥1, · · ·, w(2k−2)≥0, w(2k−1)<0}

={w(0) = 0, w(1)≥1, w(2)≥1, · · ·, w(2k−2) = 0, w(2k−1) =−1}

だから

(2k-2,0)

(0,0)

(2k-1,-1)

-1 0

図

6.1 2k−1

_{で負になる}

path

P[w(0) = 0, w(1)≥1, · · ·, w(2k−2)≥0, w(2k−1)<0]

=P[w(0) = 0, w(1)≥1,· · ·, w(2k−2) = 0, w(2k−1) =−1]

= 1

2^2k−1 1

k ^2k−2C_k−1= 1 2ku_2k−2.

Step 2.

初めて負になる時刻は常に奇数時刻

.

これに注意すると

,

{

時刻

1,2,· · ·,2n

_{では非負}

}={

全体

}−{

時刻

1

_{で初めて負になる}

}

−{

時刻

3

_{で初めて負になる}

}−· · ·−{

時刻

2n−1

_{で初めて負になる}

}

だから

,

P[w(0) = 0, w(1)≥0, w(2)≥0,· · ·, w(2n)≥0]

= 1−P[w(1) =−1]−P[w(1)≥0, w(2)≥0, w(3) =−1]

−· · ·−P[w(1)≥0,· · ·, w(2n−2)≥0, w(2n−1) =−1]

= 1−1 2u0−1

4u2−· · ·− 1

2nu2n−2. (6.3)

ここで

(6.3)=(6.2)

だから

(ii)

と一致し

, (iii)

が得られた

. !

(∗) RW

_{を使って証明できる}

,

_{次の恒等式は}

,

以後の計算に有用である

.

計算で有用な補題

! "

補題

6.2. n≥1

_とする

. u2n≡ 1

2²ⁿ²ⁿCn

に対し

,

_{次式が成立}

.

(6.4) u2n=

%n k=1

1

2ku2k−2·u2n−2, u0≡1. $

# $

[

_証明

] Step 1. w(0) = 0

_である

RW

_を考える

. (6.1)

_式

! "

P[w(0) = 0, w(1)$= 0, w(2)$= 0,· · ·, w(2k−1)$= 0, w(2k) = 0]

= 1 2^2k

2

k ^2k⁻²Ck−1= 1

2k u2k−2.

# $

(16)

より

,

この

RW

の

path

が最初に

0

_{に到達する時刻を}

2T

_とおく

. 2T = 2k

_となる

path

の個数は

2

k ^2k⁻²Ck−1= 2

ku2k−2.

また「

w(2k) = 0→· · ·→w(2n) = 0

_となる

path

の個数」は

2(n−k)Cn−k =u2n−2k.

よって

「

w(0) = 0

_{から出発し}

,

_時刻

2k

_で初めて

0

_に帰還し

, w(2n) = 0

_となる

path

_」

(6.5)

の個数は

2

k ^2k⁻²Ck−1×2(n−k)Cn−k= 2

ku2k−2·2^2k⁻²×u2n−2k·2²ⁿ⁻^2k

= 2²ⁿ

2k u_2k−2·u_2n−2k.

2k 2n

O

初めて 0 に帰還

ずっと正の側

2k 2n

O

ずっと負の側初めて 0 に帰還

Step 2. w(0) = 0

_という

RW

_を考える

.

_前述の定理

6.1 (i)

! "

w(0) = 0

であるランダム・ウォークに対し

,

P[w(0) = 0, w(2n) = 0] =u2n.

# $

より

,

この

RW

は時刻

2n

_で

0

_にいる

.

そこで

, (6.5)

を考えて

u2n=P[w(0) = 0, w(2n) = 0]

= Xn

k=1

P[w(0) = 0,

時刻

2k

で初めて

0

に帰還

, w(2n) = 0]

= Xn

k=1

2²ⁿ

2k u2k−2·u2n−2k× 1 2²ⁿ =

Xn

k=1

1

2ku2k−2·u2n−2k. !

7 path _の周遊 (excursion)

再び

,

公平なコイン・トスによって駆動されるランダム・ウォークを扱う

.

つまり

,

公平なコインを投げ

,

k

_{回目のコイントスで}

!

表が出る

⇒ρk = 1,

_確率

1/2

裏が出る

⇒ρk =−1,

_確率

1/2

とする

. a= 0

_とおき

,

w(n) =

! 0"n n= 0

k=1ρk n≥1

は

n

回のコイントスで得られた累積損得額となる

.

また

ランダム・ウォークの性質

! "

• W : (0,0)→(n, w(n)

_という

path

_は

2ⁿ

_個

,

•

一つ一つの

path

_が

1/2ⁿ

_{の確率を持つ}

.

# $

(17)

(∗) §3

で述べた

(7.1)

右端で最高値

b >0

_になる

path

原点から出発し右端で最高値をとる path

ここが最高値

n b

0 は「時刻

n

_で初めて

b

_{に到達する}

path

_{」と言い換えられる}

.

また

,

定理

3.1[

双対原理

]

で

(7.1)

の個数は判っている

.

!

双対原理

"

定理

3.1 b >0

_とする

. (0,0)→(n, b)

_という

path

_で

b=w(n)> w(k) for allk= 1,· · ·, n−1“

⇔

右端が最高値

”

となるものの個数は

b

n ⁿC(n+b)/2. $

# $

これを使うと

,

次の定理が得られる

.

双対原理から導かれる命題

! "

命題

7.1. b

_{を自然数とする}

.

原点から出発したランダム・ウォークが

,

時刻

2n−b

_に初めて

b

_{に到達する}

path

の個数は

b

2n−b ²ⁿ⁻^bCn, n≥b >0, %

# $

(∗)

さらに詳しくランダム・ウォークの挙動を見る

.

•

原点から出発したランダム・ウォークは何度も原点に戻る

.

•

「時刻

0

_で原点

→ 1

回目の原点への帰還」の時間区間の

path

を

,

最初の周遊と呼ぶ

.

•

同様に「

k−1

_{回目の原点への帰還}

→ k

回目の原点への帰還」の時間区

間の

path,

を

k

_{番目の周遊という}

.

•

「周遊が幾つあるのか」を調べる

.

0

最初の周遊

第2の周遊第3の周遊

第4の周遊

b

_{番目に戻る確率}

! "

定理

7.2. b

_{を自然数とする}

.

原点から出発したランダム・ウォークが

,

時刻

2n

_{で原点に戻り}

,

_かつ

b

_{個の周遊を持つ確率}

= b

2n−b ²ⁿ⁻^bCn

1 2²ⁿ⁻^b. %

# $

(18)

[

定理

7.2

の証明

Part 1.] b >0

_{を自然数として}

,

(7.2)

原点から出発し

,

時刻

2n−b

_で初めて

b

_{に到達する}

path w

を考える

.

ここが最高値

2n-b b

0

図

7.1 pathw

この

path

_に「傾き

−1,

_長さ

1

_の線分

L0

」を次の手順で

b

_{個挿入する}

. (i)

_{原点のすぐ右}

,

(ii)

_初めて

1

に到達する時刻のすぐ右

,

(iii)

初めて

2

に到達する時刻のすぐ右

,

...

(iv)

_初めて

b−1

に到達する時刻のすぐ右

ここが最高値

2n-b b

0

ここに挿入ここに挿入

ここに挿入

挿入する線分 L0

ここが最高値

2n-b b

0 T1 T2

1 2

ここが最高値

2n-b b

0

ここが最高値

2n+1-b T1 b-1

T2

T1 T2

ここが最高値

2n-b b

0

ここが最高値

2n+2-b b-2 T1

T2

T1 +1 T2 +2

ここが最高値

2n-b b

0

ここが最高値

2n+3-b b-3 T1

T2

T1 +1 T2 +2

(19)

⇒

こうやって得られた

path

を

w^∗

_とする

.

0 ここに挿入

ここに挿入

2n 0

ここに挿入

すると

w^∗

_{はいかの性質を満たす}

. w^∗

_の性質

! "

w^∗(0) = 0, w^∗(2n) = 0, w^∗(k)≤0 for k= 0,1,· · · ,2n, (7.3)

k= 0,1,· · · ,2n

_のなかで

,w^∗(k) = 0

_となる

k

_は

b+ 1

_個

. (7.4)

# $

!

補足

"

補題

7.3.

「

(7.3), (7.4)

が成立」は判りにくいので

,

証明する

. %

# $

[

補足の証明

]

図

7.1

の

pathw

_にたいし

,

次のように置く

:

•

初めて

1

_{に到達する時刻を}

T1,

•

初めて

2

に到達する時刻を

T2, ...

•

初めて

b−1

_{に到達する時刻を}

Tb−1

ここが最高値

2n-b b

0

ここに挿入ここに挿入

ここに挿入

T1 T2

「傾き

−1,

_長さ

1

_{の線分」を}

L0

とする

. pathw^∗

_は

, pathw

_{から次の手} 順で得られた

.

_{挿入の手順を追うと}

0

_{になる回数が判る}

.

(i)

_{原点のすぐ右に}

L0

を挿入

⇒ w^∗(1) =−1, (ii) w

_が

,

初めて

1

_{に到達する時刻}

T1.

⇒ (i)

_で

L0

が

1

_{個挿入されたので}

,w^∗

_では

T1→T1+ 1.

また

w^∗(T1+ 1) = 0.

⇒ T1+ 1

_は

w^∗

_が

1

回目に

0

_{に帰還する時刻}

=

最初の周遊

.

0

ここに挿入

2n 0

ここに挿入

T1 +1 T2 +2

(20)

0

2n 0

ここに挿入

T₁ +1 T₂+2

1つ増えた

ここに挿入 1つ下げた

計2つ増えた計2つ下げたここに挿入

計3つ下げた

計3つ増えた

(iii) w

_に対し

T₁

_の右に

L₀

_を挿入

⇒ w(T1+ 2) =−1, (iv) w

_が

,

_初めて

2

_{に到達する時刻}

T2.

⇒ (i), (ii)

で

L0

が

2

個挿入されたので

,w^∗

_では

T2→T2+ 2.

また

w^∗(T2+ 2) = 0.

⇒ T2+ 2

_は

w^∗

_が

2

回目に

0

_{に戻る時刻}

=2

番目の周遊

.

(v) w

_に対し

T1

の右に

L0

を挿入

⇒ w(T1+ 2) =−1, ...

(vi) w

_が

,

_初めて

b−1

_{に到達する時刻}

T_b₋₁.

⇒ (i), · · ·,

で

L0

が

b−1

_{個挿入されたので}

,

w^∗

_では

Tb−1→Tb−1+b−1.

_また

w^∗(Tb−1+b−1) = 0.

⇒ T_b₋₁+b−1

_は

w^∗

_が

b−1

_回目に

0

_{に戻る時刻}

=b−1

_{番目の周遊}

.

(vii) w

_に対し

Tb−1

の右に

L0

を挿入

⇒ w(Tb−1+b) =−1, (viii) w

_は

,

_時刻

2n−b

_で初めて

b

_に到達

.

⇒ (i),· · ·, (vii)

_で

L0

が

b

_{個挿入されたので}

,w^∗

_では

2n−b→2n.

また

w^∗(2n) = 0.

⇒ 2n

_は

w^∗

_が

b

_回目に

0

_{に戻る時刻}

=b

_{番目の周遊}

. !

[

定理

7.2

の証明

,Part 2]

逆に

(7.3), (7.4)

の条件時刻

2n

が

b

回目の

0

への帰還となる

path w^†

! "

(7.3) w^†(0) = 0, w^†(2n) = 0, w^†(k)≤0 fork= 0,1,· · ·,2n, (7.4) k= 0,1,· · ·,2n

_のなかで

,w^†(k) = 0

_となる

k

_は

b+ 1

_個

.

# $

を満たす

path w^†

_{があるとする}

.

逆の手順

(7.5)

! "

この

w^†

_から

,

(7.2)

原点から出発し

,

時刻

2n−b

_で初めて

b

_を通る

pathw#

を作ることができる

.

# $

[

_定理

7.2

_の証明

,Part 3] Step 1.

_証明

, Part 1

_および

Part 2

_から

,

時刻

2n

が

b

_回目の

0

への帰還となる

pathw

! "

(7.3) w(0) = 0, w(2n) = 0, w(k)≤0 for k= 0,1,· · ·,2n, (7.4) k= 0,1,· · · ,2n

_のなかで

,w(k) = 0

_となる

k

_は

b+ 1

_個

.

# $

と

右端の時刻

2n−b

_が最高点

b

_の

path

! "

(7.2)

原点から出発し

,

時刻

2n−b

_で初めて

b

_{に到達する}

pathw

# $

が

1 : 1

に対応していることが証明できた

.

(21)

ここで命題

7.1

より

前者の個数

=

_{後者の個数}

= b

2n−b ²ⁿ⁻^bC_n. Step 2. (7.3), (7.4)

_を満たす

pathw

_を考える

.

_この

w

_は

時刻

0→

最初に

0

_{に帰還する時刻}

$ %& '

最初の周遊

→

→2

番目に

0

_{に帰還する時刻}

$ %& '

2

_{番目の周遊}

→· · ·

→b−1

_番目に

0

_{に帰還する時刻}

→b

_番目に

0

_{に帰還する時刻}

$ %& '

b

_{番目の周遊} と

b

_{個の周遊に分解できる}

.

• (7.3)

より「

pathw

_{のすべての周遊は}

x

_{軸より下にある」}

.

• x

軸より上にある周遊を鏡像で作ると

,2^b

_{個の異なった}

path

_ができる

.

0

最初の周遊第2の周遊第3の周遊第4の周遊

図

7.2

_赤が

path w,

_{青の周遊を鏡像で作る}

•

つまり「原点から出発し

,

時刻

2n

_{で原点に戻り}

,

かつ

b

_{個の周遊を持} つ

path

_{」の個数は}

,

b

2n−b ²ⁿ⁻^bCn×2^b.

•

一方

,

時刻

2n

_までの

path

の総数は

2²ⁿ

_個だから

,

「原点から出発し

,

時刻

2n

_{で原点に戻り}

,

かつ

b

個の周遊を持つ確率」は

b

2n−b ²ⁿ⁻^bCn×2^b× 1

2²ⁿ = b

2n−b ²ⁿ⁻^bCn

1

2²ⁿ⁻^b. !

8 Arc sine _の法則 - 不公平の法則

•

時刻

k−1

_から

k

_までの

path w

_が

x

_{軸より上にあるとき}

,

「

RW

が期間

1

_{だけ正の側にいた」}

と言う

.

•

より詳しく言うと

,

{w(k−1)≥0, w(k)>0}

もしくは

{w(k−1)>0, w(k)≥0}

が成立することで

,

「コイントスによる賭の累積損益が正の期間」と解釈できる

.

•

「

RW

が正の側にいる期間の長さ」を調べる

.

(22)

Arc sin

の法則

! "

定理

8.1.

_{原点から出発する}

pathw

_に対し

,

R(2k,2n)≡RW

が期間

2k

_{だけ正の側におり}

,

期間

2n−2k

_{だけ負の側にいる確率} とおく

.

すると

R(2k,2n) = 1

2^2k ·^2kCk× 1

2²ⁿ⁻^2k ·²ⁿ−2kCn−k. $

# $

注意

8.2.

_直感では

RW

_が期間

n

_{だけ正の側におり}

,

_{同じ長さの} 期間

n

_{だけ負の側にいる確率}

=R(n,2n)% 1

2.

⇒

ところが実際は全く異なる

.

例

n= 10

_のとき

2k 0 2 4 6 8 10

20 18 16 14 12

R(2k,20) 0.176 0.092 0.073 0.065 0.061 0.06

で

,

「ずっと正の側にいるグループ」

(=

「ずっと負の側にいるグループ」

)

の確率が最大

:

1 2 3 4 5 6 7 8 9 10 11

0.00 0.05 0.10 0.15

• n= 10

_で

R(0,20)!

R(10,20)%3.

•

この傾向は

n

を大きくしても変わらない

.

•

実際

,n= 54

_で

˘R(0,54) +· · ·+R(4,54)¯.˘

R(25,54) +· · ·+R(29,54)¯

#3.5

2 4 6 8 10

0.05 0.10 0.15

図

8.1

_青が

n= 10,

_赤が

n= 54

の場合

(∗)

「極端なグループの確率が大きい」ことは

,n= 49

_{での「正の側に長} くいる組」「正の側にまあまあ長くいる組」

· · ·

と分類すると明瞭になる

.

正の側にいる割合

81%

以上の組

80%−61%

の組

60%−40%

の組

19%

以下の組

39%−20%

の組

その確率

29% 14% 13%

1 2 3 4 5

0.00 0.05 0.10 0.15 0.20 0.25

図

8.2

_左から

81%

_以上

, 80-61%, 60-40%, 39-20%, 19%

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