The ballot problem, ties allowed

Question

Candidate A gets a votes and candidate B gets b votes, with a b, counted in uniformly random order. What is the probability that A is never behind B at any point in the count (ties allowed)?

Accepted Answer

Model the count as a path: +1 for each A vote, -1 for each B. The path starts at 0 and ends at a - b 0. "Never behind" means the path never goes below 0 (touching 0 is fine). All \binom{a+b}{a} orders are equally likely. Count the bad paths by reflection. A path is bad if it ever reaches -1. Reflect the segment up to the first time it hits -1 across the line y = -1: this moves the starting point from 0 to -2 and leaves the endpoint at a - b. The result is a bijection between bad paths (from 0 to a-b, touching -1) and all paths from -2 to a - b. The latter use a+b steps to climb a - b + 2, so …

The ballot problem, ties allowed

Your answer

More Probability questions