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.

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