Теорема Гливенко–Кантелли

Теория вероятности

Левая диаграмма иллюстрирует теорему Гливенко–Кантелли для равномерных распределений. Правая диаграмма иллюстрирует теорему Донскера–Скорохода–Колмогорова.

Та же диаграмма для нормальных распределений

В теории вероятностей теорема Гливенко –Кантелли (иногда называемая Основной теоремой статистики ), названная в честь Валерия Ивановича Гливенко и Франческо Паоло Кантелли , описывает асимптотическое поведение эмпирической функции распределения по мере роста числа независимых и одинаково распределенных наблюдений. ^[1] В частности, эмпирическая функция распределения сходится равномерно к истинной функции распределения почти наверняка .

Равномерная сходимость более общих эмпирических мер становится важным свойством классов функций или множеств Гливенко–Кантелли . ^[2] Классы Гливенко–Кантелли возникают в теории Вапника–Червоненкиса с приложениями к машинному обучению . Приложения можно найти в эконометрике, использующей М-оценщики .

Заявление

Предположим, что являются независимыми и одинаково распределенными случайными величинами с общей кумулятивной функцией распределения . Эмпирическая функция распределения для определяется как ${\displaystyle X_{1},X_{2},\dots }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle F(x)}$ ${\displaystyle X_{1},\dots ,X_{n}}$

${\displaystyle F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}I_{[X_{i},\infty )}(x)={\frac {1}{n}}\ {\bigl |}\left\{\ i\ \mid X_{i}\leq x,\ 1\leq i\leq n\right\}{\bigr |}}$

где — индикаторная функция множества Для каждого (фиксированного) — последовательность случайных величин, которая сходится к почти наверняка по усиленному закону больших чисел . Гливенко и Кантелли усилили этот результат, доказав равномерную сходимость к ${\displaystyle I_{C}}$ ${\displaystyle \ C~.}$ ${\displaystyle \ x\ ,}$ ${\displaystyle \ F_{n}(x)\ }$ ${\displaystyle F(x)}$ ${\displaystyle \ F_{n}\ }$ ${\displaystyle \ F~.}$

Теорема

${\displaystyle \|F_{n}-F\|_{\infty }=\sup _{x\in \mathbb {R} }{\bigl |}F_{n}(x)-F(x){\bigr |}\longrightarrow 0}$почти наверняка. ^{[3] (стр. 265)}

Эта теорема была сформулирована Валерием Гливенко ^[4] и Франческо Кантелли [ ^5] в 1933 году.

Замечания

• Если — стационарный эргодический процесс , то сходится почти наверняка к Теорема Гливенко–Кантелли дает более сильный режим сходимости, чем этот в случае независимого тождественного распределения. ${\displaystyle \ X_{n}\ }$ ${\displaystyle F_{n}(x)}$ ${\displaystyle \ F(x)=\operatorname {\mathbb {E} } {\bigl [}1_{X_{1}\leq x}{\bigr ]}~.}$
• Еще более сильный результат равномерной сходимости для эмпирической функции распределения доступен в форме расширенного типа закона повторного логарифма . ^{[3] (стр. 268)} См. асимптотические свойства эмпирической функции распределения для этого и связанных с ним результатов.

Доказательство

Для простоты рассмотрим случай непрерывной случайной величины . Зафиксируем такое, что для . Теперь для всех существует такое, что . ${\displaystyle X}$ ${\displaystyle -\infty =x_{0}<x_{1}<\cdots <x_{m-1}<x_{m}=\infty }$ ${\displaystyle F(x_{j})-F(x_{j-1})={\frac {1}{m}}}$ ${\displaystyle j=1,\dots ,m}$ ${\displaystyle x\in \mathbb {R} }$ ${\displaystyle j\in \{1,\dots ,m\}}$ ${\displaystyle x\in [x_{j-1},x_{j}]}$

${\displaystyle {\begin{aligned}F_{n}(x)-F(x)&\leq F_{n}(x_{j})-F(x_{j-1})=F_{n}(x_{j})-F(x_{j})+{\frac {1}{m}},\\F_{n}(x)-F(x)&\geq F_{n}(x_{j-1})-F(x_{j})=F_{n}(x_{j-1})-F(x_{j-1})-{\frac {1}{m}}.\end{aligned}}}$

Поэтому,

