In an election, suppose we have two candidates A and B, such that A receives more votes than B (lets say A receives votes, B receives b votes, and a > b). Votes are counted in random order.

Let S_k be the difference in the total votes for A and B after k votes are counted. With n = a + b voters, then S_n = a - b.

a.Let W_k = S_n-k /n-k with W₀ = S_n /n = a-b /a+b. Show that {W_k 0 < <-1} is a Martingale.

b. Let T = min {k > 0 W_k = 0} (where T = n-1 if W_k > 0; 0 < k n-1). Note that

Pr(T = n-1) = Pr(A is always ahead)

Show that E[W_T] = Pr(T = n-1)