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 be a sequence of independently and identically distributed Bernoulli random variables. Let’s say each represents a vote either for candidate () or represents a vote for candidate (). Let . Suppose and candidate receives a total of votes and candidate receives a total of votes and compute the following probability that candidate was always ahead of candidate .

Let’s try to attack this combinatorially. The total number of assignments is given by because we can place votes in one of 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
  1001.0

Now, the number of sequences in which candidate 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)
  429.0

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

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.