問題
1辺の長さが1の立方体ABCD-EFGHの辺の上を次の規則に従って動く点Mがある。
(i) 時刻0においてMは頂点Aの上にある。
(ii) 各辺上でのMの速さは1である。ただし，辺の途中で後戻りしない。
(iii) 各頂点においてMはとどまらず，その頂点を端点とする3本の辺の中から確率で1つを選んで次の頂点まで移動し続ける。
このとき，以下の問いに答えよ。
(1) 時刻4，5においてMが頂点Aの上にある確率をそれぞれ求めよ。
(2) 時刻においてMが頂点Aの上にある確率をを用いて表せ。ただし，は負でない整数とする。
(3) 時刻8においてMが頂点Aの上にあるとき，その時刻までにMが立方体のすべての頂点を通る条件付き確率を求めよ。
方針
立方体の頂点をからまでの0,1座標で表し，1回の移動は3つの座標のうち1つを反転する操作と見る。時刻にAへ戻るには，各座標が偶数回ずつ反転されればよいので，3種類の記号からなる長さの列で各記号の出現回数が偶数のものを数える。(3)は時刻8で全頂点を通るなら，A以外の7頂点をちょうど1回ずつ通るハミルトン閉路になるため，反転記号列の形を数える。
解答
頂点をとし，隣り合う頂点への移動を，3つの座標のうち1つを反転する操作と考える。各時刻で3本の辺を等確率に選ぶので，長さの移動列は全部で通りである。
(1), (2)
時刻にへ戻るための条件は，3つの座標がそれぞれ偶数回反転されることである。3種類の記号の出現回数がすべて偶数である長さの列数をとする。偶奇を取り出す標準的な数え上げにより である。したがって，求める確率は
である。
特にが奇数のときはであり，が偶数のときは である。よって である。
(3)
時刻8にへ戻る移動列の総数は である。
時刻8までにすべての頂点を通り，かつ時刻8ににいるなら，時刻0と時刻8のを除いて，残り7頂点をそれぞれ1回ずつ通る。つまり長さ8の閉路で全頂点を一周する場合を数えればよい。
反転する座標をで表す。最初の2手は同じ座標を続けて選ぶとに戻ってしまうので，相異なるを選ぶ。残る座標をとすると，全頂点を1回ずつ通って戻る列は，この最初のに対して の2通りである。ここで空白を詰めて書けば，それぞれ である。の選び方は通りなので，有利な移動列は 通りである。
したがって求める条件付き確率は である。