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

• Круглов, Василий Игоревич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Круглов, Василий Игоревич

Введение

1 Пуассоновская аппроксимация

2 Рассматриваемые задачи

3 Апробация работы и публикации

4 Структура работы

5 Обозначения

6 Используемые методы

6.1 Теорема Б. А. Севастьянова

6.2 Метод Чена-Стейна.

6.3 Метод А. М. Зубкова

7 Полученные результаты

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

8 Постановка задачи

9 Комбинаторные свойства линейных соотношений

10 Вероятностные свойства линейных соотношений

11 Предельная пуассоновская теорема

12 Замечания и примеры

12.1 Группы вида где М -> оо и d= const.

12.2 Группы вида Zfj, где q - фиксированное простое число и d —» оо

12.3 Пример предельного сложного пуассоновского распределения.

13 Теоремы о сходимости к сложному пуассоновскому распределению

14 Статистические критерии

II Параллелограммы: общая часть

15 Геометрическая интерпретация линейного соотношения х3\ ~ ХП = Х3я ~~ ХМ

16 Ограничения, налагаемые на параллелограммы

17 Обозначения

18 Техническая лемма

19 Общие свойства

20 Предельная пуассоновская теорема

21 Лемма о распределении индикаторов

III Параллелограммы: ограничения на расстояния

22 Постановка задачи

23 Технические леммы

24 Метод Б.А. Севастьянова

24.1 Предельная пуассоновская теорема.

25 Метод Чена-Стейна

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

26 Метод А.М. Зубкова

26.1 Технические леммы.

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

IV Параллелограммы: ближайшие точки

27 Постановка задачи

28 Технические леммы

29 Доказательство предельной пуассоновской теоремы

Введение диссертации (часть автореферата) на тему «Предельные распределения чисел конфигураций, удовлетворяющих линейным соотношениям»

1 Пуассоновская аппроксимация

При решении вероятностных задач довольно часто возникает необходимость изучения сумм случайных индикаторов, то есть сумм случайных величин, каждая из которых принимает значения из множества {0,1}. Так, например, исследуя задачу о нагрузке на телефонную сеть, насчитывающую п абонентов, мы можем рассмотреть п случайных индикаторов, каждый из которых равен единице, если в данный момент соответствующий данному индикатору абонент пользуется телефонной сетью. Тогда общая нагрузка на сеть, т.е. общее количество активных в некий момент абонентов, будет равна сумме п введённых нами индикаторов.

Нахождение точного распределения суммы случайных индикаторов обычно представляет собой сложную задачу и, кроме того, точные формулы могут оказаться столь громоздкими, что это помешает сделать из них какие-либо выводы или применить их на практике. Поэтому практические задачи часто решают путём аппроксимации исследуемого распределения, то есть вычисляя такое распределение вероятностей, которое в том или ином смысле близко к распределению рассматриваемой суммы индикаторов и представляет собой более "простое" распределение вероятностей, например, нормальное распределение или распределение Пуассона. Правомерность данного подхода подтверждается не только работами в области теории вероятностей, но в том числе и исследованиями, проводимыми как в сфере прикладной математики (см., например, [24],[29]), так и в иных областях науки, таких как физика и биология ([33],[34],[20],[23]).

Самой известной теоремой о пуассоновской аппроксимации, по всей видимости, является классическая теорема Пуассона для схемы испытаний Бернулли (см., например, [15], т. 1, §6). Из данной теоремы следует в частности, что если телефонная сеть состоит из п абонентов, каждый из которых принимает решение воспользоваться телефоном независимо от остальных абонентов, и если для каждого абонента вероятность того, что он в данный момент использует телефонную сеть, фиксирована и равна р, причём число пр является сравнительно небольшим, то распределение нагрузки на телефонную сеть может быть достаточно хорошо аппроксимировано распределением Пуассона с параметром Л = пр.

Следует отметить, что эта теорема применима только к суммам независимых одинаково распределённых индикаторов, в то время как при решении практических задач исследователь может столкнуться как с зависимостью рассматриваемых индикаторов. так и с тем, что они будут иметь разные распределения, в таких случаях требуются иные методы пуассоновской аппроксимации, например, предложенные в работах Б.А.Севастьянова ([6],[14]), А.М.Зубкова ([2]), В.Г.Михайлова ([12]) или часто используемый в последнее время ([22],[31],[19],[21],[32]) метод Чена-Стейна (см., например, [17], [18]).

Список литературы диссертационного исследования кандидат физико-математических наук Круглов, Василий Игоревич, 2009 год

1. Глухов М.М., Елизаров В.П., Нечаев A.A. Алгебра: Учебник. В 2-х т. Том L М.:Гелиос АРВ, 2003. - 336 е., ил. 1.BN 8-85438-071-4

2. Зубков A.M. Неравенства для распределения суммы функций от независимых случайных величин. — Математические заметки, т. 22, номер 5 (1977), стр. 745758.

