【再生過程】均衡分布とは?待ち時間の極限分布を例に解説!

【再生過程】均衡分布とは?待ち時間の極限分布を例に解説!再生過程
スポンサーリンク

どうも!初めましての方は初めまして、初心者のWebサイト勉強のとみーです!

バス会社や鉄道会社のサービスを向上させるには、

乗客の待ち時間を減らす

ことが重要です。

しかし、運行本数や頻度を増やすのには限界がありますよね。

実は、運行本数や頻度を変えずに待ち時間を減らす方法は存在します。

そして、その方法を導くためには再生過程の均衡分布を理解する必要があります。

とみー
とみー

そこで今回は、バスの待ち時間を例に均衡分布と待ち時間を最小にする条件について解説していきます!

対象レベル

確率の基本的な知識がある方(高校数学〜大学入門)

スポンサーリンク

均衡分布とは?

均衡分布とは、一言でいうと

待ち時間の極限分布

です。

とみー
とみー

といってもこれだけではわからないと思うので、詳しく説明します。

スポンサーリンク

待ち時間を考えるための再生過程

均衡分布の話に入る前に、まずは問題の設定を明らかにしておきましょう。

問題の設定・条件

ここでは、バスの到着に関する再生過程を考えます。

次のように変数をおきましょう。

  • $X_n$:$n-1$ 台目のバスと $n$ 台目のバスの到着間隔
  • $Z_n$:$n$ 台目のバスの到着時刻

図にすると、次の画像のような感じになります。

待ち時間 $Y(t)$

この再生過程で、時刻 $t$ に到着した客の待ち時間$Y(t)$ とします。

再生過程 $M(t)$ は、時刻 $t$ までに到着したバスの本数を表します。

時刻 $t$ までに $M(t)$ 本到着するので、次のバスの到着時刻は $Z_{M(t) + 1}$ ですね。

とみー
とみー

この $Y(t)$ の確率分布がわかれば待ち時間の確率的な振る舞いがわかるので、最小化する方法が分かります。

そのため、$Y(t)$ の確率分布

$$F_Y (y) = \mathbb{P} (Y(t) \leq y)$$

($y$ は任意の定数)を求めることが目標になります。

しかし、これを求めるにはテクニックが必要なので、一旦次のような再生報酬過程を考えます。

スポンサーリンク

待ち時間の分布を求めるための再生報酬過程

報酬の導入

求めたいのは

$$\mathbb{P} (Y(t) \leq y)$$

なので、次のような報酬を考えます。

報酬

