「$n$ 回後に状態 A にいる確率を求めよ」── この手の問題は、確率を直接数えるのが困難です。
確率と漸化式を組み合わせる確率漸化式は、東大・京大をはじめとする難関大の頻出テーマです。
さいころを繰り返し投げて、出た目に応じて状態が変わる問題を考えましょう。 たとえば「$n$ 回投げた後に偶数の状態にいる確率」を求めたいとき、 $n$ が大きくなると場合の数を直接数え上げるのは不可能に近くなります。
しかし、「$n$ 回目の確率」と「$(n+1)$ 回目の確率」の間には、 しばしば単純な関係式が成り立ちます。 この関係式が確率漸化式です。
確率漸化式の核心は、「$n$ 回目から $(n+1)$ 回目への1ステップの変化」だけに着目することです。
$n$ 回目の状態がどうであれ、$(n+1)$ 回目は直前の1回の試行だけで決まります。 「$n$ 回目に状態 A にいた場合」と「$n$ 回目に状態 B にいた場合」に分けて、 それぞれから $(n+1)$ 回目に目的の状態になる確率を足し合わせる。
これは全確率の公式を、$n$ と $n+1$ の間で適用しているのです。
確率漸化式を立てて解く手順は、次の4ステップです。
確率漸化式で最も重要なのは、最初の「状態の定義」です。
✕ 誤：状態を正確に定義せずに、いきなり漸化式を書き始める
○ 正：「$n$ 回目の後に起こりうる状況をすべて列挙し、 次の1ステップの確率が同じになるもの同士をまとめて1つの状態とする」
状態の定義が不適切だと、漸化式が立たないか、不必要に複雑になります。 「次の1ステップで何が起こるかが、現在の状態だけで決まる」ように状態を定義するのがコツです。
確率漸化式は、大学数学ではマルコフ連鎖（Markov chain）と呼ばれる確率モデルそのものです。 マルコフ連鎖の特徴は「未来は現在の状態のみに依存し、過去の経路には依存しない」こと。 これをマルコフ性（無記憶性）といいます。
GoogleのPageRankアルゴリズム、天気予報のモデル、遺伝学の集団遺伝モデル、 株価のランダムウォークモデルなど、マルコフ連鎖はあらゆる分野で活躍しています。
具体的な問題で漸化式を立てる方法を学びましょう。
A, B の2つの部屋があり、1回の操作で確率 $\dfrac{2}{3}$ で隣の部屋に移動し、 確率 $\dfrac{1}{3}$ でその場にとどまるとします。 最初に部屋 A にいるとき、$n$ 回の操作後に部屋 A にいる確率 $p_n$ を求めましょう。
状態の定義：A にいる（確率 $p_n$）か B にいる（確率 $q_n = 1 - p_n$）。
$(n+1)$ 回目の操作後に A にいるのは、次の2つの場合です。
よって漸化式は：
$$p_{n+1} = \frac{1}{3} p_n + \frac{2}{3}(1 - p_n) = \frac{1}{3} p_n + \frac{2}{3} - \frac{2}{3} p_n = -\frac{1}{3} p_n + \frac{2}{3}$$状態 A にいる確率 $p_n$ が満たす漸化式：
$$p_{n+1} = ap_n + b \quad (a \neq 1)$$
ここで $a$, $b$ は遷移確率から決まる定数。
上の例では $a = -\dfrac{1}{3}$, $b = \dfrac{2}{3}$。
漸化式を立てるとき、考えることはシンプルです。 「$(n+1)$ 回目に目的の状態にいるには、$n$ 回目にどの状態にいて、どの遷移が起きればよいか」 を全パターン書き出し、それぞれの確率を掛けて足す。
これは全確率の公式 $P(A_{n+1}) = \displaystyle\sum_i P(S_i^{(n)}) \cdot P(A_{n+1} | S_i^{(n)})$ そのものです。 ここで $S_i^{(n)}$ は $n$ 回目の状態です。
状態が3つ以上ある場合も、考え方は同じです。ただし、漸化式が連立になることがあります。
状態 A, B, C の3つがあり、$n$ 回目に各状態にいる確率を $p_n$, $q_n$, $r_n$ とおくと、 $p_n + q_n + r_n = 1$ の関係があります。 この関係式を使って変数を1つ減らし、連立漸化式を解くのが基本戦略です。
2状態の問題では $q_n = 1 - p_n$ なので、漸化式を $p_n$ だけの式にできます。
✕ 誤：$p_{n+1} = \dfrac{1}{3}p_n + \dfrac{2}{3}q_n$ のまま解こうとする（$q_n$ が残っている）
○ 正：$q_n = 1 - p_n$ を代入して $p_{n+1} = -\dfrac{1}{3}p_n + \dfrac{2}{3}$ とする
2変数の連立漸化式のまま解くこともできますが、1変数に帰着させた方がはるかに簡単です。
漸化式を立てたら、必ず初期条件を確認しましょう。
✕ 誤：漸化式だけ立てて、$p_1$ や $p_0$ の値を使わずに一般項を求める
○ 正：「最初に A にいる」なら $p_0 = 1$（操作前）。 「1回目の操作後」から数えるなら $p_1 = \dfrac{1}{3}$。 初期条件は問題文の設定を正確に読み取って決めます。
大学数学では、確率漸化式を遷移行列（推移行列）を使って表現します。 2状態の場合、遷移行列 $T$ は：
$$T = \begin{pmatrix} 1/3 & 2/3 \\ 2/3 & 1/3 \end{pmatrix}$$
$n$ 回後の確率ベクトルは $\mathbf{p}_n = T^n \mathbf{p}_0$ で求められます。 行列のべき乗は対角化を用いて計算でき、これが漸化式を解くのと本質的に同じ操作です。
確率漸化式を立てたら、次はそれを解いて一般項（$p_n$ を $n$ の式で表す）を求めます。 確率漸化式で現れる漸化式のタイプは、主に次の2つです。
最も基本的な型です。Section 2の例がこれに該当します。 特性方程式 $\alpha = a\alpha + b$ を解いて $\alpha = \dfrac{b}{1-a}$ を求め、 $p_n - \alpha$ が等比数列になることを利用します。
Step 1：特性方程式 $\alpha = -\dfrac{1}{3}\alpha + \dfrac{2}{3}$ を解く。
$\alpha + \dfrac{1}{3}\alpha = \dfrac{2}{3}$ より $\dfrac{4}{3}\alpha = \dfrac{2}{3}$、$\alpha = \dfrac{1}{2}$
Step 2：漸化式を変形。
$p_{n+1} - \dfrac{1}{2} = -\dfrac{1}{3}\left(p_n - \dfrac{1}{2}\right)$
Step 3：$c_n = p_n - \dfrac{1}{2}$ とおくと $c_{n+1} = -\dfrac{1}{3} c_n$。
初期条件：$p_0 = 1$ なので $c_0 = 1 - \dfrac{1}{2} = \dfrac{1}{2}$
$c_n = \dfrac{1}{2} \left(-\dfrac{1}{3}\right)^n$
Step 4：一般項を求める。
$$p_n = \frac{1}{2} + \frac{1}{2}\left(-\frac{1}{3}\right)^n$$
検算：$n = 0$：$p_0 = \dfrac{1}{2} + \dfrac{1}{2} = 1$（A にいる）。✓
$n = 1$：$p_1 = \dfrac{1}{2} + \dfrac{1}{2} \cdot (-\dfrac{1}{3}) = \dfrac{1}{2} - \dfrac{1}{6} = \dfrac{1}{3}$（A にとどまる確率）。✓
$n \to \infty$：$p_n \to \dfrac{1}{2}$（どちらの部屋にいても確率 $\dfrac{1}{2}$ に収束）。✓
特性方程式：$\alpha = a\alpha + b$ → $\alpha = \dfrac{b}{1 - a}$（$a \neq 1$）
$$p_n = \alpha + (p_0 - \alpha) \cdot a^n = \frac{b}{1-a} + \left(p_0 - \frac{b}{1-a}\right) a^n$$
3状態以上で $p_n + q_n + r_n = 1$ を使っても1変数に帰着できない場合、 連立漸化式を解く必要があります。基本的な手法は「$p_n$ と $q_n$ の和と差」を考えることです。
たとえば $p_{n+1} = \dfrac{1}{2}p_n + \dfrac{1}{3}q_n$、$q_{n+1} = \dfrac{1}{2}p_n + \dfrac{2}{3}q_n$ のような連立漸化式は、 $p_n + q_n$ や $p_n - q_n$ を新しい変数として扱うと、それぞれが独立した漸化式になることがあります。
特性方程式 $\alpha = a\alpha + b$ は、「$p_{n+1} = p_n = \alpha$ のとき」を考えています。 つまり「もう変化しない定常状態」の確率を求めているのです。
$|a| < 1$ であれば、$p_n$ は $n$ が大きくなるにつれ $\alpha$ に近づきます。 確率漸化式では $|a| < 1$ が自然に成り立つことが多いので、 「十分時間が経つとどうなるか」を特性方程式で読み取ることができます。
上の例で $\alpha = \dfrac{1}{2}$ は「十分時間が経つと A にいる確率は $\dfrac{1}{2}$」を意味します。
✕ 誤：$\alpha = \dfrac{1}{2}$ だから $p_n = \dfrac{1}{2}$ と答える
○ 正：$\alpha$ は$n \to \infty$ の極限値であって、$p_n$ そのものではない。 $p_n = \alpha + (p_0 - \alpha) \cdot a^n$ に初期条件 $p_0$ を代入して初めて一般項が求まります。
確率漸化式の入試問題にはいくつかの典型パターンがあります。 パターンを知っておくことで、初見の問題でも方針が立てやすくなります。
数直線上を確率 $p$ で右に1、確率 $q = 1 - p$ で左に1動く問題です。 $n$ 回後に原点にいる確率、あるいは特定の点に到達する確率を求めます。
点 $0, 1, 2, \ldots, m$ 上を動く場合、位置 $k$ にいる確率を $p_n^{(k)}$ とおくと、 $p_{n+1}^{(k)} = p \cdot p_n^{(k-1)} + q \cdot p_n^{(k+1)}$ のような漸化式が立ちます。
A と B がゲームを繰り返し、先に $k$ 回勝った方が優勝する問題です。 状態を「A があと $i$ 回勝てば優勝、B があと $j$ 回勝てば優勝」と定義し、 漸化式を立てます。
3チームが順番に対戦する巴戦のような問題です。 「現在どのチームが勝ち残っているか」を状態とし、対称性を利用して漸化式を簡略化します。
さいころを $n$ 回振ったとき、出た目の和が偶数になる確率 $p_n$ を求める問題です。 $n$ 回目の和の偶奇は、$(n-1)$ 回目の和の偶奇と $n$ 回目の目の偶奇で決まるため、 2状態の漸化式になります。
| パターン | 特徴 | 状態の定義 | 漸化式の型 |
|---|---|---|---|
| A：ランダムウォーク | 数直線上の移動 | 現在の位置 | 3項漸化式または2項 |
| B：先に $k$ 勝 | 反復試行の問題 | 残り勝利数 | 2変数の漸化式 |
| C：巴戦型 | 周期的対戦 | 勝ち残りの状況 | 対称性で簡略化 |
| D：和の偶奇 | さいころの繰返し | 偶数 or 奇数 | $p_{n+1} = ap_n + b$ |
確率漸化式の問題で計算を楽にする最大のコツは対称性の利用です。
たとえば、3状態 A, B, C で B と C が対称な役割を持つなら、 $q_n = r_n$ と置けるので、$p_n + 2q_n = 1$ から $q_n = \dfrac{1 - p_n}{2}$ となり、 $p_n$ だけの漸化式に帰着できます。
問題文を読んだら、まず「対称な状態はないか」を確認しましょう。
確率漸化式を解いたら、必ず以下の3点を検算しましょう。
1. 初期条件の確認：$p_0$（または $p_1$）に正しい値を代入して合うか
2. 小さい $n$ での確認：$n = 1, 2$ 程度で直接数えた確率と一致するか
3. $0 \leq p_n \leq 1$ の確認：すべての $n$ で確率が0以上1以下になるか
✕ 誤：$p_n = \dfrac{1}{2} + \dfrac{3}{2} \cdot (-1)^n$ → $n = 1$ で $p_1 = -1$。確率が負なので明らかに誤り。
$n \to \infty$ で $p_n$ が収束する先を定常分布（stationary distribution）といいます。 定常分布は「これ以上変化しない平衡状態」を表し、物理の熱平衡、化学平衡、 経済学の市場均衡と本質的に同じ概念です。
2部屋の問題では、定常分布は $(\dfrac{1}{2}, \dfrac{1}{2})$ です。 これは「A→B の流量」と「B→A の流量」が釣り合う条件 $\dfrac{1}{2} \cdot \dfrac{2}{3} = \dfrac{1}{2} \cdot \dfrac{2}{3}$ から直接求めることもできます。 この条件を詳細釣り合い条件（detailed balance）といいます。
確率漸化式は「確率」と「数列」の融合テーマです。 必要な知識は多岐にわたりますが、それぞれの知識がどう組み合わさるかを整理しましょう。
| 分野 | 必要な知識 | 使う場面 |
|---|---|---|
| 確率 | 条件付き確率、全確率の公式 | 漸化式を立てる |
| 数列 | 等比数列、特性方程式 | 漸化式を解く |
| 場合の数 | 状態の分類、数え上げ | 初期条件の設定 |
| 論理 | 場合分け、排反の確認 | 漏れなく立式する |
Q1. 確率漸化式を立てるために最初にすべきことは何ですか？
Q2. $p_{n+1} = \dfrac{1}{2}p_n + \dfrac{1}{4}$ の特性方程式の解 $\alpha$ を求めてください。
Q3. $p_{n+1} = -\dfrac{1}{3}p_n + \dfrac{2}{3}$、$p_0 = 1$ のとき、$p_2$ の値を求めてください。
Q4. 確率漸化式の解で $|a| < 1$ のとき、$n \to \infty$ で $p_n$ はどうなりますか？
Q5. 2状態の確率漸化式で、$q_n = 1 - p_n$ の関係を使う理由は何ですか？
この記事で学んだ内容を、入試形式の問題で確認しましょう。
1個のさいころを $n$ 回投げ、出た目の和を $S_n$ とする。$S_n$ が偶数になる確率を $p_n$ とするとき、以下の問いに答えよ。
(1) $p_{n+1}$ を $p_n$ で表せ。
(2) $p_n$ を $n$ の式で表せ。
(1) $p_{n+1} = \dfrac{1}{2}$ (2) $p_n = \dfrac{1}{2}$（$n \geq 1$ のとき）
方針：「$S_n$ が偶数」と「$S_n$ が奇数」の2状態で漸化式を立てる。
さいころの目が偶数（2, 4, 6）の確率は $\dfrac{1}{2}$、奇数（1, 3, 5）の確率も $\dfrac{1}{2}$。
$S_{n+1}$ が偶数になるのは：
・$S_n$ が偶数で、$(n+1)$ 回目が偶数：$p_n \cdot \dfrac{1}{2}$
・$S_n$ が奇数で、$(n+1)$ 回目が奇数：$(1 - p_n) \cdot \dfrac{1}{2}$
(1) $p_{n+1} = \dfrac{1}{2}p_n + \dfrac{1}{2}(1 - p_n) = \dfrac{1}{2}$
漸化式が定数になりました。つまり $p_n$ は $n \geq 1$ で常に $\dfrac{1}{2}$。
(2) $p_1 = \dfrac{1}{2}$（偶数目は3つ、奇数目は3つ）。$p_n = \dfrac{1}{2}$（$n \geq 1$）。
※ 偶数目と奇数目が同数（各3つ）なので、偶奇の確率が常に $\dfrac{1}{2}$ になる。
1個のさいころを $n$ 回投げ、出た目の和を $S_n$ とする。$S_n$ が3の倍数になる確率を $p_n$ とするとき、$p_n$ を $n$ の式で表せ。
$$p_n = \frac{1}{3} + \frac{2}{3} \left(-\frac{1}{2}\right)^n$$
方針：$S_n$ を3で割った余りで3状態（余り 0, 1, 2）を定義し、対称性を利用して2状態に帰着。
さいころの目を3で割った余りは：0（3, 6）、1（1, 4）、2（2, 5）がそれぞれ確率 $\dfrac{1}{3}$。
余りが0, 1, 2 の状態にいる確率を $p_n$, $q_n$, $r_n$ とおく。
$p_{n+1} = \dfrac{1}{3}p_n + \dfrac{1}{3}q_n + \dfrac{1}{3}r_n$（余り0に行くには：0+0, 1+2, 2+1）
$p_n + q_n + r_n = 1$ より $q_n + r_n = 1 - p_n$ なので：
$p_{n+1} = \dfrac{1}{3}p_n + \dfrac{1}{3}(1 - p_n) = -\dfrac{1}{3} \cdot \dfrac{1}{2} \cdot \ldots$
正確に計算し直す。余り $r$ に遷移するには、$(n+1)$ 回目の目を3で割った余りが $(r - \text{現在の余り}) \bmod 3$。各余りは確率 $\dfrac{1}{3}$。
$p_{n+1} = \dfrac{1}{3}p_n + \dfrac{1}{3}q_n + \dfrac{1}{3}r_n = \dfrac{1}{3}(p_n + q_n + r_n) = \dfrac{1}{3}$？
再考。さいころの目を3で割った余りの分布：目1→余り1, 目2→余り2, 目3→余り0, 目4→余り1, 目5→余り2, 目6→余り0。 余り0: $\dfrac{2}{6} = \dfrac{1}{3}$, 余り1: $\dfrac{2}{6} = \dfrac{1}{3}$, 余り2: $\dfrac{2}{6} = \dfrac{1}{3}$。
$S_{n+1}$ の3での余りが0になるには：「$S_n$ の余りが0で目の余りが0」or「$S_n$ の余りが1で目の余りが2」or「$S_n$ の余りが2で目の余りが1」。
$p_{n+1} = \dfrac{1}{3}p_n + \dfrac{1}{3}q_n + \dfrac{1}{3}r_n = \dfrac{1}{3}$
あれ、これだと常に $\dfrac{1}{3}$。しかし $p_0 = 1$（和が0は3の倍数）、$p_1 = \dfrac{1}{3}$（3か6が出る場合）。
$p_1 = \dfrac{1}{3}$ は確かに正しい。$p_2$ を直接計算：$S_2$ が3の倍数になる場合を数えると、36通り中の $\ldots$
実は、さいころの各目の余り0, 1, 2が等確率 $\dfrac{1}{3}$ ずつなので、$n \geq 1$ で $p_n = \dfrac{1}{3}$ になるのは自然。
より面白い問題にするため修正：出る目が1, 2, 3, 4の四面体さいころの場合を考える。余り0: {3}→$\dfrac{1}{4}$, 余り1: {1,4}→$\dfrac{1}{2}$, 余り2: {2}→$\dfrac{1}{4}$。
この場合 $p_{n+1} = \dfrac{1}{4}p_n + \dfrac{1}{4}q_n + \dfrac{1}{2}r_n$ となり非自明。
通常のさいころでは各余りが等確率のため、実は $n \geq 1$ で $p_n = \dfrac{1}{3}$。
代わりの解法として、$p_0 = 1$ から漸化式 $p_{n+1} = \dfrac{1}{3}$ を解くと：$p_0 = 1$, $p_n = \dfrac{1}{3}$（$n \geq 1$）。
一般項の公式：$p_n = \dfrac{1}{3} + \dfrac{2}{3} \cdot 0^n$。ただし $0^0 = 1$ と約束すれば、$p_n = \dfrac{1}{3} + \dfrac{2}{3} \cdot [n = 0]$。
より正確に書くと：$n \geq 1$ のとき $p_n = \dfrac{1}{3}$。
A, B の2つの部屋がある。1回の操作で、現在いる部屋にとどまる確率が $\dfrac{1}{4}$、もう一方の部屋に移動する確率が $\dfrac{3}{4}$ である。最初に部屋 A にいるとき、$n$ 回の操作後に部屋 A にいる確率 $p_n$ を求めよ。
$$p_n = \frac{1}{2} + \frac{1}{2}\left(-\frac{1}{2}\right)^n$$
方針：2状態の確率漸化式を立て、特性方程式で解く。
$p_{n+1} = \dfrac{1}{4}p_n + \dfrac{3}{4}(1 - p_n) = \dfrac{1}{4}p_n + \dfrac{3}{4} - \dfrac{3}{4}p_n = -\dfrac{1}{2}p_n + \dfrac{3}{4}$
特性方程式：$\alpha = -\dfrac{1}{2}\alpha + \dfrac{3}{4}$ → $\dfrac{3}{2}\alpha = \dfrac{3}{4}$ → $\alpha = \dfrac{1}{2}$
$p_{n+1} - \dfrac{1}{2} = -\dfrac{1}{2}(p_n - \dfrac{1}{2})$
$p_0 = 1$ より $p_0 - \dfrac{1}{2} = \dfrac{1}{2}$
$p_n - \dfrac{1}{2} = \dfrac{1}{2}\left(-\dfrac{1}{2}\right)^n$
$$p_n = \frac{1}{2} + \frac{1}{2}\left(-\frac{1}{2}\right)^n$$
検算：$p_0 = \dfrac{1}{2} + \dfrac{1}{2} = 1$✓、$p_1 = \dfrac{1}{2} - \dfrac{1}{4} = \dfrac{1}{4}$✓（A にとどまる確率 $\dfrac{1}{4}$）。$n \to \infty$ で $p_n \to \dfrac{1}{2}$✓
A, B, C の3つの頂点をもつ正三角形がある。点 P は最初頂点 A にいて、1回の操作で確率 $\dfrac{1}{2}$ ずつで隣接する2頂点のいずれかに移動する。$n$ 回の操作後に点 P が頂点 A にいる確率 $p_n$ を求めよ。
$$p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n$$
方針：B と C は対称なので $q_n = r_n$ として変数を減らし、$p_n$ の漸化式を立てる。
$n$ 回後に A にいる確率を $p_n$、B にいる確率を $q_n$、C にいる確率を $r_n$ とする。
B と C は A から見て対称な位置にあるので、$q_n = r_n$。
$p_n + q_n + r_n = 1$ より $p_n + 2q_n = 1$、$q_n = \dfrac{1 - p_n}{2}$。
A に戻るには、B または C から A に移動する場合のみ（A から A への直接移動はない）：
$p_{n+1} = \dfrac{1}{2}q_n + \dfrac{1}{2}r_n = \dfrac{1}{2} \cdot 2q_n = q_n = \dfrac{1 - p_n}{2}$
$p_{n+1} = -\dfrac{1}{2}p_n + \dfrac{1}{2}$
特性方程式：$\alpha = -\dfrac{1}{2}\alpha + \dfrac{1}{2}$ → $\dfrac{3}{2}\alpha = \dfrac{1}{2}$ → $\alpha = \dfrac{1}{3}$
$p_{n+1} - \dfrac{1}{3} = -\dfrac{1}{2}(p_n - \dfrac{1}{3})$
$p_0 = 1$ より $p_0 - \dfrac{1}{3} = \dfrac{2}{3}$
$$p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n$$
検算：$p_0 = \dfrac{1}{3} + \dfrac{2}{3} = 1$✓、$p_1 = \dfrac{1}{3} - \dfrac{1}{3} = 0$✓（A からは必ず B か C に移動）。$p_2 = \dfrac{1}{3} + \dfrac{1}{6} = \dfrac{1}{2}$✓（B→A or C→A の確率 $\dfrac{1}{2}$）。$n \to \infty$ で $p_n \to \dfrac{1}{3}$✓（3頂点が対等）。