Главная > Распознавание образов > Метод потенциальных функций в теории обучения машин
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 3. Основные теоремы о сходимости

Рассмотрим случайный процесс

в дискретном времени определяемый условными распределениями вероятностей появления случайной величины момент времени при условии, что в моменты случайные величины принимали значения соответственно.

Доказываемые далее теоремы и устанавливают достаточные условия того, чтобы последовательность удовлетворяющая условию А, стремилась к нулю в том или ином смысле.

Теорема Пусть задан случайный процесс и последовательность скалярных функций (7), удовлетворяющих условиям:

1°. Условию А, причем

где некоторые константы, тйкая последовательность функций что

Тогда

и, тем самым, последовательность случайных величин стремится к нулю по вероятности при

Если же условие 2° выполняется при то, кроме того, при

Доказательству этой теоремы предпосылаются леммы которые нужны не только для доказательства теоремы I, но и для ряда последующих теорем настоящей главы.

Лемма Пусть числовые последовательности таковы, что:

Пусть, далее, числовая последовательность неотрицательна и удовлетворяет условиям:

1°. Ряд сходится.

2°. , где некоторые постоянные.

Тогда предел последовательности при существует и равен нулю.

Доказательство леммы Заметим сначала, что без ограничения общности можно считать положительными и что ряд

в силу условия в) леммы и условия 1° сходится, а ряд в силу условия б) расходится. Поэтому, переопределив соответствующим образом последовательности можно без ограничения общности заменить условие 2° условием

Утверждение леммы означает, что для любого найдется такой номер что при всех Покажем, что номер существует.

Рассмотрим множество номеров таких, что и соответствующую последовательность Если множество конечно, и максимальный номер, входящий в это множество, есть то можно положить Поэтому в дальнейшем обсуждается лишь возможность бесконечной последовательности

В соответствии с условием 1° леммы ряд сходится. Поэтому найдется такой номер что

Рассмотримтакже такой номер что при всех

Такое существует в силу условий а) и в) леммы. Заметим, что в силу условия б) леммы множество номеров, не входящих в множество бесконечно. Поэтому всегда найдется номер не входящий в и такой, что

Покажем, что при любых