${\displaystyle \|F_{n}-F\|_{\infty }=\sup _{x\in \mathbb {R} }|F_{n}(x)-F(x)|\leq \max _{j\in \{1,\dots ,m\}}|F_{n}(x_{j})-F(x_{j})|+{\frac {1}{m}}.}$

Так как по сильному закону больших чисел мы можем гарантировать, что для любого положительного и любого целого числа такого, что , мы можем найти такое, что для всех , мы имеем . В сочетании с приведенным выше результатом это далее подразумевает, что , что является определением почти наверняка сходимости. ${\textstyle \max _{j\in \{1,\dots ,m\}}|F_{n}(x_{j})-F(x_{j})|\to 0{\text{ a.s.}}}$ ${\textstyle \varepsilon }$ ${\textstyle m}$ ${\textstyle 1/m<\varepsilon }$ ${\textstyle N}$ ${\displaystyle n\geq N}$ ${\textstyle \max _{j\in \{1,\dots ,m\}}|F_{n}(x_{j})-F(x_{j})|\leq \varepsilon -1/m{\text{ a.s.}}}$ ${\textstyle \|F_{n}-F\|_{\infty }\leq \varepsilon {\text{ a.s.}}}$

Эмпирические измерения

Можно обобщить эмпирическую функцию распределения , заменив множество произвольным множеством C из класса множеств, чтобы получить эмпирическую меру , индексированную множествами ${\displaystyle (-\infty ,x]}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C\in {\mathcal {C}}.}$

${\displaystyle P_{n}(C)={\frac {1}{n}}\sum _{i=1}^{n}I_{C}(X_{i}),C\in {\mathcal {C}}}$

Где - индикаторная функция каждого набора . ${\displaystyle I_{C}(x)}$ ${\displaystyle C}$

Дальнейшее обобщение — это отображение, индуцированное измеримыми действительными функциями f , которое задается формулой ${\displaystyle P_{n}}$

${\displaystyle f\mapsto P_{n}f=\int _{S}f\,dP_{n}={\frac {1}{n}}\sum _{i=1}^{n}f(X_{i}),f\in {\mathcal {F}}.}$

Тогда важным свойством этих классов становится то, выполняется ли усиленный закон больших чисел равномерно на или . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {C}}}$

Класс Гливенко–Кантелли

Рассмотрим множество с сигма-алгеброй борелевских подмножеств A и вероятностной мерой для класса подмножеств, ${\displaystyle \ {\mathcal {S}}\ }$ ${\displaystyle \ \mathbb {P} ~.}$

${\displaystyle {\mathcal {C}}\subset {\bigl \{}C:C{\text{ is measurable subset of }}{\mathcal {S}}{\bigr \}}}$

и класс функций

${\displaystyle {\mathcal {F}}\subset {\bigl \{}f:{\mathcal {S}}\to \mathbb {R} ,f{\mbox{ is measurable}}\ {\bigr \}}}$

определить случайные величины

${\displaystyle {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}=\sup _{C\in {\mathcal {C}}}{\bigl |}\mathbb {P} _{n}(C)-\mathbb {P} (C){\bigr |}}$

${\displaystyle {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {F}}=\sup _{f\in {\mathcal {F}}}{\bigl |}\mathbb {P} _{n}f-\mathbb {P} f{\bigr |}}$

где — эмпирическая мера, — соответствующая карта, а ${\displaystyle \ \mathbb {P} _{n}(C)\ }$ ${\displaystyle \ \mathbb {P} _{n}f\ }$

${\displaystyle \ \mathbb {P} f=\int _{\mathcal {S}}f\ \mathrm {d} \mathbb {P} \ ,}$при условии, что он существует.

Определения

• Класс называется классом Гливенко–Кантелли (или классом GC , или иногда сильным классом GC ) относительно вероятностной меры P, если ${\displaystyle \ {\mathcal {C}}\ }$

${\displaystyle \ {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}\to 0\ }$почти наверняка как ${\displaystyle \ n\to \infty ~.}$

• Класс является слабым классом Гливенко-Кантелли относительно P , если он вместо этого удовлетворяет более слабому условию ${\displaystyle \ {\mathcal {C}}\ }$

${\displaystyle \ {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}\to 0\ }$по вероятности как ${\displaystyle \ n\to \infty ~.}$

