It is time to vote for a new mathematics department chair. All 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 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.

Does the probability of a tie approach a limit as , 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 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 of a tie vote where candidates may vote for themselves is

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

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

Reference:

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

You are correct that 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 is just a placeholder variable in a formal power series. The notation means “the coefficient of in the polynomial ; in the formula for , the notation means “ times the coefficient of in .”

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,

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

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

You are correct that 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 is just a placeholder variable in a formal power series. The notation means “the coefficient of in the polynomial ; in the formula for , the notation means “ times the coefficient of in .”

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

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,

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