Преобразования случайных последовательностей и предельные теоремы для сумм r-независимых случайных величин тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Гч

Сг

^ На правах рукописи

- со

-

ГЛАДКОВ Борис Васильевич

ПРЕОБРАЗОВАНИЯ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ СУШ Г-НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ВЕЛИЧИН

01.01.05 - ."Теория вероятностей и математическая статистика"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1997

Работа выполнена в Московском государственном институте электроники и математики (технический университет)

Научный руководитель

Официальные оппоненты

Ведушдя организация

- доктор физико-математических наук, профессор Колчин В.Ф.

- доктор физико-математических наук, профессор Медведев Ю.И.

- доктор физико-математических наук Михайлов В.Г.

- Московский государственный университет им. М.В.Ломоносова, факультет Вычислительной математики и кибернетики

Защита состоится " 1997 г.

в час. на заседании диссертационного Совета

К 063.68.05 Московского государственного института электроники и математики по адресу: 109028, Москва, Большой Трехсвятительский переулок, 3/12.

С диссертацией можно ознакомиться в библиотеке МГИШ.

- (0 - ои^^/л

Автореферат разослан

1997 г.

Ученый секретарь

диссертационного Совета л

К 063.68.05 МГИШ

кандидат физико-математических

наук, доцент П.В.Шнурков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Впервые последовательности случайных величин, любые г из которых независимы, были рассмотрены Н.С.Бахваловым в 1964 году (Бахвалов Н.С. Об оптимальных оценках сходимости квадрируемых процессов и методов интегрирования типа Монте-Карло на классах функций // Численные методы решения дифференциальных и интегральных уравнений и квадратурные формулы. - М.: Наука, 1964.- С. 5-63.) и использованы при вычислении на ЭВМ определенных интегралов методом Монте-Карло с помощью реализаций г-независимых дискретных случайных величин , каждая из которых равномерно распределена на числовом множестве {m/N, m = 0,..,N-1 >, причем случайные величины £,г+1,..., являются функциями г исходных независимых случайных величин

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

Методом, изложенным в упомянутой работе Н.С.Бахвагова, а также методом, предложенным автором в С1], можно получать последовательности г-независимых случайных величин с произвольными одномерными распределениями.

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

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

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

Кроме того, многие алгоритмы крайне чувствительны к отклонениям распределения исходной последовательности в том

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

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

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

Методы исследования, в диссертации при доказательстве предельных теорем и получении оценок отклонения использовались метод усечения случайных величин и метод характеристических функций, а также оценки отклонения Эссеена и Берри-Эссеена.

Научная новизна. Результаты диссертации являются новыми. В диссертации решены следующие новые задачи:

- доказано, что в схеме серий сумма гп-независи-мых в п-ой серии случайных величин , п = 1,2,..; к =

= 1,..,МП, 2 < гп < Ип, при п, Ип, гп - 00 (и любой скорости возрастания гп) имеет то же самое предельное распределение, что и сумма 5п сопровождающих независимых в каждой серии

л»

случайных величин {£, } с такими же (произвольными) одно-

ПК

мерными распределениями - как при наличии гп первых моментов у случайных величин n-ой серии, - так и в общем случае без предположения о существовании моментов (задания совместных распределений размерности, большей гп, у случайных величин {г,пк> не требуется);

- получены оценки отклонения распределения линейной функции суммы г-независимых случайных величин от стандартного нормального распределения;

- при некоторых дополнительных условиях исследованы вероятности больших уклонений сумм гп-независимых случайных величин {£,nk> в схеме серий в узкой зоне нормальной сходимости при п, Nn, гп m и любой скорости возрастания гп ;

- найдены алгоритмы преобразования исходной последовательности независимых случайных элементов (величин), распределенных на некотором множестве, в новую последовательность независимых случайных элементов (величин) одинаково распределенных наконечном множестве S(m) = {slf...,s > с заданным произвольным распределением {й ,...,йт> или распределением в некотором смысле сколь угодно близким к заданному.

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

Апробация работы. Результаты диссертации докладывались автором на семинарах в МИАН им. В.А.Стеклова, на факультете ВМиК МГУ им. М.В.Ломоносова (1986 - 1988 гг.), на Конференции по вероятностным методам в дискретной математике (г. Петрозаводск, 1988 г.), на семинарах в Научно-исследовательском институте автоматики (1981, 1988, 1993, 1996 гг.) и в Московском государственном институте электроники и математики (1993, 1996, 1997 гг.).

Публикации. Основные результаты диссертации опубликованы в четырех работах, список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 21 наименование. Общий объем диссертации 86 страниц. В каждой главе диссертации принята своя нумерация параграфов, утверждений и формул. В автореферате первая цифра ссылки на то или иное предложение диссертации означает номер главы.

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В главе 1 рассматривается последовательность серий гп-независимых в п-ой серии случайных величин Че,пК>, п = 1,2,.., к = 1,..,ЫП, 2 < гп < Ып , и последовательность серий независимых в каждой серии сопровождающих случайных величин <£.пк> таких, что случайная величина £,пк имеет то же самое произвольное распределение, что и случайная величина £,пк. Без ограничения общности можно считать гп четным.

Задания совместных 1П-мерных (1П > гп + 1) распределений случайных величин <^пк> в п-ой серии не требуется.

Следующие два утверждения являются основными результатами главы 1.

"V

a) Если случайные величины ^пк и г,пк имеют все моменты или в п-ой серии гп первых моментов и для нахождения предельного распределения сумм

Ир ~

3 = 1Г . и Б = £ а п к=1 ^пк п к=1 <*пк

применим метод моментов, то суммы Бп и Бп имеют одно и то предельное распределение при п, , гп ■* "> и любой скорости возрастания гп (теорема 1.1).

b) Второе утверждение формулируется в виде теоремы, задающей достаточные условия асимптотической нормальности сумм Зп-

ТЕОРЕМА 1.3. Если в схеме серий последовательность распределений сумм Б= Е независимых в каждой серии равно-

П ПК

мерно бесконечно малых случайных величин {£.пк> с функциями распределения Упк(х) при п, °° слабо сходится к нормальному распределению с параметрами (а,б), то последовательность распределений сумм Б = £ . гп- независимых в

П ПК

п-ой серии случайных величин с теми же функциями

распределения Упк(х) при п, Ып, гп = 2гп ■*• 00 (и любой скорости возрастания гп) слабо сходится к тому же самому нормальному распределению.

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

Нахождение предельных распределений сумм Бп гп-неза-висимых случайных величин <£пк> производилось фактически при неполной информации о допредельных распределениях указанных сумм, поскольку задания совместных 1п-мерных (1п > гп + 1) распределений этих случайных величин в п-ой серии не требовалось. Однако условие гп-независимости случайных величин п-ой серии является столь сильным, что и при отсутствии полной информации нахождение некоторых (в частности, нормальных) предельных распределений сумм Б остается возможным.

В главе 2 получены оценки сверху отклонения распределе-

-1 N

ния линейной функции вида в Е - <х от стандартного

k=l к

нармального распределения, где В > О, <х - произвольные действительные числа, - г-независимые случайные

величины с произвольными функциями распределения, 2 < г < N, г - четно (теоремы 2.1 и 2.2). В качестве меры близости указанных распределений используется равномерная метрика (метрика Колмогорова)

Д = sup | Р-С В-1 £ - « < х } - Ф(х) |, xER к

где Ф(х) - функция распределения стандартного нормального

закона.

Существования моментов у случайных величин не предполагается, задания 1-мерных (1 > г+1) совместных распределений не требуется.

Получены также оценки указанного отклонения в случае существования моментов у случайных величин при

определенным образом заданных «ив (теорема 2.3).

Полученные оценки отклонения Д имеют вид: Д < 6(r,N). Выражения для 5(r,N), как и известные выражения для оценки отклонения в случае независимых случайных величин, - громоздки и поэтому в автореферате не приводятся. Однако во всех рассмотренных случаях 6(r,N) имеет явное выражение вплоть до числовых значений входящих в него постоянных (в том числе и постоянных из неравенств Эссеена или Берри-Эссеена). При замене указанных постоянных их оценками сверху возможно находить числовые значения S(r,N) при любых г и N.

В схеме серий для гп-независимых в п-ой серии случайных величин ■С£.пк> полученные оценки отклонения Д = Дп дают возможность оценить скорость сходимости в центральной предельной теореме для последовательности случайных величин -1

Вп £ е,пк- ап при п, гп, -» 00 и соответствующим образом выбранных вп > 0 и ссп.

В наиболее простом случае, когда случайные величины •{^пк> в п-ой серии распределены одинаково и имеют гп первых моментов (следствие теоремы 2.3),

б = бп = б(гп, Ып) = 0(1 Мъ).

При некоторых дополнительных условиях исследованы вероятности больших уклонений сумм гп-независимых случайных величин £.п1,...,£,пЫ в схеме серий при п, Ып, гп-* <» в узкой зоне нормальной сходимости (теорема 2.4).

При получении оценок существенным образом использовалась лемма 1.6.

В главе 3 предлагаются алгоритмы преобразования исходной последовательности независимых случайных элементов (величин) Ь = 1,2,...>, одинаково распределенных на некотором множестве X, в новую последовательность независимых случайных элементов 3 = 1,2,..Л. одинаково распределенных на конечном множестве 3(ш) = ...,зт> с заданным распределением ■Сй1,...,дт> (первый алгоритм - алгоритм А) или распределением в некотором смысле сколь угодно близким к заданному (второй алгоритм - алгоритм Всю). При этом заданное распределение и распределение элементов исходной последовательности должны быть связаны лишь некоторым

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

Условнее. При заданном распределении .....

распределение случайного элемент исходной последовательности на множестве X и само множество X обладают следующим свойством:

можно подобрать такое отображение ф: X ■» Э(т) и в X выделить такое множество Н, что

р = н> > о

и для т непересекающихся подмножеств

т

Н = -Сх: <р(х) = я е Э(т), х е Н>, (1 = 1,..,ш, и н = Н, дм. м.

(прообразов элементов в множестве Н при отображении ф)

имеют место соотношения

р = Н } = рй , р. = 1,..,ш,

ц Ъ р. д

или, что то же (поскольку Н^ С Н), условные вероятности

Р{гц.е н^е н> = Р<:це / к^е н> = 0ц, ц = 1,..,т.

Рассматривается только нетривиальный случай, когда распределение случайного элемента на множестве X дискретно и р = Н> < 1.

Алгоритм А. Время Г, затрачиваемое на формирование случайного элемента , з = 1,2..... не ограничено.

Если первый из случайных элементов

исходной последовательности, попадающий в множество Н, то полагаем \(;))= ) и переходим к формированию сле-

дующего случайного элемента \ .

Алгоритм В(к). Время Г(к), затрачиваемое на формирование случайного элемента , ограничено: ГСк) < к, где целое к>1 задано.

(1). Пусть к = 1. Тогда Р-СГ(1) = 1> = 1. В этом случае полагаем \(;|)= и переходим к формированию следующего случайного элемента

(П). Пусть к > 2. Если - первый из случайных

элементов ^......Ч+к-2 исходной последовательности,

попадающий в множество Н, то полагаем Ф^^))

