§ 5. Еще одно условие сходимости рекуррентных алгоритмов
В условиях теоремы 1 не
предполагалось, что существует минимум функционала 
. Достаточно было того, что
функционал ограничен снизу и, следовательно, существует точная нижняя грань.
Сходимость к точной нижней грани и утверждала теорема.
Сейчас будем предполагать, что
минимум функционала существует. Это позволит ослабить требования к порядку
роста модуля градиента функции потерь.
Теорема 9.2. (Б. М. Литваков [44]). Пусть
выполнены следующие условия:
1)
функционал ограничен
снизу и существует непустое множество 
,
2) 
,
3) 
.
Тогда при любом 
с вероятностью
единица справедливо: 
.
Доказательство. Выберем
произвольную точку 
.
Оценим долю 
тех
последовательностей, которые хоть раз выйдут из гипершара 
с центром в 
и радиуса 
. Для этого положим,
что рекуррентные соотношения (9.13) выполняются лишь для 
и вне гипершара последовательность
«залипает», т. е.
.
Таким
образом, последовательность, выйдя из гипершара, не может войти обратно.
Аналогично теореме 9.1, учитывая
условия выпуклости 
и
условия теоремы 9.2, можно показать, что справедливо неравенство
. (9.24)
Усилим
неравенство (9.24), для чего оценим величину
.
Воспользовавшись
неравенством 
,
получим
. (9.25)
Подставляя
(9.25) в (9.24), получим
. (9.26)
Из
неравенства (9.26) следует, что величина 
ограничена числом 
, не зависящим от номера 
. Покажем это.
Обозначим 
, 
. Покажем, что справедливо
неравенство
. (9.27)
Для
справедливость
неравенства легко проверяется:
.
По
индукции легко доказывается справедливость неравенства и для любого , если оно справедливо
для 
:
Остается показать, что величина ограничена, т. е.
. (9.28)
В
самом деле, в произведении (9.28) сомножитель 
ограничен, так как 
.
Сомножитель
также
ограничен, так как бесконечное произведение
ограничено
тогда и только тогда, когда сумма
ограничена.
Таким образом,
.
Используя
неравенство Чебышева, можно получить неравенство 
.
На множестве функция 
ограничена. Рассмотрим
процесс, отличающийся от (9.13) лишь тем, что при выходе за пределы он «залипает».
Очевидно, что все реализации исходного процесса, не покидающие , при этом сохранятся
и вероятность «залипания» меньше . Применительно к новому процессу можно
повторить все рассуждения теоремы (9.1) и показать, что с вероятностью,
превышающей 
,
для этого процесса
.
Отличие
лишь в том, что в лемме 2 величина 
есть вероятность того, что процесс за
первые шагов
ни разу не вышел из области и не вошел в 
. Получая, далее, что 
, приходим к выводу,
что с вероятностью, превышающей , процесс входит в . Остальные рассуждения повторяются,
по существу, без изменения.
Далее, соответствующим выбором величина может быть сделана
сколь угодно малой, откуда и следует утверждение теоремы.