Прежде всего, это очевидно (по определению множества для тех номеров которые не принадлежат так как для этих номеров

Пусть теперь некоторый номер, принадлежащий Рассмотрим максимальный номер меньший не принадлежащий так что

Поскольку не принадлежит номер и поэтому в силу (13)

Используя формулу (10), получаем

В силу соотношений (15) и (11)

а в силу соотношений (15) и (12)

Поэтому, учитывая (14), из (16) заключаем, что

Тем самым завершено доказательство того, что при любом Лемма доказана.

Лемма II. Пусть задан случайный процесс и последовательность функций такая, что выполнено условие

где — последовательность функций случайных аргументов для которой

Тогда при стремится почти наверное к некоторой случайной величине А:

причем

Если, кроме того, выполнено условие 2°. Последовательность функций бесконечно большая, то почти все реализации случайного процесса ограничены.

Доказательство леммы И. Рассмотрим случайную величину

В силу условия 1° леммы величина удовлетворяет неравенству

т. е. является полумартингалом, и значения ограничены. Действительно, из (19) имеем

Учитывая это обстоятельство и используя теорему о полумартингалах (см. § 1 этой главы), заключаем, что последовательность сходится почти наверное к некоторой случайной величине

Далее, в соответствии с принципом монотонной сходимости сходится почти наверное к случайной величине причем в силу условия 1° леммы Поэтому при стремится почти наверное к случайной величине

При этом

Таким образом, первое утверждение леммы доказано. Втооое же утверждение леммы следует немедленно из определения бесконечно большой последовательности функций, если учесть, что в силу первого утверждения почти все последовательности сходятся к конечному пределу. Лемма доказана.

Приступим теперь к доказательству теоремы Доказательство теоремы Докажем сначала утверждение (9) теоремы. Покажем, что только лишь условие А обеспечивает существование такой последовательности удовлетворяющей условию

что

где некоторая константа. Действительно, введем функцию

Условие А гарантирует сходимость произведения

в силу чего и имеет место (24). Умножение же неравенства (8) в условии А на введение обозначения (25) и оценка

приводят непосредственно к (23).

Перейдем в неравенствах (23) от условных математических ожиданий к безусловным и просуммируем полученные неравенства.

В результате будем иметь

Из последнего соотношения получаем

По условию 1° теоремы поэтому из (26) следует

Совершая теперь переход, к безусловным математическим ожиданиям в неравенствах условия 2° теоремы, получим

причем по условию 2° теоремы Условия (27) и (28) составляют в совокупности условия леммы I, если положить В силу этой леммы утверждение (9) доказано.

Утверждение о сходимости последовательности к нулю по вероятности следует теперь из (9). Поэтому для того чтобы завершить доказательство теоремы, остается показать, что при С этой целью заметим, что в силу (27) и сходимости ряда имеем

и при из условия 2° теоремы следует

Условия (29) и (30) составляют в совокупности условия пункта 1° леммы II, если отождествить и с Поэтому в силу леммы II существует случайная величина V, такая, что

и

Но по доказанному выше и поэтому случайная величина V может быть только нулем:

Теорема I доказана полностью.

При исследовании конкретных процессов может оказаться, что величины фигурирующие в условии 2° теоремы I, являются не константами, а некоторыми функциями

Если при этом последовательности функции не могут быть промажорированы константами, то, разумеется, теорема I неприменима. Однако если удается из каких-либо соображений установить ограниченность последовательностей для почти всех реализаций случайного процесса, то сходимость по вероятности к нулю может быть доказана. Ограниченность же последовательностей может следовать, в частности, из ограниченности реализаций случайного процесса. Условия, гарантирующие ограниченность почти всех реализаций случайного процесса как уже указывалось в § 2, могут быть выражены в форме ограничения на вид последовательности функций Именно, достаточно потребовать, чтобы последовательность была бесконечно большой.

Теорема 1а. Пусть функции (7) удовлетворяют условиям:

1°. Условию А, причем

где функции, которые для любой ограниченной последовательности мажорируются константами соответственно, последовательность функций такая, что

3°. Последовательность функций бесконечно большая.

Тогда последовательность случайных величин стремится к нулю по вероятности при и

Доказательство теоремы 1а опирается как на лемму I, так и на лемму II, которая как раз позволяет устанавливать ограниченность почти всех реализаций случайного процесса используя свойства бесконечно больших последовательностей функций.

Доказательство теоремы 1а. Докажем сначала, что почти все реализации случайного процесса (при выполнении условий 1° и 3° теоремы 1а) ограничены. Из соотношения (23), являющегося следствием лишь условия А, и из условия 1° теоремы 1а следует условие 1° леммы II. Из условия 3° доказываемой теоремы и из определения (25) следует условие 2° леммы II. Таким образом, оба условия леммы II выполнены, и в силу утверждения леммы II почти все реализации случайного процесса в условиях теоремы 1а действительно ограничены. Ограниченность почти всех реализаций случайного процесса как легко видеть, эквивалентна следующему утверждению: для любого найдется такое число и такое множество реализаций вероятность которого больше, чем что в каждой реализации из множества имеет место при всех

Рассмотрим множества реализаций, для которых при Очевидно, так что

На каждой реализации из в силу условия 2° теоремы 1а справедливы неравенства

В дальнейшем нам понадобится следующее неравенство:

справедливое для любых неотрицательных функций

заданных на реализациях

случайного процесса.

Перейдем теперь в неравенствах (23) к условным (при условии математическим ожиданиям, умножая

затем левую и правую части на Получим при этом

Используя неравенство (33) (положив при этом и очевидное неравенство

справедливое при получаем

Отсюда совершенно аналогично тому, как было выведено условие (27), получаем

Перейдем к условным (при условии математическим ожиданиям в неравенствах, фигурирующих в условии 2° доказываемой теоремы, принимая во внимание неравенства (32). Получим

Умножая это неравенство на используя (33) (полагая и учитывая очевидное неравенство

будем иметь

Поскольку в силу условия 2° теоремы, замечаем, что неравенства (34) и (35) составляют в совокупности условия леммы I, если положить

В силу утверждения этой леммы

Для каждого и каждого натурального введем в рассмотрение множество реализаций такое, что в каждой реализации этого множества Для любого справедлива следующая цепочка неравенств:

Второе неравенство этой цепочки следует из того, что на множестве всегда справедливо неравенство (по определению множества Третье неравенство цепочки (37) следует из очевидного теоретикомножественного соотношения

так как в силу этого соотношения

и, с другой стороны,

Принимая во внимание неравенство (31) и учитывая, что по определению множества

получим из (37)

Отсюда

где

Поскольку произвольно, из (39) и (38) следует, что для любого

т. е. случайная величина стремится по вероятности к нулю. Теорема доказана.

Следующая теорема II весьма близка по своим условиям к теореме I, но, в отличие от нее, содержит требование об ограничении роста последовательности (условие 2°), не в смысле математических ожиданий, а на почти каждой реализации. Это и позволяет установить сходимость к нулю последовательности почти наверное.

Теорема II. Пусть функции (7) удовлетворяют условиям:

1°. Условию А, причем

2°. Для любого найдется такое множество реализаций случайного процесса вероятность которого больше и найдутся такие константы что на каждой реализации этого множества выполнены неравенства

где последовательность таких чисел (может быть, своя для каждой реализации), что ряд сходится.

Тогда при последовательность случайных величин стремится к нулю почти наверное.

Доказательство теоремы II. В условиях теоремы II соотношение (27), полученное при доказательстве теоремы I, также имеет место, так как его вывод основан лишь на условии 1°, общем для обеих теорем. Поэтому в силу принципа монотонной сходимости (см. § 1 этой главы) последовательность при сходится почти наверное к случайной величине Для случайной величины (как и для всякой случайной величины) для любого найдется

такое число что

Рассмотрим множество тех реализаций, на которых одновременно выполнено неравенство (40) условия 2° теоремы II и неравенство

Вероятность этого множества не меньше, чем Каждая из реализаций этого множества удовлетворяет условиям леммы I, если отождествить последовательность в данной реализации с последовательностью фигурирующей в тексте леммы

В силу леммы I на каждой такой реализации при Поскольку же вероятность множества таких, реализаций больше, чем то в силу произвольности отсюда следует, что при . Теорема II доказана.

Легко видеть, что если в неравенствах (40) величины могут быть выбраны не зависящими от 6, а последовательность чисел одна и та же для всех реализаций, то из (40) следуют соотношения на математические ожидания, фигурирующие в условиях 2° теоремы I, и тем самым в силу теоремы I будет гарантировано стремление к нулю и

Условие 2° теоремы II может быть ослаблено, если предположить, что последовательность бесконечно большая (подобно тому как это сделано по отношению к теореме I). Следующая теорема устанавливает условия сходимости почти наверное в случае, когда величины фигурирующие в условии 2° теоремы II, могут явно зависеть от

Теорема IIа. Пусть функции (7) удовлетворяют условиям:

1°. Условию А, причем

где и функции, которые для любой ограниченной последовательности мажорируются константами и соответственно, а числовая последовательность такая, что ряд сходится.

3°. Последовательность функций бесконечно большая.

Тогда последовательность случайных величин стремится при к нулю почти наверное.

Теорема IIа является, по существу, следствием теоремы II. Действительно, из условий 1° и 3° теоремы На следует (см. начало доказательства теоремы 1а), что для любого найдется такое множество реализаций, вероятность которого больше и такое число что на этом множестве реализаций при всех Из этого утверждения и из условия 2° теоремы На следует выполнение условия 2° теоремы II. В силу этой последней теоремы стремится к нулю почти наверное, что и доказывает утверждение теоремы Па.

В следующих далее теоремах и IV устанавливаются достаточные условия сходимости уже не последовательности а последовательности (из условия А) в том или ином смысле.

Теорема III. Пусть функции (7) удовлетворяют условиям:

1°. Условию А, причем

2°. Почти все реализации случайного процесса удовлетворяют требованию: если существует последовательность (быть может, своя для каждой реализации), такая, что в данной реализации то в этой реализации и

Тогда при последовательность случайных величин стремится к нулю почти наверное:

и, кроме того, при любом

Доказательство теоремы III. Заметим сначала, что соотношения

полученные при доказательстве теоремы I (см. формулы (27), (23) и (25) соответственно), следуют лишь из условия 1° теоремы I, которое сохраняется и в условиях теоремы III. Из сходимости ряда (42) и расходимости ряда следует существование подпоследовательности такой, что

Из (45) следует, что случайная последовательность стремится по вероятности к нулю при Но из стремления случайной последовательности к нулю по вероятности следует существование подпоследовательности которая стремится к нулю почти наверное при (см. § 1). Отсюда и из условия 2° теоремы сразу следует, что

Из соотношения (43), учитывая сходимость ряда заключаем, что выполнено условие 1° леммы II. Поэтому

а в силу (44) и (47) получаем

Из этого соотношения и соотношения (46) очевидным образом следует теперь, что случайная величина с вероятностью единица равна нулю, т. е.

Для того чтобы установить соотношение (41) и тем самым завершить доказательство теоремы III, заметим, что последовательность случайных величин при также стремится к нулю почти наверное (в силу

Кроме того, легко установить, что величины при равномерно интегрируемы. Действительно, как это следует из (43) и (44), с учетом того факта, что безусловные математические ожидания ограничены одной и той же константой

и поэтому в силу достаточного условия равномерной интегрируемости (см. § 1) величины при равномерно интегрируемы. Из равномерной интегрируемости и из (50) следует, что

Теорема доказана.

Сделаем теперь следующее замечание: если, как это часто бывает, помимо условия 2° выполнено обратное условие, т. е. требование, согласно которому из следует, что то и при

Сделаем еще ряд замечаний о том, как фактически можно проверить условие 2° теоремы III. На первый взгляд кажется, что это условие практически непроверяемо, так как оно требует знания особенностей реализаций случайного процесса На самом деле это не так, и можно указать ряд случаев, когда это условие легко проверяется. Мы отметим здесь два

наиболее важных случая, охватывающих большинство практических приложений теоремы.

а) Первый случай в значительной степени тривиален. Пусть функции таковы, что если на некоторой последовательности (не обязательно являющейся реализацией исследуемого случайного процесса), то и на этой последовательности. Ясно, что в этом случае условие 2° теоремы заведомо выполнено.

б) Пусть из каких-либо соображений установлена ограниченность почти всех реализаций случайного процесса Тогда, если функции таковы, что на любой ограниченной последовательности из следует условие 2° также выполнено. Таким образом, в отличие от случая а), в данном случае допускается, чтобы при некоторых неограниченных последовательностях последовательность стремилась к нулю при в то время как последовательность к нулю не стремилась.

Тем самым, в последнем случае б) остается лишь установить условия, которые гарантируют ограниченность почти всех реализаций случайного процесса и ранее (см. теоремы 1а, IIа), эти условия могут быть выражены в форме требования, согласно которому последовательность функций является бесконечно большой.

Теорема Пусть функции (7) удовлетворяют условиям:

1°. Условию А, причем

2°. Почти все ограниченные реализации случайного процесса удовлетворяют требованию: если существует последовательность (быть может, своя для каждой реализации) такая, что в данной реализации то в этой реализации и

3°. Последовательность функций бесконечно большая.

Тогда при последовательность случайных величин стремится к нулю почти наверное и, кроме того, при любом

Теорема в силу сказанного выше является простым следствием теоремы III, и для ее доказательства достаточно установить лишь ограниченность почти всех реализаций случайного процесса Последний же факт установлен в начале доказательства теоремы 1а, так как условия 1° и 3° теорем 1а и совпадают.

Используем теперь теорему III для того, чтобы доказать следующую теорему IV, установленную А. Дворецким [8].

В теореме IV рассматривается векторный процесс определяемый рекуррентным

соотношением

где векторные детерминированные функции, случайные функции, такие, что

Теорема Дворецкий). Пусть векторный случайный процесс определяется рекуррентным соотношением (51), (52), а функции удовлетворяют условиям

где — неотрицательные числовые последовательности, удовлетворяющие следующим условиям:

Тогда при последовательность случайных величин стремится к нулю почти наверное и, крсше того, при любом

Доказательство теоремы IV. Легко показать, что в условии (53) теоремы без ограничения общности можно считать, что последовательность невозрастающая, а сходится. Для этого надо лишь заменить в (53) последовательность невозрастающей мажорирующей последовательностью, а последовательность такой минорирующей последовательностью, у которой сумма квадратов сходится.

Учитывая это замечание, условия теоремы Дворецкого могут быть дополнены условиями:

Имея в виду воспользоваться далее теоремой III, покажем, как, исходя из условий теоремы Дворецкого, можно выбрать функции так, чтобы они удовлетворяли условиям теоремы III.

Для того чтобы выбрать функции введем в рассмотрение функцию определив ее так:

Легко видеть, что функция обладает следующими свойствами:

1) монотонно неубывающая функция 0;

4) если два произвольных вектора, а действительное число, такое, что то

