Problem of the Week 1091

A Close Election

MacPOW Home || Math Forum POWs || Search MacPOW

Solution

We consider the general case of an (a,b) election with a > b votes. Here Alice gets a votes and Bob gets b votes. We show that the probability that Alice never trails is

(a - b + 1)/(a + 1).

In particular, Alice never trails in a (11,10) election with probability 1/6.

Proof: Let's think of the vote count as tracing out a path between (0,0) and the point (a,b) where each step is at an integer lattice point (x,y). We'll call this an (a,b) lattice path.

For example, one (3,2) lattice path is (0,0), (1,0), (1,1), (1,2), (2,2), (3,2). The total number of distinct (a,b) lattice paths is Bin(a + b,b). (We have to choose b to move "up" b out of a + b times.)

Let's call an (a,b) lattice path "good" if the corresponding path never steps above the diagonal. (In other words, Bob's current vote count is never larger than that of Alice.) Otherwise the lattice path is "bad." We'll count the bad elections.

Given a bad (a,b) lattice path, let k be the smallest positive integer such that (k,k + 1) is on the path. This k must exists since the election is bad. Modify the path after this point by changing every Alice vote to Bob and every Bob vote to Alice. Now Alice gets b - k - 1 additional votes and Bob gets a - k additional votes. The final tally of this election is (k,k + 1) + (b - k - 1, a - k) = (b - 1, a + 1).

The process is reversible: every election with final score (b - 1, a + 1) is won by Bob, so there is a least k such that (k,k + 1) is on the corresponding lattice path. Switching votes after this point results in a bad (a,b) lattice path.

This shows that we have the same number of (b - 1, a + 1) elections as there are bad (a,b) elections. Hence, there are Bin(a + b, a + 1) bad elections. The number of good elections is Bin(a + b,a) - Bin(a + b, a + 1). Dividing this difference by Bin(a + b,a) and simplifying yields (a - b + 1)/(a + 1).

[Back to Problem 1091]

© Copyright 2008 Stan Wagon. Reproduced with permission.