Puzzle:
Many election methods for N-candidate elections with rank-order ballots,
as their first step, compute the "pairwise table" giving the "margin" by which A defeats
B (i.e. the number of voters who prefer A>B minus the number who prefer B>A,
for every A,B).
Suppose all V votes are independent random orderings (all N! orderings equiprobable) with V very large.
a. The upper-triangle of the matrix is an (N-1)N/2-dimensional zero-centered Gaussian distribution. (Note: not N² dimensional, because the diagonal of the matrix is all-zero and the lower triangle is determined by antisymmetry from the upper triangle.) The "Gaussian" is a result of the central limit theorem in the V→∞ limit in this (N-1)N/2-dimensional space.
The entries in a given row or column of the matrix are correlated. Specifically, if V_{AB} is a ±1-valued coin-toss random deviate indicating for some voter indicating whether she prefers A over B or the reverse, then its mean is E(V_{AB})=0 and its variance is var(V_{AB})=1. Because once we know a voter prefers A>B, the probability is 2/3 she prefers A>C [consider the three possibilities A>B>C, A>C>B, C>A>B], we have that correl(V_{AB},V_{AC})=1/3=2/3-1/3. Therefore (now applying the central limit theorem to these votes after rescaling and translating everything appropropriately) in the limit of a huge number of voters we get that the mean of each off-diagonal matrix element's Gaussian is 0, its variance is 1, and the correlation between any two different Gaussians in the same row (or in the same column) of the upper triangle is 1/3.
b. The naive slow algorithm, running in O(N!·N^{2}) steps, would be to generate a (standard Gaussian random) vote-count for each of the N! different possible kinds of vote, then add the resulting N! matrices (each N×N) together. That generates the correct (N-1)N/2-dimensional Gaussian distribution.
There is an interesting faster algorithm. If N=1+p, where p is prime, then instead of using N! vote types it suffices to use (N-2)(N-1)N. (And if N≠1+p that is ok; simply increase N to the next suitable value by adding extra fake candidates. Because of standard number-theoretical results about "prime gaps" and polynomial time primality testing, this won't increase the runtime bound by more than a constant factor; nor will it alter the correctness of the statistical distribution.)
The (N-2)(N-1)N permutations are precisely the members of the triply-transitive permutation group SL_{2}(p) got as follows. Let the N items being permuted be {∞,0,1,2,...,p-1}. The permutations are then precisely the degree-(1,1) rational bijections
E.g. see George Mackiw: The Linear Group SL(2,3) as a Source of Examples, The Mathematical Gazette 81,490 (March 1997) 64-67.
Why does the subgroup SL_{2}(p) generate the (same) correct (N-1)N/2-dimensional Gaussian distribution as the full N!-size group? Because all its covariances are the same. Specifically:
But there is a much simpler and faster algorithm still: Let X_{ab} (for 1≤a≤b≤N) be (N+1)N/2 independent standard normal random variables, then Margin_{ab}=X_{aa}-X_{bb}-X_{ab} for a≠b. Thus: Direct an edge in the defeat-tournament from a to b if X_{aa}-X_{bb}>X_{ab} and from b to a otherwise. This is an incredibly simple O(N²)-time algorithm and the space usage may even be reduced to O(N) by only handling one row of X at a time (but storing the diagonal of the X matrix always). (The correctness of the algorithm is again because it produces the correct pairwise correlations – namely 1/3 – that is straightforward to check.)
INCREDIBLY SIMPLE ALGORITHM TO GENERATE NxN Margin Matrix (and defeat matrix): for a from 1 to N { diag[a] = RandNormal(); MarginMat[a][a] = 0.0; DefeatMat[a][a] = 0; } for a from 1 to N-1 { for b from a+1 to N { x = RandNormal(); y = diag[a] - diag[b] - x; MarginMat[a][b] = y; MarginMat[b][a] = -y; if(y>0.0){ DefeatMat[a][b] = 1; DefeatMat[b][a] = -1; } else{ DefeatMat[a][b] = -1; DefeatMat[b][a] = 1; } } } NOTE the margin matrix will be correct up to a scaling factor.