# What are the odds of a tie in a random election with k candidates?

Consider an election with $N$ voters and $k$ candidates, where each voter votes randomly for one of the candidates. What are the odds of a tie?

Here "tie" means that multiple candidates get the highest number of votes, not necessarily that all candidates get the same number of votes.

For $k = 2$ the answer is given by ${N \choose {N/2}} \frac{1}{2^N}$.

I'm not sure how to generalize to $k > 2$. If a closed formula doesn't exist, can we still say something about the asymptotic behavior as $k$ grows?

Edit: asking for "asymptotic behavior" was ambiguous. The question I'm most interested in is: for $k \ll N$, what can we say about how the odds change if $k$ increases by $1$ (or, if it's a cleaner answer, if $k$ doubles). Perhaps it's incorrect to call this asymptotic behavior at all! And, unfortunately, I'm not sure what "$\ll$" should mean in this context. I suppose that's part of the question as well.

• Your formula for $k=2$ is incorrect if $N$ is odd, in which case the answer is $0$. – Tony Huynh Sep 4 '17 at 21:53
• You could perhaps argue that $\binom N {N/2}$ is zero for odd $N$... – Ben Barber Sep 4 '17 at 22:49
• With respect to asymptotics, you should keep both variables in mind. How are you changing $N$ as $k$ changes - or do you want to keep track of both for asymptotics? – user44191 Sep 4 '17 at 22:59
• "where each voter votes randomly for one of the candidates" it turns out this is a very accurate model of real elections. – PyRulez Sep 5 '17 at 0:04

For $1\ll k\ll N$, I would roughly estimate the probability of a tie by $O(\sqrt{(k\log k)/N})$. This is a very loose calculation. The number of votes to candidate $i$, $X_i$, is distributed $Bin(1/k,n)$. The loose part of this answer is assuming the $X_i$'s were mutually independent. I guess that it shouldn't change the asymptotic result (maybe this argument can be made precise by using that the $X_i$'s are negatively correlated).

I estimate the probability of the event $E_{i}=\{X_i=\max_{j\neq i}X_j\}$. Let $\mu$ and $\sigma^2$ be the expectation and the variance of $X_i$ respectively. By CLT, $\Pr(E_i)\sim \Pr(|Y-Z_{k-1}|<1/\sigma)$, where $Y$ and $Z_{k-1}$ are independent, $Y$ is standard normal and $Z_{k-1}$ is the maximum of $k-1$ iid standard normal random variables. The CDF of $Z_k$ is $\Phi^k(x)$, the PDF is $(\Phi^k(x))'=k\Phi^{k-1}(x)\phi(x)$, and the expectation is $\int_{-\infty}^\infty k\Phi^{k-1}(x)\phi(x)x\ dx$. Where $\Phi(x)$ and $\phi(x)$ are the standard normal CDF and PDF respectively.

Since $\phi(x)$ is Lipschitz, $\Pr(|Y-Z_{k-1}|<1/\sigma)=O(\frac 1 \sigma\int_{-\infty}^\infty (\Phi^{k-1}(x))'\phi(x)\ dx)$. Integrating by parts we get \begin{multline} \int_{-\infty}^\infty (\Phi^{k-1}(x))'\phi(x)\ dx = \left[\Phi^{k-1}(x)\phi(x)\right]_{-\infty}^\infty + \int_{-\infty}^\infty \Phi^{k-1}(x)\phi(x)x\ dx \\ = \frac 1 k \mathbb E[Z_k]\leq \frac {\sqrt{2\log k}}k, \end{multline} where the last inequality is a standard bound on the expectation of $Z_k$ (see https://math.stackexchange.com/a/89147/251766).

It follows that $\Pr(E_i)=O(\frac 1 \sigma \frac {\sqrt{2\log k}}k)$. Since $\sigma^2=N(1-\frac 1 k)\frac 1 k$, taking the union bound yields $\Pr(\cup E_i)=O(\sqrt{(k\log k)/N})$.

• Edit: improved the bound. Now I think it is tight. – Ron P Sep 5 '17 at 14:24
• This looks great. Sorry if this is obvious, but when you take the union bound, I would have thought that was equivalent to multiplying the bound by ${k \choose 2}$, but you seem to have multiplied it by $k{k \choose 2}$. Where does the extra $k$ come from? – gb7688 Sep 5 '17 at 14:43
• Tnx. That was a typo. I've corrected that. I see more serious problems with my answer. It is not true that the distribution of $X_1-X_2$ depends only on $L$ conditioned on $E_{1,2}$; it depends also on the maximum of the other $X_j$s. – Ron P Sep 5 '17 at 15:38
• For what it's worth, some simulation data I have aligns well with $O(\sqrt{k/N})$. So, +1 for it being a pretty good guess, even if the argument is loose. – gb7688 Sep 5 '17 at 17:20
• Edit: I've managed to correct my previous answer. It stills lack an explanation why we may assume iid. Also, a missing reference. – Ron P Sep 8 '17 at 4:16

For $k=3$ with $N$ not divisible by $3$, the probability of a tie is $$\sum_{m= \lceil N/3 \rceil}^{\lfloor N/2 \rfloor} \dfrac{N!}{m! m! (N-2m)!} 3^{1-N}$$ The sum seems not to have a closed form.

As for asymptotics, as $k \to \infty$ with $N>1$ fixed, the probability of a tie is greater than $1 - {N \choose 2} k^{-1}$, where ${N \choose 2} k^{-1}$ is the expected number of pairs of voters who vote for the same candidate. Thus if no two voters vote for the same candidate, there is an $N$-way tie among candidates who receive $1$ vote each.

In general, the probability is $$\frac{1}{k^N}\sum_{j=2}^k{k \choose j}\sum_{m=0}^{\lfloor N/j\rfloor}{N \choose mj}\frac{(mj)!}{(m!)^j}\sum_{\substack{(a_1,\dots,a_{k-j})\\a_1+\dots+a_{k-j}=N-mj\\0\leq a_i<m}}{N-mj\choose a_1,\dots,a_{k-j}}$$ where for some choices of $(N,k,m,j)$ the innermost sum is $0$. The variable $m$ is the same as in Robert Israel's answer. The winning candidates each receive $m$ votes. The variable $j$ is the number of winning candidates. Thus, we choose $j$ winning candidates out of the original $k$ candidates in ${k \choose j}$ ways, to each receive $m$ votes. Then we choose $mj$ voters out of the $N$ voters in ${N \choose mj}$ ways to vote for the winning candidates. Then we assign the $mj$ votes that go to the winning candidates to the $j$ winning candidates in $\frac{(mj)!}{(m!)^j}$ ways. Now, there are $N-mj$ votes left to go to the $k-j$ non-winning candidates, and each non-winning candidate receives a maximum of $m-1$ votes, thus the conditions on the innermost sum. The formula is also valid for $k>N$.

• Is this supposed to be obvious? If not, some backup would be nice. – Igor Rivin Sep 5 '17 at 15:51
• @IgorRivin Thank you very much for the comment! Will add more explanation. – Release the Christians. Sep 5 '17 at 17:24