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$
  • 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 '17 at 21:53
  • 3
    $\begingroup$ You could perhaps argue that $\binom N {N/2}$ is zero for odd $N$... $\endgroup$ – Ben Barber Sep 4 '17 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 '17 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$ – PyRulez Sep 5 '17 at 0:04
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$
  • $\begingroup$ Edit: improved the bound. Now I think it is tight. $\endgroup$ – Ron P Sep 5 '17 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 '17 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 '17 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 '17 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 '17 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
    $\begingroup$ Is this supposed to be obvious? If not, some backup would be nice. $\endgroup$ – Igor Rivin Sep 5 '17 at 15:51
  • $\begingroup$ @IgorRivin Thank you very much for the comment! Will add more explanation. $\endgroup$ – Release the Christians. Sep 5 '17 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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