Выберем теперь функции фигурирующие в теореме III, следующим образом:

В силу этого определения условие теоремы III очевидным образом удовлетворяется. Поэтому для того, чтобы можно было воспользоваться теоремой III, остается проверить только условие 1° теоремы III. Если это будет сделано, то в силу теоремы III будет установлено, что при Но поскольку по условию 1° теоремы Дворецкого то отсюда сразу будет вытекать, что и Кроме того, в силу ремы III отсюда также будет следовать, что при

Из последней же формулы следует, что и

Действительно, поскольку в силу свойства 2) функции

то, применяя очевидное неравенство справедливое для любых неотрицательных чисел имеем при

Поэтому из заключаем, что при любом

Таким образом, чтобы завершить доказательство теоремы, остается проверить выполнение условия 1° теоремы III.

С этой целью введем в рассмотрение вектор

Легко проверить, что из определения (59) следует

и

Используя свойство 4) функции и полагая имеем

и

Заменяя в выражением (51), получаем

Из формулы (61) и (64) следует теперь, что

где

Докажем, что

С этой целью используем условие (53) теоремы Дворецкого. Если то неравенство (67) очевидно, так как левая часть обращается при этом в нуль. Если же то в силу условия (53)

и поэтому

так что знак в обеих частях неравенства (67) может быть отброшен; получаемое при этом неравенство сразу следует из неравенства (68).

