確率漸化式
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
確率漸化式は『確率の問題』ではなく『状態遷移の問題』。n回目に起こりうる状況を有限個の状態に分類し、1手先でどこへ移るかだけを書く。難しいのは計算ではなく分類で、状態の取り方が決まった瞬間に問題は終わっている。逆に言えば、手が止まるのは常に『何を状態と見るか』を決めていないとき。
こんなときに使う
- 『n回の操作』『n秒後』など、回数が文字で与えられている → まず漸化式を疑う
- 毎回の操作が同じルールで、直前の状況だけで次が決まる（それ以前の履歴によらない）→ 漸化式が立つ確定サイン
- 『ちょうどn回目に初めて〜』→ 状態に『まだ達していない』を含める
- 状態が2つなら p_n と 1-p_n で足りる。3つ以上なら連立漸化式を覚悟する
手順
- 1. n回後の状態を、互いに排反で網羅的な有限個に分類する（ここが本体）
- 2. 各状態にいる確率を p_n, q_n, ... と置き、必ず p_n + q_n + ... = 1 を確認する
- 3. n回後の各状態から、n+1回目の1手で行き先と確率を全部書き出す（遷移図を描く）
- 4. p_{n+1} = （各状態からp状態へ流れ込む確率の和）として立式
- 5. 初期条件を n=0 と n=1 の両方で確認する（どちらで始めるかで式がずれる）
- 6. 漸化式を型で解く（多くは等比型 or 特性方程式）
- 7. 検算：n=1,2 を式に入れ、手で数えた値と一致するか見る
例題
部屋 A, B, C がある。点Pは1回の操作で、今いる部屋以外の2部屋のどちらかへ等確率で移動する。最初 A にいるとき、n回後に A にいる確率 p_n を求めよ。
解答
- n回後にAにいる確率を p_n とすると、Aにいない確率は 1 - p_n。
- 対称性から、Aにいないとき B にいる確率と C にいる確率は等しい（ここに気づくと状態が2つで済む）。
- n回後にAにいる場合、次の1手で必ずAを出るので、Aに留まる寄与は 0。
- n回後にAにいない場合（確率 1 - p_n）、その部屋から見てAは『今いる部屋以外の2部屋』の一方なので、Aへ移る確率は 1/2。
- よって p_{n+1} = (1/2)(1 - p_n)、p_0 = 1。
- 特性方程式 α = (1/2)(1 - α) より α = 1/3。
- p_{n+1} - 1/3 = -(1/2)(p_n - 1/3) となり、p_n - 1/3 = (2/3)(-1/2)^n。
- ∴ p_n = 1/3 + (2/3)(-1/2)^n
- 検算：p_0 = 1/3 + 2/3 = 1 ○。p_1 = 1/3 - 1/3 = 0 ○（1回で必ずAを出る）。p_2 = 1/3 + 1/6 = 1/2 ○（B or C から戻る確率 1/2）。
別解・ほかの見方
- 状態が3つ以上で対称性が使えないときは連立漸化式。p_n + q_n + r_n = 1 で1本消して2元にするのが定石
- 遷移が行列で書けるときは行列の n 乗（ただし東大では対角化を要求する形では出にくい）
- n が小さい場合を全部書き出して一般項を予想し、数学的帰納法で示す — 漸化式が解けない形のときの逃げ道。東大はこちらを要求することがある
- 『初めて到達する確率』は、到達済みを吸収状態にして分けると素直になる
落とし穴
- 状態の分類が粗く、同じ状態に見えて遷移確率が違うものを混ぜてしまう（最頻出の敗因）
- 逆に状態を増やしすぎて漸化式が解けなくなる。対称性で潰せないか必ず一度考える
- 確率の和が1になる検算をしない
- p_0 で立てた式に p_1 の初期条件を入れて添字が1ずれる
- 『n回後』と『n回目の操作で』を混同する
- 状態の分類が粗い／遷移の漏れ／和が1になる検算をしない
なぜ大事か
東大理系で最頻出の型。n回目の状態を有限個に分類し、1手先で遷移を書く
東大での出方
東大理系で最も出題頻度が高い型の一つ。設定が複雑（サイコロ、カードの並べ替え、格子上の点の移動など）で、状態を自分で設計させる形で出る。誘導で(1)に小さいnの具体値を求めさせ、(2)で漸化式、(3)で極限、という3段構成が典型。
確認問題
- サイコロを n 回投げ、出た目の和が3の倍数になる確率を求めよ（状態を『和を3で割った余り』に取る）
- 上の問題で n→∞ の極限を求め、直感と合うか確かめよ
発展
状態数が n に依存して増える設定（例：n個の箱を使う）では漸化式が立たない。その場合は数え上げか、別のパラメータで漸化式を立て直す。
前提になるノード
このノードを前提にするノード
「確率」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。