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

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

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

Пример

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

• AAABB
• AABAB
• ABAAB
• BAAAB
• AABBA
• ABABA
• BAABA
• ABBAA
• BABAA
• BBAAA

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

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

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

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

${\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 ). Получаем, что вероятность первого быть впереди второго вплоть до последнего голоса равна

${\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.

Примечания

Ссылки