Bertrand Ballot Prefix Paths

Worked Example

Let's consider an election with a = 3 votes for A and b = 1 vote for B.

First, we calculate the total number of ways to order the votes:

Total Orderings = (a + b)! / (a! * b!) = 4! / (3! * 1!) = 24 / 6 = 4.

The 4 possible orderings are:

1. AAAB (Valid: A is always strictly ahead after the first vote)
2. AABA (Valid: A is always strictly ahead)
3. ABAA (Invalid: After the second vote, A has 1 and B has 1; A is not strictly ahead)
4. BAAA (Invalid: B is ahead on the first vote)

There are 2 valid paths out of 4 total orderings. Using Bertrand's ballot theorem for the strict case, the probability is:

P(Strict) = (a - b) / (a + b) = (3 - 1) / (3 + 1) = 2 / 4 = 0.5.

Thus, the probability of A staying strictly ahead is 0.5.

Experiment

You can interactively explore the ballot paths in the Bertrand Ballot Prefix Paths module.

1. Set the A votes control to 3.
2. Set the B votes control to 1.
3. Set the Rule control to "Strict".
4. Observe that the Valid paths output displays 2, the All orderings is 4, and the Probability is 0.5.
5. Change the Rule control to "Weak" and notice the difference in valid conditions.

Limitations

The simple formulas for the ballot theorem assume that all orderings of the votes are equally likely. In a real election, votes might arrive in correlated batches from different precincts, which would invalidate the assumption of independent, identically distributed counting steps. Additionally, the formula for the strict case requires a > b; if a = b, it is impossible for A to be strictly ahead at the end, so the strict probability is trivially 0.

References

The exact counting of lattice paths that stay below or above a boundary has a rich history in combinatorial mathematics. These problems are intimately connected to the Catalan numbers and their generalizations. For detailed formal definitions, identities, and proofs regarding combinations and path counting, refer to the mathematical literature such as the NIST Digital Library of Mathematical Functions.

• NIST Digital Library of Mathematical Functions: Section 26.3 - Contains foundational combinatorial identities often related to path counting and Catalan numbers.