베르트랑(Bertrand)은 자신의 원래 논문에서 점화 관계(recursion relation)를 활용한 일반 공식을 바탕으로, 유리한 순서의 개수를 계산하는 증명 방법을 설명했습니다. 베르트랑 투표 정리에 따르면, 개표 과정에서 후보 A가 후보 B보다 항상 앞서 있을 확률은 다음과 같이 계산됩니다.
P = (p − q) / (p + q)
여기서 p는 A에 투표한 유권자 수, q는 B에 투표한 유권자 수입니다. 아래 예제를 통해 이 정리가 실제로 어떻게 적용되는지 살펴보겠습니다.
예제
총 5명의 유권자가 있다고 가정해 보겠습니다. 이 중 3명은 후보 A에게, 2명은 후보 B에게 투표합니다(즉, p = 3, q = 2). 이때 투표가 진행될 수 있는 순서는 총 10가지가 존재합니다.
AAABB
AABAB
ABAAB
BAAAB
AABBA
ABABA
BAABA
ABBAA
BABAA
BBAAA
순서 AABAB의 경우
투표 순서가 AABAB일 때, 개표가 진행되면서 집계되는 득표 수는 아래와 같습니다.
| 후보 | A | A | B | A | B |
|---|---|---|---|---|---|
| A | 1 | 2 | 2 | 3 | 3 |
| B | 0 | 0 | 1 | 1 | 2 |
각 단계에서 A의 득표 수가 항상 B의 득표 수보다 크므로, A는 개표 내내 B보다 엄격하게 앞서 있습니다.
순서 AABBA의 경우
반면 투표 순서가 AABBA일 때의 집계 결과는 다음과 같습니다.
| 후보 | A | A | B | B | A |
|---|---|---|---|---|---|
| A | 1 | 2 | 2 | 2 | 3 |
| B | 0 | 0 | 1 | 2 | 2 |
이 순서에서는 네 번째 표가 개표된 시점에 B가 A와 동수가 되어 버립니다. 즉, A가 B보다 항상 엄격하게 앞서 있다고 볼 수 없습니다.
결론
가능한 10가지 순서 중에서 A가 처음부터 끝까지 B보다 앞서 있는 경우는 AAABB와 AABAB, 단 2가지뿐입니다. 따라서 A가 항상 엄격하게 앞서 있을 확률은 다음과 같습니다.
P = 2/10 = 1/5
그리고 정리가 예측한 대로 이 값은 (p − q)/(p + q) = (3 − 2)/(3 + 2) = 1/5와 정확히 일치합니다. C나 C++ 프로그램으로 이 문제를 구현할 때도 동일한 점화 관계를 활용하면, 모든 순열을 일일이 검사하지 않고도 O(p + q) 시간 안에 확률을 효율적으로 계산할 수 있습니다.