3. Одномерная стохастическая аппроксимация

Теперь рассмотрим вопрос о сходимости метода Роббинса — Монро в общем случае, когда может принимать произвольные значения, а не только 1 или 0. Этот случай рассматривался Роббинсом и Монро [1], доказавшими сходимость итерационных значений в среднеквадратичном и по вероятности; Блюм [1] доказал сходимость процедуры почти наверное при довольно простых условиях. Рассматривал эту задачу и Каллианпур [1]. Дворецкий [1] доказал общий результат, который охватывает все ранее полученные. Его доказательство, упрощенное Вольфовицем [1], воспроизводится ниже. Дерман и Сакс [1] получили другое упрощение этого результата. (см. задачу 9 этой главы.)

Теорема 2. (Дворецкий). Пусть последовательности неотрицательных действительных чисел, такие, что

Пусть — действительное число, измеримые преобразования, удовлетворяющие условию

для всех Пусть действительные случайные величины. Положим

Тогда из условий

и

следует, что

Доказательство. Без ограничения общности мы можем взять

1) Из (4) и (6) следует, что для любого

2) Пусть если ни один из сомножителей не равен нулю, и если какой-нибудь из сомножителей равен нулю. Положим

Тогда ряд сходится с вероятностью единица в силу леммы (доказанной в приложении 2, § 4) и условий (6) и (7). Введем такое обозначение:

Для произвольных положительных существует такое что

3) Положим

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

она равна

Так как мы видим, что абсолютное значение выражения (10) не превосходит

Из соотношений (2), (9) и последнего утверждения следует, что для любых положительных существует такое, что для и

Теперь утверждение теоремы 2 вытекает из следующей теоремы.

Теорема 3 (Дворецкий). Пусть

(см. скан)

Для любого существуют неотрицательные удовлетворяющие условиям

и

равномерно по всем последовательностям для которых

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

и

с вероятностью единица Тогда

и

Доказательство. Снова положим и пусть — произвольные положительные числа. Чтобы доказать (10), достаточно показать, что

Пусть столь велико, что для Пусть столь велико, что и

Примем также, что это как раз то для которого имеет место соотношение (3).

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

Предположим, что выполнены следующие четыре условия:

Здесь Если то (17) имеет место для а (18) пусто (по окончании доказательства станет ясно, что не может быть равным бесконечности).

Из неравенства для а также из (15), (16) и (17) следует, что

Используя (4) с нулевыми значениями у, получим, что лежит между нулем и

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

Абсолютное значение (22) не больше, чем

Отсюда

Чтобы доказать (12), остается только показать, что два следующих условия:

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

Поэтому справедливо соотношение (3). Из (25) и (26) следует, что

Теперь можно применить рассуждения, которые использовались для доказательства (23), но с Y удовлетворяющими условию (3). После этого заключаем, что для всех абсолютное значение не превосходит величины

которая для достаточно больших становится отрицательной, а это противоречит (26). Этим завершается доказательство соотношения (10).

Пусть целое число, которое будет выбрано позже. В силу (10) для доказательства равенства (11) достаточно показать, что Пусть обозначает вероятностную меру, произвольное множество в пространстве выборок, которое может быть определено в терминах

Используем неравенство

которое может быть выведено из (4) и (9). Обозначим через множество для а через дополнение множества Применяя повторно неравенство (31), получим в конце концов верхнюю границу для (итерационный процесс начинается с а в качестве А используются соответственно множества

В каждом случае последний член подинтегрального выражения в правой части (31) обращается в нуль. Суммируя, мы получаем, что выражение

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

Отсюда в силу неравенства Минковского

Второй член в правой части этого неравенства может быть сделан произвольно малым, если выбрать достаточно большим. Первый член можно сделать произвольно малым, если выбрать достаточно большим, — так как

Это завершает доказательство соотношения (11).