Теорема Бертрана о выборах

В комбинаторике, Теорема Бертрана о выборах, названная в честь Жозефа Бертрана, который опубликовал её в 1887 году — утверждение, доказывающее ответ на вопрос «Какова вероятность того, что на выборах с участием двух кандидатов, в которых первый набрал p голосов, а второй набрал q < p, первый будет опережать второго в течение всего времени подсчета голосов?». Ответ на этот вопрос:

{\frac {p-q}{p+q}}

.

В своей публикации Бертран сделал наброски доказательства данной теоремы по индукции, и задался вопросом о том, может ли она быть доказана комбинаторными методами. Такое доказательство было предложено Д. Андре[1].

Пример

Предположим, есть 5 голосов, из которых 3 отданы кандидату A и 2 — кандидату B. В таком случае p=3 и q=2. Поскольку известен лишь исход голосования, то имеется 10 $\left(C_{5}^{2}\right)$ вариантов последовательностей голосов:

AAABB
AABAB
ABAAB
BAAAB
AABBA
ABABA
BAABA
ABBAA
BABAA
BBAAA

Для последовательности AABAB подсчет голосов будет выглядеть следующим образом:

Кандидат	A	A	B	A	B
A	1	2	2	3	3
B	0	0	1	1	2

Видно, что в каждом столбце количество голосов для A строго больше количества голосов для B, а значит, данная последовательность голосов удовлетворяет условию.

Для последовательности AABBA имеем следующее:

Кандидат	A	A	B	B	A
A	1	2	2	2	3
B	0	0	1	2	2

В данном случае, A и B сравняются после четвертого голоса, и поэтому данная последовательность не удовлетворяет заданному условию. Из 10 возможных последовательностей подходят лишь AAABB и AABAB. Поэтому вероятность того, что A будет опережать B в течение всего периода голосования, равна

{\frac {2}{10}}={\frac {1}{5}}={\frac {3-2}{3+2}}

в полном соответствии с предсказанием теоремы.

Доказательство по индукции

База индукции. Очевидно, теорема верна при p > 0 и q = 0: в данном случае вероятность равна 1, так как первый кандидат получает все голоса. Теорема также верна при p = q > 0: вероятность равна 0 из-за того, что количество голосов кандидатов сравняются хотя бы в конце подсчета.
Индукционное предположение. Будем считать, что теорема верна при p = a − 1 и q = b и когда p = a и q = b−1 при условии a > b > 0.
Индукционный переход. Тогда в случае с p = a и q = b последний подсчитанный голос принадлежит первому кандидату с вероятностью a/(a + b) и второму с вероятностью b/(a + b). Получаем, что вероятность первого быть впереди второго вплоть до последнего голоса равна

{a \over (a+b)}{(a-1)-b \over (a+b-1)}+{b \over (a+b)}{a-(b-1) \over (a+b-1)}={a-b \over a+b}.

.

Наличие у первого кандидата количества голосов строго большего, чем у второго после последнего голоса обеспечено условием p=a > b=q.

Таким образом, теорема верна для всех p и q таких, что p > q > 0.

Примечания

D. André, Solution directe du problème résolu par M. Bertrand, Comptes Rendus de l’Académie des Sciences, Париж 105 (1887) 436—437.

Ссылки

The Ballot Problem, Марк Рено

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] D. André, Solution directe du problème résolu par M. Bertrand, Comptes Rendus de l’Académie des Sciences, Париж 105 (1887) 436—437.