Ballot numbers

In this post I want to present the ballot numbers, what are they? well, as you may alredy guessed, they are related to elections somehow. How exactly? that’s what we’re going to find out. Let’s start with a quick warm-up:

Warming up

“In an election with two candidates, thousand people participate. What is the probability that the election will end in a tie?” Think about what the answer should be – maybe it’s about 1 / 1000, or maybe 1 / 10 or 1 / 10,000, or maybe even none of those? Pick some number that you believe is the answer, and we’ll see right away if you intuition is good or not.

Finding the solution

Ok, before we’ll solve it, let’s understand what we are asked to do. We want to find the probability of an event. What is the event? that the election will end in tie, that is, both candidates will recieve 500 (=1000 / 2) votes. To get the probability we need to find the number of possible ways for the election to end up in a tie and divide it by the number off all the possible events:

P=\frac{\#\text{ both recieved 500 votes}}{\#\text{ all of the possible events}}

Great, now that we understand what we need to do, let’s solve the problem:

• Note: we assume that every participant can only vote once. Moreover, we assume each one of the participant is making a choice randomly, so no candidate has any sort of priority.

For the elections to end in a tie we need that both candidates will recieve 500 votes. But this is equivalent to one of them recieve 500 votes (since there are total of 1000 votes) How many events are there?

So there are 1000 participants, and we need to choose 500 people from them that will vote to the same candidate – every choice yields different event. Thus the answer is:

1000\choose500

Nice, so now we only need to find out how many events are there. Well, there are 1000 participants, each one of them of them has 2 options. We can line up the people in a row and label them – “the first participant, the second participant….” Can you recognize what kind of a selection is that?

This is a situation of a choice where order matters and repitions are allowed – there are:

2^{1000}

different events. Great, now we can find the probability:

P=\frac{1000\choose500}{2^{1000}}\thickapprox 0.025=\frac{1}{40}

What about that? The odds are not that low… that’s pretty cool right?

Ok, it’s time to move to a bit more complicated question:

Strictly ahead of…

Now I’m asking a different question. Suppose that the results of the elections were:

501:499

(Poor loser, he almost won it!) The question is, what are the chances that the winner was strictly ahead of the loser throughout the count?

For example, if there were only 6 participants and the result was:

AABAAB

Then A was strictly ahead throughout the elections. After one vote he led 1:0, after 2, he led 2:0. After three votes, he still led with 2:1, after the forth, 3:1, then 4:1 and finally 4:2.

However, if the sequence were:

ABABAA

Then A didn’t strictly led – after two votes there was a tie.

Ok, I’ll solve this problem for the general case – participant A recieved votes, participant B recieved votes, and .

So in total, there were participants, and the number of events that participant A got votes (which is the same number as the number of events that participant B got votes) is:

a+b\choose a

Let’s denote by the set of all the possible sequences where participant A strictly led. Then the probabilty is:

P=\frac{|S|}{a+b\choose a}

The only thing left to figure out is the size of the set.

The lattice

To find the size of we will use a geometric description of the problem – (don’t worry though, I won’t ask you to calculate the area of a triangle or something like that…).

I am going to look at the lattice , which is the collection of all the points in the plane with integer coordinates:

\mathbb{Z}^2=\{(x,y):x,y\in\mathbb{Z}\}

We are going to look at lattice paths that starts at and ends at where we can only move on step right or up at a time. If we move right, we add one for the count of A, if we go up, we add one for the count of B. For exapmle:

Here the first vote was for A, then B got one vote, after that, A got 2 in a row, then B got two in a row, and finally A got one. Hence, this path descirbes the sequence:

ABAABBA

What path are we interested in? well our paths are exactly the ones that go only through points with , since if then in that specific position, B led or they were tied.

In other words, we are intersted in paths that are always under the line and they never ‘touch’ the line:

So we need to count how many paths are there such as green one.

As it turns out, it’s easier to count the number of paths such as the red one, so we’ll do that (to get the number of the desired path we just substract the number of bad paths from the total number of paths)

Counting ‘bad’ paths

There are two types of bad paths:

Type one – bad from the beginning

Those are the paths that first go up to (0,1) – That is, B got the first vote, so it is obviously a bad one.

Here’s the trick: The number of such path is exactly the number of paths from to . In those paths we need to walk steps right and steps up. Or, in an equivalent way, we need to choose times to go right out of choices. Thus, the number of such paths is:

a+b-1\choose a

An important remark: Note that such path will always intersect the line . Why? since by out assumption , thus the point is under the line . Remember this fact, since it’s the key for counting the second type!

Type 2 – starts good, but turns out to be bad

Now A has the lead first, but B may take the the lead later on, or they might be tied at some point.

We are going to do another trick here – sometehing a bit more complicated than what we’ve done in the first type of bad paths. Consider this path:

This is a classic example of bad path of the second type. I am now going to consider only the part of the path from the origin until it’s first intersection with the line and reflect this part along the line. This action yields a new path:

Would you look at that! This action yield a path from the first type. So we’ve found a way to translate paths of the second type to paths of the first type in a unique way – different second type paths yield different first type paths.

Is there a way to reverse this process? If I’ll give you a path of the first type and I want you to translate it to path of the second type, can you do it?

Well it depeneds on a simple fact – does every line of the first type intersects the line ? If it is, then of course we can reverse the action, we just do the same action – we consider only the part of the path from the origin until it’s first intersection with the line and reflect this part along the line.

Luckily, every line of the first type intersects the line . That’s what I explained in the remark!

Great so this correspondence between the first type and the second type is one-to-one and onto. That is, we match every first type path to it’s unique second type path and vice versa.

Therefore, the number of second type path is exactly the same as paths of the same type, which is:

a+b-1\choose a

Deducing the answer

So in total, we have:

{a+b-1\choose a} +{a+b-1\choose a}=2{a+b-1\choose a}

Bad paths, hence, the number of good paths is:

|S|=\#\text{ total amount of paths} - \text{\# bad paths} = {a+b\choose a}-2{a+b-1\choose a}

Let’s simplify it (recall that ):

|S|= {a+b\choose a}-2{a+b-1\choose a}=\frac{(a+b)!}{a!b!}-2\frac{(a+b-1)!}{a!(b-1)!}  \\

= \frac{(a+b)!}{a!b!} (1-2\cdot \frac{b}{a+b})={a+b\choose b} (\frac{a+b-2b}{a+b})=\frac{a-b}{a+b}\cdot{a+b\choose b} 

Ok, this is actually looking pretty nice, and numbers of such form have a name – they are called the ballot numbers . Now let’s calculate the probability:

P=\frac{|S|}{a+b\choose a}=\frac{\frac{a-b}{a+b}\cdot{a+b\choose b} }{a+b\choose a}=\frac{a-b}{a+b}

Wow! This is such a simple expression! How great is that?

If we substitute we’ll get that:

P=\frac{501-499}{501+499}=\frac{2}{1000}=0.002

And that’s a pretty low chance… So even though B lost the election, he probably led or was tied with A at some point of the election, so, good for him.

What if we allow a tie?

Well, the process is pretty similar, now instead of the requierment of we only require that (which is equivalent to [ or ])

The case is really similar, however there is only one type of bad paths since from the origin you can't go above the line after one step.

The reflection of such bad lines along the line starts at and ends, of course, at . So from we have to move steps right and steps up. This gives us a total of steps where we choose of them to be steps to the right. Therefore, the number of bad paths is:

a+b\choose a+1

And the total number of paths stays the same as before. Thus, the size of the set of the good paths is:

|S|=\#\text{ total amount of paths} - \text{\# bad paths} = {a+b\choose a}-{a+b\choose a+1}

=\frac{(a+b)!}{a!b!}-\frac{(a+b)!}{(a+1)!(b-1)!}=\frac{(a+b)!}{a!b!}(1-\frac{b}{a+1})

=\frac{(a+b)!}{a!b!}(\frac{a+1-b}{a+1})=\frac{a+1-b}{a+1}\cdot{a+b\choose a}

So, the probabilty is:

P=\frac{\frac{a+1-b}{a+1}\cdot{a+b\choose a}}{{a+b\choose a}}=\frac{a+1-b}{a+1}

Cool. If we get:

P=\frac{501+1-499}{501+1}=\frac{3}{502}\thickapprox 0.006

Summary

What do you think about this solution? I think it's a really elegant one - we represent the question in a geomteric way and find a really nice solution with almost no effort!

I just want to mention one more thing before I'll end this post: Note that if where we allow tie (of course we'll allow, the result is a tie), we'll get that the number of events where A strictly led / was tied with B is:

\frac{n+1-n}{n+1}\cdot{n+n\choose n}=\frac{1}{n+1}\cdot{2n\choose n}

This number probably won't say anything to you now, but you will not believe how useful is this number. it is called the catalan number - .

Why exactly is it so useful? We'll find out on the next post...