Ballot problem with tie

Question

We have two candidates $c_1$ and $c_2$. At the end of a ballot each candidate receives $p$-many votes.

What is the probability that $c_2$ has never been ahead of $c_1$ the whole process of vote counting? (assume that each path of votes has the same probability)

My approach:

We are allowed to use the ballot theorem: $c_1$ wins with $a$-many votes and $c_2$ loses with $b$-many votes ($a>b$). The number of paths where $c_1$ leads is given by ${a+b\choose a}\frac{a-b}{a+b}$.

First we define the sample space by $\Omega:=\left\{\omega\in\{-1,1\}^{2p}\right\}$ where $1$ rerpresents a vote for $c_1$ and $-1$ represents a vote for $c_2$. We define the set $A:=\{\omega\in\Omega\mid \sum\limits_{i=1}^{n}\omega_i\geq 0\text{ for each } 1\leq n\leq 2p\}$ which denotes the set of paths where $c_2$ never leads/$c_1$ always leads or has the same amounts of votes as $c_2$.

Now we consider a second ballot where $c_1$ got $p+1$-many votes and $c_2$ only $p$- many votes. The respective sample space is $\Omega':=\left\{\omega'\in\{-1,1\}^{2p+1}\right\}$. We know by ballot theorem that all paths where $c_1$ leads can be counted by ${2p+1\choose p}\frac{1}{2p+1}$. Let's denote this set of paths by $B$ where $B:=\{\omega'\in\Omega'\mid \sum\limits_{i=1}^{n}\omega_i\geq 1\text{ for each } 1\leq n\leq 2p+1\}$.

We construct a bijection between $A$ and $B$. Let be $\omega'\in B$ if we remove the first vote of $\omega'$ then we get a new path $\omega$ which lies in $A$. On the other hand, if we consider a path $\omega\in A$ and add a vote for $c_1$ at the beginning then we get a new path $\omega'$ which lies in $B$. Moreover, it is obviously that this mapping is injective. Hence, $|A|=|B|={2p+1\choose p}\frac{1}{2p+1}\implies P(A)=\frac{|A|}{|\Omega|}=\frac{1}{p+1}$.

---

Is this approach correct?

Answer 1

While I can't comment on your approach, your result is correct.

The thing that confused me in the comments is that probability of $c_1$ is always leading or equal to $c_2$ within $2p$ votes distributed evenly is actually equal to $c_1$ is always leading or equal to $c_2$ within $2p-1$ votes with $c_1$ getting $p$ of them. Thus, removing a single envelope does not change the result.

In other words, we know that $c_1$ and $c_2$ will have a draw at the end of counting. So, for $c_1$ never to fall behind, the last envelope has to be for $c_2$ anyway. Thus, removing an envelope does not alter the probability.

Now we can use Bertrand's Ballot theorem directly for (p, p-1) votes, giving us $\frac{1}{p+1}$.

I have the simulation results and the simulation code here.

def hitting_simulation(m,p):
    hit=0
    for j in range(m):
        votes=np.ones(2*p)
        while not sum(votes)==0:
            a=random.randint(0,2*p-1)
            votes[a]=-1
        voting=np.cumsum(votes)
        #print(voting)
        if any(voting<0):
            hit+=1
    return m-hit