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

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

p − q p + q {displaystyle {frac {p-q}{p+q}}} .

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

Пример

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

AAABB
AABAB
ABAAB
BAAAB
AABBA
ABABA
BAABA
ABBAA
BABAA
BBAAA

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

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

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

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

2 10 = 1 5 = 3 − 2 3 + 2 {displaystyle {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 ( a + b ) ( a − 1 ) − b ( a + b − 1 ) + b ( a + b ) a − ( b − 1 ) ( a + b − 1 ) = a − b a + b . {displaystyle {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.