【期待値マスター講座45】ランダムウォークの吸収時間を漸化式で解く （大学入試数学）

この記事では、1次元ランダムウォークで両端の境界に到達するまでの期待回数を、漸化式 ${e_i = 1 + \frac{1}{2}e_{i-1} + \frac{1}{2}e_{i+1}}$ から導きます。

答えは ${e_i = i(n-i)}$ という綺麗な形になります。

公式LINEでテキスト配布中
公式LINE追加→ 期待値テキスト と送信
で120ページ超えのテキストを自動送信！
ㅤ
無料勉強相談も受付中
学習相談も受け付けています。
ゴウカライズは情報の少ない獣医学部や医学部受験にも精通しています。
一般入試はもちろん、総合型選抜や推薦など、なんでもお問い合わせください！

シリーズ全体の流れを先に見たい方は、まず 期待値マスター講座の導入記事 からどうぞ。全56回の構成と読み進め方をまとめています。

https://note.com/goukalize/n/n9de4e3c6c4fb

問題

数直線上の位置 $${i}$$（ $${0\le i\le n}$$、 $${i}$$ は整数）に駒がある。毎回、確率 $${\frac{1}{2}}$$ で右に $${+1}$$、確率 $${\frac{1}{2}}$$ で左に $${-1}$$ 移動する。位置 $${0}$$ または位置 $${n}$$ に到達したらゲーム終了。最初の位置が $${i}$$ のとき、終了までの試行回数の期待値を $${e_i}$$ とする。 $${e_i}$$ を $${i, n}$$ で表せ。

これは「両端で吸収される1次元ランダムウォーク」と呼ばれる古典的な問題です。位置 $${0}$$ と位置 $${n}$$ が 吸収壁 で、そこに到達するとゲームが止まります。

漸化式を立てる

境界条件：$${e_0 = e_n = 0}$$（すでに端にいれば0回で終了）。

$${0 < i < n}$$ では、1回試行すると確率 $${\frac{1}{2}}$$ で位置が $${i+1}$$ に動き、確率 $${\frac{1}{2}}$$ で位置が $${i-1}$$ に動きます。期待値の関係から

$$
e_i = 1 + \frac{1}{2} e_{i-1} + \frac{1}{2} e_{i+1}\quad (0 < i < n).
$$

「1回試行する $${+}$$ 遷移先からの期待回数」を、 $${\frac{1}{2}}$$ ずつの確率で重み付けして足したものです。

整理すると

$$
e_{i+1} - 2 e_i + e_{i-1} = -2.
$$

これは 2階線形差分方程式 の形で、特殊解と斉次解の和として書けます。

解く

差分方程式 $${e_{i+1} - 2 e_i + e_{i-1} = -2}$$ の 斉次解 は $${A + Bi}$$（線形関数）。

特殊解 は $${-i^2}$$ が満たします。実際 $${(i+1)^2 - 2i^2 + (i-1)^2 = (i^2 + 2i + 1) - 2i^2 + (i^2 - 2i + 1) = 2}$$ で、 $${-i^2}$$ なら $${-2}$$ を返します。

一般解は

$$
e_i = A + Bi - i^2.
$$

境界条件 $${e_0 = 0}$$ から $${A = 0}$$。 $${e_n = 0}$$ から $${Bn - n^2 = 0}$$ で $${B = n}$$。

したがって

$$
e_i = n i - i^2 = i(n - i).
$$

答えは $${e_i = i(n - i)}$$。

結果の読み方

具体的に小さな $${n}$$ で見ます。

$${n = 10}$$ で各位置からの期待回数：

• $${e_1 = 1\cdot 9 = 9}$$
• $${e_5 = 5\cdot 5 = 25}$$
• $${e_9 = 9\cdot 1 = 9}$$

中央 $${i = 5}$$ から始めるのが最も時間がかかり、平均25回 。端 $${i = 1, 9}$$ なら平均9回（左にずっと進めば即終了するので、平均は短い）。

対称性 $${e_i = e_{n-i}}$$ も自然に出ています。 $${i}$$ から左端 $${0}$$ までと、 $${n-i}$$ から右端 $${n}$$ までは、対称な距離だから時間も同じ。

$${e_i = i(n-i)}$$ の意味

$${e_i = i(n - i)}$$ は、 「左端までの距離」 × 「右端までの距離」 という、ちょっと意外な形をしています。

直観的な解釈は次の通り。 $${i}$$ から終了までの期待回数は、左に $${i}$$、右に $${n - i}$$ という不対称な状況で決まります。両方向の距離の積が、平均試行回数になる、という結果は 計算してみないと気づきにくい 形です。

連続版（ブラウン運動）でも同様の結果が成り立ち、 $${[0, n]}$$ の中での吸収時間の期待値が距離の積になる、というのは確率論の古典的な結果として広く知られています。

検算：$${n = 2}$$ の場合

$${n = 2}$$、 $${i = 1}$$ で考えます。位置1からスタートし、 $${\frac{1}{2}}$$ で0、 $${\frac{1}{2}}$$ で2、どちらも吸収壁。1回で必ず終了するので $${e_1 = 1}$$。