и переходим к формированию следующего случайного элеме-

Если ни один из к-1 случайных элементов ^ • • • >^+к_2 не принадлежит множеству Н, то полагаем ф(г,ъ+к_1)

и переходим к формированию следующего случайного элеме-

В теореме 3.1 доказывается, что новая последовательность, полученная по алгоритму А в предположении, что условие С выполнено, - имеет заданное распределение на множестве Б(т), а число элементов исходной последовательности затрачиваемых на формирование одного элемента новой последовательности, - случайно и имеет геометрическое распределение с параметром р = Р-С^е Н>.

В теореме 3.2 доказывается, что новая последовательность, полученная по алгоритму В(к) (в предположении, что условие С выполнено), - имеет на множестве БОЮ распреде-деление сколь угодно близкое к заданному (сближение происхо-

дит при возрастании параметра к), а число элементов исходной последовательности <Ч>, затрачиваемых на формирование одного элемента новой последовательности, - случайно и имеет усеченное геометрическое распределение с параметром р.

В случае, когда исходная последовательность явля-

ется последовательностью независимых одинаково распределенных п-мерных случайных векторов с симметрично зависимыми компонентами, каждая из которых распределена произвольным образом на некотором множестве М с Л, |М| > п, предложенные алгоритмы А и В(Ю используются для формирования последовательностей независимых случайных подстановок степени п (размещений, сочетаний из п по Т элементов) с равномерным или сколь угодно близким '(в указанном выше смысле) к равномерному распределением на группе подстановок 5п (множестве всех размещений или сочетаний из п по Г элементов). При этом упомянутое выше отображение - <р: X -» БСт) , где

X = М", 3(т) = Б , т = п! , множество Н состоит из век-п

торов с попарно различными компонентами, а условие С выполнено, - следующим образом определяется процедурой построения вариационного ряда из компонент вектора Если случайный вектор принял значение х £ X , то ему ставится в соответствие подстановка степени п, нижней строкой которой является строка индексов вариационного ряда, составленного из компонент п-мерного вектора х. Если х е Н , то вариационный ряд выстраивается в единственном варианте). Если же х 0 И , то в алгоритме В(к) (при необходимости) одинаковые по величине компоненты вектора х можно располагать, например, в поядке возрастания их номеров.

