数学A / 確率

持ち点が0かNになるまで(破産問題と2階漸化式)

実戦編確率確率漸化式2階線形漸化式ランダムウォーク単元横断

問題

持ち点 $k$ ( $0 < k < N$ )から始める。1回ごとに確率 $\frac{1}{2}$ で持ち点が $1$ 増え、確率 $\frac{1}{2}$ で $1$ 減る。持ち点が $N$ になれば成功、 $0$ になれば失敗として終了する。持ち点 $k$ から出発して(失敗より先に)成功する確率 $q_{k}$ を求めよ。

ヒントを見る

いまの持ち点 $k$ から1手進めると $k \pm 1$ 。それぞれから成功する確率で $q_{k}$ を表すと、 $q_{k - 1}, q_{k}, q_{k + 1}$ の関係(2階漸化式)になる。両端の値は決まっている。

解答・解説

方針

1手先で条件をつけて $q_{k}$ の漸化式を立てる。境界は $q_{0} = 0, q_{N} = 1$ 。2階の漸化式を解く。

解答

⓪ 発想 — どう考え始めるか。 “出発点 $k$ ごとの成功確率” $q_{k}$ を、 $k$ を変数とする数列とみなす。

$1$ 手だけ先を見る。 $k$ からは $\frac{1}{2}$ ずつで $k + 1$ か $k - 1$ に動き、その先の成功確率は $q_{k + 1}, q_{k - 1}$ 。これで $q_{k}$ の2階漸化式が立つ。

両端の値は明らかだ。 $q_{0} = 0$ (もう破産)、 $q_{N} = 1$ (もう成功)。境界つきの漸化式を解けばよい。

① 漸化式を立てる。 1手先で場合分けして $q_{k} = \frac{1}{2} q_{k + 1} + \frac{1}{2} q_{k - 1} (0 < k < N), q_{0} = 0, q_{N} = 1.$ ② 等差数列と見抜く。 上式を変形すると $q_{k + 1} - q_{k} = q_{k} - q_{k - 1}$ 。

重要隣り合う差が一定

\Rightarrow

{q_{k}}

は等差数列

つまり階差 $q_{k + 1} - q_{k}$ は $k$ によらず一定。

③ 境界で決める。 等差数列だから $q_{k} = q_{0} + k \cdot d = k d$ 。 $q_{N} = N d = 1$ より $d = \frac{1}{N}$ 。したがって $q_{k} = \frac{k}{N} .$

0 と N は吸収壁(そこで終了)。各回 1/2 で ±1 動き、N に先に着けば成功。成功確率は k/N(図は N=5 の例)。

まとめ 確率を“出発点ごとの値の列”と見て、1手先で条件を付けると2階漸化式。 $q_{k + 1} - q_{k}$ が一定=等差、と気づけば境界 $q_{0} = 0, q_{N} = 1$ で即決まる。答えは直感どおり $\frac{k}{N}$ 。確率と漸化式の代表的融合(ランダムウォーク)。

発展 — 一歩先へ。 勝つ確率が $p \neq = \frac{1}{2}$ の不公平な賭けでは、 $q_{k + 1} - q_{k}$ が等比数列になり、 $r = \frac{1 - p}{p}$ として $q_{k} = \frac{1 - r ^{k}}{1 - r ^{N}}$ 。わずかに不利なだけでも $N$ が大きいと成功確率は急速に $0$ へ近づく。カジノが長期では必ず勝つ数学的な理由である。

答

$q_{k} = \frac{1}{2} (q_{k - 1} + q_{k + 1})$ 、 $q_{0} = 0, q_{N} = 1$ 。等差数列になり $q_{k} = \frac{k}{N}$ 。

別解

別解 — 「公平な賭けでは平均が動かない」で見抜く(得意な人向けの高い視点)。 毎回 $\pm 1$ が確率 $\frac{1}{2}$ ずつだから、 $1$ 手あとの持ち点の期待値はいまの持ち点と同じ。つまりこのゲームは“公平”で、持ち点の期待値は何手たっても $k$ のままである。

ゲームはいつか必ず終わる(挟まれた範囲を永遠に漂う確率は $0$ )。終わったときの持ち点は $N$ (確率 $q_{k}$ )か $0$ (確率 $1 - q_{k}$ )しかない。

期待値が終了時まで保たれるなら

$N \cdot q_{k} + 0 \cdot (1 - q_{k}) = k ⟹ q_{k} = \frac{k}{N} .$

漸化式を解かずに答えが先に見える、強力な見方だ。ただし「終了時まで保存を持ち越せること」は本当は証明が要る(大学で学ぶ内容)。答案では本解の漸化式を主役にし、この見方は見通しと検算に使うのが安全である。

ポイント

成功確率を“出発点 $k$ ごとの値の列 $q_{k}$ ”とみる。
1手先で条件を付けると $q_{k} = \frac{1}{2} (q_{k - 1} + q_{k + 1})$ (2階漸化式)。
$q_{k + 1} - q_{k}$ が一定=等差数列。境界 $q_{0} = 0, q_{N} = 1$ で $q_{k} = \frac{k}{N}$ 。

よくある間違い

境界条件 $q_{0} = 0, q_{N} = 1$ を書き忘れ、一般解の定数が決まらない。
「成功までの回数」と混同して時間の変数まで持ち込み、 $2$ 変数の式で行き詰まる(問われているのは確率だけ)。
$q_{k + 1} - q_{k} = q_{k} - q_{k - 1}$ (階差が一定=等差)に気づかず、 $3$ 項間漸化式の一般論(特性方程式は重解 $1$ )へ進んで遠回りする。