何を状態として覚えるかを決め、重複と漏れのない漸化式を立てます。
1．解く前に「数えているもの」を定義する
応用問題では、漸化式を解く計算より、次に必要な情報を状態として選ぶことが難所です。長さ、位置、直前の結果などのうち、将来の選択肢を決める情報を残します。分類は互いに重ならず、全ての場合を尽くす必要があります。
2．隣り合う1を禁止した0・1列
例題1：末尾で分ける
長さ $n$ の0・1列で、11を含まないものの個数を $T_n$ とします。末尾0なら直前は任意の適格な長さ $n-1$ の列です。末尾1なら、その前は0でなければならず、$n\ge2$ では末尾01を取り去って長さ $n-2$ の列に対応します。よって $$T_n=T_{n-1}+T_{n-2}\quad(n\ge2),\qquad T_0=1,\ T_1=2.$$ 空の列を1通りとすることで $T_2=3$ も同じ式に含まれます。$T_2,T_3,T_4,T_5=3,5,8,13$ です。
末尾1の前に「0を1つ付ける」ことと、その0が既に列の一部であることを混同すると、余計な2倍を掛ける誤りが起きます。対応が一対一かを確かめましょう。
3．確率は状態別に足し合わせる
例題2：まだHHが出ていない確率
公平で独立なコイン投げを考えます。$u_n$ を「最初の $n$ 回にHHがなく、末尾がT」の確率、$v_n$ を「HHがなく、末尾がH」の確率とします。0回の時点は便宜的に $u_0=1,v_0=0$ とします。$$u_{n+1}=\frac{u_n+v_n}{2},\qquad v_{n+1}=\frac{u_n}{2}.$$ HHが出ると成功済みの状態へ移り、$u,v$ には戻りません。
HHがまだ出ない確率は $q_n=u_n+v_n=T_n/2^n$。従って $q_5=13/32$、5回以内にHHが出る確率は $19/32$。$q_{n+2}=q_{n+1}/2+q_n/4$ と1本の式にもできます。確率の漸化式の係数を、個数の漸化式とそのまま同じにしないことが要点です。
4．待ち時間の期待値も状態から立てる
例題3：初めてHHが出るまで
$E_0$ を「直前にHがない状態」からの残り回数の期待値、$E_1$ を「直前がH」からの残り回数の期待値とします。次の1回を必ず数えて、$$E_0=1+\frac12E_0+\frac12E_1,\qquad E_1=1+\frac12E_0.$$ 後者で次がHなら終了するので、その先の残り回数は0です。解いて $E_0=6,E_1=4$。
期待値が有限である根拠も付けられます。重ならない2回ずつのブロックが全てHHでない確率は $(3/4)^k$。全体でHHがまだない確率はこれ以下なので $q_{2k}\le(3/4)^k$。尾確率の和が等比級数で抑えられ、待ち時間の期待値は有限です。
作問者の視点――条件と解法の関係
確認演習と解答
まず方針と必要な条件を言葉にしてから計算してください。解答は開いて確認できます。
演習1 11を含まない長さ6の0・1列の個数は。
解答・考え方を開く
$T_6=T_5+T_4=13+8=21$。
演習2 各回独立、Hの確率が $p\in(0,1)$ のとき、状態確率の式を作れ。
解答・考え方を開く
$u_{n+1}=(1-p)(u_n+v_n),v_{n+1}=pu_n$。$u_0=1,v_0=0$。
演習3 同じ条件でHHまでの期待回数を求めよ。
解答・考え方を開く
$E_0=1+(1-p)E_0+pE_1,\ E_1=1+(1-p)E_0$。解いて $E_0=(1+p)/p^2$。2回ブロックの成功確率 $p^2>0$ により有限性も確保できます。
関連する解説
参考資料
定理・基本的な方法の確認に使える公開教材です。本ページの例題・演習・作問上のコメントは、解説用に独自に構成しています。