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.



What are the odds of a tie in a random election with k candidates?
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})$. 


