Consider a game where n players choose one of them to be leader. You vote for exactly one player, which can be yourself. The player who gets the most votes wins (plurality voting). If no player gets more votes than all other players, it's a tie.

If you vote randomly (equal chance of voting for each player, including yourself) and so do the other players, what is the probability of a tie?

For n=0, there are no players and no votes, so technically "no player gets the most votes" and it's a tie. P(0) = 100%

For n=1, there is one player and they must vote for them self. With one vote, they have the most votes. P(1) = 0

For n=2, there are two players (call them A and B). A can vote for either A or B, and B can vote for either A or B. So there's 4 vote combinations total (AA, AB, BA, BB), and 2 of them are ties (AB, BA). P(2) = 2/4 = 50%

For any n, the total number of vote combinations is n^n, since each player has n ways to vote and there are n players.

For small n, we can manually count the number of ways to achieve a tie/win. For larger n, it's a bit trickier - maybe there isn't a simple formula?

For n=3, there are n^n=27 vote combinations total. There are 6 ways to get a tie (ABC, ACB, BAC, BCA, CAB, CBA). P(3) = 6/27 = 2/9 = ~22.2%

If each player receives one vote, it's a tie. This can happen n! ways - it's the permutations of who casts which vote. For n=2 and n=3, this is the only way to get a tie, so the "n!" formula works. But for n>=4, there are more ways to tie, such as 2 players each getting 2 votes.

From manually counting and a few shortcuts, I think we have:

P(4) = 60/256 = 15/64 = ~23.4%

P(5) = 1020/3125 = 204/625 = ~32.6%

For n=0,1,2,3,4,5

P(n) ~= 100%, 0%, 50%, 22.2%, 23.4%, 32.6%.

Does this sequence even converge? Might have to write some code to find out.

I wrote some code to find P(n) for larger n and got these results:

P(6) = 19020/46656 = ~40.8%

P(7) = 372540/823543 = ~45.2%

P(8) = 7839160/16777216 = ~46.7%

(For n = 0 through 5, I got the same results as I found manually.)

Here's the python code I used:

It simply checks every single vote combination to count how many are ties. It takes a while to find P(8), takes too long to find P(9).

import sys
from collections import defaultdict as ddict
def all_combos(pcount, vcount=None):
if vcount is None:
vcount = pcount
if pcount is 0:
yield ()
return
for i in range(vcount):
for combo in all_combos(pcount - 1, vcount):
yield (i,) + combo
def is_tie(combo):
totals = ddict(int)
for vote in combo:
totals[vote] += 1
counts = sorted(totals.values(), reverse=True)
if len(counts) is 0:
return True # Nothing voted for = technically a tie
if len(counts) is 1:
return False # Only one thing voted for = not a tie
return counts[0] == counts[1] # A tie iff the two biggest counts are equal
def main():
maxn = 9
if len(sys.argv) > 1:
maxn = int(sys.argv[1])
for n in range(maxn + 1):
total = 0
ties = 0
for combo in all_combos(n):
total += 1
if is_tie(combo):
ties += 1
print("P({0}) = {1}/{2} = ~{3}%".format(n, ties, total, 100*ties/total))
if __name__ == '__main__':
main()