>>61
たぶん75％は間違い
4方向への移動を
a=(1,0),b=(0,1),c=(-1,0),d=(0,-1)
とベクトルで表し
n歩進むことをabcdの文字列で表す
4方向へ進むのは等確率で
その地点で終わるのはどの位置でも等確率
p
だとすると
4方向へ進むのはそれぞれ
(1-p)/4
の確率で選択されることになるので
Wn={a,b,c,d}^n
のそれぞれの元
w∈Wn
の出現確率は
P(w)=p((1-p)/4)^n
となる
ランダムウォークの全体は
W=∪Wn
でありこれはウォークをつなげる演算で半群となる
（最初から動かない空ウォークが単位元）
Wから
F2=<a,b>（2次の自由群）
への半群の準同形fを
f(a)=a,f(b)=b,f(c)=a^-1,f(d)=b^-1
として定義する
x∈F2
に対して
W(x)=f^-1(x)
とすると
この問題は
P(W(a)b)/P(W(ab))
を求めよという問題だということになる
W(a)=W(e)aW(e)
W(ab)=W(e)aW(e)bW(e)
W(e)W(e)=W(e)
であることに注意すると
P(W(a)b)/P(W(ab))=P(W(e)aW(e)b)/P(W(e)aW(e)bW(e))
となる