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?