2次元単純ランダムウォークは原点にいつ帰ってくるか？

質問

原点スタートの2次元単純ランダムウォークを考えます。すなわちX_iを独立同分布でそれぞれ確率1/4で(±1,0),(0,±1)のいずれかのベクトルを取る確率ベクトルとし、S_n=X_1+X_2+…+X_nとします。S_nを2次元単純ランダムウォークと呼ぶことにします。n>0のとき初めてS_n=0となったとするとき、H=nとおきます。Hを原点への最初再帰時刻（あるいは最初到達時刻）と呼ぶことにします。P(H<∞)=1、E(H)=∞がよく知られています。つまりいつかは必ず帰っては来るものの、その期待値は∞だということです。これらのことは大抵の確率論の本には書いています。そこで最初再帰時刻Hの分布を知りたいと思いました。時刻2nにしか戻らないので、P(H=2n)はいくらか？という問題といってもいいです。

このことは組み合わせ論の問題だと考えられます。つまりZ^2格子上で原点からスタートした長さ2nの道で、最初と最後以外に原点を通らないものは何通りあるか？という問題と同値です。もし途中で原点を通ってもよいのであれば、その道の本数は4項分布を用いて簡単に書き下せます。つまりi回右に、i回左に、j回上に、j回下に動いたとして、i+j=nであればよいので、Σ_{i+j=n}(2n;i,i,j,j)(1/4)^{2n}とかけるわけです。ただし(2n;i,i,j,j)=(2n)!/{i!i!j!j!}は4項係数とします。2n回目で初めて原点に戻ってくるというのは、2n回目に原点にいるような道から、2k回目に初めて原点に戻ってきて、その後2(n-k)回で原点に戻ってくる（この間は何回戻ってもよい）ような道の数をk=1～n-1まで引いてやればいいですから、p_n:=P(H=2n)の満たす漸化式を導くことは容易です。しかしそれが4項係数の和を含み、またp_nを決めるのにp_1～p_{n-1}の情報が全部いるという難解なものです。うまい数え方を見つけてp_nを簡単に表すよい方法はないものでしょうか？ちなみに1次元では簡単に解けましたが、同じ方法では出来そうもありませんでした。

回答No.2

stomachman

漸近評価ですか。
んと、こんなページ↓見つけました。
ご参考になりそうな文献がいくつか挙げられています。（え？読んでもないのに推薦しちゃいけない？えと、あの、その。）

参考URL：

http://www.geocities.jp/ikuro_kotaro/koramu/376_l8.htm

お礼

ありがとうございます。一応斜め読みはしたことがあるのですが、おそらく載っていなかったと思います。また後日確認しますが。先日東京に行ったおり、ジュンク堂池袋店で「ランダム・ウォーク : 乱れに潜む不思議な現象 / 津野義道著」なる本を見かけて読んでみたのですが、そこにもありませんでした。これもきちんとは読んでないですが、フェラーの本にも書いていないですし、難しい問題なのかも知れません。知り合いの専門家にちらっとうかがったところ、動機を聞かれて、知りたいだけだ、というようなことをいったら、そんなことはあまり意味があることとは思えない、というような答えをもらってしまいました。誰も求めようとしたりはしないのだろうか、とも思ったり．．．

回答No.1

stomachman

p[1] = q[1]
p[n] = q[n] - Σ{j=1～n}(p[j]q[n-j])

という漸化式の問題だと思ってみますと、一般項は

p[n] = Σ{Σ(jk[j]) = n}（((-1)^(1+s)) (s!/Π{j=1～n}k[j]!)(Π{j=1～n}(q[j]^k[j])))
ここに、s = Σ{j=1～n}k[j]

ただし最初のΣ{Σ(jk[j]) = n}…てのは、「自然数(≧0)の列<k[1], k[2], …, k[n]>のうちでΣ{j=1～n}(jk[j]) = nを満たすようなもの全部についての総和」。

になるんじゃないかと。こう書いてみたところで、p[n]が簡単に計算できるようになるんだかどうだか、そりゃ分かりませんけどね。

ところでstomachman、計算間違いは毎度のことですのでチェックよろしく。

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?qid=90849

お礼

ありがとうございます。コンピュータにかけて計算速度を調べてみましたが、やはりダメでした。実はp[n]のnに関する漸近評価が知りたいというのが動機だったのです。q[n]=((2n)!)^2/(n!)^4でq[n]は簡単になるようですが、p[n]はどうしても簡単になりません。1次元の場合、q[n]=(2n)!/(n!)^2であって、この場合はp[n]=(2n)!/(n!(n+1)!)とやたらと簡単になるようです。カタラン数と呼ばれる重要な組み合わせ論的数です。2次元でもこうはいかないものでしょうか．．．