Ballot Theorem – 3 (26/365)

In the last post I showed how to count the number of valid vote sequences given that candidate A ends up with only one extra vote over candidate B. In general, candidate A may end up with n+k votes. How do the counts change?

In terms of balanced parantheses this means we have k extra open parantheses to make use of. Let’s say n=3 and k=3 then

  1. There are C_3 ways to arrange 3 votes for each candidate

  2. For each of the C_3 valid ways we can insert an extra open paranthesis in 7 possible places. After this, we can insert the next extra open paranthesis in 8 possible places. So, we now have 8 \times 7 \times C_3 arrangements.

  3. The last extra parantheses we know we have to place it at the beginning. But there are k choices for the first paranthesis. So now have 3 \times 8 \times 7 \times C_3 possible arrangements.

  4. Finally, since the extra parantheses are also indistinguishable we have to divide by (8!)(7!).

Thus the number of ways to arrange n+k votes for candidate A and n votes for candidate B where candidate A always has the higher number of votes is

\displaystyle  \frac{k \times (n+k-1)\times \dots \times (n+1)}{(n+k)\times \dots \times (n+2)} \times \frac{(2n)!}{(n+1)!n!} = \frac{k(n+k-1)!}{(n+k)!n!}

The probability that candidate A always has the higher number of votes than candidate B and ends up with a and b votes respectively is

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

We have in fact arrived at the solution without the use of martingales. Next time, let’s see why this example is used in the chapter on martingales.

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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