Sparre Andersenの定理(Sparre Andersen theorem)とは、独立同分布な実数値の確率変数の部分和 $S_n$ について、1 歩の分布が $0$ について対称で 1 点の確率がどれも $0$ なら、分布によらず $P(S_1>0,\ldots,S_n>0)=\binom{2n}n4^{-n}$ となるという定理である。同じ仮定のもとで、正の部分和の個数 $N_n$ は $P(N_n=k)=\binom{2k}k\binom{2n-2k}{n-k}4^{-n}$ に従い、$N_n/n$ は逆正弦分布に分布収束する。土台は、交換可能な列で正の部分和の個数と最大値を初めてとる時刻が同じ分布をもつという等価原理と、Wiener–Hopf 分解から得られる母関数 $\sum_np_ns^n=\exp(\sum_n\frac{s^n}nP(S_n>0))$ である。
前提知識: ランダムウォーク, 逆正弦法則, Wiener–Hopf分解(確率論)
独立同分布な実数値の確率変数 $X_1,X_2,\ldots$ の部分和 $S_n=X_1+\cdots+X_n$ が、最初の $n$ 歩の間ずっと正である確率 $P(S_1>0,\ldots,S_n>0)$ は、ふつうは 1 歩の分布によって変わる。ところが 1 歩の分布が $0$ について対称で、どの 1 点の確率も $0$ なら、分布によらず
$$
P(S_1>0,S_2>0,\ldots,S_n>0)=\binom{2n}n\frac1{4^n}
$$
となる。正規分布でも、$[-1,1]$ の一様分布でも、Cauchy 分布でも同じ値である。これを Sparre Andersenの定理(Sparre Andersen theorem)という。同じ仮定のもとで、$S_1,\ldots,S_n$ のうち正であるものの個数 $N_n$ の分布も普遍的で、$2n$ 歩の公平な単純ランダムウォークが正の側にいる時間の半分の分布(逆正弦法則)と一致する。
その土台にあるのが、交換可能な列について「正の部分和の個数」と「最大値を初めてとる時刻」が同じ分布をもつという 等価原理 である。この記事では、等価原理(thm-sa-equivalence)を置換の数え上げで証明し、Wiener–Hopf分解(確率論) の因子の指数公式と組み合わせて主定理(thm-sa-main)を導く。保険数学の「Sparre Andersen のモデル」(請求の到着の間隔を独立同分布にした破産のモデル。保険数学)は同じ人名に由来する別の対象である。
実数の列 $y=(y_1,\ldots,y_n)$ の部分和を $s_0=0$、$s_k=y_1+\cdots+y_k$ とし、
$$
N(y):=\#\{1\le k\le n\mid s_k>0\},\qquad L(y):=\min\{m\mid s_m=\max(s_0,\ldots,s_n)\}
$$
とおく。確率変数の列 $(X_1,\ldots,X_n)$ について $N_n:=N(X_1,\ldots,X_n)$、$L_n:=L(X_1,\ldots,X_n)$ と書く。$L_n$ は最大値 $\max(S_0,\ldots,S_n)$ を初めてとる時刻である。
$(X_1,\ldots,X_n)$ が 交換可能 であるとは、$\{1,\ldots,n\}$ のどの置換 $\pi$ についても $(X_{\pi(1)},\ldots,X_{\pi(n)})$ が $(X_1,\ldots,X_n)$ と同じ同時分布をもつことをいう。独立同分布なら交換可能である。また $u_{2m}:=\binom{2m}m4^{-m}$ とおく(逆正弦法則 の記号)。
$x\in\mathbb R^n$ と $0\le k\le n$ について、置換 $\pi$ のうち $N(x_{\pi(1)},\ldots,x_{\pi(n)})=k$ となるものの個数と、$L(x_{\pi(1)},\ldots,x_{\pi(n)})=k$ となるものの個数は等しい。
$n$ についての帰納法で示す。$n=0$ では $N=L=0$ で、どちらも 1 個である。$n\ge1$ とし、長さ $n-1$ のすべての列で主張が成り立つとする。$T:=x_1+\cdots+x_n$ は $\pi$ によらない。$y=(y_1,\ldots,y_n)$ を並べ替えた列とし、$y'=(y_1,\ldots,y_{n-1})$、$y''=(y_2,\ldots,y_n)$ とおく。
$N$ の側. $s_n=T$ なので $N(y)=N(y')+\mathbf 1_{\{T>0\}}$ である。
$L$ の側、$T>0$ の場合. $k\ge1$ では $s_k=y_1+s''_{k-1}$($s''$ は $y''$ の部分和)であり、$\max_{k\ge1}s_k\ge s_n=T>0=s_0$ なので、最大値は $k\ge1$ でだけとられる。定数 $y_1$ を足しても最大値をとる位置は変わらないので $L(y)=1+L(y'')$ である。
$L$ の側、$T\le0$ の場合. $s_n=T\le0=s_0$ なので、$\max(s_0,\ldots,s_{n-1})$ はすでに $s_n$ 以上で、それを初めてとる時刻は $n-1$ 以下である。よって $L(y)=L(y')$ である。
数える. $x$ から第 $i$ 成分を除いた列を $x^{(i)}$ とし、長さ $n-1$ の列 $z$ について $a_j(z):=\#\{\sigma\mid N(z\circ\sigma)=j\}$、$b_j(z):=\#\{\sigma\mid L(z\circ\sigma)=j\}$ とおく。$\pi(n)=i$ の置換 $\pi$ は、$y'$ が $x^{(i)}$ の並べ替えをちょうど 1 回ずつ走るように対応し、$\pi(1)=i$ の置換は $y''$ について同じである。したがって $T>0$ なら
$$
\#\{\pi\mid N(y)=k\}=\sum_{i=1}^na_{k-1}(x^{(i)}),\qquad\#\{\pi\mid L(y)=k\}=\sum_{i=1}^nb_{k-1}(x^{(i)})
$$
であり、$T\le0$ なら添字 $k-1$ を $k$ に替えた式が成り立つ。帰納法の仮定 $a_j=b_j$ から主張を得る。$\square$
$(X_1,\ldots,X_n)$ が交換可能なら、$N_n$ と $L_n$ は同じ分布をもつ。
$X^\pi:=(X_{\pi(1)},\ldots,X_{\pi(n)})$ とおく。交換可能性から $P(N_n=k)=P(N(X^\pi)=k)$ がすべての $\pi$ で成り立つので、$\pi$ について平均して
$$
P(N_n=k)=\mathrm E\Bigl[\frac1{n!}\#\{\pi\mid N(X^\pi)=k\}\Bigr]=\mathrm E\Bigl[\frac1{n!}\#\{\pi\mid L(X^\pi)=k\}\Bigr]=P(L_n=k)
$$
である。中央の等号は lem-sa-comb を $x=X(\omega)$ ごとに使った。$\square$
Sparre Andersen はこの等価性を、対称従属(交換可能と同じ意味)の確率変数について、最小値を最後にとる時刻を含めた形で述べている(SA54 Theorem A、p. 197。SA53 p. 264 の Theorem 1 も同じ)。交換可能性は外せない。$X_1=-1$、$X_2=2$(定数)なら $N_2=1$、$L_2=2$ である。
以下、$X_1,X_2,\ldots$ は独立同分布とし、
$$
p_k:=P(S_1>0,\ldots,S_k>0),\qquad q_k:=P(S_1\le0,\ldots,S_k\le0)\qquad(p_0=q_0=1)
$$
とおく。Wiener–Hopf分解(確率論) の記号では $p_k=P(\tau_->k)$、$q_k=P(\tau_+>k)$ である。
$0\le k\le n$ について $P(N_n=k)=P(L_n=k)=p_k\,q_{n-k}$ である。
$L_n=k$ は「$S_k>S_j$($0\le j< k$)」かつ「$S_j\le S_k$($k< j\le n$)」と同じである。前者は $X_1,\ldots,X_k$ で、後者は $X_{k+1},\ldots,X_n$ で決まるので独立である。後者は $X_{k+1}+\cdots+X_{k+i}\le0$($1\le i\le n-k$)と書けるので確率は $q_{n-k}$ である。前者は、$X'_i:=X_{k+1-i}$ の部分和 $S'_i=S_k-S_{k-i}$ を使うと $S'_i>0$($1\le i\le k$)と書け、$(X'_1,\ldots,X'_k)$ は $(X_1,\ldots,X_k)$ と同じ分布をもつので確率は $p_k$ である。$N_n$ については thm-sa-equivalence による。$\square$
$0\le s< 1$ について
$$
\sum_{n\ge0}p_ns^n=\exp\Bigl(\sum_{n\ge1}\frac{s^n}nP(S_n>0)\Bigr),\qquad\sum_{n\ge0}q_ns^n=\exp\Bigl(\sum_{n\ge1}\frac{s^n}nP(S_n\le0)\Bigr)
$$
である。とくに $p_1,\ldots,p_n$、$q_1,\ldots,q_n$ と $N_n$ の分布は、$P(S_1>0),\ldots,P(S_n>0)$ だけで決まる。
$\sum_ns^nP(\tau_->n)=(1-\mathrm E[s^{\tau_-};\tau_-< \infty])/(1-s)$ である($P(\tau_->n)=1-\sum_{j\le n}P(\tau_-=j)$ に $s^n$ を掛けて足す)。Wiener–Hopf分解(確率論) の定理「因子を部分和の分布で表す」で $t=0$ とすると、分子は $\exp(-\sum_n\frac{s^n}nP(S_n\le0))$ であり、$\frac1{1-s}=\exp(\sum_n\frac{s^n}n)$ なので第 1 式を得る。第 2 式は $\tau_+$ について同じ計算をすればよい。後半は、右辺の $s^n$ の係数が $P(S_1>0),\ldots,P(S_n>0)$ の多項式であることと prop-sa-split による。$\square$
この 2 式と prop-sa-split は、Sparre Andersen が示したものである(SA54 Theorem 1 の (3.3)・(3.6)・(3.7)、pp. 197–198)。
$X_1,X_2,\ldots$ を独立同分布とし、すべての $n\ge1$ で $P(S_n>0)=\frac12$ とする。$X_1$ の分布が $0$ について対称で、どの 1 点の確率も $0$ なら、この条件は満たされる。このとき、すべての $n\ge0$ と $0\le k\le n$ について
$$
P(S_1>0,\ldots,S_n>0)=P(S_1\le0,\ldots,S_n\le0)=u_{2n}=\binom{2n}n\frac1{4^n},\qquad P(N_n=k)=P(L_n=k)=u_{2k}\,u_{2n-2k}
$$
である。
条件の確認. $X_1$ が対称なら $-X_i$ たちは $X_i$ たちと同じ同時分布をもつので、$S_n$ と $-S_n$ は同じ分布をもつ。$S_n$ の分布も 1 点の確率が $0$ である。実際、$S_{n-1}$ と $X_n$ は独立なので、Fubiniの定理 により $P(S_n=c)=\mathrm E[P(X_n=c-y)|_{y=S_{n-1}}]=0$ である。よって $P(S_n>0)=P(S_n< 0)$、$P(S_n=0)=0$ で、$P(S_n>0)=\frac12$ である。
母関数. thm-sa-genfun により
$$
\sum_{n\ge0}p_ns^n=\sum_{n\ge0}q_ns^n=\exp\Bigl(\frac12\sum_{n\ge1}\frac{s^n}n\Bigr)=(1-s)^{-1/2}
$$
である。二項級数により $(1-s)^{-1/2}$ の $s^n$ の係数は
$$
(-1)^n\binom{-1/2}n=\frac{\frac12\cdot\frac32\cdots\frac{2n-1}2}{n!}=\frac{1\cdot3\cdots(2n-1)}{2^nn!}=\frac{(2n)!}{2^nn!\cdot2^nn!}=u_{2n}
$$
なので $p_n=q_n=u_{2n}$ である。後半は prop-sa-split による。$\square$
| $n$ | $1$ | $2$ | $3$ | $4$ | $5$ |
|---|---|---|---|---|---|
| $P(S_1>0,\ldots,S_n>0)$ | $\frac12$ | $\frac38$ | $\frac5{16}$ | $\frac{35}{128}$ | $\frac{63}{256}$ |
Stirlingの公式 により $u_{2n}\sim1/\sqrt{\pi n}$ なので、ずっと正である確率は $n^{-1/2}$ の速さでしか減らない。
thm-sa-main の仮定のもとで、$N_n/n$ と $L_n/n$ は、密度 $\frac1{\pi\sqrt{x(1-x)}}$($0< x< 1$)の逆正弦分布に分布収束する。
公平な単純ランダムウォークが $2n$ 歩のうち正の側にいる時間 $\Pi_{2n}$ について、逆正弦法則 の定理「離散の逆正弦法則」は $P(\Pi_{2n}=2k)=u_{2k}u_{2n-2k}$ を与える。thm-sa-main により $N_n$ は $\Pi_{2n}/2$ と同じ分布をもつので、$N_n/n$ は $\Pi_{2n}/2n$ と同じ分布をもち、同記事の定理「逆正弦分布への収束」により主張を得る。$L_n$ は $N_n$ と同じ分布をもつ。$\square$
正の部分和の割合は $\frac12$ に集まらず、$0$ や $1$ の近くになりやすい。しかもこの分布は、平均や分散が存在しない Cauchy 分布でも変わらない。
thm-sa-genfun から、$P(S_n>0)$ が $n$ によらない一定の値 $a$($0< a< 1$)なら、$\sum p_ns^n=(1-s)^{-a}$、$\sum q_ns^n=(1-s)^{a-1}$ となり、
$$
p_n=(-1)^n\binom{-a}n,\qquad q_n=(-1)^n\binom{a-1}n,\qquad P(N_n=m)=p_m\,q_{n-m}
$$
である(SA54 Theorem 2 の (4.1) と、その証明の (4.10)・(4.11)、pp. 200–201)。$a=\frac12$ が thm-sa-main である。
$0< a< 1$、$c:=\cot(\pi a)$ とし、$C_1,C_2,\ldots$ を独立な標準 Cauchy分布(密度 $\frac1{\pi(1+x^2)}$)に従う確率変数として $X_i:=C_i-c$ とおく。標準 Cauchy 分布の特性関数は $e^{-\lvert t\rvert}$(特性関数(確率論) の例「Cauchy 分布の特性関数」)なので、$(C_1+\cdots+C_n)/n$ の特性関数は $(e^{-\lvert t\rvert/n})^n=e^{-\lvert t\rvert}$ で、$S_n/n$ は $C_1-c$ と同じ分布をもつ。よって
$$
P(S_n>0)=P(C_1>c)=\frac12-\frac1\pi\arctan(\cot\pi a)=\frac12-\Bigl(\frac12-a\Bigr)=a
$$
である($0< \pi a< \pi$ で $\arctan(\cot\pi a)=\frac\pi2-\pi a$)。たとえば $a=\frac13$ では $p_1=\frac13$、$p_2=\frac{a(a+1)}2=\frac29$ である。この例は SA54 の Theorem 2 のあとの注意(p. 200)にある。
$X_1$ が対称で 1 点の確率が $0$ なら、$\varepsilon_i:=\operatorname{sign}X_i$ と $\lvert X_i\rvert$ は独立で、$\varepsilon_i$ は $\pm1$ を確率 $\frac12$ ずつとる($B\subset(0,\infty)$ について $P(X_i\in B)=P(X_i\in-B)=\frac12P(\lvert X_i\rvert\in B)$ による)。$S_1>0$、$S_2>0$ は、$\varepsilon_1=\varepsilon_2=1$ か、$\varepsilon_1=1$、$\varepsilon_2=-1$、$\lvert X_1\rvert>\lvert X_2\rvert$ かのどちらかである。$\lvert X_1\rvert$ と $\lvert X_2\rvert$ は独立同分布で一致する確率は $0$ なので $P(\lvert X_1\rvert>\lvert X_2\rvert)=\frac12$ で、
$$
p_2=\frac14+\frac14\cdot\frac12=\frac38=u_4
$$
である。$[-1,1]$ の一様分布で $p_3$ を積分で計算しても、正規分布で 3 変数の正規分布の象限の確率として計算しても、$\frac5{16}=u_6$ になる。
公平な単純ランダムウォーク($\pm1$ を確率 $\frac12$ ずつ)は対称だが 1 点の確率が正なので、thm-sa-main の仮定を満たさない。実際 $p_2=P(X_1=X_2=1)=\frac14$ である。一方、逆正弦法則 で使う「正の側にいる時間」$\Pi_{2n}$ は、原点に戻る瞬間の扱いを線分で数えることで同じ分布 $u_{2k}u_{2n-2k}$ を得ている。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 対称性 | $X_i$ が平均 $1$、分散 $1$ の正規分布 | thm-sa-main:$p_1=\Phi(1)\approx0.8413\ne\frac12=u_2$ |
| 1 点の確率が $0$ | 公平な単純ランダムウォーク | thm-sa-main:$p_2=\frac14\ne\frac38=u_4$ |
| 独立性 | $X_n=X_1$(すべての $n$)、$X_1$ は標準正規分布 | thm-sa-main:$p_2=\frac12\ne\frac38$ |
| 交換可能性 | $X_1=-1$、$X_2=2$(定数) | thm-sa-equivalence:$N_2=1$ だが $L_2=2$ |
1 行目:$p_1=P(X_1>0)=P(Z>-1)=\Phi(1)$($Z$ は標準正規変数、$\Phi$ はその分布関数)である。2 行目:$S_1>0$ は $X_1=1$ で、そのとき $S_2>0$ は $X_2=1$ である。3 行目:$S_k=kX_1$ なので $S_1>0,S_2>0$ は $X_1>0$ と同じで確率 $\frac12$ である。この列は交換可能なので thm-sa-equivalence は成り立ち、独立性を使うのは prop-sa-split の段である。4 行目:$S_1=-1$、$S_2=1$ で、正の部分和は $S_2$ だけ、最大値 $1$ は時刻 $2$ で初めてとられる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する