公式から $${e_1 = 1\cdot (2 - 1) = 1}$$。一致。

$${n = 3}$$、 $${i = 1}$$ なら $${e_1 = 1\cdot 2 = 2}$$。手で確かめると、1回目に左に行けば終了（確率 $${\frac{1}{2}}$$ で1回）、右に行けば位置2でまた同じ問題（対称性から $${e_2 = e_1 = 2}$$ ）、…と書くと幾何分布混じりの計算になり、結局 $${e_1 = 2}$$ に到達します。

$${e_i}$$ の漸化式の解き方をもう一度

「2階線形差分方程式 $${e_{i+1} - 2 e_i + e_{i-1} = -2}$$」を解く流れは、 数列の漸化式の解法と全く同じ です。

• 斉次解 $${e_i^{(h)}}$$：差分が0になる方程式 $${e_{i+1} - 2 e_i + e_{i-1} = 0}$$ の解。特性方程式 $${\lambda^2 - 2\lambda + 1 = 0}$$ が重解 $${\lambda = 1}$$ を持つので $${A + Bi}$$。
• 特殊解 $${e_i^{(p)}}$$：$${-i^2}$$ など、定数差分（ここでは $${-2}$$ ）を満たす形。
• 一般解 $${e_i = e_i^{(h)} + e_i^{(p)}}$$、境界条件で定数 $${A, B}$$ を決定。

数列の漸化式と同じ枠組みです。確率の問題で漸化式を解くときは、 「差分方程式の解法を知っているか」が直接答えにつながる ことが多いので、復習しておくと役立ちます。

練習問題

数直線上の位置 $${i}$$（ $${0\le i\le 5}$$ ）に駒があり、確率 $${\frac{1}{2}}$$ で右に $${+1}$$、 $${\frac{1}{2}}$$ で左に $${-1}$$ 動く。位置 $${0}$$ または $${5}$$ に到達したら終了。位置 $${2}$$ から始めたときの期待試行回数を求めよ。

公式 $${e_i = i(n - i)}$$ に $${i = 2, n = 5}$$ を入れて

$$
e_2 = 2\cdot 3 = 6.
$$

平均6回で端まで到達、という結果。これは公式に当てはめるだけで一瞬で出ます。

補足：非対称な遷移

「左に行く確率が $${p}$$、右に行く確率が $${q = 1 - p}$$」の場合、漸化式は

$$
e_i = 1 + p e_{i-1} + q e_{i+1}
$$

となり、解は少し複雑になります。 $${p = q = \frac{1}{2}}$$ の対称な場合だけ $${e_i = i(n - i)}$$ という綺麗な形になる、というのが本記事のメインです。入試では対称な場合が大半なので、 $${e_i = i(n - i)}$$ を覚えておけば十分です。

次に読む記事

次回は、 2人じゃんけんで決着するまでの回数 を漸化式で扱います。「あいこになったらやり直し」型の問題で、初期状態に戻る発想を、別の角度から再確認します。

【無料相談受付中】学習マネジメントはゴウカライズにおまかせを！

「成績が伸び悩んでいるけどどうやって打破すればいいかわからない…」
「塾・予備校に行ってるけど、全体の成績が思ったように上がらない…」

そんな悩みをお持ちの受験生・保護者の皆様、ゴウカライズにご相談ください！

入試を突破するため、私たちはあなたの志望校や受験方式に必要なすべてをトータルサポートします。

【一般入試】完全オーダーメイドの学習計画 ：
入試は、わずかな失点が合否を分けることもあります。
あなたの現状と志望校の出題傾向を分析し、合格ラインに到達するための最短ルートを設計。
日々の進捗管理で、学習の遅れも見逃しません。

【推薦・総合型選抜】面接・小論文もプロが対応 ：
推薦入試や総合型選抜で必須となる「面接・小論文・志望理由書」の対策もお任せください。
医学部や獣医系特有のテーマ（動物倫理や獣医療時事など）に対応できるプロ講師が、合格レベルの答案作成と受け答えを指導します。

プロ講師・優秀学生講師の個別指導 ：
学習管理だけでなく、経験豊富なプロ講師や、高倍率から選抜された優秀な学生講師による完全個別指導も提供。
苦手科目の克服や過去問解説など、あなたのニーズに合わせた1対1の指導が可能です。

【医学部・獣医学部対策】特殊な対策に完全対応 ：
医学部入試、獣医学部入試は特殊な対策が必要です。
面接などがある入試形式の場合、面接対策も侮れません。
そんな入試に精通したプロがゴウカライズには多数在籍しています。
ゴウカライズ代表の大北も医学部・獣医学部受験の指導経験は15年を超える大ベテランです。

まずは無料相談で、あなたの合格までのロードマップを一緒に描きませんか？
無理な勧誘は一切ありません。
予備校選びに迷っているなどの相談でも、客観的にアドバイスを行います。

公式LINEでいつでも無料相談を受け付けています！

https://goukalize.com/

https://goukalize-official-line-harness.tiny-atlas.workers.dev/r/Expected-Value

#オンライン予備校 #大学受験 #数学 #ランダムウォーク #漸化式