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

Question

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.

Answer 1

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})$.

Answer 2

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.

Answer 3

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$.