§ 6. Оценка скорости сходимости

Теоремы, установленные в §§ 3—5, дают достаточные признаки сходимости в том или ином смысле случайного процесса. При сопоставлении различных процедур существенно не только установить факт их сходимости, но и оценить их асимптотику, т. е. поведение процесса после большого числа шагов. Наибольший интерес при этом представляет оценка скорости сходимости «сверху», т. е. мажорирование изучаемого процесса некоторыми детерминированными и стремящимися к нулю функциями.

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

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

Начнем с рассмотрения оценок скорости сходимости математических ожиданий. Рассмотрим сначала способ получения оценок сверху. В теоремах о сходимости § 3 фигурировали случайные последовательности функций В первом условии этих теорем фигурировали неравенства

(см. формулу (8) условия А). Переходя в этом неравенстве от условных к безусловным математическим ожиданиям и полагая перепишем его в таком виде:

Все конкретные процессы метода потенциальных функций, рассмотренные в этой книге, при надлежащем выборе удовлетворяют неравенству (214). Кроме того, в этих процессах при некоторых дополнительных предположениях, которые каждый раз будут выясняться и оговариваться, оказывается справедливым также следующее неравенство:

где некоторая константа. Условие (215) в совокупности с условием (214) приводит к следующему неравенству, содержащему уже только математические ожидания функций

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

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

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

Тогда существует константа такая, что справедлива оценка

Доказательство теоремы XVI. Нам достаточно доказать справедливость неравенства (220) при пп. Действительно, если установлено существование такой константы что

то, выбирая новую константу

находим, что неравенство (220) справедливо при всех Поэтому доказательству подлежит соотношение (221).

Пусть сначала выполнено условие (218). Введем вспомогательную переменную

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

В соответствии с условием (218) это неравенство при может быть усилено:

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

Поскольку и сумма в правой части этого неравенства сходится при в силу (218), неравенство (223) можно усилить:

Возвращаясь к определению величин (формула (222)), устанавливаем выполнение соотношения (221).

Предположим теперь, что выполнено не условие (218), а условие (219), и докажем неравенство (221) по индукции. Пусть при некотором неравенство (221) выполнено, а именно, пусть

Покажем, что неравенство выполнено и при Действительно, в силу (217) и (224)

Но поскольку С 11,

и в силу (219)

Поэтому, усиливая неравенство (225), получаем

и тем самым устанавливаем, что из того факта, что (221) верно для некоторого следует, что оно верно и для Что же касается первого шага индукции, т. е. то справедливость (221) устанавливается очевидным неравенством

так что

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

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

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

Условие (227) вместе с утверждением теоремы XVI позволяет очевидным образом оценить сверху и математическое ожидание величины

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

позволяющее минорировать последовательность

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

Пусть, кроме того, существует последовательность положительных чисел 0 таких, что при выполнено условие

Тогда существует константа такая, что при справедлива оценка

Доказательство теоремы XVII полностью аналогично доказательству теоремы XVI в случае, когда

выполнено условие (218), если в этом доказательстве изменить смысл всех неравенств на противоположный.

В отношении теоремы XVII можно сделать замечание, аналогичное замечанию, высказанному в связи с теоремой XVI. Именно, неравенство (215) позволяет вместе с утверждением теоремы XVII оценить снизу не только математическое ожидание величины но и математическое ожидание величины

Таким образом, если одновременно выполнены условия теорем XVI и XVII, то для математического ожидания величины справедлива оценка

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

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

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

Определим еще множество как множество всех реализаций. Очевидно, что так что последовательность множеств монотонно не возрастает, а предельное множество есть множество всех тех реализаций, для которых последовательность величин мажорируется последовательностью Заметим теперь, что множеству в пространстве соответствует некоторое множество точек, выделяемое условием (235). Мы будем обозначать это множество точек тем же символом . Тогда на могут быть введены в рассмотрение следующие кратные интегралы — «ненормированные математические ожидания»

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

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

начиная с некоторого при всех достаточно больших С выполнены условия:

где В — константа, не зависящая от С.