Легко проверить, что из (67) следует неравенство

где

Если то неравенство (70) очевидно; если же то вновь выполнено неравенство (69), и в этом случае из (67) следует, что

где обозначено

Воспользовавшись свойством 3) функции получаем (70).

Возведем неравенство (70) в квадрат и воспользуемся легко проверяемым неравенством справедливым при положив при этом

В результате получаем

Усилим теперь неравенство (65) с помощью неравенства (72). В результате после выполнения операции возведения в квадрат квадратной скобки в правой части последнего неравенства получим

Возьмем условное математическое ожидание от обеих частей этого неравенства:

где введены обозначения:

В (77) учтено уже, что в силу определения (66)

а по условию (52)

Для того, чтобы показать, что неравенство (74) совпадает с условием 1° теоремы III, остается установить, что суммы сходятся, а ряд расходится.

Заметим, что в формуле (71) можно опустить операцию так как в силу условия (57) и неотрицательности чисел выражение под знаком в (71) неотрицательно, и

Оба ряда в правой части этого выражения сходятся в силу условий (54) и (55) теоремы. Таким образом, ряд сходится.

Сходимость суммы следует теперь в силу определения (75) из того факта, что сходятся ряды и 2 (последний ряд сходится по условию (55) теоремы).

Сумма математических ожиданий

