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.