Третий и четвертый алгоритмы, которые получили обозначения - У(Х)А¥ и У(Х)В(1°¥ соответственно, являются модификацией первых двух и позволяют из исходной последовательности независимых случайных элементов {¿ц., t = 1,2,...}, произвольным образом (без каких-либо дополнительных условий) одинаково распределенных с ненулевыми вероятностями на некотором конечном множестве 2 из N элементов, - получать новую последовательность независимых случайных элементов 3 = 1,2,...}, имеющую на другом конечном множестве г* из ш элементов (И, ш > 2 - произвольны) распределение равномерное (третий алгоритм) или в указанном выше смысле сколь угодно близкое к равномерному (четвертый алгоритм). Доказательство этих утверждений дается в теоремах 3.3 и 3.4.

При этом в качестве промежуточного звена в алгоритмах У(Х)А¥ и У(Х)ВСк:,¥ используется формирование последовательности подстановок степени п {т^^} с равномерным (или сколь угодно близким к равномерному) распределением на с помощью процедуры построения вариационного ряда из п (лексикографически) упорядоченных Ь-мерных векторов, составленных из элементов исходной последовательности , где

п - такое наименьшее натуральное число, что п! кратно т,

ь

а Ь выбрано так, что выполнено неравенство N > п. Тогда £*ш= <Кт^(;))) , где отображение ф: - г* таково, что каждый элемент множества г* имеет одинаковое число .прообразов в