сходится потому, сходятся суммы (в силу условия Условия (52) теоремы).

Сумма же 2 расходится, так как по определению а сумма расходится по условию (54) теоремы.

Этим замечанием исчерпывается доказательство теоремы Дворецкого, так как доказано выполнение всех условий теоремы III.

В формулировках доказанных выше теорем I—III требование сходимости ряда является существенным. Формулируемая ниже теорема V позволяет ослабить это требование за счет существенного усиления условия 2° этих теорем. Отказ в теореме V от требования сходимости ряда позволит в дальнейшем (см. § 4) отказаться в некоторых случаях от обычного для

алгоритмов стохастической аппроксимации требования (6а) на последовательность заменив его требованием (66).

Теорема Пусть функции (7) удовлетворяют условиям.

1°. Условию А, причем

2°. Существует такая константа что

Тогда

и последовательность случайных величин стремится к нулю по вероятности при

Доказательство теоремы Как было показано при доказательстве теоремы I только лишь из условия А следуют соотношения

Поэтому эти соотношения верны и в условиях теоремы Используя условие 2° теоремы V, с помощью (78) и (79) после перехода к безусловным математическим ожиданиям получаем:

где и величины обозначены вновь через Теперь из условия 1° теоремы V следует

где Из неравенств (80) следует, что

