Комбинаторные методы в теории случайных процессов - Такач Л.
Скачать (прямая ссылка):
особо.
Материал данной книги основывается только на элементах теории
вероятностей и теории случайных процессов. Большинство представленных
здесь результатов получедо автором в течение последних шести лет,
некоторые из них опубликованы в ряде статей.
Пало-Альто
Лайош Такац
Глава 1 ТЕОРЕМЫ О БАЛЛОТИРОВКЕ
§ 1. ВВЕДЕНИЕ
В теории вероятностей часто возникает задача нахождения распределений
максимума случайных величин и верхней грани значений случайного процесса.
Цель настоящей книги состоит в том, чтобы показать, что для широкого
класса случайных величин и широкого класса случайных процессов такие
задачи можно решить элементарными методами на основе следующего обобщения
^классической теоремы о баллотировке.
Теорема 1. Пусть ф (и) - неубывающая функция при 0 ^ и ^ t, для которой
ф'(ы) = 0 почти всюду и ф(0) = 0. Пусть ф (t + u) - = ф (/) + ф (и) для 0
^ и ^ t. Определим на отрезке 0 ^ и ^ t функцию б (и), положив ее равной
1, если ф(у) - ф(ы) ^ v - и для u^v^u + t, и равной 0 в противном случае.
Тогда
если ф (t)^t ')•
Если ф(") -неубывающая ступенчатая функция при то ф(") имеет конечное или
счетное число скачков, ф'(") = 0 почти всюду, и поэтому теорема 1
применима. Если ф("), -
неубывающая непрерывная сингулярная функция, то ф'(") = 0 почти всюду, и
к таким функциям теорема 1 также применима. Примером может служить
лебегова сингулярная функция (Хьюитт и Стромберг [21, стр. 113]). Другой
пример для случая строго возрастающей сингулярной функции дан Секефальви-
Надем [32, стр. 198-200].
Следующая теорема является интересным частным случаем теоремы 1.
Теорема 2. Если kb k2, ..., kn-неотрицательные целые числа, ¦причем kx+
... + kn = k ^п, то для n - k из п циклических перестановок (ku k2, ...,
kn) сумма первых г элементов меньше г для всех г = 1, 2, ..., п.
*) Здесь t фиксировано, а равенство <p (t + и) =*<р (<) + <р (н)
определяет функцию ф (и) на отрезке [t, 21], - Прим. ред.
(1)
о
8
Гл. 1. Теоремы, о баллотировке
Если в теореме 1 положить t = n и 6, + ... + kr = q> (и) для г^ы<г+1, то
получится теорема 2. Обратно, с помощью подходящего предельного перехода
можно вывести теорему 1 из Теоремы 2.
Мы будем пользоваться теоремой 1 при нахождении явных формул для
распределений максимума случайных величин и верхней грани значений
случайного процесса. При нахождении некоторых предельных распределений мы
будем также обращаться и к таким теоремам, как слабый закон больших
чисел, к некоторым абелевым и тауберовым теоремам. Все эти теоремы
приводятся в дополнении. Иногда будет указываться, что некоторые
результаты можно получить, используя сильный закон больших чисел, теоремы
для рекуррентных процессов и теорему непрерывности для преобразований
Лапласа - Стильтьеса. Эти теоремы также приводятся в дополнении.
Используя упомянутые методы, мы сможем найти распределения максимума
случайных величин и верхней грани значений случайного процесса,
возникающих в теориях очередей, водохранилищ, запасов, страхования, в
физике, технике, в теории порядковых статистик, случайных блужданий,
азартных игр и т. д.
§ 2. ОБОБЩЕНИЕ КЛАССИЧЕСКОЙ ТЕОРЕМЫ
О баллотировке
Следующая теорема, которая достойна названия классической теоремы о
баллотировке, относится к 1887 г.
Теорема 1. Если при баллотировке кандидат А набирает а голосов, а
кандидат В набирает Ъ голосов, причем а ^ pft, где
р - неотрицательное целое число, то вероятность того, что при
последовательном подсчете бюллетеней число голосов, поданных за А, все
время более чем в р раз превосходит число голосов, поданных за В, равна
р =-а~гг (О
а + Ъ ' '
в предположении, что все возможные избирательные протоколы ')
равновероятны.
Заметим, что вероятность того, что число голосов, поданных за А, всегда
по меньшей мере в р раз больше числа голосов, поданных за В, равна
Q^J!±LzJ!!L. (2)
') Здесь под протоколом понимается вся последовательность бюллетеней,
поданных за кандидатов. - Пр им. ред.
§ 2. Обобщение классической теоремы о баллотировке
9
Можно легко доказать, что из формулы (1) следует (2) и обратно.
Вероятность (1) была найдена в 1887 г. Бертраном [8] для случая |i=l и
Барбье [6] для случая 1. Доказательство формулы (1) для р= 1 дал в 1887
г. Андрэ [5], а для ц>1 в 1924 г. Эппли [2, 3]. Другие доказательства
формулы (1) были даны в 1947 г. Дворецким и Моцкином [13], в 1950 г.
Гроссманом [18] и в 1961 г. Моханти и Нараяна [29].
В действительности же частный случай р = 1 можно отнести к 1708 г., когда
Муавр [11] изучал следующую задачу о продолжительности игры в теории
азартных игр. Два игрока А и В разыгрывают между собой последовательность
игр. В каждой игре, независимо от остальных, либо А выигрывает монету у В
с вероятностью р, либо В выигрывает монету у А с вероятностью q, причем p
+ q = 1. Предположим; что начальный капитал игрока А составляет а - b
монет, а у В капитал бесконечный. Какова вероятность того, что А
разорится на (а + Ь)-й игре?
Муавр нашел, что вероятность того, что продолжительность игры р равна а +