Тогда для любого найдется такое число что

Замечание. Может показаться, что неравенство (239) для конкретных процессов практически невозможно проверить из-за сложности определения величин Однако, как будет показано в соответствующих разделах книги, в алгоритмах метода потенциальных функций условие (239) легко устанавливается из свойств алгоритмов.

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

Очевидно,

и

Докажем теперь вспомогательное неравенство

Для доказательства этого неравенства рассмотрим величину (см. формулу и оценим выражение условного математического ожидания

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

По определению множества интегралы вида

равны

Поэтому, учитывая, что

из (246) получаем

Вспоминая определение (формула и формулу (242) для и замечая, что

последнее неравенство можно записать в виде

эквивалентном (244).

Из условия 2° теоремы (формула и из доказанного неравенства (244) сразу следует

Введем теперь новые переменные соотношением

Формула (247) в этих переменных переписывается так:

Используя условие 1° теоремы (формула (238)), усилим это неравенство при

Суммируя неравенства (249) от до получаем

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

В последнем неравенстве учтено второе неравенство в (238) и тот факт, что Из неравенства (250), учитывая, что в силу (242)

получаем

Но поскольку

то выбором достаточно большого С можно одновременно

удовлетворить соотношения

что влечет в силу (251) неравенство совпадающее с (240). Теорема доказана.

В заключение настоящего параграфа рассмотрим вопрос о проверке условий доказанных выше теорем при их использовании для оценки скорости сходимости конкретных процессов метода потенциальных функций. Условия этих теорем требуют, во-первых, специального подбора мажорирующих (или минорирующих) последовательностей удовлетворяющих условиям (218) или (219), и, во-вторых, установления справедливости соотношений (217) и (239). Что касается подбора последовательностей то хотя здесь и не дается регулярный способ построения в конкретных случаях сами алгоритмы подсказывают естественный выбор этих последовательностей. Установление же соотношений (217) и (239) в этой книге будет производиться на основе следующей ниже леммы VI, учитывающей специфику алгоритмов метода потенциальных функций.

Лемма VI. Пусть для рекуррентных соотношений (154) с конечномерным вектором с выполнены условия теоремы XIV, причем минимум функции достигается в точке с. Тогда

1°. Если где -некоторая константа, то выполнено соотношение (217) с

2°. Если для каждого найдется такое, что

то для любого и любой последовательности где константа, не зависящая от С,

выполнено соотношение (239), где определяются из условий (236), (237) с

и

Замечание к лемме VI. Заметим, что условие пункта 2° леммы более слабое, нежели условие пункта 1°. Поэтому в тех случаях, в которых выполнено условие пункта 1°, справедливы утверждения как пункта 1°, так и пункта 2° леммы с

Доказательство леммы VI. Выполнение условий теоремы XIV, конечномерность вектора с и существование минимума функции гарантирует, что выполнены также и условия теоремы XIII. В условиях этой теоремы было доказано соотношение (145), которое в обозначениях этого параграфа имеет вид

где

В условиях теоремы XIV установлены неравенства (194), (195), из которых следует, что

где некоторые константы. Из неравенств (252) и (253) получаем неравенство

Поскольку то, начиная с некоторого (а именно, такого, что , из (254)

следует неравенство

Из неравенства (255) следует утверждение Г леммы VI, если в этом неравенстве перейти к безусловным математическим ожиданиям и воспользоваться условием

Для доказательства утверждения 2° леммы VI умножим обе части неравенства (255) на плотность вероятности и проинтегрируем по множеству на котором

Воспользовавшись обозначениями (236), (237), получим

Если обозначить

то на множестве при любом выполнено неравенство

Тогда в силу условия пункта 2° леммы VI найдется такая константа что на множестве при любом имеет место соотношение

Поэтому в интеграле, фигурирующем в правой части неравенства (256), можно заменить выражение выражением Произведя такую замену и воспользовавшись обозначением (237), приходим к неравенству (239), завершая тем самым доказательство утверждения 2° леммы VI. Лемма VI доказана.