更新過程(renewal process)とは、独立で同じ分布に従う正の間隔 $\xi_1,\xi_2,\dots$ の和 $T_n$ を更新の時刻とするときの、時刻 $t$ までの更新の回数 $N(t)$ のなす過程である。間隔の平均を $\mu$ とすると、更新関数 $m(t)=E[N(t)]$ は $m(t)/t\to1/\mu$ を満たす(基本更新定理)。周期ごとの報酬の時間平均は 1 周期の報酬の平均を $\mu$ で割ったものになり、無作為な時刻を含む間隔は平均 $E[\xi_1^2]/\mu$ で $\mu$ 以上になる(検査のパラドックス)。間隔が指数分布なら Poisson 過程である。
前提知識: 強大数の法則, Poisson過程, 畳み込み, Doobの任意抽出定理
更新過程(renewal process)は、独立で同じ分布に従う正の時間間隔 $\xi_1,\xi_2,\dots$ の和 $T_n=\xi_1+\dots+\xi_n$ を「更新」の時刻とする点の列と、時刻 $t$ までの更新の回数 $N(t)$ のなす過程である。電球が切れるたびに取り替えるとき、$\xi_i$ は $i$ 本目の寿命で、$N(t)$ は時刻 $t$ までに取り替えた本数である。間隔が指数分布なら Poisson過程 になる。
更新の直後には、過程は過去と独立に新しく始まる。この性質があるので、間隔の分布が一般でも、長い時間の平均は 1 周期の平均から計算できる。主な結論は次のとおりである。
$F$ を $(0,\infty)$ 上の確率分布の分布関数とする。$\xi_1,\xi_2,\dots$ を独立に分布 $F$ に従う確率変数とし、$\mu:=E[\xi_1]\in(0,\infty]$ とおく。
$T_0:=0$、$T_n:=\xi_1+\dots+\xi_n$ とする。$T_n$ を 更新の時刻、$\xi_n$ を 間隔 といい、
$$
N(t):=\#\{n\ge1\mid T_n\le t\}\qquad(t\ge0)
$$
を 更新過程 という。更新関数 は $m(t):=E[N(t)]$ である。
定義から $\{N(t)\ge n\}=\{T_n\le t\}$ である。$F^{*n}$ を $F$ の $n$ 回の 畳み込み とすると、$T_n$ の分布関数は $F^{*n}$ なので
$$
m(t)=\sum_{n\ge1}P(T_n\le t)=\sum_{n\ge1}F^{*n}(t)
$$
である。文献によっては時刻 $0$ の更新も数え、$U(t):=1+m(t)$ を更新関数と呼ぶ(Dur19 §2.6)。この記事では両方の記号を使う。
すべての $t$ について、$N(t)$ は確率 $1$ で有限で、$m(t)< \infty$ である。
$a:=E[e^{-\xi_1}]$ とおく。$\xi_1>0$ なので $a< 1$ である。Markovの不等式 から
$$
P(T_n\le t)=P(e^{-T_n}\ge e^{-t})\le e^ta^n
$$
である。$m(t)\le e^ta/(1-a)< \infty$ である。$\square$
$\tau(t):=N(t)+1=\inf\{n\mid T_n>t\}$ は、$\mathcal G_n:=\sigma(\xi_1,\dots,\xi_n)$ についての停止時刻である。$N(t)$ そのものは停止時刻ではない。$\{N(t)=n\}$ は $\xi_{n+1}$ に依存するからである。
$m$ は $m(t)=F(t)+\int_{(0,t]}m(t-s)\,dF(s)$ を満たす。さらに、$h$ が有界な区間で有界な可測関数なら、
$$
H(t)=h(t)+\int_{(0,t]}H(t-s)\,dF(s)\qquad(t\ge0)
$$
の、有界な区間で有界な解は $H(t)=h(t)+\int_{(0,t]}h(t-s)\,dm(s)$ だけである。
$\xi_1\le t$ なら $N(t)=1+N'(t-\xi_1)$ である。$N'$ は $\xi_2,\xi_3,\dots$ から作った更新過程で、$\xi_1$ と独立で同じ法則に従う。$\xi_1>t$ なら $N(t)=0$ である。期待値をとると最初の式を得る。
$H:=h+h*m$ が解であることは、$m*F=m-F$ から $H*F=h*F+h*(m-F)=h*m=H-h$ となることで分かる。積分はすべて有界な区間の上の有限測度によるので、畳み込みの順序は入れ替えてよい。
一意性:$K$ を 2 つの解の差とすると、$K=K*F$ である。繰り返すと $K=K*F^{*n}$ なので、$\lvert K(t)\rvert\le\sup_{s\le t}\lvert K(s)\rvert\,F^{*n}(t)$ である。$\sum_nF^{*n}(t)=m(t)< \infty$ なので $F^{*n}(t)\to0$ である。$\square$
Laplace–Stieltjes 変換 $\hat F(s):=\int e^{-sx}\,dF(x)$ をとると、更新方程式は $\hat m=\hat F+\hat m\hat F$ となり、
$$
\hat m(s)=\frac{\hat F(s)}{1-\hat F(s)}
$$
である。$\hat F$ は $F$ を決めるので、$m$ と $F$ は互いを決める。
| $F$ | $\mu$ | $m(t)$ |
|---|---|---|
| 指数分布 $\mathrm{Exp}(\lambda)$ | $1/\lambda$ | $\lambda t$ |
| ガンマ分布 $\Gamma(2,\lambda)$(形 $2$、強度 $\lambda$) | $2/\lambda$ | $\frac{\lambda t}2-\frac14+\frac14e^{-2\lambda t}$ |
| 一様分布 $(0,1)$ | $1/2$ | $e^t-1$($t\le1$) |
| 定数 $c$ | $c$ | $\lfloor t/c\rfloor$ |
指数分布では $\hat m=\lambda/s$ で、Poisson過程 の $E[N(t)]=\lambda t$ に戻る。ガンマ分布 では $\hat m(s)=\lambda^2/(s(s+2\lambda))$ を逆変換する。一様分布では、$t\le1$ で更新方程式が $m(t)=t+\int_0^tm(u)\,du$ となり、微分して解く。
大数の法則の形は 強大数の法則 の命題「再生過程の数え上げ」にある。$\mu=\infty$ でも、切り詰めで同じ結論を得る。
確率 $1$ で $N(t)/t\to1/\mu$ である($1/\infty=0$)。
$\mu< \infty$ の場合は上の命題である。$\mu=\infty$ のとき、$c>0$ について $\xi_i\wedge c$ から作った更新過程を $N^c$ とすると、$N\le N^c$ で、$N^c(t)/t\to1/E[\xi_1\wedge c]$ である。$c\to\infty$ として $\limsup N(t)/t=0$ である。$\square$
確率 $1$ の収束から期待値の収束は自動的には出ない。次の定理の証明には Wald の等式を使う。
$(\xi_i,R_i)$ を独立で同じ分布に従う組、$R_i\ge0$、$\mathcal H_n:=\sigma((\xi_i,R_i)\mid i\le n)$ とする。$\tau$ が $(\mathcal H_n)$ の停止時刻なら $E\bigl[\sum_{i\le\tau}R_i\bigr]=E[R_1]E[\tau]$ である。
$\{\tau\ge i\}=\{\tau\le i-1\}^c\in\mathcal H_{i-1}$ は $R_i$ と独立である。Tonelliの定理 から $E\bigl[\sum_iR_i\mathbf 1_{\{\tau\ge i\}}\bigr]=\sum_iE[R_1]P(\tau\ge i)=E[R_1]E[\tau]$ である。$\square$
$R_i=\xi_i$ のときが Doobの任意抽出定理 の系「Waldの等式」の、非負の場合である。ここでは $\tau$ が $R_i$ 以外の情報にも依存してよい形が要る。
$t\to\infty$ で $m(t)/t\to1/\mu$ である($1/\infty=0$)。
下からの評価。 $\mu< \infty$ とする。$E[\tau(t)]=U(t)< \infty$ なので、lem-rn-wald から $E[T_{\tau(t)}]=\mu U(t)$ である。$T_{\tau(t)}>t$ なので、$U(t)\ge t/\mu$ である。$\mu=\infty$ なら下からの評価は要らない。
上からの評価。 $T_{\tau(t)}$ は $t$ を、最後の間隔の分だけ超える。間隔が有界なら超過も有界である。$c>0$ とし、$\xi_i^c:=\xi_i\wedge c$ から作った更新過程に上付きの $c$ を付ける。$T_{\tau^c(t)}^c\le t+c$ なので、lem-rn-wald から $E[\xi_1^c]U^c(t)\le t+c$ である。$\xi_i^c\le\xi_i$ なので $N\le N^c$ で、$U\le U^c$ である。よって
$$
\limsup_{t\to\infty}\frac{U(t)}t\le\frac1{E[\xi_1\wedge c]}
$$
である。$c\to\infty$ の単調収束定理で、右辺は $1/\mu$ に近づく。$U=1+m$ なので結論を得る。$\square$
切り詰めが要るのは、超過 $T_{\tau(t)}-t$ の平均が大きくなりうるからである。$E[\xi_1^2]=\infty$ なら、超過の時間平均は無限大である(thm-rn-inspection)。
$\sigma^2:=\operatorname{Var}(\xi_1)\in(0,\infty)$、$\mu< \infty$ とする。$t\to\infty$ で
$$
\frac{N(t)-t/\mu}{\sigma\sqrt{t/\mu^3}}
$$
は標準正規分布に分布収束する。
$x\in\mathbb R$ を固定し、$n=n(t):=\lceil t/\mu+x\sigma\sqrt{t/\mu^3}\,\rceil$ とおく。$\{N(t)< n\}=\{T_n>t\}$ である。$n\sim t/\mu$ で、$t-n\mu=-x\sigma\sqrt{t/\mu}+O(1)$ なので、$(t-n\mu)/(\sigma\sqrt n)\to-x$ である。中心極限定理 から
$$
P(N(t)< n)=P\Bigl(\frac{T_n-n\mu}{\sigma\sqrt n}>\frac{t-n\mu}{\sigma\sqrt n}\Bigr)\to P(Z>-x)=P(Z< x)
$$
である。$Z$ は標準正規変数である。$\square$
基本更新定理は平均の傾きを述べる。短い区間の中の更新の数まで $h/\mu$ に近づくかどうかは、$F$ の格子性で分かれる。$F$ の台がある $d>0$ について $\{d,2d,3d,\dots\}$ に含まれるとき、$F$ は 格子的(arithmetic)であるという。そのような $d$ の最大のものを スパン という。
$F$ が格子的でないなら、すべての $h>0$ について、$t\to\infty$ で
$$
m(t+h)-m(t)\to\frac h\mu
$$
である($\mu=\infty$ なら右辺は $0$)。
この記事では証明しない。Dur19 Theorem 2.6.4(p. 93)は閉区間 $[t,t+h]$ の更新の数の形で述べており、区間の端を $\varepsilon$ ずらしてはさむと上の形になる。同書は $\mu< \infty$ の場合を結合の方法で示している。$T_n$ と、定常な更新過程(ex-rn-stationary)の更新の時刻が $\varepsilon$ 以内に近づく番号を探し、そこから先の間隔をそろえる。$\mu=\infty$ の場合は別の議論による(pp. 96–98)。
格子的な場合は Markov連鎖 の収束定理に帰着する。
$\xi_1$ は正の整数の値をとり、$\gcd\{k\mid P(\xi_1=k)>0\}=1$、$\mu< \infty$ とする。$u_n:=P(\text{ある }k\text{ で }T_k=n)$ とおくと $u_n\to1/\mu$ である。
$X_n:=\min\{T_k-n\mid T_k\ge n\}$(次の更新までの残り時間)は、$0$ から $j$ へ確率 $P(\xi_1=j+1)$ で移り、$i\ge1$ から $i-1$ へ確率 $1$ で移る Markov 連鎖である。$X_0=0$ から出発し、$u_n=P(X_n=0)$ である。$\pi(i):=P(\xi_1>i)/\mu$ は確率分布で($\sum_{i\ge0}P(\xi_1>i)=\mu$)、$\pi(i)=\pi(i+1)+\pi(0)P(\xi_1=i+1)$ から定常である。$0$ から到達できる状態の上で連鎖は既約で、gcd の条件から非周期である。Dur19 Theorem 5.6.6 により $P(X_n=0)\to\pi(0)=1/\mu$ である(連鎖は同書の Example 5.5.8)。$\square$
Blackwell の定理を、区間の個数から関数へ広げたものが次の定理である。関数 $h\ge0$ の、幅 $\delta$ の区間ごとの上限・下限の和
$$
\overline I_\delta:=\delta\sum_{k\ge0}\sup_{[k\delta,(k+1)\delta)}h,\qquad\underline I_\delta:=\delta\sum_{k\ge0}\inf_{[k\delta,(k+1)\delta)}h
$$
が $\delta\to0$ で同じ有限の値に近づくとき、$h$ は 直接 Riemann 可積分 であるという。$h\ge0$ が単調減少で積分可能なら、直接 Riemann 可積分である(Dur19 Lemma 2.6.13)。
$F$ が格子的でないとする。$h$ が直接 Riemann 可積分なら、thm-rn-equation の解 $H$ は $t\to\infty$ で $H(t)\to\frac1\mu\int_0^\infty h(s)\,ds$ を満たす。
Dur19 Theorem 2.6.12 は thm-rn-blackwell からこれを導いている(同書の名は renewal theorem)。階段関数で上下からはさむだけである。この記事では証明しない。$F$ が格子的でないときの帰結は次の 2 つである(同 Example 2.6.14、2.6.15)。
周期ごとに報酬が付く場合を考える。$(\xi_i,R_i)$ を独立で同じ分布に従う組とする。$R_i$ は実数値で、$\xi_i$ に依存してよい。$R(t):=\sum_{i\le N(t)}R_i$ を時刻 $t$ までに終わった周期の報酬の和とする。
$\mu< \infty$、$E\lvert R_1\rvert< \infty$ とする。$t\to\infty$ で、確率 $1$ で $R(t)/t\to E[R_1]/\mu$ であり、$E[R(t)]/t\to E[R_1]/\mu$ である。
$R_i^\pm$ に分けて、$R_i\ge0$ としてよい。
確率 $1$ の収束:$N(t)\to\infty$ なので、$\frac{R(t)}t=\frac{R(t)}{N(t)}\cdot\frac{N(t)}t\to E[R_1]\cdot\frac1\mu$ である。強大数の法則 と prop-rn-slln による。
期待値:$R(t)=\sum_{i\le\tau(t)}R_i-R_{\tau(t)}$ で、lem-rn-wald から $E[R(t)]=E[R_1]U(t)-g(t)$、$g(t):=E[R_{\tau(t)}]$ である。thm-rn-elementary から、$g(t)/t\to0$ を示せばよい。$g(t)\le E[R_1]U(t)$ は有界な区間で有界である。最初の更新で分けると
$$
g(t)=h(t)+\int_{(0,t]}g(t-s)\,dF(s),\qquad h(t):=E[R_1;\xi_1>t]
$$
である。thm-rn-equation から $g=h+h*m$ である。$h\le E[R_1]$ で、$t\to\infty$ で $h(t)\to0$ である。$\varepsilon>0$ に対して、$s\ge A$ で $h(s)\le\varepsilon$ となる $A$ をとる。$t>A$ について
$$
g(t)\le h(t)+\varepsilon m(t)+E[R_1]\bigl(m(t)-m(t-A)\bigr)
$$
である。ここで $m(t)-m(t-A)\le U(A)$ である。実際、$s:=t-A$ とする。$(s,t]$ の更新は $T_{\tau(s)}>s$ から始まる。$\xi_{\tau(s)+1},\xi_{\tau(s)+2},\dots$ は $\tau(s)$ までと独立で同じ法則に従うので、これらから作る更新過程 $N'$ を使うと、$(s,t]$ の更新の数は $1+N'(A)$ 以下である。よって $\limsup g(t)/t\le\varepsilon/\mu$ である。$\square$
周期の途中の報酬を連続的に受け取る場合も、1 周期の総額が $R_i$ で途中の値がその間にあれば、確率 $1$ の結論は同じである。
寿命が一様分布 $(0,1)$ の部品を、壊れたら費用 $5$ で、年齢 $a$ に達したら費用 $1$ で取り替える。周期は $\xi=\min(X,a)$ で、$X$ は寿命である。$E[\xi]=a-a^2/2$、1 周期の費用の平均は $5a+(1-a)=1+4a$ なので、長い時間の費用の率は
$$
c(a)=\frac{1+4a}{a-a^2/2}
$$
である。$c'(a)=0$ は $2a^2+a-1=0$ で、$a=\frac12$、$c(\frac12)=8$ である。壊れるまで使うと $c(1)=10$ である。
機械が平均 $\mu_1$ の時間だけ動き、平均 $\mu_2$ の時間だけ修理される。組(稼働時間、修理時間)が独立で同じ分布に従うなら、1 周期の稼働時間を報酬として、長い時間のうち動いている時間の割合は $\mu_1/(\mu_1+\mu_2)$ である。稼働時間と修理時間は互いに依存してよい。
時刻 $s$ を含む間隔の長さを $L(s):=\xi_{\tau(s)}$、次の更新までの時間を $B(s):=T_{\tau(s)}-s$ とする。
$\mu< \infty$ とする。確率 $1$ で、$t\to\infty$ のとき
$$
\frac1t\int_0^tB(s)\,ds\to\frac{E[\xi_1^2]}{2\mu},\qquad\frac1t\int_0^tL(s)\,ds\to\frac{E[\xi_1^2]}\mu
$$
であり($E[\xi_1^2]=\infty$ なら極限は $\infty$)、$x>0$ について
$$
\frac1t\int_0^t\mathbf 1_{\{L(s)\le x\}}\,ds\to\frac{E[\xi_1;\xi_1\le x]}\mu
$$
である。
$f\ge0$ を $B,L$、$\mathbf 1_{\{L\le x\}}$ のどれかとし、$R_i:=\int_{T_{i-1}}^{T_i}f(s)\,ds$ とおく。それぞれ $R_i=\xi_i^2/2$、$\xi_i^2$、$\xi_i\mathbf 1_{\{\xi_i\le x\}}$ である。$f\ge0$ なので
$$
\sum_{i\le N(t)}R_i\le\int_0^tf(s)\,ds\le\sum_{i\le N(t)+1}R_i
$$
である。$E[R_1]< \infty$ なら、両端を $t$ で割ると thm-rn-reward の確率 $1$ の収束から $E[R_1]/\mu$ に近づく($N(t)/t$ と $(N(t)+1)/t$ の極限は同じである)。$E[\xi_1^2]=\infty$ なら、$R_i\wedge c$ を報酬にして左の不等式を使い、$c\to\infty$ とする。$\square$
$E[\xi_1^2]/\mu=\mu+\operatorname{Var}(\xi_1)/\mu\ge\mu$ で、等号は間隔が定数のときに限る。間隔が定数でなければ、無作為な時刻を含む間隔は平均の間隔より長い。最後の式は、間隔の長さの分布が、$F$ を長さ $y$ で重みづけた分布 $y\,dF(y)/\mu$ に替わることを述べている。
| 間隔の分布(平均 $\mu$) | 時間平均の待ち時間 | 時間平均の間隔の長さ |
|---|---|---|
| 定数 | $\mu/2$ | $\mu$ |
| 一様分布 $(0,2\mu)$ | $2\mu/3$ | $4\mu/3$ |
| 指数分布 | $\mu$ | $2\mu$ |
| $E[\xi_1^2]=\infty$ の分布 | $\infty$ | $\infty$ |
指数分布の行は Poisson過程 の例「待ち時間の逆説」である。バスが平均 $\mu$ の間隔で来ても、待ち時間の平均は時刻表どおりの場合の 2 倍になる。
$\mu< \infty$ とし、$G(x):=\frac1\mu\int_0^x(1-F(y))\,dy$ とおく。$\xi_0$ を分布 $G$ に従わせ、$\xi_1,\xi_2,\dots$ と独立とする。$T_n':=\xi_0+T_n$($n\ge0$)を更新の時刻とする。rem-rn-key の 2 つ目の極限は、$1-G(x)$ である。この過程の更新の回数の平均は $\sum_{n\ge0}G*F^{*n}=G+G*m$ である。Laplace–Stieltjes 変換は
$$
\hat G(1+\hat m)=\frac{1-\hat F(s)}{\mu s}\cdot\frac1{1-\hat F(s)}=\frac1{\mu s}
$$
で、これは $t/\mu$ の変換である。すなわち、最初の遅れを $G$ にすると、更新の平均は時間に正確に比例する。
| 主張 | 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|---|
| prop-rn-finite | 同分布 | $\xi_i=2^{-i}$ | $t\ge1$ で $N(t)=\infty$ |
| prop-rn-slln の極限が定数 | 独立性 | $\xi_1=\xi_2=\dots=X$($X$ は正の確率変数) | $N(t)/t\to1/X$ で、極限は確率変数 |
| thm-rn-blackwell | 格子的でないこと | $\xi_i\equiv1$、$h=\frac12$ | $m(t+h)-m(t)$ は $0$ と $1$ の間で振動する |
| prop-rn-lattice | gcd が $1$ | $\xi_i\in\{2,4\}$ | $u_n$ は奇数の $n$ で $0$ |
| thm-rn-reward | 組の独立性 | $\xi_i\equiv1$、$R_i=X$(共通の可積分な確率変数) | $R(t)/t\to X$ で、極限は $E[X]$ でない |
| thm-rn-inspection の有限性 | $E[\xi_1^2]< \infty$ | $P(\xi_1>x)=x^{-3/2}$($x\ge1$) | $\mu=3$ だが待ち時間の時間平均は $\infty$ |
反例の確かめ:3 行目では、$t=n+\frac12$ なら $m(t+\frac12)-m(t)=1$、$t=n$ なら $0$ である。ただし基本更新定理は成り立つ。6 行目では、$E[\xi_1]=1+\int_1^\infty x^{-3/2}\,dx=3$ で、$E[\xi_1^2]=\frac32\int_1^\infty x^{2-5/2}\,dx=\infty$ である。
定義、thm-rn-elementary の下からと上からの評価の方針、thm-rn-equation(Theorem 2.6.9)は Dur19 §2.6(pp. 91–103)による。thm-rn-reward の期待値の部分の $g(t)/t\to0$ の議論と、thm-rn-inspection の報酬としての書き方は、この記事で組み立てた。待ち行列 の Little の公式も、周期の平均から時間平均を求める同じ種類の議論である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する