Glivenko–Cantelliの定理(Glivenko–Cantelli theorem)とは、独立同分布な実数値の確率変数列の経験分布関数が、真の分布関数に確率 $1$ で実数全体にわたって一様に収束するという定理である。分布関数の連続性は仮定しない。分位点の格子と Hoeffding の不等式から指数型の確率の上界とともに示せて、独立だが同分布でない列や定常エルゴード列にも広がる。半直線を集合族に広げると、可測性の条件のもとで、分布によらない一様な収束は VC 次元の有限性と同値である。
前提知識: 累積分布関数, 強大数の法則, Borel–Cantelliの補題, Hoeffdingの不等式
Glivenko–Cantelli の定理(Glivenko–Cantelli theorem)とは、独立同分布な実数値の確率変数列から作った経験分布関数が、真の分布関数に確率 $1$ で実数全体にわたって一様に収束するという定理である。分位点 や分布の形を標本から推定できることの出発点である。
各点 $x$ での収束は 強大数の法則 からすぐ分かる。問題は、非可算個の $x$ について同時に、しかも一様に近づくことである。鍵は分布関数が単調であることで、有限個の点での収束から全体の収束が出る。
標準の証明は Kolmogorov–Smirnov検定 の定理「Glivenko–Cantelliの定理」と 経験過程 の系「分布関数の一様収束(Glivenko–Cantelli の定理)」にある。どちらも強大数の法則を使う。この記事は別の道をとり、有限個の分位点に当てる確率の不等式から、確率の上界つきで同じ結論を出す。さらに、仮定をどこまで弱められるかを 3 つの方向で調べる。
| 主張 | 内容 |
|---|---|
| lem-gc-grid | 分位点の格子の上で近ければ全体で近い(確率を使わない補題) |
| thm-gc-exp | 同分布を仮定しない指数型の不等式 |
| thm-gc-main | Glivenko–Cantelli の定理 |
| prop-gc-quantile | 標本分位点の一致性 |
| thm-gc-ergodic | 独立性をエルゴード性に弱めてよい |
| thm-gc-vc | 半直線を集合族に広げると、分布によらない一様性は VC 次元の有限性と同値 |
$X_1,X_2,\dots$ を実数値の確率変数とする。$F_n(x)=\frac1n\#\{i\le n\mid X_i\le x\}$ を 経験分布関数 という。これは標本の各点に質量 $1/n$ を置いた分布の 累積分布関数 で、右連続な階段関数である。関数 $G$ の左極限を $G(x-)=\lim_{y\uparrow x}G(y)$ と書く。分布関数 $F$ に対して
$$
D_n=\sup_{x\in\mathbb{R}}\lvert F_n(x)-F(x)\rvert
$$
とおく。$F_n-F$ は右連続なので、$D_n$ は有理数 $x$ での値の上限に等しく、確率変数である。
$F$ が連続なら、$F_n-F$ の上限は標本点の前後で達するので、順序統計量 $X_{(1)}\le\dots\le X_{(n)}$ を使って
$$
D_n=\max_{1\le i\le n}\max\Bigl\{\frac in-F(X_{(i)}),\ F(X_{(i)})-\frac{i-1}n\Bigr\}
$$
と計算できる。$F(x)=x$($[0,1]$ の一様分布)で標本が $0.1,\ 0.35,\ 0.4,\ 0.7,\ 0.95$ のとき、$\frac in-X_{(i)}$ は $0.1,\ 0.05,\ 0.2,\ 0.1,\ 0.05$、$X_{(i)}-\frac{i-1}n$ は $0.1,\ 0.15,\ 0,\ 0.1,\ 0.15$ なので、$D_5=0.2$ で、$x=0.4$ で達する。
分布関数 $G$ の分位点関数を $Q_G(p)=\inf\{x\mid G(x)\ge p\}$($0< p< 1$)とする(分位点 の定義「分位点関数」)。$x=Q_G(p)$ について $G(x-)\le p\le G(x)$ である。
$G$ を分布関数、$H\colon\mathbb{R}\to[0,1]$ を非減少な関数とする。$k\ge1$、$t\ge0$ とし、$x_j=Q_G(j/k)$($1\le j\le k-1$)とおく。すべての $j$ で
$$
\lvert H(x_j)-G(x_j)\rvert\le t,\qquad\lvert H(x_j-)-G(x_j-)\rvert\le t
$$
なら、$\sup_{x}\lvert H(x)-G(x)\rvert\le t+\frac1k$ である。
$k=1$ なら $\lvert H-G\rvert\le1$ で明らかなので $k\ge2$ とする。$x_0=-\infty$、$x_k=+\infty$ とおく。任意の $x$ はある $j$ で $x_{j-1}\le x< x_j$ をみたす($j=1$ では $x< x_1$)。
上から($j\le k-1$)。 $H(x)\le H(x_j-)\le G(x_j-)+t\le\frac jk+t$ である。$j\ge2$ なら $G(x)\ge G(x_{j-1})\ge\frac{j-1}k$、$j=1$ なら $G(x)\ge0=\frac{j-1}k$ なので、$H(x)\le G(x)+\frac1k+t$ である。$j=k$ なら $H(x)\le1$ と $G(x)\ge\frac{k-1}k$ から同じ不等式を得る。
下から($j\ge2$)。 $H(x)\ge H(x_{j-1})\ge G(x_{j-1})-t\ge\frac{j-1}k-t$ である。$j\le k-1$ なら $G(x)\le G(x_j-)\le\frac jk$、$j=k$ なら $G(x)\le1=\frac jk$ なので、$H(x)\ge G(x)-\frac1k-t$ である。$j=1$ なら $G(x)\le G(x_1-)\le\frac1k$ と $H(x)\ge0$ から同じ不等式を得る。$\square$
左極限の条件が要るのは $G$ が跳ぶときである。点 $x_j$ の左と右で $G$ が大きく変わっても、両側で $H$ が追随していれば差は開かない。
補題は thm-gc-main で $H=F_n$、$G=F$ とする形で使うが、$H$ は確率と無関係である。
$X_1,\dots,X_n$ を独立とし、$X_i$ の分布関数を $F_i$、$\bar F_n=\frac1n\sum_{i\le n}F_i$ とする。$D_n'=\sup_x\lvert F_n(x)-\bar F_n(x)\rvert$ について、整数 $k\ge1$、$t>0$ で
$$
\Pr\Bigl(D_n'>t+\frac1k\Bigr)\le4(k-1)e^{-2nt^2}
$$
である。とくに $0< \varepsilon\le1$ で $\Pr(D_n'>\varepsilon)\le\frac8\varepsilon e^{-n\varepsilon^2/2}$ である。
$\bar F_n$ は分布関数なので、$x_j=Q_{\bar F_n}(j/k)$ とおく。固定した $x$ について、$\mathbf{1}\{X_i\le x\}$ は独立で値は $[0,1]$ にあり、和の平均は $n\bar F_n(x)$ である。Hoeffdingの不等式 の定理「Hoeffding の不等式」($D=n$ の場合)から
$$
\Pr(\lvert F_n(x)-\bar F_n(x)\rvert\ge t)\le2e^{-2n^2t^2/n}=2e^{-2nt^2}
$$
である。$\mathbf{1}\{X_i< x\}$ についても同様で、平均は $n\bar F_n(x-)$、$\frac1n\sum_i\mathbf{1}\{X_i< x\}=F_n(x-)$ である。$j=1,\dots,k-1$ の両方の事象を合わせると、確率 $4(k-1)e^{-2nt^2}$ 以上を除いて lem-gc-grid の仮定が成り立つので、$D_n'\le t+\frac1k$ である。
後半は $t=\varepsilon/2$、$k=\lceil2/\varepsilon\rceil$ とする。$\frac1k\le\frac\varepsilon2$、$k-1< \frac2\varepsilon$、$2nt^2=\frac{n\varepsilon^2}2$ である。$\square$
$X_1,X_2,\dots$ が独立で同じ分布関数 $F$ に従うとき、確率 $1$ で $D_n\to0$($n\to\infty$)である。$F$ の連続性は仮定しない。
同分布のとき $\bar F_n=F$ である。$0< \varepsilon\le1$ を固定すると、thm-gc-exp から $\sum_n\Pr(D_n>\varepsilon)\le\frac8\varepsilon\sum_ne^{-n\varepsilon^2/2}< \infty$ である。Borel–Cantelliの補題 により、確率 $1$ で十分大きいすべての $n$ で $D_n\le\varepsilon$ である。$\varepsilon=1/m$ の可算個の事象の共通部分をとると $D_n\to0$ を得る。$\square$
定理そのものは Dur19 Theorem 2.4.9(p. 79)にある。この証明は強大数の法則を使わないので、$n$ ごとに標本の組が変わる三角配列でも同じ結論が出る。独立で分布が異なるときも、同じ議論で確率 $1$ で $\sup_x\lvert F_n(x)-\bar F_n(x)\rvert\to0$ である。
thm-gc-exp の設定で、確率 $1$ で十分大きいすべての $n$ について
$$
D_n'\le\sqrt{\frac{\log n}n}+\frac1{\sqrt n}
$$
である。
$k=\lceil\sqrt n\rceil$、$t=\sqrt{\log n/n}$ とすると、$\frac1k\le\frac1{\sqrt n}$、$k-1< \sqrt n$、$e^{-2nt^2}=n^{-2}$ なので、確率の上界は $4n^{-3/2}$ で総和可能である。Borel–Cantelli の補題で結論を得る。$\square$
$\lfloor\log_2i\rfloor$ が偶数の $i$ で $X_i\sim N(0,1)$、奇数の $i$ で $X_i\sim N(3,1)$ とし、独立とする。$N(0,1)$ に従うものの割合は、$n=2^{2m}-1$ でちょうど $\frac13$ で、$n=2^{2m+1}-1$ で $\frac23$ に近づく。よって $\bar F_n(1.5)$ は収束せず、上極限と下極限の差は $\frac13(2\Phi(1.5)-1)\approx0.2888$ である($\Phi$ は標準正規分布の分布関数)。$F_n$ も収束しない。しかし $\sup_x\lvert F_n(x)-\bar F_n(x)\rvert\to0$ である。
単調性の役割。 各点の収束だけでは一様収束は出ない。$F_n$ と $F$ が単調であること、言いかえると半直線の族が小さいことを使っている。単調でない族では同じ主張は偽である(thm-gc-vc のあとの表)。
thm-gc-exp の定数は粗い。比較のために、この記事で証明しない 2 つの結果を述べる。
期待値の上界。 独立同分布なら、$F$ によらない定数 $C$ で $E[D_n]\le C/\sqrt n$ である(Ver18 Theorem 8.3.26、p. 213)。cor-gc-rate の $\sqrt{\log n}$ は、この形では取り除ける。
Massart の不等式。 独立同分布なら、すべての $F$、$n$、$\varepsilon>0$ で
$$
\Pr(D_n>\varepsilon)\le2e^{-2n\varepsilon^2}
$$
である(Dvoretzky–Kiefer–Wolfowitz の不等式の定数を最良にしたもの、Mas90)。
$n=1000$ とする。
| $\varepsilon$ | thm-gc-exp の上界 | Massart の不等式の上界 |
|---|---|---|
| $0.05$ | $160e^{-1.25}\approx45.8$(意味がない) | $2e^{-5}\approx0.0135$ |
| $0.1$ | $80e^{-5}\approx0.539$ | $2e^{-20}\approx4.1\times10^{-9}$ |
Massart の不等式で右辺を $0.05$ にすると $\varepsilon=\sqrt{\log40/2000}\approx0.04295$ である。すなわち、確率 $0.95$ 以上で $F$ 全体が $F_n$ の幅 $\pm0.043$ の帯に入る。これは Kolmogorov–Smirnov検定 の定理「Kolmogorov の極限定理」の 5% 点から得る $1.3581/\sqrt{1000}\approx0.04295$ とほぼ一致する。極限の裾の級数 $2\sum_{j\ge1}(-1)^{j-1}e^{-2j^2\lambda^2}$ の第 1 項が $2e^{-2\lambda^2}$ だからである。
$F$ が連続のときの $\sqrt nD_n$ の分布の極限と、それが $F$ によらないことは Kolmogorov–Smirnov検定、過程としての極限は Donskerの定理 で扱う。Glivenko–Cantelli の定理が大数の法則の段階、これらは中心極限定理の段階である。
$Q_n(p)=\inf\{x\mid F_n(x)\ge p\}$ を 標本分位点($p=\frac12$ のとき中央値の一つ)とする。
thm-gc-main の設定で $0< p< 1$、$q=Q_F(p)$ とする。すべての $\delta>0$ で $F(q+\delta)>p$ なら、確率 $1$ で $Q_n(p)\to q$ である。
$\delta>0$ とする。$q$ の定義から $F(q-\delta)< p$ である。$\eta=\min\{p-F(q-\delta),\ F(q+\delta)-p\}>0$ とおく。$D_n< \eta$ なら、$F_n(q-\delta)< F(q-\delta)+\eta\le p$ より $Q_n(p)\ge q-\delta$ であり、$F_n(q+\delta)>F(q+\delta)-\eta\ge p$ より $Q_n(p)\le q+\delta$ である。$D_n\to0$ から結論を得る。$\square$
$F$ が $q$ の右で平らなときは一致性が成り立たない(下の反例の表)。一様収束の利点は、$p$ を固定しないで済むことである。$F$ が連続で狭義増加なら、$\delta$ を固定したとき $[a,b]\subset(0,1)$ の上で $\eta$ の下限が正なので、$[a,b]$ の上で一様に $Q_n\to Q_F$ である。
thm-gc-exp は独立性を集中不等式で使うが、結論だけなら、格子点での大数の法則があれば足りる。
$(X_k)_{k\in\mathbb{Z}}$ を実数値のエルゴード的な強定常列とし(定常過程 の定義「エルゴード的な定常列」)、$F$ を $X_0$ の分布関数とする。このとき、確率 $1$ で $\sup_x\lvert F_n(x)-F(x)\rvert\to0$ である。
固定した $a\in\mathbb{R}$ について、エルゴード定理 の定理「Birkhoff の個別エルゴード定理」を $\mathbf{1}\{x_1\le a\}$、$\mathbf{1}\{x_1< a\}$ に当てると、確率 $1$ で $F_n(a)\to F(a)$、$F_n(a-)\to F(a-)$ である。整数 $k\ge1$ と $x_j=Q_F(j/k)$ の全体は可算個なので、確率 $1$ の事象の上で、これらのすべての点で収束が成り立つ。その上で $k$ を固定すると、$n$ が十分大きければ lem-gc-grid が $t=1/k$ で使えて、$\sup_x\lvert F_n(x)-F(x)\rvert\le2/k$ である。$k$ は任意なので結論を得る。$\square$
この証明は収束そのものだけを与え、thm-gc-exp のような速さの評価は与えない。
1.フリップ。 $X_0$ を値 $0,1$ の公平な硬貨とし、$X_{k+1}=1-X_k$ とする。独立でなく混合的でもないが、標本は 2 本($\dots0101\dots$ とそのずらし)で、$\theta$ がそれらを入れ替えるので不変事象は確率 $0$ か $1$ である。$F_n(0)\to\frac12$ である。
2.無理数回転。 $U$ を $[0,1)$ の一様分布、$\alpha$ を無理数とし、$X_k=k\alpha+U\bmod1$ とする。これはエルゴード的である(Dur19 Example 6.1.7、pp. 333–334)。$F(x)=x$ で、$X_k$ の間に強い依存があるのに結論が成り立つ。$\alpha=\sqrt2-1$、$U=0.3$ の標本では $D_{100}\approx0.0203$、$D_{10000}\approx0.000265$ で、$1/\sqrt n$ よりずっと小さい。依存が収束を遅くするとは限らない。
3.Markov 連鎖。 既約で正再帰な連鎖を定常分布から出発させた列はエルゴード的である(Dur19 Example 6.1.6、p. 333)。実数値の状態をもつなら thm-gc-ergodic が当てはまる。
$\xi$ を値 $0,1$ の公平な硬貨、$(Y_k)$ を $\xi$ と独立な $N(0,1)$ の独立列とし、$X_k=Y_k+3\xi$ とおく。この列は定常で交換可能だが(de Finettiの定理 の型の混合)、エルゴード的でない。$\xi$ を条件にして thm-gc-main を当てると、確率 $1$ で $F_n$ は $\Phi(\,\cdot\,-3\xi)$ に一様収束する。これは周辺の分布関数 $F=\frac12(\Phi+\Phi(\,\cdot\,-3))$ ではなく、
$$
\sup_x\lvert F_n(x)-F(x)\rvert\to\frac12(2\Phi(1.5)-1)\approx0.4332
$$
である。極限が確率的になるので、標本 1 本から $F$ は読み取れない。
経験過程 の記号を使う。$(\mathcal{X},\mathcal{A})$ を可測空間、$P$ をその上の確率測度、$X_1,X_2,\dots$ を $P$ に従う独立な列、$P_n=\frac1n\sum_{i\le n}\delta_{X_i}$ とする。$F_n(x)=P_n((-\infty,x])$ なので、thm-gc-main は半直線の族についての一様な大数の法則である。半直線の族を一般の集合族 $\mathcal{C}\subset\mathcal{A}$ に広げたものが 経験過程 の定義「Glivenko–Cantelli 族」である。
$\mathcal{C}$ が 一様 Glivenko–Cantelli 族 であるとは、すべての $\varepsilon>0$ で
$$
\sup_P\Pr\Bigl(\sup_{C\in\mathcal{C}}\lvert P_n(C)-P(C)\rvert>\varepsilon\Bigr)\to0\qquad(n\to\infty)
$$
となることをいう。上限はすべての確率測度 $P$ にわたる。
上限の可測性のため、$\mathcal{C}$ は可算であるか、可算な部分族があって各 $\mathbf{1}_C$ がその元の指示関数の列の各点収束の極限であるとする(半直線の族は有理数の端点の族の極限なので、これをみたす)。
上の可測性の条件のもとで、$\mathcal{C}$ が一様 Glivenko–Cantelli 族であることと、$\mathcal{C}$ の VC次元 が有限であることは同値である。
有限なら。 次元 $d\ge1$ なら、経験過程 の定理「VC 族の一様な大数の法則」により、$n\ge d$、$0< \delta< 1$ のとき、確率 $1-\delta$ 以上で
$$
\sup_{C\in\mathcal{C}}\lvert P_n(C)-P(C)\rvert\le2\sqrt{\frac{2d\log(en/d)}n}+\sqrt{\frac{\log(2/\delta)}{2n}}
$$
である。右辺は $P$ によらないので、$\varepsilon,\delta$ に対して $n$ を大きくとればよい。$d=0$ なら $\mathcal{C}$ の元は高々 1 個で、Hoeffdingの不等式 で足りる。
無限なら。 $n$ を固定する。VC 次元が無限なので、$2n$ 点の集合 $A$ で $\mathcal{C}$ に打ち砕かれるものがある(VC次元 の定義「打ち砕くことと VC 次元」)。$P$ を $A$ の上の一様分布とする。標本 $X_1,\dots,X_n$ の値の集合を $S\subset A$ とすると、$\lvert S\rvert\le n$ で、打ち砕かれることから $C\cap A=S$ となる $C\in\mathcal{C}$ がある。このとき $P_n(C)=1$、$P(C)=\lvert S\rvert/(2n)\le\frac12$ なので、$\sup_{C}\lvert P_n(C)-P(C)\rvert\ge\frac12$ が必ず成り立つ。よって $\varepsilon=\frac14$ で定義の式の上限はどの $n$ でも $1$ である。$\square$
後半は Ver18 Exercise 8.3.29(p. 214)の主張にあたる。前半と後半で、分布によらない学習可能性の特徴づけ(統計的学習理論、PAC学習)と同じ形が出ている。Glivenko–Cantelli 族の名前は、この定理の名に由来する(SSBD14 §4.4、p. 58)。
$\mathbb{R}^d$ の 左下の直交象限 $\prod_{i}(-\infty,a_i]$ の族の VC 次元は $d$ である。
分布に依存する形は別物である。 特定の $P$ だけなら、VC 次元が無限でも $P$-Glivenko–Cantelli でありうる。
$P$ が可算集合 $S$ の上の確率測度なら、$S$ の全部分集合の族は $P$-Glivenko–Cantelli 族である。実際、確率 $1$ で
$$
\sup_{A\subset S}\lvert P_n(A)-P(A)\rvert=\frac12\sum_{s\in S}\lvert P_n\{s\}-P\{s\}\rvert\to0
$$
である。
等号は $A=\{s\mid P_n\{s\}>P\{s\}\}$ で上限が達することと、$\sum_s(P_n\{s\}-P\{s\})=0$ による。$\delta>0$ に対して有限集合 $K\subset S$ を $P(S\setminus K)< \delta$ ととる。強大数の法則から確率 $1$ で $s\in K$ の $P_n\{s\}$ が $P\{s\}$ に収束し、$\sum_{s\notin K}P_n\{s\}=1-\sum_{s\in K}P_n\{s\}\to P(S\setminus K)$ である。よって和の上極限は $2\delta$ 以下である。$\square$
一方、$P$ が原子をもたなければ、有限集合の族(VC 次元は無限)は $P$-Glivenko–Cantelli 族でない。$C=\{X_1,\dots,X_n\}$ で $P_n(C)=1$、$P(C)=0$ だからである。同じ族でも分布によって答えが変わる。
| 族 | VC 次元 | $P$ 離散 | $P$ 原子なし | 一様 |
|---|---|---|---|---|
| $\mathbb{R}$ の半直線 | $1$ | はい | はい | はい |
| $\mathbb{R}^d$ の左下の直交象限 | $d$ | はい | はい | はい |
| $\mathbb{R}$ の有限部分集合 | 無限 | はい | いいえ | いいえ |
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-gc-main の独立性 | $X_i=X_1$($F$ は連続) | $F_n$ は $X_1$ で跳ぶ関数のままで、$D_n\ge\frac12$ |
| thm-gc-main の同分布 | ex-gc-blocks | 単一の $F$ がなく、$F_n$ は収束しない($\bar F_n$ との差は $0$ に近づく) |
| thm-gc-main の族が半直線であること | 有限集合の族($P$ 原子なし) | 上限がどの $n$ でも $1$ |
| thm-gc-ergodic のエルゴード性 | ex-gc-nonergodic | $F$ からの距離が約 $0.4332$ に収束する |
| prop-gc-quantile の $F(q+\delta)>p$ | 値 $\pm1$ の公平な硬貨、$p=\frac12$ | $q=-1$ だが、$-1$ の個数が半数未満になる $n$ が確率 $1$ で無限個あり、$Q_n(\frac12)=1$ と $-1$ を振動する |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する