§ 4. Условия сходимости алгоритма

Условия сходимости описанной выше процедуры формулируются далее в терминах спрямляющего пространства. Имея в виду условия экстремума (49) — (51) и тот факт, что выстраиваемая к шагу разделяющая плоскость имеет вид (52), убеждаемся, что сходимость процедуры к экстремуму функционала обеспечивается, если предельные значения величин, выстраиваемых алгоритмом, описанным в предыдущем параграфе, удовлетворяют соотношениям:

Сходимость процедуры (53) — (59) к значениям удовлетворяющим соотношениям (68), устанавливается следующей теоремой.

Теорема III. Пусть -мерное пространство, а функция переменных

непрерывно дифференцируема при

Тогда в силу процедуры (53) — (59) при

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

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

Замечание 1. Условие дифференцируемости функции (69) означает, по существу, что ни на одной из гиперплоскостей не сосредоточена конечная вероятность, т. е. что в пространстве X ни на одной из поверхностей вида не сосредоточена конечная вероятность появления точек

Замечание 2. Важной особенностью (которой мы в дальнейшем воспользуемся) функции фигурирующей в (69), является равенство ее нулю вне некоторой конечной области 2, пространства Действительно, для любого

Но функция всегда ограничена некоторой константой, а следовательно, и длина тех векторов z, для которых ограничена этой же константой.

Доказательство теоремы III. Предлагаемое ниже доказательство сводится к установлению следующих трех фактов:

3. Соотношения (71).

Из этих трех фактов немедленно следует утверждение теоремы.

Для того чтобы доказать первый факт — соотношения (72), воспользуемся теоремой II главы IV. В качестве последовательностей фигурирующих в условиях теоремы II, выберем последовательности

Для того, чтобы в соответствии с теоремой II главы IV можно было утверждать, что (и, следовательно, выполнены соотношения (72)), надо установить справедливость условий 1° и 2° теоремы II.

Что же касается второго и третьего фактов (соотношений (71) и (73)), то они будут доказаны одновременно после того как будут проверены условия 1° и 2° теоремы И, и тем самым будет завершено доказательство соотношений (72).

Проверка выполнения условий Г теоремы II главы IV.

Из (74) имеем:

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

Пусть . Тогда в соответствии с соотношениями (53) — (55) и

