ランダム・ウォークの到達確率と平均到達時間の計算龍谷大学理工学部数理情報学科飯田晋司研究室 T970100 連昭雄目次 1. 2. 3. 4. 5. 確率モデルとは？ランダム・ウォークコンピュータ・シミュレーション結果のまとめおわりに確率モデルとは？ • 例えば、液体の浸透・森林火災の広がり・伝染病の伝播のような、様々な自然現象に確率的ルールを定め単純なモデルに置き換えてこれらの様子を研究する。このようにモデル化されたものが確率モデルである。ランダム・ウォーク • 数直線上の原点に粒子を置き、左右それぞれ１動く確率を１／２とする。これを１ステップとしｎステップ後にはｘの場所に存在する確率を導くことのできるモデルである。ランダム・ウォーク（吸収壁）のメインソースⅠ void main(void){ （略） for(k_start =1; k_start < N+1;k_start++){ 粒子の発射点設定 printf(" k_start %d ¥n",k_start); for(i =0; i< N_walker;i++) x[i] = k_start; 設定した出発点に粒子を置く N_goal = 0; N_s = N_walker ; t = 0; prob[0] =0.; while( (N_s > 0) && (t < t_max ) ){ ループ条件（ゴールしてない粒子が０になるまでかつ時間がMAXまで） i = 0; while(i < N_s ){ u = urand(); if (u < p) x[i] = x[i] + 1; 確率ｐの時に右に１移動ランダム・ウォーク（吸収壁）のメインソースⅡ 確率qの時に左に１移動 else if(u < p + q) x[i] = x[i]-1; if(x[i]==0){ ０に到達したらゴールした粒子を＋１としゴールしていない粒 for(j=i+1;j<N_s;j++) x[j-1] = x[j]; 子を−１とする N_s = N_s -1; N_goal = N_goal +1; t_av = t_av + t +1; i = i-1; } else if(x[i]==N) { 吸収壁の条件でNに到達したらゴールしていない粒子を−１とする for(j=i+1;j<N_s;j++) x[j-1] = x[j]; N_s = N_s -1; i = i-1; } i = i+1; } t = t+1; コンピュータ・シミュレーション試行方法 • １次元の場合、移動確率をｐ、ｑ、ｓとし数直線は０ ∼２０でステップ数は１０００とする。 • ２次元の場合、移動確率をｐU、ｐD、ｐR、ｐLとしｘｙ平面は無限でステップ数は９０００とする。 • 上のグラフはｐ＝０．６、ｑ＝０．４で出発点を３次元の場合、移動確率をｐN、ｐS、ｐE、ｐW、ｐD、１０とした場合の到達確率のグラフｐUとしｘｙｚ平面は無限でステップ数は９０００とする。ランダム・ウォーク（吸収壁）到達確率のグラフ p=0.5,q=0.5 p=0.4,q=0.6 p=0.6,q=0.4 ■ p=0.3,q=0.4,s=0.3 ■ p=0.4,q=0.3,s=0.3 ■ p=0.1,q=0.1,s=0.8 ランダム・ウォーク（吸収壁）平均到達時間のグラフ p=0.5,q=0.5 p=0.4,q=0.6 p=0.6,q=0.4 ■ p=0.3,q=0.4,s=0.3 ■ p=0.4,q=0.3,s=0.3 ■ p=0.1,q=0.1,s=0.8 ランダム・ウォーク（反射壁）到達確率のグラフ出発点が２０に近く出発点が２０に近くなるにつれ減少なるにつれ減少 p=0.5,q=0.5 p=0.6,q=0.4 p=0.4,q=0.6 p=0.6,q=0.4 ■ p=0.3,q=0.4,s=0.3 ■ p=0.4,q=0.3,s=0.3 ■ p=0.1,q=0.1,s=0.8 ランダム・ウォーク（反射壁）平均到達時間のグラフ理論値とはずいぶん理論値とはずいぶん違う違う p=0.5,q=0.5 p=0.4,q=0.6 ■ p=0.3,q=0.4,s=0.3 ■ p=0.4,q=0.3,s=0.3 ■ p=0.1,q=0.1,s=0.8 p=0.6,q=0.4p=0.6,q=0.4 ２次元ランダム・ウォーク再帰確率、平均再帰時間のグラフ再帰確率のグラフ pU=pD=pR =pL=0.25 平均再帰時間のグラフ ■pU=0.2,pD=0.2,pR=0.3,pL=0.3 ■pU=0.1,pD=0.1,pR=0.4,pL=0.4 ■pU=0.3,pD=0.3,pR=0.2,pL=0.2 ■pU=0.2,pD=0.2,pR=0.3,pL=0.3 ■pU=0.1,pD=0.1,pR=0.4,pL=0.4 ■pU=0.3,pD=0.3,pR=0.2,pL=0.2 ■pU=0.2,pD=0.2,pR=0.3,pL=0.3 上下確率が小さい程上下確率が小さい程 pU=pD=pR ■pU=0.1,pD=0.1,pR=0.4,pL=0.4 再帰確率は大きい =pL=0.25 再帰確率は大きい ■pU=0.3,pD=0.3,pR=0.2,pL=0.2 ３次元ランダム・ウォーク再帰確率、平均再帰時間のグラフ再帰確率のグラフ pU=pD=pN =pW=pS=pE ■ pUの増加=0.1 ■ pUの増加=-0.1 平均再帰時間のグラフ pU=pD=pN =pW=pS=pE ■ pUの増加=0.1 ■ pUの増加=-0.1 結果のまとめ • 反射壁の場合、移動確率がｐ＞ｑだと右へ動こうとするので結果的に長い時間０に到達しない。 • ２次元の場合、上下への移動確率が小さいほど再帰確率が大きい。また理論値に上のグラフはｐ＝０．６、ｑ＝０．４で出発点を１０とした場合の到達確率のグラフ（横軸は近ずけるには、もっと大きな試行が必要で時間で縦軸は到達確率）ある。 • ３次元の場合、再帰確率はおそらく１より小さいと分かった。また２次元の場合同様もっと大きな試行が必要である。おわりに • コンピュータ・シミュレーションの結果は一部を除きかなり理論値に近い値が示された。 • ランダム・ウォークを実用レベルにまでもってくるにはさらに条件を付け加え工夫をしより複雑なシミュレーションにする必要があるだろう。