§ 2. ЗАДАЧА О БАЛЛОТИРОВКЕ

Теперь мы хотим показать некоторые применения пуассоновских процессов и соответствующих порядковых статистик к анализу различных случайных величин, связанных с эмпирическими функциями распределения. Для этого мы сначала получим некоторые результаты, известные под названием задачи о баллотировке, которые представляют значительный интерес и ценность сами по себе.

Задача о баллотировке может быть сформулирована следующим образом.

При баллотировке (выборах) и общем количестве избирателей с кандидаты получают а и голосов соответственно, . В течение подсчета голосов лидерство кандидатов может все время меняться. Задача о баллотировке (в ее простейшем варианте) состоит в следующем: предполагая, что найти вероятность того, что кандидат А при подсчете голосов будет всегда впереди (хотя бы на один голос).

Непосредственное решение задачи о баллотировке следующее. Рассмотрим фиксированное размещение а символов символов В на окружности. Для данного размещения определим число начальных позиций, при отсчете от которых, скажем по часовой стрелке, символы А всегда будут лидировать в счете.

Чтобы найти эти позиции, исключим последовательно все соседние пары проходя для этого окружность, возможно, несколько раз. В результате останется символов А. Легко понять, что оставшиеся места и являются теми исходными позициями, при отсчете от которых символы А всегда лидируют. Отсюда следует, что вероятность того, что А всегда лидирует (возможное наблюдение является описанным размещением или одной из его циклических перестановок), равна Эта вероятность не зависит от выбора исходной последовательности. Отсюда вероятность того, что кандидат А всегда лидирует при подсчете голосов, равна

Проведенный анализ весьма элегантен. Однако, поскольку мы имеем в виду другие обобщения, сформулируем теперь задачу о баллотировке в терминах более общей «урновой схемы» и проанализируем ее структуру.

В урне а карт, на которых написан нуль, и карт, на которых написана двойка, а Карты вынимаются из урны одна за другой случайным образом без возвращения до тех пор,

пока не будет вынута последняя карта. Пусть случайная величина, равная числу, написанному на карте, Тогда задача о баллотировке будет решена, если найти

Это утверждение следует из того факта, что если среди первых чисел имеется а нулей и двоек то условие означает, что или Очевидно, (2.1) является вероятностью того, что это неравенство выполняется для

Чтобы найти вероятность (2.1), заметим сначала, что является набором из а нулей и двоек и все из возможных перестановок равновероятны. Это означает, что для любого и любого множества различных чисел из набора совместное распределение совпадает с распределением Говорят, что случайные величины обладающие таким свойством, перестановочны. (Независимые одинаково распределенные случайные величины являются перестановочными.) Тогда, поскольку

имеем

Поскольку перестановочны, все имеют одно и то же маргинальное распределение и, следовательно,

Используя этот факт, докажем теперь по индукции относительно с, что

Покажем сначала, что (2.4) справедливо для Но из того, что следует, что поскольку неравенство предполагалось в постановке задачи. Тогда, очевидно,

Утверждение (2.4) тривиально для поскольку в этом случае

Предположим теперь, что (2.4) выполнено для всех с Мы хотим доказать, что (2.4) справедливо также для

Пусть целое число, такое, что Тогда

так как неравенство всегда выполнено при с в силу условия (2.2). Но правая часть ляется выражением того же типа, что и левая часть (2.4) при условии вида (2.2). Действительно, в (2.4) заменены лишь с на и на Используя гипотезу индукции, где с и заменены соответственно на и получаем

Чтобы завершить доказательство, запишем

в силу (2.6). Но

в силу (2.1). Следовательно, из (2.7) вытекает, что

Таким образом, (2.4) выполняется для Это завершает доказательство.

Обобщение задачи о баллотировке состоит в предположении о наличии урны с с картами, на которых написаны числа такие, что

Если снова означает число на по счету карте, вынутой из урны без возвращения, то (2.4) для общего случая примет вид

Доказательство этого более общего утверждения можно провести, почти дословно повторяя доказательство (2.4). Мы опускаем детали. (Читателю предлагается провести доказательство самостоятельно.)

Дальнейшее обобщение ведет к следующей задаче. Пусть неотрицательные перестановочные случайные величины и

Пусть порядковые статистики для независимых наблюдений случайной величины, равномерно распределенной на отрезке

Рис. 1.

Предположим далее, что случайные величины не зависят от величин

Введем в рассмотрение ступенчатую функцию (рис. 1)

и поставим вопрос, чему равна вероятность того, что график не пересечет прямой (рис. 1). Аналитическая формулировка и решение этой задачи таковы:

Докажем (2.10) по индукции. При

поскольку распределена равномерно на

Предположим теперь, что (2.10) выполняется для Накладывая условия

и

найдем условную вероятность

Предположим сначала, что Тогда в силу (2.9) неравенство

будет заведомо выполнено при условии (2.11). Следовательно, вероятность (2.12) равна

в силу гипотезы индукции, поскольку при условии (2.11) являются порядковыми статистиками для независимых случайных величин, равномерно распределенных на

Далее, помня, что не зависит от при всех рассмотрим плотность

Тогда для

так как из (2.9) и перестановочности следует, что

При однако,

поскольку при условии (2.11) неравенство

выполнено быть не может. Далее, в силу (1.13) плотность величины равна

Тогда в силу (2.13) и (2.14) при

При очевидно,

Это доказывает равенство (2.10).

Мы теперь в состоянии дать некоторые приложения упомянутых идей к порядковым статистикам.