8
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ Your formula for $k=2$ is incorrect if $N$ is odd, in which case the answer is $0$. $\endgroup$
    – Tony Huynh
    Sep 4, 2017 at 21:53
  • 3
    $\begingroup$ You could perhaps argue that $\binom N {N/2}$ is zero for odd $N$... $\endgroup$
    – Ben Barber
    Sep 4, 2017 at 22:49
  • $\begingroup$ 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? $\endgroup$
    – user44191
    Sep 4, 2017 at 22:59
  • 1
    $\begingroup$ "where each voter votes randomly for one of the candidates" it turns out this is a very accurate model of real elections. $\endgroup$ Sep 5, 2017 at 0:04

3 Answers 3

7
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Edit: improved the bound. Now I think it is tight. $\endgroup$
    – Ron P
    Sep 5, 2017 at 14:24
  • $\begingroup$ 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? $\endgroup$
    – gb7688
    Sep 5, 2017 at 14:43
  • $\begingroup$ 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. $\endgroup$
    – Ron P
    Sep 5, 2017 at 15:38
  • $\begingroup$ 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. $\endgroup$
    – gb7688
    Sep 5, 2017 at 17:20
  • $\begingroup$ Edit: I've managed to correct my previous answer. It stills lack an explanation why we may assume iid. Also, a missing reference. $\endgroup$
    – Ron P
    Sep 8, 2017 at 4:16
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.