Отметим, что непосредственно для формирования элементов новой последовательности не требуется даже задания распределения элементов исходной последовательности {г^}. Знание

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

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

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Гладков Б.В. Суммы случайных величин, любые г из которых независимы // Матем. заметки. - 1982. - Т. 32, вып. 3. - С. 385-399.

2. Гладков Б.В. Центральная предельная теорема даз^ для сумм случайных величин, любые г из которых независимы^ Дискретная математика. - 1989. - Т. 1, вып. 1. - С. 22-28.

(В переводе - Gladkov B.V. Central limit theorem for the sums of random variables any r of wich are independent // Discrete Mathematics and Applications. - 1991. - V. 1, N. 1. - P. 73-79.)

3. Гладков Б.В., Даценко-Чигорин А.Н. О некоторых преобразованиях случайных последовательностей // Дискретная математика.- 1994. -Т. 6, вып. 1.- С. 127-136.

(В переводе - Qladkov B.V., Datsenko-Chigorin A.N.

On some transformations of random sequences // Discrete Mathematics and Applications. - 1994. - V. 4, N. 2. - P. 163-170.)

4. Gladkov B.V. Estimates of the deviaton of the distribution of r-independent randcsn variables from the normal distribution. In: Probabilistic Methods in Discrete Mathematics. - Utrecht: VSP, 1997. - P. 199-210.

Подписано к печати 29,03.97 г. Зак.120 Объём I п.л. Тир.90 МГИЭМ. Москва, М. Пионерская ул.,12