酔歩
モデリングとシミュレーション
2
確率過程 (Stochastic Process)
系の時間発展が非決定的なもの
酔歩
確率過程の標準モデル
一次元格子
各時刻で、確率𝑝𝑝 で右に、1 − 𝑝𝑝 で左に移
動
3
酔歩：イメージ
時間
4
理論的解析
原点から出発した粒子の位置𝑥𝑥
時刻𝑡𝑡 で位置𝑥𝑥 に居るためには𝑚𝑚 =
(𝑡𝑡 + 𝑥𝑥)/2回右に移動
左右の移動順序の可能な組み合わせに注
意
時刻𝑡𝑡 で位置𝑥𝑥 に居る確率
 t 
( t − x ) /2
( t + x ) /2


P ( x)
p
=
(1 − p )
t+x
 2 
5
母関数を使う
確率
𝑥𝑥に対する確率から𝑚𝑚に対するものへ
P ( x ) : x = 2m − t , m ∈ [ 0, t ]
⇓
x+t
Q (=
m) : m
, m ∈ [ 0, t ]
2
母関数
t
G ( z ) = ∑Q ( m ) z m
m =0
6
母関数を使う：一般論
G (1)
=
t
=
Q (m)
∑
1
m =0
t
G ' ( z ) = ∑ mQ ( m ) z m −1
m =1
=
G ' (1)
t
mQ ( m )
∑=
m
x =0
=
G '' ( z )
t
m−2
−
m
m
Q
m
z
1
(
)
(
)
∑
m=2
t
2
−
=
− m
G '' (1) =
m
m
Q
x
m
1
∑ ( ) ( )
m =0
7
t m
t −m
Q ( m )   p (1 − p )
二項分布 =
m
に対して
t m
t −m
t
=
G ( z ) ∑   p (1 − p ) z m = ( zp + 1 − p )
m =0  m 
G (1) = 1
t
tp
G ' (=
z ) tp ( zp + 1 − p =
G (z)
)
zp + 1 − p
t −1
G ' (1) = tp
m = tp
x=
2m − t = 2tp − t= t ( 2 p − 1)
8
−tp 2
tp
G (z) +
G '( z )
2
zp + 1 − p
( zp + 1 − p )
G '' ( z )
−tp 2
=
( zp + 1 − p )
2
G '' (1=
tp
)
( −1 + t )
2
=
σ=
x2 − x
2
(
2
G (z) +
t 2 p2
( zp + 1 − p )
2
G (z) =
4m 2 − 4mt + t 2 − x
)
2
= 4G " (1) + 4 m (1 − t ) + t − x
2
( zp + 1 − p )
2
G (z)
2
= 4 m − m + 4 m (1 − t ) + t − x
2
tp 2 ( −1 + t )
2
2
(
)
= 4tp 2 ( t − 1) + 4tp (1 − t ) + t 2 − t 2 4 p 2 − 4 p +=
1 4tp (1 − p )
9
分布をもっと調べる
時刻𝑡𝑡が十分に大きいときに、位置の
平均の周囲の様子を調べる
10
準備：Stiringの公式
N
∑ ln n − ln N
N
∑ ln n
n =1
n =1
∫
N
1
N
1
ln xdx < ∑ ln n
N
N
∫
N
ln xdx
n =1
∑ ln n − ln N < ∫
1
n =1
ln xdx
N
∫
N
1
N
ln xdx < ∑ ln n < ∫ ln xdx + ln N
n =1
N
1
Stiringの公式
11
∫
N
1
N
ln xdx < ∑ ln n < ∫ ln xdx + ln N
N
1
n =1
N
N ( ln N − 1) + 1 < ∑ ln
=
n ln ( N !) < N ( ln N − 1) + 1 + ln N
n =1
ln=
N ! N ( ln N − 1) + O ( ln N )
d
( x ln x − x=) ln x + 1 − 1= ln x
dx
∫ ln xd=x
x ln x − x + C
12
分布の展開
仮定𝑡𝑡, 𝑡𝑡 − 𝑚𝑚, 𝑚𝑚 ≫ 1
t!
p m qt −m , q = 1 − p
Q ( m)=
( t − m )!m !
ln Q ( m ) = ln t !− ln ( t − m ) !− m !+ m ln p + ( t − m ) q
~ t ( ln t − 1) − ( t − m ) ( ln ( t − m ) − 1) − m ( ln m − 1)
+ m ln p + ( t − m ) ln q
~ t ln t − ( t − m ) ln ( t − m ) − m ln m + m ln p + ( t − m ) ln q
13
𝑚𝑚が平均𝑡𝑡𝑡𝑡から少しずれている範囲
1
ξ
=
( m − tp )
t
=
m t( p +ξ )
t − m = t (1 − p − ξ )
14
ln Q ( m ) ~ t ln t − ( t − m ) ln ( t − m ) − m ln m + m ln p + ( t − m ) ln q
~ t ln t − t (1 − p − ξ ) ln t (1 − p − ξ ) − t ( p + ξ ) ln t ( p + ξ )
+ m ln p + ( t − m ) ln q
~ −t (1 − p − ξ ) ln (1 − p − ξ ) − t ( p + ξ ) ln ( p + ξ )
+t ( p + ξ ) ln p + t (1 − p − ξ ) ln q
ln (1 + ξ ) =ξ −
ξ2
2
ln (1 − ξ ) =−ξ −
+ O (ξ 3 )
ξ2
2
+ O (ξ 3 )
15
−t ( p + ξ ) ln ( p + ξ ) + t ( p + ξ ) ln p
=
−t ( p + ξ ) ln (1 + ξ / p )
ξ 1 ξ2
2 
=
−t ( p + ξ )  −
+ O (ξ ) 
2
p 2 p

