Spitzerの公式(Spitzer's formula)とは、独立同分布な実数値の確率変数の部分和 $S_n$ とその最大値 $M_n=\max(0,S_1,\ldots,S_n)$ について、$0\le s< 1$ で $\sum_ns^n\mathrm E[e^{itM_n}]=\exp(\sum_k\frac{s^k}k\mathrm E[e^{itS_k^+}])$ が成り立つという公式である。道全体で決まる最大値の分布が、各時刻の部分和の分布だけで決まる。最大値と最大値からの下がり幅の同時分布に広げた形は Wiener–Hopf 分解から導かれ、最大値の平均 $\mathrm E[M_n]=\sum_{k\le n}\mathrm E[S_k^+]/k$、全体の最大値の分布、幾何分布の時刻での独立性が従う。窓口が 1 つの待ち行列の待ち時間も $M_n$ と同じ分布をもつ。
前提知識: ランダムウォーク, 特性関数(確率論), Wiener–Hopf分解(確率論)
独立同分布な実数値の確率変数 $X_1,X_2,\ldots$ の部分和 $S_n=X_1+\cdots+X_n$($S_0=0$)と、その最大値 $M_n:=\max(S_0,S_1,\ldots,S_n)$ を考える。Spitzerの公式(Spitzer's formula)は、$0\le s< 1$、$t\in\mathbb R$ について
$$
\sum_{n\ge0}s^n\,\mathrm E\bigl[e^{itM_n}\bigr]=\exp\Bigl(\sum_{k\ge1}\frac{s^k}k\,\mathrm E\bigl[e^{itS_k^+}\bigr]\Bigr)\qquad(S_k^+:=\max(S_k,0))
$$
が成り立つという主張である。左辺の $M_n$ は道全体を見て決まる量だが、右辺には各時刻の $S_k$ の分布しか現れない。したがって最大値の分布は、部分和の 1 次元の分布の列だけから計算できる。Spitzer が組合せ論の補題から導いた公式で(Spi56)、Baxter の論文の冒頭にこの形で引かれている(Bax58 (1.1)、p. 649)。
この記事では、最大値と、最大値からの下がり幅 $S_n-M_n$ の同時分布の公式として主定理(thm-spf-main)を証明する。証明は Wiener–Hopf分解(確率論) の梯子時刻の補題と因子の指数公式による。系として、最大値の平均の公式(cor-spf-mean)、全体の最大値の分布(cor-spf-sup)、幾何分布の時刻での独立性(cor-spf-geometric)を示し、待ち行列の待ち時間への応用を述べる。
以下、$X_1,X_2,\ldots$ は独立で同じ分布に従う実数値の確率変数とし、$\mathrm E[Y;A]:=\mathrm E[Y\mathbf 1_A]$ と書く。$\tau_+:=\min\{n\ge1\mid S_n>0\}$、$\tau_-:=\min\{n\ge1\mid S_n\le0\}$ と、その変換 $F_\pm(s,t)$ は Wiener–Hopf分解(確率論) の定義「梯子時刻と梯子高さ」のものである。
$n\ge0$ について $M_n:=\max(S_0,\ldots,S_n)$ を 最大値、$D_n:=S_n-M_n\le0$ を 最大値からの下がり幅、$L_n:=\min\{m\le n\mid S_m=M_n\}$ を最大値を初めてとる時刻という。
$0\le s< 1$、$t,u\in\mathbb R$ について次が成り立つ。
時刻 $L_n$ での分解. $0\le m\le n$ について、$L_n=m$ であることは、$S_m>S_j$($0\le j< m$)かつ $S_j\le S_m$($m< j\le n$)であることと同じである。前者を $A_m$、後者を $B_{m,n}$ とおく($A_0$ は全事象)。$A_m\in\sigma(X_1,\ldots,X_m)$ で、$B_{m,n}$ は $S_{m+i}-S_m=X_{m+1}+\cdots+X_{m+i}\le0$($1\le i\le n-m$)と書けるので $\sigma(X_{m+1},\ldots,X_n)$ に属する。$L_n=m$ のとき $M_n=S_m$、$D_n=S_n-S_m$ である。$S_n-S_m$ も $X_{m+1},\ldots,X_n$ で決まり、$(X_{m+1},\ldots,X_n)$ は $(X_1,\ldots,X_{n-m})$ と同じ分布をもつので、
$$
\mathrm E\bigl[e^{itM_n+iuD_n};\ L_n=m\bigr]=\mathrm E\bigl[e^{itS_m};\ A_m\bigr]\cdot\mathrm E\bigl[e^{iuS_{n-m}};\ \tau_+>n-m\bigr]
$$
である($B_{m,n}$ を $X_{m+1},\ldots$ で書き直すと、ずらした歩みについての $\tau_+>n-m$ になる)。
母関数. $m=0,\ldots,n$ について足し、$s^n$ を掛けて $n\ge0$ について足す。各項の絶対値は $1$ 以下なので、和は 2 つの級数の積(Cauchy 積)になり、
$$
\sum_{n\ge0}s^n\,\mathrm E\bigl[e^{itM_n+iuD_n}\bigr]=\Bigl(\sum_{m\ge0}s^m\,\mathrm E\bigl[e^{itS_m};\ A_m\bigr]\Bigr)\Bigl(\sum_{j\ge0}s^j\,\mathrm E\bigl[e^{iuS_j};\ \tau_+>j\bigr]\Bigr)=\frac1{1-F_+(s,t)}\cdot\frac1{1-F_-(s,u)}
$$
である。最後の等号は、Wiener–Hopf分解(確率論) の補題「梯子時刻の集合」の 3($A_m$ は $S_m>\max_{j< m}S_j$)と補題「時間の反転」による。
指数公式. 同記事の定理「因子を部分和の分布で表す」により $1/(1-F_+(s,t))=\exp(\sum_k\frac{s^k}k\mathrm E[e^{itS_k};S_k>0])$、$1/(1-F_-(s,u))=\exp(\sum_k\frac{s^k}k\mathrm E[e^{iuS_k};S_k\le0])$ なので、1 を得る。2 は 1 で $u=0$ とおけばよい。$\mathrm E[e^{itS_k};S_k>0]+P(S_k\le0)=\mathrm E[e^{itS_k^+}]$ だからである。$\square$
1 の右辺は $t$ だけの因子と $u$ だけの因子の積である。$s=0$ の係数から順に比べると、$n=1$ では $\mathrm E[e^{itM_1}]=\mathrm E[e^{itS_1^+}]$($M_1=S_1^+$)を、$n=2$ では
$$
\mathrm E\bigl[e^{itM_2}\bigr]=\frac12\mathrm E\bigl[e^{itS_2^+}\bigr]+\frac12\Bigl(\mathrm E\bigl[e^{itS_1^+}\bigr]\Bigr)^2
$$
を与える。右辺の第 2 項は独立な 2 つの $S_1^+$ の和の特性関数で、$M_2$ の分布が $S_2^+$ の分布と「$S_1^+$ を 2 つ独立に足したもの」の分布の半々の混合になることを言っている。
$\mathrm E[X_1^+]< \infty$ なら、$n\ge1$ について
$$
\mathrm E[M_n]=\sum_{k=1}^n\frac1k\,\mathrm E\bigl[S_k^+\bigr]
$$
である。
$b_k(t):=\mathrm E[e^{itS_k^+}]$ とおく。$\exp(\sum_k\frac{s^k}kb_k(t))$ の $s^n$ の係数は $b_1(t),\ldots,b_n(t)$ の($t$ によらない有理数係数の)多項式 $R_n$ であり、thm-spf-main の 2 により $\mathrm E[e^{itM_n}]=R_n(b_1(t),\ldots,b_n(t))$ である。$0\le S_k^+\le X_1^++\cdots+X_k^+$、$0\le M_n\le X_1^++\cdots+X_n^+$ なので、どれも平均が有限で、特性関数(確率論) の定理「積率と微分」により $b_k'(0)=i\,\mathrm E[S_k^+]$、$\frac d{dt}\mathrm E[e^{itM_n}]\big|_{t=0}=i\,\mathrm E[M_n]$ である。形式的冪級数として $\frac{\partial}{\partial t}\exp(B)=\exp(B)\,\frac{\partial B}{\partial t}$($B:=\sum_k\frac{s^k}kb_k(t)$)が係数ごとに成り立ち、$t=0$ では $b_k(0)=1$ より $\exp(B)=\exp(\sum_k\frac{s^k}k)=\frac1{1-s}$ である。よって
$$
i\,\mathrm E[M_n]=[s^n]\,\frac1{1-s}\sum_{k\ge1}\frac{s^k}k\,i\,\mathrm E[S_k^+]=i\sum_{k=1}^n\frac1k\,\mathrm E[S_k^+]
$$
である。$\square$
$\sum_{k\ge1}\frac1kP(S_k>0)< \infty$ とする。このとき $M_\infty:=\sup_nS_n$ は確率 $1$ で有限で、
$$
\mathrm E\bigl[e^{itM_\infty}\bigr]=\exp\Bigl(-\sum_{k\ge1}\frac1k\,\mathrm E\bigl[1-e^{itS_k};\ S_k>0\bigr]\Bigr)
$$
である。
$M_\infty< \infty$ は Wiener–Hopf分解(確率論) の系「上限が有限になる条件」による。$M_n\uparrow M_\infty$ なので、有界収束定理により $c_n:=\mathrm E[e^{itM_n}]\to\mathrm E[e^{itM_\infty}]$ であり、Abelの連続性定理 により $(1-s)\sum_ns^nc_n\to\mathrm E[e^{itM_\infty}]$($s\uparrow1$)である。右辺は、$1-s=\exp(-\sum_k\frac{s^k}k)$ を使うと
$$
(1-s)\exp\Bigl(\sum_k\frac{s^k}kb_k(t)\Bigr)=\exp\Bigl(-\sum_k\frac{s^k}k\bigl(1-b_k(t)\bigr)\Bigr),\qquad1-b_k(t)=\mathrm E\bigl[1-e^{itS_k};\ S_k>0\bigr]
$$
で、$\lvert1-b_k(t)\rvert\le2P(S_k>0)$ だから級数は $s\in[0,1]$ で一様に絶対収束し、$s\uparrow1$ で $s=1$ の値に近づく。$\square$
平均が有限で負($\mathrm E\lvert X_1\rvert< \infty$、$\mathrm E[X_1]< 0$)なら、大数の強法則 により $S_n\to-\infty$ なので $M_\infty< \infty$ であり、Wiener–Hopf分解(確率論) の同じ系により $\sum_kP(S_k>0)/k< \infty$ である。
$0< s< 1$ とし、$N$ を $(X_n)$ と独立で $P(N=n)=(1-s)s^n$($n\ge0$)の確率変数とする。このとき $M_N$ と $D_N=S_N-M_N$ は独立で、
$$
\mathrm E\bigl[e^{itM_N}\bigr]=\exp\Bigl(-\sum_{k\ge1}\frac{s^k}k\,\mathrm E\bigl[1-e^{itS_k};\ S_k>0\bigr]\Bigr),\qquad\mathrm E\bigl[e^{iuD_N}\bigr]=\exp\Bigl(-\sum_{k\ge1}\frac{s^k}k\,\mathrm E\bigl[1-e^{iuS_k};\ S_k\le0\bigr]\Bigr)
$$
である。
$\mathrm E[e^{itM_N+iuD_N}]=(1-s)\sum_ns^n\mathrm E[e^{itM_n+iuD_n}]$ である。thm-spf-main の 1 に $1-s=\exp(-\sum_k\frac{s^k}k(P(S_k>0)+P(S_k\le0)))$ を掛けると、右辺は上の 2 つの式の右辺 $g(t)$ と $h(u)$ の積 $g(t)h(u)$ になる。$h(0)=g(0)=1$ なので、$u=0$ として $\mathrm E[e^{itM_N}]=g(t)$、$t=0$ として $\mathrm E[e^{iuD_N}]=h(u)$ である。よって $(M_N,D_N)$ の同時特性関数は周辺の特性関数の積で、これは独立な 2 つの変数の同時特性関数でもある。$\mathbb R^2$ の上の分布も特性関数で決まる(特性関数(確率論) の補足「確率ベクトルの特性関数」)ので、$M_N$ と $D_N$ は独立である。$\square$
$S_N$ の特性関数は $(1-s)/(1-s\varphi(t))$ なので、この系は $S_N=M_N+D_N$ を独立な 2 つの部分に分けたもので、Wiener–Hopf分解(確率論) の分解 $1-s\varphi=(1-F_+)(1-F_-)$ を確率変数の言葉で読んだものである。
窓口が 1 つの待ち行列で、客 $n$ が到着してからサービスが始まるまでの待ち時間を $W_n$ とする。客 $n-1$ のサービス時間から、客 $n-1$ と客 $n$ の到着の間隔を引いたものを $X_n$ とすると、$W_n=\max(W_{n-1}+X_n,0)$ が成り立つ(前の客が去る前に着けば差だけ待ち、そうでなければ待たない)。この漸化式は Lindley による(Lin52)。サービス時間どうし、到着の間隔どうしがそれぞれ独立同分布で互いに独立なら、$X_n$ は独立同分布である。
$X_1,X_2,\ldots$ を独立同分布とし、$W_0:=0$、$W_n:=\max(W_{n-1}+X_n,0)$ とおく。このとき
$$
W_n=\max(0,\ X_n,\ X_n+X_{n-1},\ \ldots,\ X_n+\cdots+X_1)
$$
であり、$W_n$ は $M_n$ と同じ分布をもつ。
$n$ についての帰納法で、$W_{n-1}+X_n=\max(X_n,X_n+X_{n-1},\ldots,X_n+\cdots+X_1)$($n=1$ では $X_1$)なので、$0$ との最大値をとって等式を得る。$(X_n,X_{n-1},\ldots,X_1)$ は $(X_1,\ldots,X_n)$ と同じ同時分布をもつので、右辺は $\max(0,S_1,\ldots,S_n)=M_n$ と同じ分布をもつ。$\square$
したがって、$W_n$ の分布は thm-spf-main の 2 で計算でき、$\sum_kP(S_k>0)/k< \infty$(たとえば $\mathrm E[X_1]< 0$)なら $W_n$ は cor-spf-sup の分布に分布収束する。$W_n$ 自身は $n$ について単調でないが、分布は $M_n$ と同じなので、各 $x$ について $P(W_n\le x)$ は $n$ とともに減る。
$P(X_1=\pm1)=\frac12$ とする。$\mathrm E[S_k^+]=\frac12\mathrm E\lvert S_k\rvert$ で、$\mathrm E\lvert S_{2m}\rvert=\mathrm E\lvert S_{2m-1}\rvert=2m\binom{2m}m4^{-m}$ である。cor-spf-mean により
| $n$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|
| $\mathrm E[S_n^+]$ | $\frac12$ | $\frac12$ | $\frac34$ | $\frac34$ | $\frac{15}{16}$ | $\frac{15}{16}$ |
| $\mathrm E[M_n]$ | $\frac12$ | $\frac34$ | $1$ | $\frac{19}{16}$ | $\frac{11}8$ | $\frac{49}{32}$ |
である。$n=2$ では、4 通りの歩み $(+,+),(+,-),(-,+),(-,-)$ の最大値が $2,1,0,0$ なので、平均は $\frac34$ で表と一致する。$M_2$ の分布($0,1,2$ を確率 $\frac12,\frac14,\frac14$)は、主定理のあとで述べた混合($S_2^+$ の分布と、独立な $S_1^+$ の 2 つの和の分布の半々)とも一致する。
$P(X_1=1)=p$、$P(X_1=-1)=q=1-p$、$p< q$ とし、$\rho:=p/q$ とおく。Wiener–Hopf分解(確率論) の例「因子を一意性から読み取る」により、上向きの梯子高さはいつも $1$ で $P(\tau_+< \infty)=\rho$ である。$M_\infty$ は梯子時刻の個数に等しく、同記事の補題「梯子時刻の集合」の 2 から $P(M_\infty\ge m)=\rho^m$ である。つまり $M_\infty$ は $P(M_\infty=m)=(1-\rho)\rho^m$ の幾何分布に従う。cor-spf-sup と比べると、
$$
\exp\Bigl(-\sum_{k\ge1}\frac1k\,\mathrm E\bigl[1-e^{itS_k};\ S_k>0\bigr]\Bigr)=\frac{1-\rho}{1-\rho e^{it}}
$$
という、二項分布についての恒等式が得られる。また cor-spf-mean で $n\to\infty$ とすると、単調収束定理 により $\sum_{k\ge1}\frac1k\mathrm E[S_k^+]=\mathrm E[M_\infty]=\frac\rho{1-\rho}=\frac p{q-p}$ である。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| $X_i$ の独立性 | $X_n=X_1$(すべての $n$)、$P(X_1=\pm1)=\frac12$ | thm-spf-main の 2:$t=\pi$ で $s^2$ の係数が左辺 $1$、右辺 $\frac12$ |
| 同じ分布 | $X_1=1$、$X_2=-1$($X_3$ 以降は任意) | thm-spf-main の 2:$t=\pi$ で $s^2$ の係数が左辺 $-1$、右辺 $1$ |
| $\sum_kP(S_k>0)/k< \infty$ | 公平な単純ランダムウォーク | cor-spf-sup:$M_\infty< \infty$ が確率 $1$ で成り立たない |
$s^2$ の係数は、主定理のあとで計算したとおり、左辺が $\mathrm E[e^{itM_2}]$、右辺が $\frac12b_2(t)+\frac12b_1(t)^2$($b_k(t)=\mathrm E[e^{itS_k^+}]$)である。1 行目:$S_k=kX_1$ なので $M_2\in\{0,2\}$ で $\mathrm E[e^{i\pi M_2}]=1$、$b_1(\pi)=\frac12(e^{i\pi}+1)=0$、$b_2(\pi)=\frac12(e^{2i\pi}+1)=1$ で右辺は $\frac12$ である。2 行目:$M_2=1$ で左辺は $e^{i\pi}=-1$、$S_1=1$、$S_2=0$ から $b_1(\pi)=-1$、$b_2(\pi)=1$ で右辺は $\frac12+\frac12=1$ である。3 行目:$P(S_k>0)=\frac12(1-P(S_k=0))\to\frac12$ なので和は発散し、Wiener–Hopf分解(確率論) の系「上限が有限になる条件」により確率 $1$ で $M_\infty=\infty$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する