Комбинаторные методы в теории случайных процессов - Такач Л.
Скачать (прямая ссылка):
222
Решений
Действительно, А все время лидирует с преимуществом большим, чем р:1,
тогда и только тогда, когда первый голос подан за него и, если не считать
этот голос, он ведет все время с преимуществом по крайней мере р : 1.
Сравнивая обе формулы для Р(а+ 1, Ь), получаем
что согласуется с формулой (2) § 2.
3. Пусть частица совершает случайное блуждание по оси х. Отправляясь
из начала координат, частица продвигается на единицу вправо, если
зарегистрированный голос подан за А, и на единицу влево, если
зарегистрированный голос
путей, не проходящих через точку х = - с. Число путей, состоящих из а
шагов в положительном направлении и Ь шагов в отрицательном направлении и
про-
жения. Рассмотрим избирательный протокол, для которого соответствующий
путь проходит через точку х = - с. После первого прохождения пути через
точку х = - с изменим последующие голоса на противоположные. Тогда мы
получим избирательный протокол, состоящий из b - с голосов за А и а А-с
голосов за В. Обратно, каждому такому избирательному протоколу отвечает
протокол, для которого соответствующий путь проходит через х = -с. Итак,
установлено взаимно однозначное соответствие между этими двумя
множествами
Если, в частности, с=1, то Q\(a, b) = (а+ 1 - b)/(a+ 1), что согласуется
С формулой (2) § 2, если положить там р = 1.
4. Обозначим через S0 множество всех избирательных протоколов,
содер-
жащих а голосов за А и b голосов за В. Их число равно
Вообще, через N (S) обозначается число элементов множества S. Пусть 5 -
множество всех избирательных протоколов, содержащих a - kd голосов за Л и
b + kd голосов за В, где k = 0, ±1, ±2 Тогда
Обозначим через 5* множество всех избирательных протоколов, содержащих Ь
- с - kd голосов за Л и а + с + kd голосов за В, где k - 0, ±1, ±2 Тогда
" , . а + 1 - \ib
Q (а, Ь) =---------------- -р
а + 1
подан за В. Для а + Ь шагов возможны
путей. Нам надо найти число
ходящих через точку
Это следует нз притциза отра-
избирательных протоколов. Всего таких протоколов искомая вероятность
равна
Таким образом,
Qc (а, Ь) =
k
N (5*)= У ( а + Ь \
' X\a + c + kd)¦
Решения
223
Множество всех избирательных протоколов, содержащих а + Ь голосов, можно
разделить на два непересекающиеся подмножества: подмножество С,
содержащее те избирательные протоколы, для которых с - d <$г - аг <с при
всех г = 1, 2а + Ь, и подмножество С, содержащее остальные избирательные
протоколы. Искомая вероятность, очевидно, равна
N(S0C) N (SC) N(S)-N(SC)
N(S0) N (S") M(S") •
Докажем теперь, что N (SC) = N (S'). Если избирательный протокол
принадлежит множеству SC, то существует наименьшее из чисел г (г = 1,
2,..., а + Ь), для которых либо р,- - аг = с, либо р,- - аг = с - й. Если
это наименьшее число равно j, изменим ()+1)-й, (/ + 2)-й, ..., (а + Ь)-й
голоса на противоположные. Новый избирательный протокол будет тогда
принадлежать множеству S*. Обратно, если избирательный протокол
принадлежит S*, то существует такое наименьшее г, что либо Р,- - аг = с,
либо рг - аг = с - d. Если этот наименьший индекс равен j, изменим ()+1)-
й, ()+2)-й, ..., (а+Ь)-й голоса на противоположные. Тогда новый
избирательный протокол будет принадлежать множеству SC. Мы установили
взаимно однозначное соответствие между элементами множеств SC и S*.
Следовательно, N (SC) = N (S*), и формула (1) дает
M(S)-M(S') 1 Y|7fl + M ( а + ь Х\ т
N (S0) ( а+Ь \ ?л\_\а - kaj \a + c + kd) J'
1 а ) *
5. Положим Nr = Vj + ... + vr для г-l,..., п. Нам надо доказать, что
Р (Nr < г для г = 1, ..., п} = 1 - ^ (1)
при k = 0, 1,..., п. Для п = 1 равенство (1) очевидно. Предположим, что
оно верно для п- 1. Докажем, что тогда оно верно и для п. Отсюда
утверждение для n> 1 будет следовать по индукции. При k - n соотношение
(1) выполняется. При k < п по предположению индукции
Р (Nr <г для г = 1,..., п- 1 | M"_i =/}== 1 - 'nL\
для / = 0, (,..., п - 1, где условная вероятность определена с
точностью до
эквивалентности. По теореме о полной вероятности
п-1
Р {NT<r для г - 1, ..., ^1 - Р (Nn-\ =/} =
Здесь мы использовали тот факт, что v. (г = 1, 2 п) имеют
одинаковые математические ожидания. Так как Vf + ... + vn = k, то.Е
{v(.} = й/n для i = 1, 2 п.
6. Случай ф (t)>t тривиален. Пусть ф (t) ^ t. Если ф (и) = inf (о - ф (и)
для v^u], то ф (и) - непрерывная неубывающая функция от и и ф(?) - ф (0)
= t-q>(t). Так как ф(и) в интервале (0, t) имеет только конечное число
скачков, этот интервал можно разделить на конечное число таких
непересекающихся интервалов, что в них либо б (и) = 1, либо б (и) = 0.
Если б (и) - 1 в интервале (а, Р), то ф (и) = и - ф (и) при а < и < р.
Тогда ф (и) в (а, Р) не имеет скачков, т. е. ф (и)
224
Решения
в (а, Р) постоянна, и следовательно, ф (р) - ф (а) = р - а. Если б (и) =
0 в интервале (а, р), то ф (Р) - ф (а) =0. Поэтому в интервале (0, t)
функция 6 (и) равна 1 на множестве меры ф (t) - ф (0) = t - ф (t).
7. (а) Можно поставить задачу иначе: если при баллотировке оба кандидата
