Приложение 3. НЕРАВЕНСТВА

1. Введение

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

Определение 1.

Определение 2.

Определение 3.

2. Неравенства, используемые в стохастической аппроксимации

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

где тогда

Доказательство. Для имеем

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

так как Таким образом, для

Обозначив левую часть неравенства через а правую часть через будем иметь

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

В противном случае для каждого имеем

Поэтому для

Таким образом, в любом случае

Лемма 2 (Буркхольдер). Предположим, что последовательность неотрицательных чисел, а последовательности вещественных чисел, такие, что для всех

где тогда

или, что эквивалентно,

Доказательство. Пусть По предположению такое существует. Можно указать такое, - что если то Таким образом, так как неотрицательна, то для

откуда, согласно лемме 1, следует (так как что

Так как — произвольное положительное число, имеем при

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

где тогда

Доказательство. Как и выше,

для всех действительных чисел сир; таким образом, для

Рассмотрим неравенство

В силу леммы 1 левая часть этого неравенства равна

Поэтому для всех достаточно больших не зависит от в) и некоторого с) будет решением этого неравенства. Отсюда для

откуда получаем

Обозначая через перепишем последнее неравенство в виде

Если для некоторого то для всех последующих это значит, что для этих

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

Таким образом, для

и ввиду того, что лемма доказана и в этом случае.

Лемма 4 (Буркхольдер). Допустим, что — неотрицательная числовая последовательность, последовательности действительных чисел, такие, что для всех

Тогда

Доказательство. В силу леммы 2 имеем

Докажем неравенство

из которого будет следовать, что

другими словами, мы получим требуемый результат.

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

В силу леммы 3

Итак, лемма доказана.

Лемма 5 (Чжун). Допустим, что является последовательностью действительных чисел такой, что для

где Тогда

Доказательство. Можно взять Имеем

Отсюда

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

Если для некоторого имеет место неравенство то оно же верно и для всех Последующих . В противном случае для каждого имеем

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

Лемма 6 (Чжун). Допустим, что последовательность действительных чисел, такая, что для

где Тогда

Доказательство. Если любое число, большее с, то

для всех Используя (1), получаем

Далее доказательство проводится так же, как и доказательство леммы 5.

Замечание. Если мы заменим с последовательностью положительных чисел, такой, что при то

Лемма 7 (Буркхольдер). Допустим, что последовательность неотрицательных чисел, а -последовательности действительных чисел, такие, что

где

тогда

Доказательство! Если то

и требуемый результат следует из леммы 2 и условия (i). Поэтому лемма 7 должна быть доказана лишь для

Для этого случая из леммы 2 и условия (i) следует, что

для некоторого или Таким образом,

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

Если то требуемый результат получен.. Если

ПОЛОЖИМ

Подстановка в неравенство (ii) приводит к соотношению

Если то требуемый результат получен. Если

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

Лемма 8 (Дерман и Сакс). Пусть последовательности действительных чисел, удовлетворяющие условиям

(i) неотрицательны,

(ii) , сходится и для всех больших некоторого имеет место неравенство

Тогда

Доказательство. Пусть положим

Возьмем и проитерируем (iii) до Мы получим

Так как

то

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

Из условий (i) и следует, что возрастает до значения В для достаточно больших Поэтому

Поскольку сходится и правая часть соотношения (3) может быть сделана произвольно

малой, если выбрать достаточно большим. Это завершает доказательство леммы.

Лемма 9 (Дерман и Сакс). Пусть такие же, как в лемме 8. Допустим, что

Тогда

Доказательство. Пусть достаточно велико, так что для Так как сходится, имеем для

В силу (ii) и того факта, что

имеем

После того как установлены соотношения (4) и (5), доказательство проводится так же, как в лемме 8.

Лемма 10 (Вентер). Пусть последовательности действительных чисел, такие, что

(a) Если последовательность неотрицательных чисел, такая, что для некоторого целого и всех

где , то

(b) Если вместо неравенства (4а) удовлетворяет условию

то и в этом случае все еще остается ограниченной.

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

Пусть . В силу условия (1) для некоторого целого и всех

Используя неравенство. которое имеет место для всех получим из (6) и (7) для

Аналогично, для

и из (1) следует, что

Используя неравенство выполняющееся для мы получим из (7) для

Отсюда для всех

Теперь положим и проитерируем (4а) в обратном направлении до Получим

В силу соотношений (8) и (3)

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

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

и при используя (10) и (3), мы получим соотношение (5),

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

получаем

для всех Так как правая часть этого неравенства конечна и не зависит от то ограничена.

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

Тогда для любого положительного целого

Доказательство. Из задачи 1 приложения 3 следует, что для любого фиксированного

Поскольку имеем для любого фиксированного

и для любого существует такое что

Возьмем Тогда из (1) и (2) следует, что

Отсюда следует требуемый результат.

Лемма 12 (Сакс). Пусть последовательность положительных действительных чисел. Пусть а каждого

Предположим, что для всех Тогда, если некоторое фиксированное положительное целое число,

Доказательство. Если положим в противном случае пусть наименьшее целое, большее, чем Для доказательства леммы достаточно показать, что

Если это выражение стремится к при Отсюда в силу леммы 11 последний член в соотношении (1) стремится к нулю при

Лемма 13 (Сакс). Пусть для всех Пусть последовательность действительных чисел, сходящаяся к где может быть равным и Тогда, если фиксированное положительное целое число,

Доказательство довольно просто, если заметить, что для любого фиксированного

Лемма 14 (Сакс). Пусть последовательность положительных чисел, такая, что

Пусть Тогда для любого положительного целого

Доказательство. Так как то утверждение будет доказано, если мы покажем, что

(см. скан)

Используя соотношение (1), видим, что для достаточно больших

где выбрано так, что для всех Таким образом, при и потому для доказательства того, что можно начинать внешнее суммирование в числителе Используя (1), имеем для

и

Таким образом, должно стремиться к нулю, так как для всех

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

Лемма 15 (Сакс). Пусть где удовлетворяет условию (1) леммы 14. Пусть а — действительное число, большее 1/2. Тогда для любого целого положительного и любого положительного

В частности, если то условие (1) записывается так

Доказательство. Пусть достаточно велико, так что в задаче 1 приложения для Тогда, используя задачу 1 и лемму 14 (условия леммы 14 выполнены, если принять во внимание сформулированные здесь условия и замечания, сопровождающие лемму 14), мы получим

где при Аналогичные выкладки дают неравенство

Так как при произвольно, получаем

для достаточно больших