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

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

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

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

Пример

Предположим, есть 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.

Ссылки

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