■

トロン飲酒運転
「酔歩」という問題がある。英語だと Random Walk。京都とか札幌で酔っ払って、曲り角のたびにランダムな方向に曲がって歩き続けるとする。時間が経った後、出発点からの距離は平均でどのくらいか。これは簡単に計算できて、時間の平方根に比例する(距離の二乗が時間に比例するのを示すのが簡単な方法)。この√ｔってのはいろんな現象に現れ、たとえばデリバティブの価値を評価するブラックショールズ式にもたくさん出て来る。株価は上下にランダムに動くと仮定すれば時間ｔ後の値動きは√ｔに比例するから。
曲り角に来る度になにか目印を落すとする。そうすると、京都みたいに平面の上を動くときは、ｔ回曲がった後にはｔ個の目印が半径√ｔの範囲に落ちている。面積は半径の二乗＝ｔに比例するから、この半径の内側ではそこらじゅうに落ちていることになる。つまり酔っ払いは京都市内をほとんどくまなく歩き回ることになり、この人とはぐれてしまってもどこかでずーーっと待っていれば必ず会える。これが三次元空間だと、ｔ個の目印が体積＝半径の三乗＝ｔの1.5乗の範囲に散乱しているので、ｔが大きくなる程密度が薄くなり、時間が経つ程酔っ払いを見つけるのは困難になる。すなわち宇宙で酔っ払ったら迷子になるってこと。
「トロン」という映画でバイクのレースをやってた。走った後には壁が出来て、これにぶつかるとアウト。これを一人で飲酒運転することを考える。一秒ごとに直進、左折、右折をランダムに選ぶ。ｔ秒後に生き残っている確率はどのくらいか。また生き残ったやつの出発点からの直線距離の平均はどのくらいか。
これは非常に単純な問題だけど、簡単には解けなくてコンピュータシミュレーションが盛んに行われている問題。鎖状高分子の性質なんかともからんでいる。シミュレーションする場合は実際にランダムに動いて行く。ただ問題があって長い間動かしてるとほとんどの場合ぶつかってアウトになり、サンプル数が少なくなってしまう。ひどい場合は一つもサンプルが得られない。ぶつかりそうになったら壁を避けてうごかせばいい、と考えるのが普通だろうけど、そうすると確率が違ってきてしまう。ランダムに動かしてたまたま生き残った場合、それぞれの経路は出現確率は(1/3)のｔ乗、で全て等しい。しかしぶつからないように運転した場合は経路によって出現確率が違ってしまう。で物理で必要とされるのは前者の確率分布なのでマズイ。
最近提唱された "PERM" というアルゴリズムでこの問題が解決された。(P.Grassberger, Rhys. Rev. E 56, 3682).まず100人くらいの運転手を別々のフィールドで同時にスタートさせる。しばらく経つとアウトになる奴がでてくる。人数が半分になったところで生き残ってる奴をそれぞれコピーして人数を倍にしてから続行する。人数が減ったらまた倍にして繰り返す。実際プログラムする場合は100人同時にやるとメモリ食うので、一人を走らせて、しばらくして生き残ってたらコピーして二人にして、これを順番に続行する。同時にやるんじゃなくて、フラクタルな木の絵とか描くプログラム組んだことある人なら分かると思うけど再帰呼出しを使って分岐させる。
実は壁を避ける方法でも計算は出来る。三方向に行ける場合は３、二方向は２、一方向の場合は１のウェイトを一歩ごとに掛け算していって、それぞれの経路についてこのウェイトを使った加重平均を計算すればOK。しかしこの場合も平均値がウェイトの極端に大きい経路に支配されてほかの大部分のサンプルは無駄になる。上の論文は実はこちらの方法を改良したもので、ウェイトが大きくなりすぎたら、これまでの経路を２つにコピーして、それぞれウェイトを半分にした二人の運転手を動かす。逆にウェイトが小さくなりすぎた場合、サイコロをふって確率1/2で計算中止、確率1/2でウェイトを二倍にして続行、というアルゴリズムを使っている。
これ実際にプログラムしてみたらメチャメチャ速くて感動。いままで使ってた他のアルゴリズムはアホみたいだ。プログラムはこれ。LINUX 用。スクリプトmkで実行ファイルaoができる。表示されるのは長さ256の経路。
それで結局のところ、距離と時間の関係はどうなるかっていうと、平面の場合は距離が時間の0.75 乗に比例、三次元だと時間の0.588乗くらいに比例することが分かっている。0.588 ってのは近似値。なんでこんな半端な値になるのかは誰も知らない。