Комбинаторные методы в теории случайных процессов - Такач Л.
Скачать (прямая ссылка):
= S Р {Ni = г - 1} Р{Аг- = 0 [Л^ = г- 1} Р {А"-Аг- = / \Nn - Nt = n~i+
1}.
1 = 1
(10)
Согласно (7), Р {Аг- = 0 | Nt = i - 1} = 1 /г при г = 1, 2, ..., п - 1.
Теорема 2, примененная к случайным величинам (vi+1- 1)..........(v"-
1),
176
Гл. 8. Порядковые статистики
дает Р{Д" -Дt = j\Nn-Nt = n-i + 1}= 1 /(n-i) для г= 1, 2, n-j, откуда
n-i
Р = /} = 2 TU^l) p M = * ~ 1} (П)
i = 1
при /= 1, 2, n- 1. Просуммировав равенства (11) для
j= 1, 2, /г- 1, получим
П - 1
1-Р{Д" = 0} = 2тР{^ = г-1}. (12)
г-i
Формула (5) вытекает теперь из (11) и (12). Теорема доказана.
С помощью теоремы 3 можно найти вероятности Pt, j =
= 0, 1, ..., а + Ь, когда а^цЬ, где 0 -целое число.
Теорема 4. Если а>рй + 1, то
Р 1 V (a-fcp-l) /sp + sWa + 6-sp-s-2\
/ I а + b \ L s (b - s) \ s - 1 / \ b - s - 1 J 1 '
{ a ) a+b~>
Ц+1
- < 5 < Ь
для j = 0, 1, ..., a + b - 1 и Pa+b = (a - b\i)/{a + b).
Если a =
= \ib + 1, to
Г-т+ь <14>
для j = 1, 2, ..., a + b. Если a = \ib, to
P - 1 V1 1 /sn + sWa + б - sp - s - 2 \
' (a + b\ L s {b - s) \ s - 1 / \ b-s-1 }
I a )о<.<"?±±
для j = 1, 2, ..., a + b - 1 и
P° = 1 "ТоЯТТ S 7(Г,5)(" + 67Д-8")- <16>
I "
Доказательство. Зададим случайные величины vr, r = = 1, 2, ..., a+ 6,
следующим образом: vr = 0, если r-й голос подан за кандидата А, и vr = p+
1, если r-й голос подан за кандидата В. Пусть Nr = V! + ... + vr для г =
1, 2, ..., а + Ь и N0 = 0. Тогда vb v2, ..., va+ft -переставляемые
случайные величины, принимающие неотрицательные целые значения, причем Vi
+ v2+ ... + va+6 = b (p + 1). Так как ЛГг = рг(р+ 1) и f = a, + p, для
г=1, 2 а + Ь, то ar>ppr тогда и только тогда, когда
§ 37. Другое обобщение теоремы о баллотировке
177
N,<r. Таким образом, Р; = Р{Д" = /' |iV" = k) можно найти с помощью
теоремы 3, положив в ней п - а + Ь, & = 6(р,+ 1),
( а НМ (М(в+*"Ч
Р {Nt - s (ц + 1" - V; j ' - ~ } (17)
при s = 0, 1, min(j, Ь) и Р{Аг = /'} = 0 в остальных случаях. Формулы
(13) -(16) получаются из соответствующих формул теоремы 3.
Существует другой метод нахождения вероятностей Pj, / =
= 0, 1 а + b. Он основан на следующей теореме Спарре
Андерсена [4] и Феллера [19].
Теорема 5. Пусть даны п вещественных чисел ch с2, ..., сп. Среди п\
перестановок последовательности (сь с2, ..., сп) число перестановок, у
которых точно k из п последовательных частичных сумм строго положительны
(неотрицательны), равно числу перестановок, у которых первый (последний)
максимальный элемент последовательности, состоящей из 0 и п
последовательных частичных сумм, встречается на k-м месте.
Доказательство. Удобно дать эквивалентную вероятностную формулировку
теоремы.
Пусть (|1; |2....|") - случайная перестановка последователь-
ности (с,, с2, .. .j сп), причем все п\ перестановок равновероятны.
Положим t,r = Ii + • • • +!/¦ Для r = 1. 2, .. ., п и ?0 = 0. Обозначим
через Д" число строго положительных чисел среди ?2> • • •> in и через Д"
число неотрицательных чисел среди ?lt ?3, ..., Пусть р" - индекс первого
максимального числа в последовательности ?0, т. е. рп = /, где /' -
наименьший из индексов,
для которых = max (?0, ..., ?"). Пусть р* - индекс последнего
максимального числа в последовательности ?0, ..., т. е.
р * = /, где / - наибольший из индексов, для которых ^ = == maxfto, ?").
Тогда
Р{Д" = А:} = Р(рп = А:} (18)
р{д; = ^} = р{Р; = ^} (19)
для k = 0, 1, ..., п.
Заметим сначала, что если заменить (сь с2 сп) на
(-с,, - с2, ..., - сп), то случайные величины Дп, Д*п, рп, р*
заменятся на п - Д*, п - Дп, " -p", п - рп соответственно.
В самом
178
Гл. 8. Порядковые статистики
деле, отображение (с^, а2 cO_>(-c,'i' ~СЧ ~Cin) Д°ка'
зывает, что верны первые два соотношения, а отображение {Civ d2, ...,
Cin)-*(~Cin, .... что верны вторые два.
Будем доказывать теорему по индукции. При п= 1 равенства
(18) и (19) очевидны. Предположим, что (18) и (19) выполняются для п- 1,
и докажем, что они выполняются для п.
Пусть С] + .. .+с"< 0. Тогда ?"<0. Так как ?0 = 0. т0 максимум
достигается не на последней сумме. Следовательно, все четыре случайные
величины Дп, Д*, рп, р* зависят от перестановок лишь из п- 1 элемента, а
тогда (18) и (19) выполняются по предположению индукции. Если с} + ... +
сп = 0, то Д" и р" зависят от перестановок лишь из п - 1 элемента и (18)
опять верно по предположению индукции.
Пусть теперь сх + ... +с">0. Тогда случайные величины п - Д*, п - Дп, п -
р', п - рп зависят от перестановок лишь из п - 1 элемента и снова
равенства (18) и (19) верны. Для случая Ci + ... + сп = 0 равенство (19)
также выполняется в силу предположения индукции для п - Д* и и -р*.
Теорема доказана.
Дадим более общую формулировку этой теоремы.
Теорема 6. Пусть |ь \2, ..., - переставляемые случай-
ные величины, принимающие вещественные значения. Пусть ?г = + ... + Ьг
при г = 1, 2, .. ., п и ?0 = 0. Обозначим через Д"
число положительных членов в последовательности ?2> •••> ?л> а через Дп
число неотрицательных членов в последовательности
