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

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.

• What does $s$ represent in your problem? Not sure to understand either what is the x-axis relative to the y-axis. Jan 2, 2020 at 14:51
• Suppose we take $p=3$. Then if they each get 3 votes and $C_1$ is ahead until the final vote, the voting must be 111222 or 112122. But in total there are ${6\choose3}=20$ ways to get 3 votes each, so prob 2/20. But the formula gives $10-4=6$ ways out of 20, so maybe it is not right. Jan 2, 2020 at 14:57
• @Jeanba, I hope the following makes it more clear: $n$ is the $x$ coordinate and $s$ the $y$-coordinate. E.g. the point $(4,3)$ means that after $4$ votes candidate $C_1$ has $3$ votes more than candidate $C_2$. At the end of the election, i.e. at the end of the path, we reach point $(n,0)$ where $n$ is the total amount of votes. Jan 2, 2020 at 15:00
• Ok thanks I got it, I was a little bit confused about how you envisioned your path. Jan 2, 2020 at 15:10
• is this homework? what level of help can we give? hint or full solution? Jan 2, 2020 at 17:07

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

• thanks for the detailled explanation, I think your idea pretty much matches with my comment above which I contemporaneously made. Jan 2, 2020 at 20:32

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$$.

• It was my intention to hide everything from "We know that" down in a spoiler block out of respect for the OP, but I couldn't make it work in the environment with the bulleted list and the MathJax. If someone knows how to address that, I would be grateful!
– user694818
Jan 2, 2020 at 17:45
• If you type >! before the expression, you can create a spoiler block. I tried this with your already typed expression, which did not work. That may be because of the itemize environment you used. My recollection is that everything in the spoiler block needs to be written in one long paragraph. Jan 2, 2020 at 20:58

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