【東大型】確率の状態設計

東大レイヤー／出題テーマ／東大での重要度 ★★★★★

アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）

要点

東大の確率は、何を状態と見るかを自分で決めさせてくる。そして状態の分類さえ正しく決まれば、残りの計算は易しいことがほとんどである。良い分類の条件は2つしかない。第一に、互いに排反で網羅的であること。第二に、同じ状態に属するなら、そこから先の遷移確率が等しいこと。第二の条件を満たさない粗い分類が最大の敗因で、これは『分類したつもりで、実は違うものを混ぜている』という形で現れる。逆に、対称性を使えば状態を大幅に減らせることが多く、ここに気づけるかどうかで計算量が数倍変わる。

こんなときに使う

同じルールの操作が n 回繰り返される → 状態と遷移で捉える
『n回後に〜である確率』『ちょうどn回目に初めて〜』→ 漸化式
状態が多そうに見える → まず対称性で潰せないか考える（正多面体、円形配置、色の入れ替え）
直前だけでなく履歴に依存しそう → 状態に情報を足して履歴依存を消す
『初めて到達する』→ 到達済みを吸収状態として分ける

手順

1. n=1, 2 を実際に書き出し、何が起こりうるかを掴む
2. 『ここから先の動き方が同じ』ものをまとめて1つの状態にする
3. 状態が互いに排反かつ網羅的か確認する（確率の和が1になるか）
4. 遷移図を描き、各状態から出る矢印と確率を全部書く
5. 漸化式を立てる（状態が3つ以上なら連立、和=1で1本消せる）
6. 対称性でさらに状態を減らせないか、ここでもう一度考える
7. 解いたあと n=1, 2 を代入し、手で数えた値と一致するか検算する

例題

正四面体 ABCD の頂点上を点Pが動く。1回の操作で、Pは今いる頂点と辺で結ばれた3つの頂点のいずれかへ等確率で移動する。最初 A にいるとき、n回の操作後に A にいる確率 p_n を求めよ。

解答

正四面体では、どの頂点も他の3頂点すべてと辺で結ばれている。
また B, C, D は A から見て完全に対等なので、『A にいる』『A 以外にいる』の2状態で足りる（対称性）。
n回後に A にいる確率を p_n とすると、A 以外にいる確率は 1 - p_n。
A にいるとき：次の1手で必ず A を出るので、A に留まる寄与は 0。
A 以外にいるとき：その頂点から移動できる3頂点のうち A はちょうど1つなので、A へ移る確率は 1/3。
よって p_(n+1) = (1/3)(1 - p_n)、p_0 = 1。
特性方程式 α = (1/3)(1 - α) より 3α = 1 - α、α = 1/4。
p_(n+1) - 1/4 = -(1/3)(p_n - 1/4) となり、p_n - 1/4 = (3/4)·(-1/3)^n。
∴ p_n = 1/4 + (3/4)(-1/3)^n
検算：p_0 = 1/4 + 3/4 = 1 ○。p_1 = 1/4 - 1/4 = 0 ○（1回で必ず A を出る）。
p_2 = 1/4 + (3/4)(1/9) = 1/4 + 1/12 = 1/3 ○（A以外の頂点から3つのうち1つが A）。
n→∞ で p_n → 1/4。4頂点が対等になるので直感とも合う。

別解・ほかの見方

対称性が使えない設定では素直に状態を増やし、連立漸化式にする。p+q+r=1 で1本消して2元にするのが定石
一般項が出せない形なら、n=1,2,3 を書き出して予想し、数学的帰納法で示す（東大はこちらを要求することがある）
期待値の線形性を使うと、漸化式を立てずに済む場合がある（『何回目に初めて』ではなく『平均何回か』を聞かれたとき）
立方体・正八面体などでは『頂点までの距離』を状態に取ると、状態数が一気に減る

落とし穴

分類が粗く、同じ状態の中に遷移確率の異なるものが混ざっている（最大の敗因）
逆に状態を増やしすぎて、立った漸化式が解けなくなる
対称性の確認を怠り、本来まとめられる状態を分けたまま計算する
確率の和が1になる検算をしない
p_0 で立てた漸化式に p_1 の初期条件を入れて添字が1ずれる
状態の個数を増やしすぎて漸化式が解けなくなる

なぜ大事か

設定が複雑で、何を状態と見るかを自分で決めさせる。分類さえ決まれば計算は易しい

東大での出方

サイコロ、カードの並べ替え、格子上や多面体上の点の移動、トーナメントなど、設定を変えて繰り返し出題される東大の主力テーマ。(1) 小さい n の具体値 →(2) 漸化式 →(3) 極限、という3段の誘導が定番で、(1) の数え方がそのまま (2) の状態設計のヒントになっている。

確認問題

立方体の8頂点を辺に沿って移動する点について、n回後に元の頂点にいる確率を求めよ（状態を『元の頂点からの距離 0,1,2,3』に取る）
上の正四面体の問題で、n回後に特定の頂点 B にいる確率を求めよ
サイコロを n 回投げ、出た目の和が3の倍数になる確率を求めよ（状態は和を3で割った余り）

発展

状態の個数が n に依存して増える設定では漸化式が立たない。その場合は直接数え上げるか、別のパラメータについて漸化式を立て直す。どちらも無理なら、実験して予想し帰納法で示す。

前提になるノード

このノードを前提にするノード

理三の合格ライン（数学 6問中4完+α / 目安80〜100点）

「出題テーマ」のノード

解説は自作です。誤りに気づいたらお問い合わせ（/contact/）から教えてください。

ノード一覧・受験数学マップについて