Ballot Theorem – 1 (24/365)

The introductory chapter on martingales in this book leads up to the Ballot Theorem. I feel it should have motivated the need for the study of martingales with a problem that couldn’t be solved with simple methods. So, I want to take a few posts to try to do this.

Let’s start with this ballot problem. Let \omega_1, \dots, \omega_n be a sequence of independently and identically distributed Bernoulli random variables. Let’s say each \omega_i represents a vote either for candidate A (\omega_i = 1) or represents a vote for candidate B (\omega_i = -1). Let S_k = \sum_{i=1}^k \omega_i. Suppose P(\omega_i=1)=P(\omega_i=-1) and candidate A receives a total of a votes and candidate b receives a total of b votes and a > b compute the following probability that candidate A was always ahead of candidate B.

\displaystyle  P(S_1 > 0, \dots, S_n > 0 | S_n = a - b) = \frac{a-b}{a+b}

Let’s try to attack this combinatorially. The total number of assignments is given by \binom{a+b}{b} because we can place b votes in one of a+b positions.

> choose :: Int -> Int -> Double
> choose n k = fact n / fact k / fact (n-k)
>   where fact a = product [2..fromIntegral a]
ghci> choose (10+4) 4

Now, the number of sequences in which candidate A always has a higher number of votes is given by the following recursion.

> valid :: (Int,Int) -> Double
> valid (_,0) = 1
> valid (a,b) | a-b == 1 = valid (a,b-1)
>             | otherwise = valid (a-1,b) + valid (a,b-1)
ghci> valid (10,4)

ghci> valid (10,4) / choose (10+4) 4 == (10-4) / (10+4)

We can easily speed up valid using memoization. A closed form solution should not be hard to come by. But next time let’s see how this chapter approaches this problem and how martingales play a part.

This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

One Response to Ballot Theorem – 1 (24/365)

  1. Pingback: Ballot Theorem – 2 (25/365) | Latent observations

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s