Комбинаторные методы в теории случайных процессов - Такач Л.
Скачать (прямая ссылка):
New York, 1959, pp. 276-299.
[36] T а с к 1 i n d S., Sur le risque de ruine dans des ieux
inequitables, Skand. Akt., 25 (1942), 1-42.
Г л а в а 8 ПОРЯДКОВЫЕ СТАТИСТИКИ
§ 37. ДРУГОЕ ОБОБЩЕНИЕ ТЕОРЕМЫ О БАЛЛОТИРОВКЕ
Классическую теорему о баллотировке, о которой шла речь в § 2, можно
сформулировать несколько иначе.
Предположим, что баллотирующийся кандидат А набирает а голосов, а
кандидат В набирает b голосов, причем все избирательные протоколы
равновероятны. Обозначим через ат и рг числа голосов среди первых г
бюллетеней, поданных за Л и за В соответственно. Пусть Pj - вероятность
того, что аг>р,рг точно для j
индексов среди г = 1, 2 а+b. Если р - неотрицательное целое
число и a^pb, то по теореме 1 § 2
р _ а ~ /i\
Га+ь- а + ь • U)
Интересно найти полное распределение {Ру}.
Мы докажем две комбинаторные теоремы, с помощью которых найдем Pj, j - 0,
1, ..., a + b, когда р - неотрицательное целое число.
Теорема 1. Пусть ku k2, ..., kn -целые числа, причем
kx + k2 + ... + kn=\. Тогда среди п циклических перестановок
множества (kx, k2, ..., kn) существует одна и только одна такая,
для которой точно j частичных последовательных сумм положительны (/ = 1,
2, ..., п).
Доказательство. Пусть kj+n - kj для j - 1, 2, .... Обозначим
dj = n(kx + ... + kj) - j
для / = 1, 2...... Тогда dj+n = dj для /= 1, 2........... Числа
dx, d2, ..., dn различны и dn = 0. Докажем, что если dt есть г-е по
величине число среди du d2, ..., dn, то циклическая перестановка (ki+x,
.. ., kl+n) имеет точно п + I - г положительных частичных сумм. Отсюда
будет следовать теорема.
Очевидно, что перестановка (ki+l, ki+1 + ki+2, ..., ki+x +/ .. . . .. +
ki+n) имеет столько же положительных членов, сколько (di+x - dlt di+2 -
dj, .. ., di+n - dj) неотрицательных. Действительно, если kl+1,+ . ..
+ki+I>0, то dl+l-dj = n(kl+1 + ... + k{+,) - j^O для j =1,2,..., п.
Обратно, если di+f-dj^ 0, to ki+1+ ... + ki+1>0 для /=1, 2, ..., п. Таким
образом, (kt+u kt+l + ki+2, ... ..., kl+x + ... + k{+n) имеет столько же
положительных членов,
174
Гл. 8. Порядковые статистики
сколько - d2-dh dn - dt) неотрицательных. Если dt есть r-е по величине
число в последовательности db d2, dn, то последняя содержит п + 1 - г
неотрицательных элементов. Теорема доказана.
Эту терему можно также доказать с помощью теоремы 2.1 из работы Спицера
[26] или теоремы 3 из работы Спарре Андерсена [3].
Из нее немедленно вытекает
Теорема 2. Если vb v2, ..., v" - циклически переставляемые случайные
величины, принимающие неотрицательные целые значения, и Д" - число
положительных частичных сумм среди V; + .. . + vr, г = 1, 2, .. ., п, то
для /= 1, 2, ..., п в предположении, что условная вероятность определена.
Теперь, используя теорему 2 и теорему 1 § 4, докажем следующую общую
теорему.
Теорема 3. Пусть vb v2, .. ., v" - переставляемые случайные величины,
принимающие неотрицательные целые значения, и пусть Nr = Vj + ... + vr, г
= 1, 2, ..., п. Обозначим через ^n число индексов г = 1, 2 п, для которых
Nr<r. Если k<n- 1, то
Р {А" = /К + ... +v"=l}=l/tt
(2)
P{An = j\Nn = k} = О
при /=0, 1, ..., n-k-l,
S(n-k-1 i (п - i)
T(ra-o''p{jV^/~1 lN"=k} npu i=n~k> •••> "-1. (3)
i = n-j +1
при j - n.
Кроме того,
Р{Ап = /|М" = п- 1} = 1 /"
(4)
для j = 1, 2, ..., n и P {Art = j \ Nn = n} =
n- 1
(5)
S г in - ii PWi = i~ 1 IMn = n) при j= 1, 2, 1.
J i (n - i)
§ 37. Другое обобщение теоремы о баллотировке
175
Доказательство. Заметим, что
Р {Л" = п I Nn = k] = 1 - k/п (6)
для k = О, 1п. Это в точности соответствует теореме 1 § 4. Далее,
Р{Ап = j\Nn = n- 1}= 1/и (7)
при /= 1, 2, . . п, что следует из теоремы 2, примененной
к случайным величинам Yi = 1 - vt, г = 1, 2, ..., п. В
дальнейшем
через А/ мы будем обозначать число индексов г=1, 2, ..., для которых Nr <
г.
Докажем сначала (3). Без ограничения общности можно предположить, что
число Nп - k фиксировано. Пусть j^.ti-1. Если АП = ]<п и Nn = k<n - 1, то
существует такое число г, что Nr - г - 1. Обозначим через / (г = 1, . .
., k + 1) наибольшее из этих чисел. Тогда Nl = i- 1 и Nr - Nt<r - i при r
= i+l, ..., п. Отсюда
р{л* = Д =
k+i
= 2 Р {Ni =i - 1} Р {А; =/+j-n \Ni = i- 1} Р {А" -Ai = n - i \N{ = i- 1}.
i ~ 1
(8)
Согласно (7), вероятность Р {Аг = г + j - п \ Nt = г - 1} равна 1 /г при
n - }<i^n и 0 в остальных случаях, а в силу (6)
Р{А" - Аг- = п - i | Nt = i - 1} = Р{А" - Дг = п-i \ Nn - Nt = k - i + 1}
= = (n - k - \)/(n - i) для /=1, ..., k+\. (9)
Таким образом, формула (3) доказана для 1. Если j<n - k,
то Р{А" = /} = 0. При j = n формула (3) сводится к (6). Итак, формула
доказана.
Формула (4) идентична с формулой (7).
Осталось доказать (5). Пусть число Nn = n фиксировано. Если А " =/, j =
1, 2, . .., п - 1, то существует число г = 1, 2, ..., п, для которого
Nr<r. Обозначим через, г наименьшее из таких чисел. Тогда Nt = i- 1, Nr^r
при г = 1, 2, . .., i - 1 и Nr<r точно для / индексов среди г = г, г+1,
..., п. Отсюда
Р {А" = Л =