3. Ивченко Г.И., Медведев Ю.И. Математическая статистика. М.: Высшая школа, 1984.

4. Клыкова Н.В. Предельное распределение числа совпадающих промежутков. — Теория вероятностей и ее применения, 2002, т. 47, вып. 1, с. 147-152.

5. Кнут Д. Искусство программирования, том 2. Получисленные методы. — М.:000 "И. Д. Вильяме", 2007

6. Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. — М.:Наука, 1976.

7. Кострикин А.И. Введение в алгебру. Часть I. Основы алгебры: Учебник для вузов. — М.:Физико-математическая литература, 2000. — 272 с. — ISBN 5-92210017-3.

8. Круглов В.И. Обобщения задачи о числе одинаковых промежутков на двумерный случай. — Обозрение прикладной и промышленной математики, 2006, т. 13, вып. 6, с. 1030-1031.

9. Круглов В.И. Предельная теорема для числа упорядоченных подвыборок, удовлетворяющих линейному соотношению. — Обозрение прикладной и промышленной математики, 2007, т. 14, вып. 3, с. 499-500.

10. Круглов В.И. Предельные распределения числа наборов, удовлетворяющих линейному соотношению. — Дискретная математика, 2008, т. 20, вып. 4, с. 120-135.

11. Ленг С. Алгебра. М.:Мир, 1968.

12. Михайлов В.Г. Некоторые оценки точности пуассоновской аппроксимации для суммы зависимых случайных индикаторов. — Обозрение прикладной и промышленной математики, 1994, выпуск 4, том 1.

13. Севастьянов Б.А. Курс теории вероятностей и математической статистики. — М.: Наука, 1982.

14. Севастьянов Б.А. Предельный закон Пуассона в схеме сумм зависимых случайных величин. — Теория вероятностей и ее применения — 1972, т. XVII, вып. 4, с. 733 738.

15. Ширяев А.Н. Вероятность. В 2-х кн. — 3-е изд., перераб. и доп. — М.: МЦНМО,2004.

16. Aldoiis D.J. Probability approximations via the Poisson clumping heuristics. — Springer, New York, 1989.

17. Barbour A.D., Chen L.H.Y. An introduction to Stein's method. — World Scientific,2005.

18. Barbour A.D., Hoist L. Janson S. Poisson Approximation. — Oxford University Press, 2002.

19. Chatterjee S., Diaconis P., Meckes E. Exchangeable pairs and Poisson approximation.- Probability Surveys 2005, Vol. 2, 64-106

20. Coupier D. Two sufficient conditions for Poisson approximations in the ferromagnetic Ising model. — Annals of Applied Probability 2008, Vol. 18, No. 4, 1326-1350

21. Couronne O. Poisson approximation for large clusters in the supercritical FI\ model.- Markov Process. Related Fields 12, 4 (2006) 627-643

22. Eichelsbacher P., Reinert G. Stein's method for discrete Gibbs measures. -- Annals of Applied Probability 2008, Vol. 18, No. 4, 1588-1618

23. Ferrari P., Picco P. Poisson approximation for large-contours in low-temperature Ising models. — Physica A: Statistical Mechanics and its Applications Volume 279, Issues 1-4, 1 May 2000, Pages 303-311

24. Grubel R., Stefanoski N. Mixed Poisson approximation of node depth distributions in random binary search trees. —Annals of Applied Probability 2005, Vol. 15, No. 1A, 279-297

25. L'Ecuyer P. Tests Based on Sum-Functions of Spacings for Uniform Random Numbers. — Journal of Statistical Computation and Simulation, 59 (1997), 251-269.

26. Marsaglia G. The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness. — http://www.stat.fsu.edu/pub/diehard/

27. A statistical test suite for random and pseudorandom number generators for cryptographic applications. — NIST Special Publication 800-22http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22b.pdf

28. Pardoux E., Veretennikov A.Yu. On the Poisson equation and■ diffusion approximation 3. — Annals of Probability 2005, Vol. 33, No. 3, 1111-1133

29. Rollin A. On Stein factors and the construction of examples with sharp rates in Stein's method. — http://arxiv.org/abs/0706.0879

30. Schuhmacher D. Stein's method and Poisson process approximation for a class of Wasserstein metrics. — http://arxiv.org/abs/0706.1172

31. Schuhmacher D. Upper bounds for spatial point process approximations. — Annals of Applied Probability 2005, Vol. 15, No. IB, 615-651

32. Vergne N., Abadi M. Poisson approximation for search of rare words in DNA sequences. — http://arxiv.org/abs/0711.2382

33. Yucheng Hu, Xiang Peng, Tiejun Li, Hong Guo. On the Poisson Approximation to Photon Distribution for Faint Lasers. — http://arxiv.org/abs/math-ph/0609063.