Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 224
Скачиваний: 4
I 7. О СХОДИМОСТИ С ВЕРОЯТНОСТЬЮ ЕДИНИЦА |
229 |
§7. О равномерной сходимости с вероятностью единица
Впредыдущем параграфе мы указали на достаточные условия равномерной сходимости (по вероятности) частот
квероятностям по классу событий S.
Здесь мы покажем, что полученные условия гаранти руют также равномерную сходимость с вероятностью еди ница. Доказательство этого утверждения основывается на использовании известной из теории вероятностей лем мы [21].
Лемма. Если для случайной последовательности ...
..., \ п, ... найдется такое £0, что для любого £ Д> 0 спра ведливо неравенство
00
І2 ^ {!Е і - Е о| > 6 } < оо, |
||
= 1 |
|
|
то последовательность |
, |
..., %п, ... сходится к £0 с ве |
роятностью единица. |
|
Обозначим через Егп собы |
Д о к а з а т е л ь с т в о . |
||
тие, состоящее в том, |
что |
выполняется неравенство |
I In — lo \> — (r — целое число).
Рассмотрим событие Sn, состоящее в том, что выполняется
хотя бы одно из событий Е щ |
Е п + ц |
|
Т- |
ѳ . |
|||
|
|
|
S rn = U En+i- |
|
|
|
|
|
|
|
i= 1 |
|
|
|
|
Оценим вероятность этого события: |
|
|
|||||
|
оо |
|
со |
|
- |
So) > 4 -} • |
d 0-2*) |
р |
{Ä } < і2—1 |
р |
{£п+і} = 2 |
L |
|||
|
|
|
І= П |
|
|
J |
|
Но так как в силу условия леммы ряд (10.21) сходится, то
lim Р {iS£} = 0. |
(10.22) |
П—>оо
Рассмотрим теперь событие Sr
ST= n S t
n = l
230 Г л . X. Д о с т а т о ч н ы е у с л о в и я р а в н о м е р н о й с х о д и м о с т и
Из того, что событие Sr влечет за собой любое из событий Sn, в силу (10.22) получаем
Р (Sr) = |
0. |
(10.23) |
Наконец, положим |
|
|
оо |
s r. |
|
5 = и |
|
|
г = 1 |
|
|
Как нетрудно установить, это событие означает, что найдется такое г, что для каждого п (п = 1,2,...) хо тя бы при одном к (к = к (п) ) будут выполняться нера венства
|
I En+fc |
£о| > |
— • |
|
|
Так как |
оо |
|
|
|
|
|
|
|
|
|
|
то в силу |
(10.23) |
г= 1 |
|
|
|
|
|
|
|
||
|
Р {S} = о, |
|
|
||
что и требовалось доказать. |
|
такое |
число п Д> 0, |
||
Теорема |
10.3. Если существует |
||||
что при 1^> п функция ms (I) < |
Іп, то справедливо |
||||
|
P{ns (хх, ..., |
жг),^ 0 } |
= 1. |
|
|
Д о к а з а т е л ь с т в о . |
В |
силу |
теоремы 10.2 |
||
Р |
{jxs (%, ..., хі) |
е) |
Qms (2l)e |
іЧІ-1) |
|
4 . |
|||||
Пусть п — такое число, что при 1^> п
ms (I) < Іп.
Выберем целое число I* так, чтобы оно превосходило и п. Тогда
оо
2 ^ { n s (xx, . . ., яг)> е } =
і=ч
г* |
«, |
= 2 р { nS ( * ! > . . |
Жг) > 6} + 2 р i nS ( * 1 . • • •> х і) > е } - |
г=і |
г=;* |
§ 8. ПРИМ ЕРЫ И ДОПОЛНИТЕЛЬНЫ Е ЗАМЕЧАНИЯ |
231 |
Первое слагаемое в правой части равенства не превосхо дит /*, а второе слагаемое
2 |
2 { l i f e |
t*(f—1) |
|
4 |
|||
i=i* |
і=і* |
|
|
сходится, как известно, |
при любом е |
0. |
|
Поэтому |
|
|
|
оо
2 Р 1=1
( Х у , . . . , Х у ) > 8 } < + ОО
и, согласно приведенной лемме,
Р {ltS { Х у , ..., Хг)г^ 0 } =1.
Теорема доказана.
§8. Примеры и дополнительные замечания
Впримере 1 § 3 в качестве пространства X взята пря мая, а в качестве системы S — множество всех лучей вида X а . В этом случае
|
Р (А) = Р{х |
а} = Ф (а) |
|
есть |
функция |
распределения |
случайной величины х, |
V (И; |
Ху, ..., Xi) |
= F (а) есть эмпирическая функция рас |
|
пределения этой случайной величины, построенная по выборке Х у , ..., Х у .
Согласно теореме |
10.2 |
Р {sup I F (а) - |
_ е» П-1) |
Ф (а) | > е}< 6ms (21)е * . |
Поскольку в соответствии с (10.9) в данном случае ms (Г) <(
< (I + 1), ТО
Е’Ц-І)
Р {sup ] F (а) — Ф (а) | ^>е) <( 6 (21 + 1) е 2
а
и имеет место равномерная сходимость эмпирических функций к функциям распределения почти наверное. Это — известная теорема Гливенко.
В примере 3 § 3 X — п-мерное пространство, S — сис тема подмножеств вида
(х, ф) > 0 (ф =/Ь0).
232 ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ СХОДИМОСТИ
В соответствии с формулами (10.19), (10.10) и(10.15) при любом задании распределения в пространстве X
Р {sup [ Р (ф) — V (ф; хъ ..., X,) I > е}<18 |
е |
|
где Р (ф) |
и V (ф) — соответственно частота и вероятность |
|
события |
{(хф) 0}, и следовательно, при I |
оо величина |
sup [ Р (ф) — V (ф) I
ф
сремится к нулю с вероятностью единица. Аналогично, если система S состоит из множеств вида
(Хф) > с,
то
^ |
( 2 1 _чу* |
—ililzzll |
|
Р { яа (х1,...,х ,)> е } < 1 8 |
{м п1і} |
в |
4 |
и, очевидно, также с вероятностью 1 имеет место равно мерная сходимость частот к вероятностям.
Это весьма существенный для приложений результат. В известном смысле он может рассматриваться как обоб щение теоремы Гливенко.
Замечание 1. Пустъ дано конечное число систем
..., S n,
для каждой из которых известна функция роста m?k (I).
Пустъ далее, система событий S 0 |
такова, что каждое со |
бытие А ЕЕ S q есть пересечение |
некоторых событий |
А = A t U А 2 ... |
UА п, |
где событие А г принадлежит |
соответственно систе |
ме S(.
Тогда
П
ms° ( l m Si(l). i—l
В самом деле, для произвольной выборки х,, ..., хг в каж дой системе S t найдется не более mSi (I) неэквивалентных событий. Рассматривая всевозможные их пересечения,
§ 8. |
ПРИМЕРЫ И ДОПОЛНИТЕЛЬНЫ Е ЗАМЕЧАНИЯ |
233 |
получим, |
что |
|
п
і=1
При этом, если каждая из функций mSi (I) растет не быст рее, чем степенным образом, то и функция тР° (I) растет не быстрее некоторой степени.
П р и м е р 4. Обобщение теоремы Гливенко на п- мерный случай в ином смысле имеет место, если в качестве
X взять Е п, а в качестве |
S — систему множеств вида |
X1 < aL, |
..., хп < а". |
В силу приведенного замечания в этом случае
т8 (I) < (I + 1)"
и, таким образом, равномерная сходимость также имеет место.
П р и м е р 5. Пусть X — «-мерное евклидово прост ранство, S — любые выпуклые многогранники с числом граней, не превосходящим к.
Тогда
так как каждый такой многогранник может рассматри ваться как пересечение к множеств вида
{(*, Ф) > с}.
Следовательно, и для этой системы имеет место равно мерная сходимость частот к вероятностям.
В примере 2 § 3 ms (I) = 21 и наши условия не гаран тируют равномерную сходимость частот к вероятностям. И действительно, как легко убедиться, например, при рав номерном распределении (и любом непрерывном) такой сходимости нет.
Замечание 2. Выше было установлено, что для всех систем событий S, у которых функция роста не равна тож дественно 21, всегда имеет место равномерная сходимость частот событий к вероятностям независимо от вероятно стной меры Р (х). При этом формула (10.19) позволяет оценить величину максимального по классу S уклонения
234 ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ СХОДИМОСТИ
частот от вероятностей независимо от распределения
Р(х).
Вслучае же, когда ms (і) = 21, величина максимального по классу S уклонения частоты от вероятности не может бытъ оценена нетривиальным образом, ни при каком конечном I, если не используются сведения о распределе
нии Р (X).
С одной стороны, существуют распределения, при ко торых величина
.. .,х,) = sup IV (Л; хъ . . ., Х[) — P{Aj |
Ae s
свероятностью 1 равна нулю при Z> 1; таким будет рас
пределение, сосредоточенное в какой-либо |
одной |
точке |
||
х 0. Это означает, что |
вероятностная мера |
задается |
усло |
|
виями: |
|
|
|
|
Р (А) |
= 1, |
если х0 ЕЕ А , |
|
|
Р (А) |
= 0 , |
если х0 ф А |
|
|
(для простоты будем считать, что одноточечное множество {х0} измеримо, хотя эта оговорка не принципиальна).
Тогда с вероятностью 1 выборка будет состоять только
из повторяющегося элемента х0 |
*^0* |
|||
|
*/ |
— |
• • м |
|
|
-у>I |
_ <Ѵ1 |
/-Ѵ» |
|
Очевидно, что при этом для всех А |
||||
ѵ(Л; х 0, |
..., |
х0) |
= 1 , |
если -х0 е е А, |
V (.А ; х0, |
..., |
х0) |
= 0, |
если х0 ф А |
и, следовательно,
sup IV (А; хъ ..., Хі) — Р (Л) I — 0,
A e s
каков бы ни был класс S.
С другой стороны, если ms (Г) ~ 21, то существуют та кие распределения, что величина
ns (хѵ ..., xt)
со сколь угодно большой достоверностью сколь угодно близка к единице.
Тем не менее, как будет показано в главе XI, сущест вуют примеры систем, для которых ms (Z) = 21 и все же
