What is the probability of a tie vote?

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]
This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to What is the probability of a tie vote?

  1. Wilf says:

    In your formula for p(n) what is x? I expected p(n) to produce a number. Thanks!

    • You are correct that p(n) evaluates to a number; the notation used here describes extracting a coefficient from a generating function (specifically, an exponential generating function in this case). That is, the x is just a placeholder variable in a formal power series. The notation [x^n]g(x) means “the coefficient of x^n in the polynomial g(x); in the formula for p(n), the notation [x^n/n!]g(x) means “n! times the coefficient of x^n in g(x).”

  2. Wilf says:

    Thanks very much for the interesting article and the kind reply!

  3. Michael Earnest says:

    What an interesting find! With the group Russian roulette, the survival probability oscillated with a period that increased exponentially, and the peaks/troughs of the oscillation for this problem also seem to be getting further apart.

    To test this further, I thought about how to approximate the problem. The number of votes each person receives is approximately Poisson with parameter 1, so I thought about approximating the whole vote vector as n independent Poisson random variables, and finding the probability such a random vector has a tie for its highest entry. That is,
    P(tie)\approx 1-n\sum_{v=2}^\infty P(Z=v)\cdot P(Z<v)^{n-1},
    where Z\sim \text{Poi}(1). It seems like a good heuristic, as I have found the error in approximation is decreasing as n increases. Furthermore, the heuristic is much less complex to compute, so you can push the computation further, and see the same trend continue; oscillation of the probability, with exponentially decaying frequency. Just though that was interesting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.