The Experimental Mathematics of Voting By Shalosh B. EKHAD and Doron ZEILBERGER

Theorem 1 The weighted generating function of The Condorcet scenario 1 → 2 → 3 → 1 (with three candidates 1, 2, 3 and according to the weight

x_{123}^{NumberOf123} ⋯ x_{321}^{NumberOf321}t^{NumberOfV otes}

is

\frac{(1 + t^{3}x_{123} x_{231} x_{312}) t^{3}x_{123} x_{231}x_{312}}{(1 − t^{2}x_{123} x_{321}) (1 − t^{2}x_{213} x_{312}) (1 − t^{2}x_{312} x_{123}) (1 − t^{2}x_{132} x_{231}) (1 − t^{2}x_{123} x_{231}) (1 − t^{2}x_{231} x_{312})} .

Setting all the the x’s to one, we get that the enumerating generating function for one of the Condorcet scenarios is

\frac{t^{3} + t^{6}}{(1 − t^{2})^{6}} .

Hence the number of such scenarios with 2n − 1 voters is the coefficient of t^{2n−1} in \frac{t^{3}}{(1−t^{2})^{6}} , i.e. the coefficient of t^{2n−4} in (1 − t^{2})^{−6}, i.e. the coefficient of t^{n−2} in (1 − t^{−6}, i.e. (−1)^{n}\binom{−6}{n−2} = \binom{n+3}{5}. The total number of compositions is the coefficient of t^{2n−1} in (1 − t)^{−6}, i.e. \binom{−6}{2n−1} = \binom{2n+5}{5}. Hence assuming that all compositions are equally likely (a very wrong assumption), the probability of one of the Condorcet scenarios, with 2n − 1 voters is

\frac{(n − 1) n (n + 3)}{2 (2 n + 1) (2 n + 3) (2 n + 5)} .

So it tends to \frac{1}{16} as n → 16. What if each voter chooses one of the six alternatives with the same probability (i.e. 1/6)? Theorem 2: Suppose three candidates, 1,2, and 3, are running for office, and there are 2n − 1 voters, each of them choosing one of the 3!=6 possible ranking with the same probability (1/6). The votes are counted and it turns out that in the vote of 1 vs. 2, 1 won 2 vs. 3, 2 won 1 vs. 3, 3 won In other words, there is a cycle 1 → 2 → 3 → 1. Let a(n) be the probability of that happening times 6^{2n−1} (i.e. the numerator)

The integer sequence, a(n), satisfies the following linear recurrence equation with polynomial coefficients

−1296 \frac{n (2 n + 3) (2 n + 1) a (n)}{(n + 1) (n + 2)^{2}} + 36 \frac{(2 n + 3) (22 n^{2} + 33 n + 12) a (n + 1)}{(n + 1) (n + 2)^{2}}

−4 \frac{(19 n^{2} + 57 n + 45) a (n + 2)}{(n + 2)^{2}} + a (n + 3) = 0 .

The asymptotic expression for a(n) is 0.043869914022955 − 0.021101164 n^{−1} + O(n^{−2}) .

By symmetry, this is also the probability of the scenario 1 → 3 → 2 → 1. So doubling, the asymptotic expression for the probability of a Condorcet scenario is

0.087739828045910 − 0.042202328 n^{−1} .

Corollary: The probability for a strict Condorcet scenario with three candidates and 2n−1 voters tends as n → ∞ to a constant, that is approximately equal to 0.087739828045910 …, and that should be named the Condorcet constant.