\begin{eqnarray} \mathbb{I}_{\{Y(t) \leq y\}} (t) = \left\{ \begin{array}{l} 1 \quad \cdots \quad Y(t) \leq y \\ 0 \quad \cdots \quad Y(t) > y \end{array} \right. \end{eqnarray}

これは、待ち時間が $y$ 以下となるような時刻 $t$ に客が到着できたら+1の報酬がもらえることを表しています。

バスの到着ではないことに注意しましょう!

$X_2 < y$ なので、区間 $X_2$ ではいつ到着しても報酬がもらえます。

とみー
とみー

言い方を変えると、バスの到着時刻の $y$ 分前に到着すれば+1の報酬が発生します。

累積報酬 $C(t)$(再生報酬過程)

報酬 $\mathbb{I}_{\{ Y(t)\leq y \}}$ の表現を使うと、再生報酬過程(累積報酬)は次のように表されます。

再生報酬過程

$$C(t) = \int_0^t \mathbb{I}_{\{ Y(u)\leq y \}}(u) du$$

とみー
とみー

時刻 $t$ と紛らわしいので、積分変数は $u$ としています。

$Y(t) \leq y$ のとき報酬が1発生するので、累積報酬の傾きは1になります。

とみー
とみー

バスの到着時刻 $\{Z_n\}$ とは関係なく報酬が変化するので、これは部分報酬モデルです!

ちなみに、この $C(t)$ は $Y(t) \leq y$ となる時間の総和、つまり

時刻 $t$ までに $y$ 分以内でバスに乗れる時間がどれくらいあるか

を表しています。

時間の単位は問題によって秒・分・時間など様々です。

再生報酬関数 $c(t)$

再生報酬過程において、$c(t) = \mathbb{E} [C(t)]$再生報酬関数といいます。

今回の例では、

時刻 $t$ までに $y$ 分以内でバスに乗れる時間がどれくらいあると見込めるか

を表します。

$C(t) = \int_0^t \mathbb{I}_{\{ Y(t)\leq y \}} (t) dt$ を代入して計算を行うと

再生報酬関数

$$c(t) = \int_0^t \mathbb{P} (Y(u) \leq y) du$$

が得られます。

とみー
とみー

時刻 $t$ と紛らわしいので、ここでも積分変数は $u$ としています。

\begin{eqnarray} c(t) &=& \mathbb{E}[C(t)] \\ &=& \mathbb{E} \left [\int_0^t \mathbb{I}_{\{ Y(u)\leq y \}} (u) du \right] \\ &=& \int_0^t \mathbb{E} [\mathbb{I}_{\{ Y(u)\leq y \}} (u)] du \end{eqnarray}

ここで、$\mathbb{I}_{ \{ Y(u) \leq y \} }$ は

  • $Y(u) \leq y$ のとき1
  • $Y(u) > y$ のとき0

なので、

\begin{eqnarray} \mathbb{E} [\mathbb{I}_{\{ Y(u)\leq y \}} (u)] &=& 1 \cdot \mathbb{P} (Y(u) \leq y) + 0 \cdot \mathbb{P} (Y(u) > y) \\ &=& \mathbb{P} (Y(u) \leq y) \end{eqnarray}

である。

よって

$$c(t) = \int_0^t \mathbb{P} (Y(u) \leq y) du$$

部分報酬 $\{R_n\}$

部分報酬モデルの考え方にしたがって、時刻 $Z_n$ の累積報酬と時刻 $Z_{n-1}$ の累積報酬の差を部分報酬 $R_n$ とすると、

部分報酬

$$\forall n \in \mathbb{N}, \quad R_n = min\{X_n, y\}$$

となります。

再生報酬定理

ここまでで再生報酬過程が定義できたので、再生報酬定理を適用します。

再生報酬定理

すべての自然数 $n$ に対し、$\mathbb{E}[X_n] = \frac{1}{\mu} < \infty, \mathbb{V}[X_n] < \infty$、$\mathbb{E}[R_n] < \infty$ が成り立つとき、

$$\displaystyle \lim_{t \to \infty} \frac{c(t)}{t} = \mu \mathbb{E}[R_n]$$

となる。

とみー
とみー

途中の式変形で登場するので、部分報酬の期待値だけ最初に確認しておきましょう。

部分報酬 $\{R_n\}$ の期待値 $\mathbb{E}[R_n]$

計算を行うと、$\{R_n\}$ の期待値は

$$\mathbb{E}[R_n] = \int_0^y \mathbb{P} (X_n > x) dx$$

であることが求められます。

部分積分を使うと

\begin{eqnarray} \int_0^\infty \mathbb{P}(R_n > x) dx &=& \left [ x \mathbb{P}(R_n > x) \right ]_0^\infty \; – \int_0^\infty x \frac{\partial}{\partial x} \mathbb{P} (R_n > x) dx \\ &=& 0 \; – \int_0^\infty x \frac{\partial}{\partial x} (1 \; – \; \mathbb{P} (R_n \leq x)) dx \\ &=& – \int_0^\infty x \frac{\partial}{\partial x} (1 \; – \; F_R(x)) dx \\ &=& – \int_0^\infty x (- f_R(x)) dx \\ &=& \int_0^\infty x f_R (x) dx \\ &=& \mathbb{E}[R_n] \end{eqnarray}

となる。

ここで、

\begin{eqnarray} \int_0^\infty \mathbb{P}(R_n > x) dx &=& \color{blue}\int_0^y \mathbb{P}(R_n > x)dx \color{black}+ \color{red}\int_y^\infty \mathbb{P}(R_n > x) dx \end{eqnarray}

だが、$R_n \leq y$ なので $y < x$ のとき

$$R_n > x$$

となることはない。よって、

$$\color{red}\int_y^\infty \mathbb{P}(R_n > x) dx = 0$$

また、$x < y$ のとき

\begin{eqnarray} R_n > x &\iff& min\{X_n, y\} > x \\ &\iff& X_n > x \end{eqnarray}

なので

$$\color{blue}\int_0^\infty \mathbb{P}(R_n > x)dx = \int_0^\infty \mathbb{P}(X_n > x)dx$$

以上をまとめると

$$\mathbb{E}[R_n] = \int_0^y \mathbb{E} (X_n > x)dx$$

再生報酬定理の適用

上で求めた $c(t)$ の表現を使うと、

$$\frac{c(t)}{t} = \frac{1}{t} \int_0^t \mathbb{P} (Y(u) \leq y) du$$

なので、再生報酬定理を適用すると

$$\lim_{t \to \infty} \frac{1}{t} \int_0^t \mathbb{P} (Y(u) \leq y) du = \mu \int_0^y \mathbb{P} (X_n > x) dx$$

となります。

とみー
とみー

これは後で式変形のために使うので、どういう意味かは置いておきましょう。

待ち時間の分布-客の到着が一様分布

さて、ここまでの話は客の到着時間に関して何も仮定していませんでした。

とみー
とみー

要するに、到着時間がどんな確率分布にしたがっていても成り立ちます。

ここからは、話をさらに深めていくために客が時刻 $0$ から $t$ の間でランダムに到着するとしましょう。

つまり、客の到着時間を $U$ としたときに、

$U$ は一様分布 $\mathcal{U}_{[0,t]}$ にしたがう

と仮定します。

このとき、確率密度関数は

\begin{eqnarray} f_U(u) = \left\{ \begin{array}{l} \frac{1}{t} \quad \cdots \quad u \in [0, t]\\ 0 \quad \cdots \quad u \notin [0, t] \end{array} \right. \end{eqnarray}

です。

待ち時間の確率分布

客の到着時間が一様分布にしたがうとき、待ち時間の累積分布関数は

$$\mathbb{P} (Y(U) \leq y) = \int_0^\infty \mathbb{P} (Y(u) \leq y) f_U(u) du$$

です。

とみー
とみー

これは累積分布関数を確率密度関数で表しただけです。

確率密度関数 $f_U$ を代入すると

$$\mathbb{P} (Y(U) \leq y) = \frac{1}{t} \int_0^t \mathbb{P} (Y(u) \leq y) du$$

となります。

とみー
とみー

これは先ほど上で見た $\frac{c(t)}{t}$ に他なりません!

待ち時間の極限分布と均衡分布

$\mathbb{P} (Y(U) \leq y)$ と $\frac{c(t)}{t}$ が同じということは、先ほどの再生報酬定理の結果が使えるので

$$\lim_{t \to \infty} \mathbb{P} (Y(U) \leq y) = \mu \int_0^y \mathbb{P} (X_n > x) dx$$

が成り立ちます。

とみー
とみー

これが待ち時間の極限分布です!

そして、この式の右辺は

$$\mu \int_0^y \mathbb{P} (X_n > x) dx= \mu \int_0^y (1 \; – \; F_X(x)) dx$$

と書き直すことができます。

これは $y$ についての関数と見ることができるので、ここで

$$F_e(y) = \mu \int_0^y (1 \; – \; F_X(x)) dx$$

としましょう。

すると、$F_e(y)$ は

$y$ についての累積分布関数

になっています。

$F_e$ が累積分布関数であることを示すためには、

  • 非減少
  • $\lim_{y \to \infty} F_e(y) = 1$

の2つを確かめればOKです。

まず、$y_1 < y_2$ とすると、

\begin{eqnarray} F_e(y_2) \;-\; F_e(y_1) &=& \mu \int_0^{y_2} (1 \; – \; F_X(x)) dx \;-\; \mu \int_0^{y_1} (1 \; – \; F_X(x)) dx \\ &=& \int_0^{y_1} (1 \; – \; F_X(x)) dx + \int_{y_1}^{y_2} (1 \; – \; F_X(x)) dx \;-\; \mu \int_0^{y_1} (1 \; – \; F_X(x)) dx \\ &=& \int_{y_1}^{y_2} (1 \; – \; F_X(x)) dx \end{eqnarray}

$F_X$ は確率変数 $\{X_n\}$ の累積分布関数だから

$$1 \; – \; F_X(x) \geq 0$$

よって、$F_e(y_2) > F_e(y_1)$ だから $F_e$ は非減少。

また、

\begin{eqnarray} \mu \int_0^\infty (1 \;-\; F_X(x))dx &=& \frac{1}{\mathbb{E}[X]} \cdot \mathbb{E}[X] \\ &=& 1 \end{eqnarray}

なので、$\lim_{y \to \infty} F_e(y) = 1$。

この $F_e$ を確率分布関数 $F_X$ の均衡分布(の生存関数)といいます。

均衡分布の生存関数

$$F_e(y) = \mu \int_0^y (1 \; – \; F_X(x)) dx$$

均衡分布の確率密度関数は、

$$f_e(y) = \mu (1 \;-\; F_X(x))$$

です。

待ち時間の期待値

以上で待ち時間の極限分布がわかったので、最後に期待値を求めると

待ち時間の期待値

$$\mathbb{E}[Y] = \frac{1}{2} \mu \left(\mathbb{V}[X_n] + \frac{1}{\mu^2} \right)$$

となります。

まず、計算に必要なので次の式変形を考える。

\begin{eqnarray} \mathbb{E}[X^2] &=& \int_0^\infty \mathbb{P}(X^2 > x) dx \\ &=& \int_0^\infty \mathbb{P}(X > x^{\frac{1}{2}}) dx \\ \end{eqnarray}

$x = y^2$ という変数変換をすると、$dx = 2ydy$ なので

\begin{eqnarray} \mathbb{E}[X^2] &=& 2 \int_0^\infty y \,\mathbb{P}(X > y) dy \\ &=& 2 \int_0^\infty y(1 \;-\; F_X(y)) dy \\ \end{eqnarray}

となる。

よって、

$$\int_0^\infty y (1 \;-\; F_X(y)) dy = \frac{1}{2}\mathbb{E}[X_n^2]$$

これを用いると、

\begin{eqnarray} \mathbb{E}[Y] &=& \int_0^\infty y f_e(y)dy \\ &=& \mu \int_0^\infty y (1 \;-\; F_X(y))dy \\ &=& \frac{1}{2}\mu \mathbb{E}[X_n^2] \\ &=& \frac{1}{2}\mu \left ( \mathbb{V}[X_n] + \mathbb{E}[X_n]^2 \right) \\ &=& \frac{1}{2} \mu \left(\mathbb{V}[X_n] + \frac{1}{\mu^2} \right) \end{eqnarray}

$\mu = \frac{1}{\mathbb{E}[X_n]}$ はバスの運行頻度なので、変更することは難しいです。

とみー
とみー

雇える運転手や所有するバスの台数には限りがあるからです。

一方で、$\mathbb{V}[X_n]$ はバスの到着時間の分散なので、運転速度やルートを変えることである程度調整することができます。

よって、この式からわかるのは分散を小さくすればするほど待ち時間が少なくなり、サービス向上につながるということです。

つまり、

できる限り同じ間隔でバスが到着するようにする

というのがサービス向上の鍵になるということが、確率的な分析の結論になります。

まとめ

今回は、再生過程の応用として待ち時間の極限分布を例に均衡分布を解説しました。

とみー
とみー

客がランダムに到着するなら、バスは等間隔で到着させるのがベスト、というのがポイントですね!

確率過程のおすすめ

コメント

タイトルとURLをコピーしました