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

combinatoricsprobabilitysolution-verificationstatistics

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.

Best Answer

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

Related Question