Учитывая, что — (так как и что — (так как выражение в фигурных скобках формулы (77) можно привести к такому виду:

Вспоминая определение находим

где множество тех точек для которых Очевидным образом верно

следующее тождество:

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

Поэтому из формулы (77) следует, что

Совершенно аналогично показывается, что если то

Рассмотрим теперь условное математическое ожидание величины Учитывая, что в силу соотношений (53) и (57)

и

а также принимая во внимание, что вероятность события есть и вероятность события есть получаем из (79) и (80) следующее соотношение:

Так как при из (53), (54) следует соотношение

а при из (57), (58) имеем

из (81) находим

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

Рассмотрим разность Если то в силу формул (56), (57)

Если же , то по формулам (53), (54)

Величина ограничена некоторой константой. Действительно, из формулы (53) следует, что

и если ограничен константой, равной то ограничен этой же константой. Но при

(см. формулу (59)), и тем самым и поэтому и для всех имеем

Подобным же образом устанавливается ограниченность

Из (86) следует, что

и из (85) находим неравенство

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

Действительно, если это утверждение верно при некотором то для В это верно в силу соотношения (84), а для в силу соотношения

следующего из (85). При соотношение (88) следует из начальных условий (59).

Рассмотрим теперь соотношения (84) и (87) и оценим с их помощью математическое ожидание величины Учитывая, что вероятность события есть получим для условного математического ожидания

Из (89) для безусловного математического ожидания имеем

Суммируя соотношения (90) по начиная с и учитывая затем неравенство (88) и сходимость ряда

получаем, что

Совершенно аналогично, при всех и

Используя (91) и (92), получаем для (см. формулу (83)):

причем для всех Это и завершает доказательство выполнения условия 1° теоремы II главы IV.

Проверка выполнения условия 2° теоремы II главы IV

Рассмотрим (см. формулу (75)):

и покажем, что если то разность оценивается выражением

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

и приращения в силу (53), (57) и оценки (86) оцениваются величиной то достаточно показать, что при приращения

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

где

а функция о такова, что при

В области величины ограничены константами, зависящими, вообще говоря, от , и, кроме того,

Отсюда следует оценка

где некоторая константа. Но поскольку в силу (53) — (58) и оценки (86) оцениваются величинами типа то из (96) сразу же следует

где некоторая константа.

Совершенно аналогично получается оценка для Для этого достаточно заметить, что в силу ограниченности пространства , определения вектора и полученной оценки (97) каждая компонента вектора оценивается величиной Используя затем конечномерность спрямляющего пространства, получаем аналогичную оценку

где некоторая константа. Формулы (97), (98) и приводят к оценке (94)

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

Действительно, если (99) будет установлено, то, полагая в условиях 2° теоремы убеждаемся,

что из (94) сразу следует выполнение условия 2° теоремы II.

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

Рассмотрим величины

Если при всех то это и будет означать, что векторы и с” лежат по разные стороны от разделяющей плоскости, имеющей на шаге направляющий вектор с и свободный член — В силу выбора начальных данных в алгоритме в виде (59) имеем

Пусть теперь и появилась точка , т. е.

Тогда в соответствии с рекуррентными соотношениями (53) -(55) алгоритма

Покажем, что

Тогда из (102) и (103) будет следовать, что при

В силу (59)

Пусть теперь . В соответствии с (53)-(55)

Если же то в соответствии с

Учитывая теперь, что при имеем

Таким образом, если , то выполняется (102) и теперь Тогда в соответствии с (56) — (58)

Из (105), учитывая (88), имеем при

Таким образом, всегда Аналогично доказывается, Следовательно, установлено, что векторы

и с” лежат по разным сторонам гиперплоскости. Из соотношения

следует формула (100).

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

С этой целью рассмотрим всевозможные положения разделяющих плоскостей, определяемые коэффициентами Множество этих коэффициентов компактно (в силу их ограниченности). Рассмотрим расстояние от гиперплоскости до среднего вектора или того полупространства (А или В), вероятность которого или больше или равна 1/2. Это расстояние является функцией параметров гиперплоскости. Существует строго положительная точная нижняя грань этой функции на компактном множестве значений параметров гиперплоскости. Действительно, если бы то это означало бы, что существует некоторая гиперплоскость, на которой полностью сосредоточена вероятность, но этот случай исключается условиями теоремы (см. замечание 1 к теореме III). Таким образом, действительно найдется такое что расстояние хотя бы одного из средних векторов или до соответствующей гиперплоскости не меньше, чем Используем теперь уже полученное нами условие 1° теоремы II главы IV. Переходя к безусловному математическому ожиданию в формуле (82), имея в виду (93) и ограниченность легко получаем, что

Условие (108) означает, что для любого существует такая константа и множество реализаций вероятности большей, чем что на каждой из реализаций этого множества

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

и, кроме того,

Поскольку же ряд расходится, а ряд сходится, то

и, следовательно, бесконечная последовательность, в которой

Из (110) следует, что

Из доказанного нами выше утверждения о том, что расстояние хотя бы одного из средних, векторов МА/РЛ

или до гиперплоскости не меньше, чем и из неравенств (112) следует, что хотя бы один из векторов или находится от гиперплоскости на расстоянии, не меньшем, чем Сопоставляя этот результат с установленным ранее фактом, что векторы всегда расположены по разные стороны от гиперплоскости, окончательно устанавливаем соотношения (106), (107) для всех реализаций из В силу же произвольности убеждаемся, что (106), (107) выполнены почти для всех реализаций.

Покажем теперь, что для почти всех реализаций справедливо соотношение

Для этого установим сначала, что для тех реализаций, для которых выполнены соотношения (106), (107), найдется такой номер (возможно, свой для каждой реализации), что

Действительно, рассмотрим реализацию, для которой (106), (107) выполнены, и выберем число удовлетворяющее условию

В силу условий и 006) такое число существует.

Рассмотрим некоторое число такое, что Для любого из процедуры (53), следует

При получении этого неравенства использована оценка (86). Поскольку при

то из (116) с учетом неравенств (115) и (107) следует

Таким образом, неравенство (114) доказано для всех для оно следует из (107).

Теперь соотношение (113) следует из (114) и (100):

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

Это означает, что на каждой реализации этого множества

и в силу произвольности для этой реализации

Но это противоречит уже доказанному утверждению (113). Таким образом, утверждение (99) доказано и тем самым установлено, что условие 2° теоремы II главы IV выполнено.

Доказательство соотношений (71) и (73). Покажем, что для почти всех реализаций, если найдется такое что и, соответственно, если то

Введем в рассмотрение величины

где такие, что на шаге

Здесь — число точек, ранее отнесенных к от первого до шага в силу начальных условий (59)).

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