Для установления того факта, что достаточно показать, что Из условия 1° следует, что первый и третий члены в правой части (82) стремятся к нулю при Поэтому для доказательства утверждения остается доказать, что

Введя величины

можно написать

Для любого натурального из (83) следует неравенство

где Поскольку последнее неравенство можно усилить:

Из того факта, что следует, что и Кроме того, из расходимости ряда следует, что при любом фиксированном Поэтому (84) гарантирует, что при Таким образом, доказано, что а следовательно, и утверждение теоремы

При сопоставлении теорем III и V может показаться, что условия теоремы V достаточны для установления сходимости последовательности к нулю не только по вероятности, но и почти наверное, так как условие 2° теоремы V заведомо более сильное, чем соответствующее условие теоремы III. Однако это не так; можно привести пример случайного процесса, который, удовлетворяя условиям теоремы V, не сходится почти наверное.

Пусть случайный процесс принимает два значения: где числовая последовательность, для которой Положим с вероятностью единица, если и

если Легко проверить, что этот случайный процесс удовлетворяет условиям теоремы V с с произвольным удовлетворяющим условию 1°, и вместе с тем не стремится к нулю почти наверное.

Этот процесс является одновременно примером процесса, сходящегося к нулю в среднем и по вероятности, но не сходящегося к нулю почти наверное. Тем самым сходимость ряда (а именно этим и отличается условие 1° теоремы III от соответствующего условия теоремы V) оказывается существенной для самого факта сходимости почти наверное. С другой стороны, относительная слабость условия 2° теоремы III не позволяет установить стремление к нулю математических ожиданий этот факт подтверждается приводимым ниже примером; теорема III устанавливает лишь стробление к нулю при

В качестве процесса, удовлетворяющего условиям теоремы III и вместе с тем такого, что не стремится к нулю при рассмотрим следующий процесс

Если то с вероятностью единица. Если же при то

и, кроме того, Легко проверить, что этот процесс удовлетворяет условиям теоремы III с и

при При этом оказывается, что при безусловные вероятности равны

и

так что а не нулю. Разумеется, при этом, как и утверждается в теореме III, стремится к нулю при любом

Этот пример служит одновременно примером случайного процесса, сходящегося к нулю почти наверное, но не сходящегося в среднем.

Приведенные выше теоремы приспособлены к установлению сходимости процессов, в которых при Для установления сходимости процессов, в которых является не зависящей от постоянной, применима следующая теорема VI.

Теорема VI. Пусть функции (7) удовлетворяют условию А, причем Тогда

и, кроме того, последовательность случайных величин стремится к нулю почти наверное при

Доказательство теоремы VI. Поскольку в силу условия А выполнены соотношения (23) и (24) из

(кликните для просмотра скана)

(кликните для просмотра скана)

доказательства теоремы I, то при выполнении условий теоремы VI выполнены соотношения

Перехода от условных математических ожиданий к безусловным и суммируя полученные неравенства, имеем

Усиливая это неравенство, получим

откуда с учетом того, что имеем

Из этого соотношения следует, что

Но поскольку величины неотрицательны, из соотношения (85) в силу принципа монотонной сходимости (§ 1) следует сходимость последовательности к нулю почти наверное. Теорема доказана.

В заключение этого параграфа объединим в общую таблицу предположения и утверждения всех доказанных теорем (за исключением теоремы IV). Во всех этих теоремах предполагается, что выполнено условие А, и поэтому этот факт не отражен в приводимой ниже таблице. Условия различных теорем отличаются, во-первых, условиями Г, которые конкретизируют некоторые детали условия А (первый столбец таблицы) и, во-вторых, условиями 2°. Во всех теоремах, номера которых содержат индекс «а», предполагается, что последовательность функций бесконечно большая. Поэтому этот факт также не отражен в таблице. В третьем столбце таблицы содержатся утверждения соответствующих теорем.

<< Предыдущий параграф Следующий параграф >>
Оглавление