• Класс называется универсальным классом Гливенко–Кантелли, если он является классом GC относительно любой вероятностной меры на . ${\displaystyle \mathbb {P} }$ ${\displaystyle ({\mathcal {S}},A)}$

• Класс является слабо однородным классом Гливенко–Кантелли, если сходимость происходит равномерно по всем вероятностным мерам на : для каждого , ${\displaystyle \mathbb {P} }$ ${\displaystyle ({\mathcal {S}},A)}$ ${\displaystyle \varepsilon >0}$

${\displaystyle \ \sup _{\mathbb {P} \in \mathbb {P} ({\mathcal {S}},A)}\Pr \left({\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}>\varepsilon \right)\to 0\ }$как ${\displaystyle \ n\to \infty ~.}$

• Класс является (сильным) однородным классом Гливенко-Кантелли, если он удовлетворяет более сильному условию, что для любого , ${\displaystyle \varepsilon >0}$

${\displaystyle \ \sup _{\mathbb {P} \in \mathbb {P} ({\mathcal {S}},A)}\Pr \left(\sup _{m\geq n}{\bigl \|}\mathbb {P} _{m}-\mathbb {P} {\bigr \|}_{\mathcal {C}}>\varepsilon \right)\to 0\ }$как ${\displaystyle \ n\to \infty ~.}$

Аналогично определяются классы функций Гливенко–Кантелли (а также их равномерные и универсальные формы), заменяя все экземпляры на . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {F}}}$

Слабые и сильные версии различных свойств Гливенко-Кантелли часто совпадают при определенных условиях регулярности. Следующее определение обычно появляется в таких условиях регулярности:

• Класс функций является допустимым по образу Суслина, если существует пространство Суслина и сюръекция, такие что отображение измеримо . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \Omega }$ ${\displaystyle T:\Omega \rightarrow {\mathcal {F}}}$ ${\displaystyle (x,y)\mapsto [T(y)](x)}$ ${\displaystyle {\mathcal {X}}\times \Omega }$

• Класс измеримых множеств является допустимым по образу Суслина, если класс функций является допустимым по образу Суслина, где обозначает индикаторную функцию для множества . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \{\mathbf {1} _{C}\mid C\in {\mathcal {C}}\}}$ ${\displaystyle \mathbf {1} _{C}}$ ${\displaystyle C}$

Теоремы

Следующие две теоремы дают достаточные условия для того, чтобы слабая и сильная версии свойства Гливенко-Кантелли были эквивалентны.

Теорема ( Талагранд , 1987) ^[6]

Пусть будет классом функций, который интегрируем , и определите . Тогда следующие условия эквивалентны: ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \mathbb {P} }$ ${\displaystyle {\mathcal {F}}_{0}=\{f-\mathbb {P} f\mid f\in {\mathcal {F}}\}}$

• ${\displaystyle {\mathcal {F}}}$является слабым классом Гливенко-Кантелли и доминируется интегрируемой функцией ${\displaystyle {\mathcal {F}}_{0}}$
• ${\displaystyle {\mathcal {F}}}$это класс Гливенко-Кантелли

Теорема ( Дадли , Джине и Зинн, 1991) ^[7]

Предположим, что класс функций ограничен. Также предположим, что множество является допустимым по образу Суслиным. Тогда является слабым равномерным классом Гливенко-Кантелли тогда и только тогда, когда он является сильным равномерным классом Гливенко-Кантелли. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}_{0}=\{f-\inf f\mid f\in {\mathcal {F}}\}}$ ${\displaystyle {\mathcal {F}}}$

Следующая теорема является центральной для статистического обучения задачам бинарной классификации.

Теорема ( Вапник и Червоненкис , 1968) ^[8]

При определенных условиях согласованности универсально измеримый класс множеств является однородным классом Гливенко–Кантелли тогда и только тогда, когда он является классом Вапника–Червоненкиса . ${\displaystyle \ {\mathcal {C}}\ }$

Существует множество условий согласованности для эквивалентности однородных классов Гливенко-Кантелли и Вапника-Червоненкиса. В частности, достаточно любого из следующих условий для класса: ^[9] ${\displaystyle {\mathcal {C}}}$

• ${\displaystyle {\mathcal {C}}}$является допустимым изображением Суслина.
• ${\displaystyle {\mathcal {C}}}$универсально отделимо : существует счетное подмножество такое , что каждое множество можно записать как поточечный предел множеств в . ${\displaystyle {\mathcal {C_{0}}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}_{0}}$