Рассмотрим сумму

где полагается по определению

Поскольку, как легко убедиться, при этом

и, кроме того, в силу (53)

то

Если теперь то в силу (117) и (118) по крайней мере для одного имеем Тогда точка находится на расстоянии, большем

от разделяющей плоскости, построенной на шаге.

Покроем множество шарами диаметра Поскольку ограничено (см. замечание 2 к теореме III), для осуществления такого покрытия достаточно конечного числа шаров. Удалим из этого покрытия те шары, вероятность попадания в которые равна нулю. Для каждого из оставшихся шаров вероятность попадания в них положительна; минимальную из этих вероятностей обозначим через Заметим, что множество таких реализаций случайного процесса, на которых точки ни разу не попадают в «выброшенные» шары, имеет, очевидно, вероятность единица, так как по построению вероятность попадания точки в выброшенный шар равна нулю. В дальнейшем мы будем иметь дело лишь с такими реализациями и считать, что все точки попадают лишь в «невыброшенные» шары; тем самым мы исключаем из рассмотрения некоторое множество реализаций нулевой вероятности.

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

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

Совершенно аналогично доказывается, что для почти всех реализаций

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

(в соответствии с и, аналогично,

Для доказательства рассмотрим соотношения (84), (87) и аналогичные соотношения для

Введем число такое, что

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

легко получающихся из (84), (87). Из этих же соотношений следует, что

Выберем число такое, что

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

Действительно, рассмотрим величины

В силу рекуррентных соотношений (84), (87) для величин и можно записать

Складывая эти соотношения, получаем

Предположим, что во все моменты времени не выполнено ни соотношение (126а), ни соотношение (1266), т. е. что

Тогда, суммируя неравенства (128) в пределах от до и используя (129), получим

Но, вспоминая определение (127), в силу (125) и следующей из (123) и (124) оценки

приходим к выводу, что неравенство (130) противоречит неотрицательности и так как из (130) следует

Поэтому предположение (129) ошибочно, что и доказывает существование момента времени в который выполнено по крайней мере одно из двух соотношений (126а) или (1266). Вспоминая теперь неравенство (122), убеждаемся, что при хотя бы одно из неравенств (121а) или (1216) будет выполнено на каждой из реализаций.

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

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

и подмножество на всех реализациях которого при выполнено неравенство

По доказанному в предыдущем разделе такое разбиение возможно (см. (121а) и (121б)).

Рассмотрим множество реализаций Для почти всех реализаций в силу (114), (1326) и (88) при имеем

В силу доказанного выше соотношения (120а) из (133) следует, что для почти всех реализаций из множества

где

Из (134) следует теперь, что на почти всех реализациях из

Действительно, поскольку принадлежность каждой реализации множеству определяется не позже чем в момент времени (см. (121а) то при

вероятность того, что при условии принадлежности реализации множеству и появлении последовательности равна

Используя теперь (84), (87), получаем с помощью (136)

Отсюда следует

Предположим теперь, что (135) неверно. Из (89) в силу леммы II главы IV следует, что последовательность стремится почти наверное к некоторой случайной величине Поэтому невыполнение (135) означает, что найдется множество вероятности число и номер такие, что для всех реализаций из множества

Вместе с тем из (137) и из оценки (123) следует, что

Условия (138) и (139) противоречивы. Действитель но, учитывая, что имеем при

Но из (139) тогда следует

Поскольку а для почти каждой реализации из этого множества в силу (134)

то и правая часть (140) также расходится, что невозможно.

Таким образом, доказано, что на множестве условие (135) выполнено почти наверное. Отсюда следует, что для почти всех реализаций из найдется такой номер (может быть, свой для каждой из реализаций), что при выполнено условие (132а). Поступая теперь так же, как и при выводе формул (133), (134), получаем при

и в силу (120б)

Точно так же, как из соотношения (134) следовало соотношение (135), из (141) теперь следует, что для почти всех реализаций из

Таким образом, доказано, что для почти всех реализаций из выполнены соотношения:

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

реализациях из соотношения (143) также выполнены.

Тем самым показано, что на почти всех реализациях действительно выполнены соотношения (71). Попутно показано также, что на почти всех реализациях

т. е. доказана справедливость утверждения (73) теоремы.

Таким образом, порознь доказаны соотношения (71) — (73), и тем самым доказательство теоремы III завершено.