The probability of intransitivity in dice and close elections (Q2210747)

This paper studies probability of intransitivity in dice and close elections. Let \(G_i\) for \(i\ge1\) be a centered stationary Gaussian sequence with expectation \(E(G_iG_j)=\rho(i-j)\) for some correlation function \(\rho\) and \(\rho(0)=0.5\). For i.i.d. copies \(a\), \(b\), \(c\) for \(\{G_1,\cdots,G_n\}\) with correlation function \(s_H\) for any given \(H\in(0,1)\), it is shown that with high probability \(a\) beats \(b\) if and only if \(\sum_{i=1}^nF(a_i)>\sum_{i=1}^nF(b_i)\). Here, \(F(x)=\Phi(\sqrt{2}x)\) is the distribution function for \(G_1\) following the normal distribution with mean 0 and variance 0.5, and \(a=(a_1,\cdots,a_n)\) is a \(n\)-side die and similar definition applies to \(b\) and \(c\). The probability that these three dice are transitive tends to one as \(n\) goes to infinity. If \(S^{ab}\) is the number of voters that prefers \(a\) to \(b\) minus the number of voters preferring \(b\) to \(a\), let \(\varepsilon_d\) be the event that \(S^{ab}\le d\) for any \(a\) and \(b\). If \(n\) is odd, \(d\ge1\), \(y\in\{-1,1\}^k\), then it is proved \(|P(Y=y|\varepsilon_d)-2^{-k}|\le\alpha_k d^2/n+o_k(1)\), where \(Y\) is the random tuple encoding the \(k\) pairwise winners via sgn\((S^{ab})\) having \(k\) entries with values in \(\{-1,1\}\), \(\alpha_k\) is a function of \(k\) but not \(d\) or \(y\), and \(o_k(1)\) tends to zero and is only a function of \(k\).