図のような6個の頂点からなる無向グラフがある。この

質問

図のような6個の頂点からなる無向グラフがある。このグラフ上を動く離散時間ランダムウォークを考える。時刻tで頂点iにいるとき、iを始点とする辺の中からランダムに選択し、時刻t+1で、選択した辺の終点jの位置に移
動する。例えば、頂点1にいるとき、それまでの軌跡とは独立に確率1/2で頂点2又は6に移動する。頂点1からスタートしたとき、初めて同じ頂点1に帰ってくるまでの時間の期待値は8となるそうですが、その理由がわかりません。どなたか教えて下さいませんか。

回答No.1

f272 · ベストアンサー

e1=頂点1にいるとき初めて同じ頂点1に帰ってくるまでの時間の期待値
e2=頂点2または6にいるとき初めて同じ頂点1に帰ってくるまでの時間の期待値
e3=頂点3または5にいるとき初めて同じ頂点1に帰ってくるまでの時間の期待値
e4=頂点4にいるとき初めて同じ頂点1に帰ってくるまでの時間の期待値
とすれば
e1=1+e2
e2=(1/3)+(1/3)(1+e2)+(1/3)(1+e3)
e3=(1/3)(1+e2)+(1/3)(1+e3)+(1/3)(1+e4)
e4=1+e3
が成り立つ。これを解けば
e1=8

お礼

非常に理解しやすかったです。助かりました。