Комбинаторные методы в теории случайных процессов - Такач Л.
Скачать (прямая ссылка):
Ь, определяется по формуле
но не привел доказательства. Задача была полностью решена в 1775 г.
Лагранжем [22] и в 1812 г. Лапласом [23, стр. 228 - 242]. Вероятность
того, что в а + Ь играх А проигрывает а игр, а В проигрывает Ь игр, равна
и, следовательно, условная вероятность того, что А разорится на (а + Ь)-й
игре, если в а + Ь играх он проигрывает а игр, а В проигрывает Ь игр,
равна
р = ттт- (4)
Рассмотрим теперь последовательность из а + Ь игр в обратном порядке и
проигрыш А будем считать голосом, поданным За А, а проигрыш В -голосом,
поданным за В. Тогда сразу видно, что р = (а - Ь)/(а + Ь) есть
вероятность того, что при подсчете а + Ь голосов А все время ведет. Таким
образом, мы получили формулу (1) для |х=1. Интересно отметить, что Ампер
[4] считал формулу (3) замечательной по своей простоте и изяществу.
В 1879 г. Уитворт [36, 37] показал, что число способов упорядочить а
выигрышей и b проигрышей так, чтобы число проигрышей
(3)
10
Гл. 1. Теоремы о баллотировке
никогда не превосходило числа выигрышен, равно
а + 1 - b
а + 1
Отсюда следует формула (2) при р=1.
Классическая теорема о баллотировке эквивалентна следующей теореме.
Теорема 2. Если урна содержит а карт, отмеченных числом 0, и b карт,
отмеченных числом р+1, и если все а + Ь карт вынимаются из урны без
возвращения, то вероятность того, что для всех г - 1, 2, ..., а+Ь сумма
первых г вынутых чисел меньше г, равна
р='-4. (о
где п - а + Ь есть число карт в урне, k - b (р + 1) - сумма чисел на всех
картах, причем предполагается, что k^n и что все возможные выборы
равновероятны.
Легко видеть, что теорема 1 и теорема 2 эквивалентны. Действительно, если
среди первых г вынутых карт аг помечены числом 0 и рг помечены числом
р+1, то ar0 + pr (р + 1) < г = аг + ft. тогда и только тогда, когда
ргр<аг.
Последняя формулировка классической теоремы о баллотировке наводит на
следующее обобщение.
Теорема 3. Пусть урна содержит п карт, помеченных неотрицательными целыми
числами ku k2, ..., kn соответственно, причем kx + k2 + ... + kn = k ^п.
Все n карт вынимаются из урны без возвращения. Обозначим через \Г, r= 1,
..., п, число на г-й вынутой карте. Тогда
P{v,+ ... +\r<r для г = 1, ..., п}= 1 (7)
в предположении, что все возможные выборы равновероятны.
Эта теорема вытекает из следующей более общей теоремы.
Теорема 4. Пусть ku k2, ..., kn - неотрицательные целые числа, причем kl
+ k2+ ... + kn = k^.n. Для n - k из п циклических перестановок (kh k2,
..., kn) сумма первых г элементов для всех r= 1, 2, ..., п меньше г.
Доказательство. Положим kr+n = kr для r= 1, 2, ... и ФT = kx+ ... +k" r=
1, 2, ...; ф0 = 0. Пусть
f 1, если i - ф; > г - ф. для i > г,
п (8)
{ U в противном случае
И
= inf{/ - фр для i>r) (9)
§ 2. Обобщение классической теоремы о баллотировке
11
для г = О, 1, 2, ... . Очевидно, что 6r = фг+1 - фг. Так как фг+" = = фг
+ фп, то 6Г+" = 6Г и фг+" = фг + п - k для г = 0, 1, 2, .... Таким
образом, среди п циклических перестановок (kh k2, .. ., kn) точно
2 бЛ = Фя+1 ~^i = n-k (10)
r=1
перестановок таковы, что сумма их первых г элементов меньше г для всех г
= 1, 2, ..., п.
Из теоремы 4 следует, что среди п\ перестановок (kh k2, . .., kn)
существует точно (n-l)l(n-k) перестановок, у которых сумма первых г
элементов для всех г = 1, 2, .. ., п меньше г. Это замечание доказывает
теорему 3.
Теорему 4 можно переформулировать так. Положим ф(ц) = ф*, если i ^ и < i
+ 1, и пусть
1, если v - ф (о) ^ и - ф (и) для v^u,
М") = г, (Ш
1 (J в противном случае.
Формула (10) эквивалентна тогда формуле
П
| б (и) du - п - ф (п), (12)
если ф (п) ^ п. Это следует из того, что 6 (и) = 6 (г) при г < и < г + 1.
В последней формулировке теоремы 4 ф("), - не-
убывающая ступенчатая функция, равная нулю при и - 0. Естественно
возникает вопрос, остается ли верным равенство (12), если ф("), 0 ^ и ^
п, - произвольная неубывающая ступенчатая функция, для которой ф (0) = 0.
Докажем теорему, показывающую, что ответ на этот вопрос утвердителен.
Теорема 5. Пусть ф("), 0 ^ и - неубывающая ступенчатая функция,
удовлетворяющая условию ф(0) = 0. Определим ф(и) для 0^.и<оо, положив ф(и
+ t) = ф(и) + ф(0 при и^0, и пусть
( 1, если V - ф (п) ^ и - ф(и) для v^u,
6(U)H n (13)
( 0 в противном случае.
Т огда
г"("хгН'-.ф<,)' если (и"
J I 0, если ф
Доказательство. Если ф (/) > /, то 6 (и) = 0 для всех и > 0 и теорема
очевидна. Рассмотрим случай ф(^)</. Для и^0 положим
ф (и) = inf {о - ф (ц) для v^u). (15)
12
Гл. 1. Теоремы о баллотировке
Так как <р (и + t) = ф (и) + Ф (t) для и > 0, то ф (и + t) = ф (и) + t -
Ф (t) для 0. Более того, 0 < ф (v) - -ф (")< v - и для Таким образом, ф
(и) - монотонная неубывающая абсолютно непрерывная функция от и.
Следовательно, ф' (и) существует для почти всех и, 0<ф'(и)<1, и
t
J ф'(ы)^ы = ф(*) - ф(0) = / - ф(/). (16)
О
Докажем теперь, что ф'(") = б(и) для почти всех и, откуда и будет
следовать теорема. Заметим, что б(и) = 1 тогда и только тогда, когда ф(")
