Комбинаторные методы в теории случайных процессов - Такач Л.
Скачать (прямая ссылка):
Замечание. Если vu v2, vn - переставляемые случайные величины,
принимающие неотрицательные значения, то
п г
Р {N г> г для /¦=1,2 п} = Р{Д^,>1}-2] ^ ТЙ} Р {Nl = 7' ^ = Г) =
/¦ = 2 / = 2
= р {Л^, > 1} - 2] тт^ту Р{^"0,Nr = r)-
г = 2
5. Н,иже будем предполагать, что тип являются фиксированными взаимно
простыми положительными целыми числами. Рассмотрим избирательные прото-
256
Решения
колы с a - km голосами за кандидата А и b = kn голосами за кандидата В,
где k = 1, 2, ... . Обозначим через ф (k, /), j = I, 2, ..k, число
избирательных протоколов, для которых аг^а$г/Ь при /•=1,2 а + b и ar =
afir/b для j
индексов г = 1, 2, ..., а + Ь. Пусть
" 1, (mk + nk'
t-*¦
(т + ri) k \ mk
для k - 1, 2,.... Следуя Бизли [8], можно определить ф {k, /), 1^/^й,
следующим способом. Прежде всего,
k
C* = S уф(й>
j-1
если й = 1, 2,.... Действительно, если образовать все а + b перестановок
всех тех избирательных протоколов, для которых ar^a$r/b для г = 1, 2,
..., а + Ь, то, с одной стороны, получатся всевозможные избирательные
протоколы, а с другой стороны, избирательный протокол встретится ровно /
раз, если он представляет собой циклическую перестановку избирательного
протокола, для которого
ar ^ afir/b для г - 1, 2, ..., а + Ь иа, = а$г/Ь для j индексов г = 1, 2
а + Ь.
Поэтому
mk + nk\ (m + n)k .
mk ) = 2u j "Р
/=1
и утверждение доказано.
Далее, очевидно, что
Ф (*./) = 2 Ф (fei, 1) Ф (*2, 1) ••• Ф (*/, 1)
для j- 1, 2 k. Здесь kt, / = 1, 2............j, - положительные целые
числа.
Обозначим ф (й) = ф (k, 1); тогда два последних соотношения дадут
ОО / ОО
2 ф (А) 2* = 1 - ехр ( - 2 С*2*
\ *=1
для | 2 | < ттпп/(т + п)т+п, откуда
V с['ф ...c'j1
*(')' i (_|) /,!"•••/,1 '
/,+2 l2+...+klk-k R
где /= 1, 2,..., й, - неотрицательные целые числа.
Таким образом, если a -km и b = kn, где (т,п) = 1, то
Pa+b-i (а, 6) = Ф (*)/(а а*
Обозначив ф' (й) = ф (й, 1) + ф (й, 2) + ... + Ф (й, й), получим
Решения
257
для | г | < т'ппп/(т + п)т+п, откуда
Ф (*) = 2j
/,+2/2+ ...+kik=k
/-Д /Д /Д L1 l2 • • •
где }{, i=*l, 2,..., k, - неотрицательные целые числа.
Таким образом, если a = km и b = kn, где (пг, ri) = 1, то
а+6
(а, 6) = Ф* (*>/(" + *).
6. В соответствии с одним неопубликованным результатом Бизли, решение
можно записать в виде
Pj (а, Ь) = -г- ь ф (г) ф" (k - г) (i = 0, 1 а + 6-1),
\ а ) IHm+n) <r<k
где ф (г) и ф' (г) (г = 1,2,...) имеют то же значение, что и в решении
задачи 5, а ф* (0) = 1.
7. В данном случае 6а, - дискретная случайная величина, принимающая
значения a + b - 2j (/ = 0, 1,2,..., [(а + 6)/2] ). Покажем сначала, что
если распределение величины б*,, k (k = 1,2...) известно, то можно легко
найти распределение величины 6а, j. Если а > Ь, то
Действительно, если 26 есть наибольшее из чисел и отрезка [0, а+Ь], для
которых а (и) - р (и), то по теореме 1 § 2
Р {а (и) > р (и) для 2?<и<а + &|о (2k) = р (2k)} = ~а при 0 k ^ b и
Р("(2Ч.|И24)),(")(")/(" + "'
Если а<Ь, то Р {6a, г, = а + 6 - 2j] можно найти по симметрии.
Докажем теперь, что
Р{6а,а = 2/}=1/(а+1)
для / = 0, I, ..., а и а - 1, 2, ... . Легко видеть, что
Р {6а, о = 2/} = Р {а,- + а,-] > pr+ Р/--1 для 2j индексов /-=1,2 2а}
=
= Р {dp -t-dp-j >Р/- + P/--I для / индексов г = 2,..4.2а} =
*= Р {dp + d,-_i > р,- + Pp-i для j индексов г = 1,
3,..., 2а - 1} ="
*= Р {d2S-i > P2S-1 для / индексов s-1, 2,..., а}.
Последнюю вероятность можно выразить также следующим эквивалентным
образом. Обозначим через \Г (г = 1, 2 а + 1) число голосов, поданных за
кандидата В между (г - 1)-м и г-м голосами, поданными за А. (При г = 1
или г - а + 1 первая или вторая половина этого определения должны быть
опущены.)
258
Решения
Тогда vb v2, va + 1 - переставляемые случайные величины,' принимающие
неотрицательные целые значения, и V] + v2 + ... + va + I=a. Легко
проверить непосредственно, что
Р {6а, а = 2/'} = Р {v, + ... + vr<r для / индексов r= 1, 2...а).
Применив теорему 2 § 37 к случайным величинам V,- =1 - vr> r = 1, 2 а+ 1
получим Р {6а, а = 2/} = l/(a + 1) для / = О, 1,..., а.
8. Пусть рп будет тем из значений j = 0, 1, ..., п, при котором
функция ?/
достигает своего максимума. С вероятностью 1 существует только один
максимальный элемент. Тогда по теореме 6 § 37
Р {Д" = /}= Р {р" = j) = Р {?;<?/ для / - 0, 1, .... "} =
= Р{?у-?г>0 для г = 0, 1, ..., /'} Р {?,¦ - ?/ <0 для / = /, ..., п} =
= Р {А;- = 0} Р {Ап-у = 0},
откуда для всех п^О
П
2 Р{А/ = 0}Р{А"_/ = 0}=1.
/=о
Умножив это уравнение на zn и просуммировав для п - 0, 1, 2, ..., получим
2р(д,_")2/,
/=0
для 1 г | < 1 и, таким образом.
рЩ=")т(^)^г
для j = 0, 1,2,....
9. Событие (п) = может произойти в одном из следующих взаимно исключающих
случаев: существует такое число г [шах (0, j + k - n) <1 г <1 min (/,?)],
что среди величин ?lt •••> ?/-1 найдется г таких, которые меньше |/, и
для этого же числа г среди величин ?/ + ь |/ + 2> найдется ? -
г таких, кото-
рые меньше |/. Эти два события независимы. Вероятность первого события
