Exercise 3.36 (Ballot Theorem). Let a, b be postive integers. Suppose there are

Question

Exercise 3.36 (Ballot Theorem). Let a, b be postive integers. Suppose there are e votes cast by c people in an election. Candidate 1 gets a votes and candidate 2 gets b votes. (So c + b.) Assume a > b. The votes are counted one by one. The votes are counted in a uniformly random ordering, and we would like to keep a running tally of who is currently winning. (News agencies seem to enjoy reporting about this number.) Suppose the first candidate eventually wins the election. We ask: with what probability wl candidate 1 always be ahead in the running tally of who is currently winning the election? As we will see, the answer is To prove this, for any positive integer k, et Sk be the number of votes for candidate 1, minus tmber of votes for candidate 2, after k votes have been counted. Then, define Xk := Sc-k/(c-k). Show that X0,X1, is a martingale. Then, let T such that T = min(0

Explanation / Answer

Proof:

Let Sk be (#A’s votes) (#B’s votes) after k votes are counted; thus Sn = a b, where n = a + b is the total number of votes. Define Xk = Snk /(n k )

Claim : Xk is a martingale

Let T = min{k | Xk = 0} or T = n 1 if no such k exists.

There are two possibilities:

• Case 1: A is always ahead. Then T = n 1, so XT = Xn1 = S1 = 1.

• Case 2: A is not always ahead. Then at some point in the process Xk must be zero, which implies that XT = 0.

Let p be the probability that Case 1 occurs. Then E[XT ] = p · 1 + (1 p)· 0 = p.

By the Optional Stopping Theorem, p = E[XT ] = E[X0] = E (Sn /n ) = a b /a + b .

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.