Комбинаторные методы в теории случайных процессов - Такач Л.
Скачать (прямая ссылка):
= и - <р(и). Неравенство ф (и) ^ и - ф (и) всегда выполняется. Кроме
того, ф (" + 0) = ф (") и почти всюду ф'(") = 0. Покажем сначала, что
ф'(и)<б(и) для почти всех и. (17)
Если производная ф'(и) существует и равна 0, то (17) с очевидностью
выполняется. Если ф' (и) существует, ф' (")>0 и ф(и + 0) = = ф (и), то
б(и)=1. В самом деле, если ф'(и)>0, то ф(и)>ф(и) для v>u и,
следовательно, ф (и) - inf {s - ф (s) для и ^ s ^ v} для всех v>u. Таким
образом, и - ф(п) ^ ф (и) ^ и - ф (и) для всех
v>u и, следовательно, и - ф (и + 0) =$Сф (и) ^ и - ф (и). Если
Ф (и + 0) = ф (и), то ф (и) = и - ф (и), откуда б (и) = 1. У тверждение
(17) вытекает теперь из того, что всегда ф'(и)^1.
Остается доказать, что
б(и)^ф'(") для почти всех и. (18)
Это очевидно, если б (и) = 0 и производная ф' (и) существует. Докажем,
что ф'(и)=1, если б(ы) = 1, ф'(") существует, ф' (и) = 0 и и - точка
накопления для множества D = {и: 6 (и) = 1, 0 ^ и < оо}. Предположим, что
u^D и и= lim ип, где ип е D и ипфи. Тогда
П~>°0
ф(и) = и -ф(и) и ф (ип) = ип - ф (ип). Если ф' (и) существует и ф' (и) =
0, то
^(и)= lim = j _ Ит ф(^фЫ= ! _фдц)= !. (19)
ОО
и~ип
Так как изолированные точки множества D образуют не более чем счетное
множество, то утверждение (18) доказано.
Одновременное выполнение неравенств (17) и (18) дает ф' (и) = = б (и) для
почти всех и. Используя (16), получаем отсюда (14) для ф(/)<!/, и теорема
доказана.
В доказательстве теоремы 5 мы использовали только то, что ф(и), 0 и <!/,
-неубывающая функция, для которой ф(0) = 0 и ф' (и) = 0 почти всюду.
Таким образом, справедлива и более общая теорема 1 § 1.
§ 3. Задачи
1-3
Заметим, что если определить б (и) так, чтобы 6(и)=1, когда v - ф (и) > и
- ф (и) для всех v> u, и 6(") = 0 в противном случае, то (14) все равно
будет выполняться. Далее, если и -точка разрыва ф("), то ф(и) может
принимать любое значение из отрезка [ф(" - 0), ф(м + 0)].
Доказательство теоремы 5 можно существенно упростить, если предположить,
что ф (и) имеет на [0, t] только конечное число скачков.
Итак, мы получили теорему 5 постепенным обобщением классической теоремы о
баллотировке. В свою очередь теорема о баллотировке немедленно следует из
теоремы 5.
§ 3. ЗАДАЧИ
1. При баллотировке кандидат А получает а голосов, а кандидат В получает
Ь голосов, причем все избирательные протоколы равновероятны. Найти
вероятность Р (а, Ь) того, что при последовательном подсчете число
голосов, поданных за А, все время более чем в ц раз превосходит число
голосов, поданных за В, где р, - неотрицательное целое число. •
2. При баллотировке кандидат А получает а голосов, а кандидат В получает
Ь голосов, причем все избирательные протоколы равновероятны. Найти
вероятность Q (а, Ь) того, что при подсчете число голосов, поданных за А,
всегда не менее чем в р раз превосходит число голосов, поданных за В, где
р - неотрицательное целое число.
3. При баллотировке кандидат А получает а голосов, а кандидат В получает
Ь голосов, причем все избирательные протоколы равновероятны. Пусть Ь < а
+ с, где с - положительное целое число. Обозначим через аг и fSr числа
голосов среди первых г зарегистрированных, поданных за А и В
соответственно. Найти вероятность Qc (a, b) = Р {рг < аг + с для г = 1,
2, ..., а+Ь).
4. При баллотировке кандидат А получает а голосов, а кандидат В получает
Ь голосов, причем все избирательные протоколы равновероятны. Пусть с - d
< b - а< с, 0 < с < d, где с и d - целые. Обозначим через аг и |3Г число
голосов среди первых г зарегистрированных, поданных за Л и В
соответственно. Найти вероятность Р = Р [с - d < |3Г - аг < с для r= 1,
2,..., а + Ь).
5. Доказать теорему 3 § 2 математической индукцией по п.
6. Доказать теорему 5 § 2 для случая, когда ф (и) имеет только конечное
число скачков в интервале (0, t).
7. Следующие три задачи являются вопросами 5669, 5744, 5804 в Educational
Times (1878) в июньском, сентябрьском и ноябрьском выпусках
соответственно (см. Уитворт [36]).
а) Человек выпивает в случайном порядке п стаканов вина и п стаканов воды
(все равного объема). Доказать, что вероятность того, что выпитое им
количество вина после каждого стакана не будет превышать выпитого им
количества воды, равна 1/(л + 1).
б) Пусть п мужчин со своими женами переходят мост в случайном порядке, но
так, что число перешедших мужчин всегда не превосходит числа перешедших
женщин. Доказать, что вероятность того, что ни один мужчина не перейдет
мост раньше своей жены, равна (п + 1)/2п.
в) Пусть человек, играя по постоянной ставке, выигрывает 2п + 1 игр и
проигрывает п + 1 игр. Доказать, что вероятность того, что он никогда не
будет беднее, чем в начале, и никогда не будет богаче, чем в конце игры,
равна nl(4n + 6).
8. Предположим, что при баллотировке кандидаты Aj, А2, ..., Ап получают
Oj, а2, ..., ап голосов соответственно. Пусть ai 7s а2 ^ ... 7S ап.
Обозначим
14
Гл. 1. Теоремы о баллотировке
через а^, а%\ а^ числа голосов среди первых г зарегистрированных, по-
