期待到達時間

モデリング・公式

ひとことで言うと

目標状態に着くまで平均で何ステップかかるかが期待到達時間です。各段を順にクリアする型では、各段の成功確率 $p_k$ に対し平均挑戦回数が $1/p_k$ （幾何分布の期待値）。期待値の線形性で、全段クリアまでは単純にそれらの和 $\sum 1/p_k$ になります。

3段階を順にクリアするシステムの各段の期待挑戦回数を横棒で示した図。各段の合格率 $p_1=0.5,p_2=0.25,p_3=0.2$ に対し期待挑戦回数は $1/p$ でそれぞれ $2,4,5$ 回。期待値の線形性で合計は $E[T]=2+4+5=11$ 回。

$E[T]=\textstyle\sum_k 1/p_k$

目標状態に到達するまでの期待ステップ数。逐次成功なら $1/p$ の和。

期待到達時間とは、ある目標状態に初めて到達するまでにかかる平均ステップ数です。ここでは concept: 吸収で導入した吸収状態の構造を使い、複数の段階を順番にクリアして最終状態（吸収状態）に到達する型の連鎖を扱います。各段階

k

では、成功するまで独立に試行を繰り返し、成功確率は

p_k

とします。1つの段階を成功するまでの試行回数は幾何分布

\mathrm{Geometric}(p_k)

に従い（concept: 幾何分布）、その期待値は

1/p_k

です。ここで効くのが期待値の線形性です。各段の試行回数が独立な幾何分布だとしても、和の期待値は各期待値の単純な和になります。全段をクリアして目標に到達するまでの総ステップ数を

T

とすると

E[T]=\sum_{k} \dfrac{1}{p_k}

です。各段で平均

1/p_k

回かかり、それを全段ぶん足すだけ、という直感どおりの式になります。数値例として、3段階のシステムで各段の合格率が

p_1=0.5,\ p_2=0.25,\ p_3=0.2

だとします。各段の期待挑戦回数は

1/p_1=2

、

1/p_2=4

、

1/p_3=5

なので、全段クリアまでの期待挑戦回数は

E[T]=2+4+5=11\ \text{回}

です。ここでランダムウォークとの違いをはっきりさせます。対称な単純ランダムウォークが2つの吸収壁に挟まれた状況で位置

i

から吸収されるまでの期待時間は

E[T]=i(N-i)

で、これは差分方程式を解いて導きます（concept: ランダムウォーク）。一方、本ページの

E[T]=\sum 1/p_k

は逐次クリア型で、各段が幾何分布に従い期待値の線形性で和をとるという全く別の設定・導出です。「目標に着くまでの平均時間」という言葉は共通でも、前者は対称ランダムウォーク、後者は逐次成功型と問題の構造が違う点を区別してください。

逐次クリア型の式

各段の成功確率 $p_k$ に対し $E[T]=\sum_k 1/p_k$ 。各段の平均挑戦回数 $1/p_k$ の和。

各段は幾何分布

1段を成功するまでの試行回数は $\mathrm{Geometric}(p_k)$ （concept: 幾何分布）、期待値 $1/p_k$ 。

期待値の線形性

総ステップ数 $T$ の期待値は各段の期待値の単純な和。分布の積和は不要、足すだけ。

成功確率が低い段ほど効く

$1/p_k$ は $p_k$ が小さいほど大きい。最も通りにくい段がボトルネックになる。

ランダムウォークとの違い

対称RWの $E[T]=i(N-i)$ （concept: ランダムウォーク、差分方程式）とは設定も導出も別物。

3段階のシステムで各段の合格率が $p_1=0.5,\ p_2=0.25,\ p_3=0.2$ （独立、前段合格で次へ）。各段の期待挑戦回数は $1/p_1=2$ 、 $1/p_2=4$ 、 $1/p_3=5$ 。全段クリアまでの期待挑戦回数は $E[T]=2+4+5=11$ 回。

逐次クリア型の期待到達時間の式は？

$p_1=0.5,\ p_2=0.25,\ p_3=0.2$ の3段階での $E[T]$ は？

この $E[T]=\sum 1/p_k$ と対称ランダムウォークの $E[T]=i(N-i)$ の関係は？

この用語を扱う問題（2）