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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В комбинаторике, Теорема Бертрана о выборах, названая в честь Жозефа Бертрана, который опубликовал ее в 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.

Примечания[править | править вики-текст]

  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.

Ссылки[править | править вики-текст]