問題
点は次の規則で数直線上の負でない整数の上を正の方向へ動くものとする。ただしは負でない整数とする。
(a) 時刻0では点は原点にある。
(b) 点が時刻で座標にあるとき，時刻には確率で座標へ移動し，確率で座標へ移動する。
(c) 点が時刻で座標にあるとき，時刻には確率1で座標へ移動する。
点が時刻で座標にある確率をと書くことにする。以下の問いに答えよ。
(1) すべての自然数に対してを求めよ。
(2) ，が自然数であるとき，となる条件を，を用いて表せ。
(3) が自然数であるときを求めよ。
方針
偶数点にいるときだけ選択があり，偶数点から次の偶数点へは，1回で進む短いブロックと，奇数点を経由して2回で進む長いブロックの2種類がある。(1)(2)は小さい時刻と到達可能範囲を確認する。(3)は座標までに偶数点間のブロックをn個終えると考え，全時刻Tにするには長いブロックが個必要であることから組合せで数える。
解答
(1)
時刻0ではQは0にある。0は偶数点なので，時刻1には にそれぞれ確率でいる。
時刻1で1にいる場合，1は奇数点なので時刻2には必ず2に進む。時刻1で2にいる場合，2は偶数点なので時刻2には3または4にそれぞれ確率で進む。したがって
である。それ以外の自然数については到達できないので
である。
(2)
1回の移動で座標は必ず正の方向に進み，増加量は1または2である。したがって時刻Tにいる座標は必ず を満たす。
逆に，この範囲の整数は到達できる。実際，T回の移動のうち，増加量2の移動を回，増加量1の移動を回含めば合計増加量はになる。ただし，規則上，奇数点からは必ず1だけ進むが，偶数点から1だけ進んだ次の移動は自動的に1だけ進んで次の偶数点へ戻る。これは後のブロックの考え方と一致し，の各点は実際に到達可能である。
したがって，が自然数のとき である。
(3)
偶数点から次の偶数点へ進む方法を1つのブロックとして見る。方法は次の2種類である。 と1回で進む場合，確率はである。また と2回で進む場合も，最初に奇数点へ進む確率が，その後は確率1で進むので，全体の確率はである。
座標に到達するには，この偶数点間ブロックをちょうどn個完了する必要がある。n個のうち，2回かかる長いブロックが個，1回で進む短いブロックが個あるとすると，全体の時刻は である。これがTに等しいためには でなければならない。したがって，すなわち のときだけ可能である。
そのとき，長いブロックをn個中個選ぶ方法は通りであり，各ブロックの確率はどちらもなので，全体の確率はである。よって
である。