問題
図のように，正三角形を9つの部屋に辺で区切り，部屋，を定める。% 図は省略1つの球が部屋を出発し，1秒ごとに，そのままその部屋にとどまることなく，辺を共有する隣の部屋に等確率で移動する。球が秒後に部屋にある確率を求めよ。
方針
図の小三角形は上向きと下向きが交互に隣接しているので、下向きの部屋 から出発すると奇数秒後には必ず上向きの部屋にいる。したがって に到達できるのは偶数秒後だけである。偶数秒だけを見れば、下向きの3部屋 の間の2秒ごとの移動に圧縮できる。図から、任意の下向き部屋から2秒後に同じ部屋へ戻る確率は 、他の2つの下向き部屋へ移る確率はそれぞれ である。対称性により 以外の2部屋の確率を同じ文字で置き、1次漸化式を解く。
解答
図の下向きの小三角形は3つあり、出発点を 、到着点を 、残り1つを と呼ぶことにする。
1秒ごとに辺を共有する隣の部屋へ移るので、下向きの部屋から1秒後には上向きの部屋へ、上向きの部屋から1秒後には下向きの部屋へ移る。したがって、下向きの部屋 から出発した球は、奇数秒後には上向きの部屋にいる。よって奇数 については、 秒後に下向きの部屋 にいる確率は である。
次に偶数秒後を考える。下向きの1つの部屋から出発して2秒後にどの下向き部屋にいるかを調べる。図を見ると、どの下向き部屋にも3つの隣室がある。そのうち1つは外側の隅にある上向き部屋で、そこからは元の下向き部屋へ戻るしかない。残り2つの上向き部屋は、それぞれ元の下向き部屋と他の下向き部屋1つに辺で接している。
したがって、たとえば から出発したとき、2秒後に へ戻る確率は である。また、2秒後に へ移る確率と へ移る確率はいずれも である。同じ関係は から出発しても成り立つ。 秒後に にいる確率を とする。図は と について対称なので、 秒後に にいる確率も である。したがって にいる確率は である。
次の2秒で にいる確率を考えると、 から へ移る確率は 、 から へ移る確率も 、 から へ戻る確率は であるから である。右辺を整理して を得る。また、出発時には にいないので である。
この漸化式の一定値を求めると、 より である。したがって であり、 から となる。よって である。
以上より、求める確率は
である。