Monthly Archives: January 2021

What is the probability of a tie vote?

Posted on by
4

This article was discussed on Reddit.

It is time to vote for a new mathematics department chair. All n=20 voting faculty members are on the ballot as eligible candidates… but no one really cares about the job, so each faculty member simply votes randomly, selecting a name uniformly at random from the n names on the ballot. The candidate receiving the most votes wins the election. What is the probability of a tie vote, that is, what is the probability that more than one faculty member receives the same maximum number of votes, requiring a runoff?

I found this problem interesting for a couple of reasons. First, the original version of the problem as presented to me was slightly different, where each candidate is excluded from voting for themselves (not only do they not care about the job, they actively avoid it). This seems significantly more difficult– or at least, much more computationally expensive– to solve. See the messy details at the end of this post.

The second interesting aspect of this problem was the potentially weird limiting behavior as the number of voting candidates grows large, as shown in the figure below.

Probability of a tie vote in an election vs. number of voting candidates.

Does the probability of a tie approach a limit as n \to \infty, or does it continue to persistently meander around? The latter would be really interesting, but perhaps not entirely unexpected: van de Brug, Kager, and Meester (see reference below) analyze the “group Russian roulette” problem, where at each time step, the survivors from an initial group of n people each shoot and kill a random other person. The probability that eventually there are no survivors (that there is a deadly tie for the win, so to speak), does not approach a limit, but instead repeatedly– but ever more slowly– varies up and down as the group size increases.

Following are my notes on the solution to both voting problems. First, the probability p(n) of a tie vote where candidates may vote for themselves is

p(n) = 1-\frac{n}{n^n}\sum\limits_{v=2}^{n}[\frac{x^n}{n!}]\frac{x^v}{v!}\left(\sum\limits_{k=0}^{v-1}\frac{x^k}{k!}\right)^{n-1}

If we constrain each candidate to vote for someone other than themselves, the resulting probability is the even more unpleasant

p^*(n) = 1-\frac{n}{(n-1)^n}\sum\limits_{v=2}^{n-1}\sum\limits_{k=0}^{n}(-1)^k [\frac{x^{n-k}}{(n-k)!}](

{{n-1} \choose {k-1}}\frac{x^{v-1}}{(v-1)!}\left(\sum\limits_{j=0}^{v-2}\frac{x^j}{j!}\right)^{k-1}\left(\sum\limits_{j=0}^{v-1}\frac{x^j}{j!}\right)^{n-k}

+ {{n-1} \choose k}\frac{x^v}{v!} \left(\sum\limits_{j=0}^{v-2}\frac{x^j}{j!}\right)^k\left(\sum\limits_{j=0}^{v-1}\frac{x^j}{j!}\right)^{n-k-1})

It’s unclear to me whether these exact formulas may be simplified, or whether they even help with analysis of asymptotic behavior.

Reference:

  1. T. van de Brug, W. Kager, R. Meester, The asymptotics of group Russian roulette. [arXiv]