−t (1 − p − ξ ) ln (1 − p − ξ ) + t (1 − p − ξ ) ln q
=
−t ( q − ξ ) ln (1 − ξ / q )
ξ 1 ξ2
3 
=t ( q − ξ )  +
+ O (ξ ) 
2
q 2q

16
ξ 1 ξ2
ξ 1 ξ2
3 
3 
−t ( p + ξ )  −
+ O (ξ )  + t ( q − ξ )  +
+ O (ξ ) 
2
2
p 2 p

q 2q

 1 ξ2 1 ξ2
1 tξ 2
3 
=
−
+ O (ξ )  =
−
+ tO (ξ 3 )
t −
2 p (1 − p )
 2 p 2 q

 ( m − tp )2 
Q ( m ) ∝ exp  −

 2tp (1 − p ) 


2
m − m = tp 2 ( −1 + t ) + tp − t 2 p=
tp (1 − p )
2
2
17
位置の分布
𝑚𝑚 = (𝑥𝑥 + 𝑡𝑡)/2を代入する
2
  x+t
 
2
− tp  
 

x − ( 2 p − 1) t ) 
(
2


=

P ( x ) ∝ exp  −
exp  −
 2tp (1 − p ) 
8tp (1 − p ) 







 ( x − x )2 

= exp  −
2
2σ




σ 2 = 4tp (1 − p )
18
酔歩のシミュレーション
何を知りたいのか
「一つの粒子がどこに行くか」ではない
時刻とともに、粒子の存在確率がどの
ように変化するか
一つの粒子を追跡するのではない
19
多数の粒子の一斉酔歩
多数の酔歩を行う粒子を準備
初期位置は同じ
お互いに独立に動く
各時刻で、全粒子を酔歩
粒子の位置のヒストグラムを作る
20
「確率𝑝𝑝で○○する」をコード
する
double r = 乱数を生成
if ( r < p ) {
○○;
}
21
一つの粒子を動かす
public int walk(){
double r = Math.random();
if (r < p) {//確率p で右へ
x++;
} else {
x--;
}
return x;
}
22
時間
23
24
発展
2次元の酔歩
境界での振る舞い
境界で反射
境界で吸収