= 0 when the probability is 1, given that the first candidate receives all the votes; it is also true when p = q > 0 as we have just seen. Assume it is true both when p = a − 1 and q = b, and when p = a and q = b − 1, with a > b > 0. (We don't need to consider the case here, since we have already disposed of it before.) Then considering the case with p = a and q = b, the last vote counted is either for the first candidate with probability a/(a + b), or for the second with probability b/(a + b). So the probability of the first being ahead throughout the count to the penultimate vote counted (and also after the final vote) is: And so it is true for all p and q with p > q > 0. Proof via the Cycle lemma A simple proof is based on the beautiful Cycle Lemma of Dvoretzky and Motzkin. Call a ballot sequence dominating if A is strictly ahead of B throughout the counting of the votes. The Cycle Lemma asserts that any sequence of A's and B's, where , has precisely dominating cyclic permutations. To see this, just arrange the given sequence of A's and B's in a circle and repeatedly remove adjacent pairs AB until only A's remain. Each of these A's was the start of a dominating cyclic permutation before anything was removed. So out of the cyclic permutations of any arrangement of A votes and B votes are dominating. Proof by martingales Let . Define the "backwards counting" stochastic process where is the lead of candidate A over B, after votes have come in. Claim: is a martingale process. Given , we know that , so of the first votes, were for candidate A, and were for candidate B. So, with probability , we have , and . Similarly for the other one. Then compute to find . Define the stopping time as either the minimum such that , or if there's no such . Then the probability that candidate A leads all the time is just , which by the optional stopping theorem is Bertrand's and André's proofs Bertrand expressed the solution as where is the total number of voters and is the number of voters for the first candidate. He