Election between $2$ candidates ends in a tie: probability one candidate leads until the penultimate vote

Question

Assume there are two candidate $C_1$ and $C_2$. At the end of the election both candidates receive the same amount of votes. What is the probability $P$ that candidate $C_1$ leads during the whole election process until the penultimate vote? (The last vote must always be in favor of candidate $C_2$)

This question was presented in our lecture in the context of the ballot-theorem. So one should think of paths which start at $(0, 0)$ along the $x$-axis and end at some point $(n,s)$, where $n,s \in \mathbb{Z}$.

My approach:

My sample space $\Omega$ includes all possible paths along the $x$-axis. If the path is above the $x$-axis then candidate $C_1$ has more votes and if the path is below then $C_2$ has more votes . If the paths touches the $x$-axis then both candidates have the same amount of votes. Hence, $|\Omega|={2p \choose p}$, where $p \in \mathbb{N}$ is the number of votes of each candidate.

Firstly, I count all paths which start at $(1,1)$ and end at $(2p,0)$. These are ${2p-1 \choose p-1}$ many. Now I subtract all paths that touch the $x$-axis, these are ${2p-2 \choose p-2}$ many. So in total I count ${2p-1 \choose p-1}-{2p-2 \choose p-2}$ paths which do not touch the $x$-axis. One can interpret all these paths as desired outcomes, i.e. where candidate $C_1$ leads until the penultimate vote. As all paths are equally probable I get the solution just by dividing by $|\Omega|={2p \choose p}$. Hence, $P = \frac{{2p-1 \choose p-1}-{2p-2 \choose p-2}}{{2p \choose p}}$.

I am not sure if this is correct. May be someone can check it or comment on it.

Answer 1

HINT

Why not just use Bertrand's ballot theorem?

A feasible $2p$-steps path in the OP problem consists of a $(2p-1)$-long front segment where $C_1$ leads throughout, and then a last vote for $C_2$. If you consider just the front segment, this fits exactly the ballot theorem.

• $M = {2p-1 \choose p} =$ no. of possible front segments.

• The ballot theorem gives the probability, i.e. the fraction $f$, of such front segments with $C_1$ leading throughout. So the no. of such front segments $= X = ???$

• The no. of $2p$-long paths where $C_1$ leads until the very end $= Y = ???$

• The total no. of $2p$-long paths is of course ${2p \choose p}$, so $P = ???$

Can you finish now?

By the ballot theorem, the fraction of such $(2p-1)$-long segments is $$f={p - (p-1) \over p + (p-1)} = {1 \over 2p-1}$$ among all ${2p-1 \choose p}$ ways to arrange the first $2p-1$ votes. Thus the no. of paths feasible for OP is $$Y = X = {1 \over 2p-1} {2p-1 \choose p} = {(2p-2)! \over p! (p-1)!}$$ The required probability is: $$P = Y \big/ {2p \choose p} = {(2p-2)! \over p! (p-1)!} \big/ {2p \choose p} = {p \over (2p) (2p-1)} = {1 \over 2(2p-1)}$$ E.g. when $p=3$ this gives $P={1 \over 10}$ agreeing with the comment by @almagest

Answer 2

Possible hint: maybe it's easier to modelize the problem this way:

Answer 3

Let's shift gears and use the ballot theorem instead of reinventing it for the case of ties. Other than the one appeal to the ballot theorem, this will be a conditional probability problem. ^_^

Our sample space will be all cases where each candidate received $p$ votes. Let $A$ be the event that $C_1$ lead all the way until the moment before the final vote was read, and let $B$ be the event that $C_2$ received the final vote.

We know that

• $P(B)=P(\overline B)=\frac12$

• $P(A\mid B)=\frac{p-(p-1)}{p+(p-1)}=\frac1{2p-1}\quad$ This is where we are using the ballot theorem.

• $P(A\mid \overline B)=0\quad$ Obviously, $C_1$ could not have lead throughout the counting and received the final vote, because the count ended in a tie.

Using all this and the law of total probability,

$$P(A)=P(A\mid B)\cdot P(B)+P(A\mid \overline B)\cdot P(\overline B)\\=\frac{1}{2p-1}\cdot\frac12+0\cdot\frac12=\frac1{4p-2}$$

Note that this formula agrees with almagest's calculation that the probability was $\frac1{10}$ when $p=3$.