Примеры

• Пусть и . Из классической теоремы Гливенко–Кантелли следует, что этот класс является универсальным классом GC. Кроме того, по теореме Колмогорова , ${\displaystyle S=\mathbb {R} }$ ${\displaystyle {\mathcal {C}}=\{(-\infty ,t]:t\in {\mathbb {R} }\}}$

${\displaystyle \sup _{P\in {\mathcal {P}}(S,A)}\|P_{n}-P\|_{\mathcal {C}}\sim n^{-1/2}}$, то есть равномерно принадлежит классу Гливенко–Кантелли. ${\displaystyle {\mathcal {C}}}$

• Пусть P — неатомическая вероятностная мера на S и — класс всех конечных подмножеств в S. Поскольку , , , то мы имеем, что и, следовательно, не является классом GC относительно P . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle A_{n}=\{X_{1},\ldots ,X_{n}\}\in {\mathcal {C}}}$ ${\displaystyle P(A_{n})=0}$ ${\displaystyle P_{n}(A_{n})=1}$ ${\displaystyle \|P_{n}-P\|_{\mathcal {C}}=1}$ ${\displaystyle {\mathcal {C}}}$

Смотрите также

• Теорема Донскера
• Неравенство Дворецкого–Кифера–Вольфовица усиливает теорему Гливенко–Кантелли, количественно определяя скорость сходимости.

Ссылки

1. Говард Г. Такер (1959). «Обобщение теоремы Гливенко–Кантелли». Анналы математической статистики . 30 (3): 828–830. doi : 10.1214/aoms/1177706212 . JSTOR  2237422.
2. ван дер Ваарт, AW (1998). Асимптотическая статистика . Издательство Кембриджского университета. п. 279. ИСБН 978-0-521-78450-4.
3. ван дер Ваарт, AW (1998). Асимптотическая статистика . Издательство Кембриджского университета. ISBN 978-0-521-78450-4.
4. Гливенко, В. (1933). «Эмпирическое определение вероятностей». Гиорн. Ист. Итал. Аттуари (на итальянском языке). 4 : 92–99.
5. Кантелли, Ф.П. (1933). «Эмпирическое определение вероятностей». Гиорн. Ист. Итал. Аттуари . 4 : 421–424.
6. Талагранд, М. (1987). «Проблема Гливенко-Кантелли». Annals of Probability . 15 : 837–870. doi :10.1214/AOP/1176992069.
7. Дадли, Ричард М.; Джине, Ева; Зинн, Джоэл К. (1991). «Равномерные и универсальные классы Гливенко-Кантелли». Журнал теоретической вероятности . 4 : 485–510. doi :10.1007/BF01210321.
8. Вапник, В. Н.; Червоненкис , А. Я. (1971). «О равномерной сходимости относительных частот событий к их вероятностям». Теория вероятностей и ее приложения . 16 (2): 264–280. doi :10.1137/1116025.
9. Пестов, Владимир (2011). «Обучаемость PAC против измерения VC: примечание к основному результату статистического обучения». Международная объединенная конференция по нейронным сетям 2011 г. . стр. 1141–1145. arXiv : 1104.2097 . doi : 10.1109/IJCNN.2011.6033352.

Дальнейшее чтение

• Дадли, Р. М. (1999). Равномерные центральные предельные теоремы . Cambridge University Press. ISBN 0-521-46102-2.
• Pitman, EJG (1979). "Функция распределения выборки". Некоторые основные теории статистического вывода . Лондон, Великобритания: Chapman and Hall. стр. 79–97. ISBN 0-470-26554-X.
• Shorack, GR ; Wellner, JA (1986). Эмпирические процессы и приложения к статистике . Wiley. ISBN 0-471-86725-X.
• ван дер Ваарт, AW ; Веллнер, Дж. А. (1996). Слабая сходимость и эмпирические процессы . Спрингер. ISBN 0-387-94640-3.
• ван дер Ваарт, Аад В .; Веллнер, Джон А. (1996). Теоремы Гливенко-Кантелли . Спрингер.
• ван дер Ваарт, Аад В .; Веллнер, Джон А. (2000). Теоремы сохранения для классов Гливенко–Кантелли и однородных классов Гливенко–Кантелли . Springer.