Biased Ballot Theorem

Question

Classical Ballot theorem states if candidate $A$ receives $a$ votes and $B$ receives $b$ votes $(b < a)$, and assume that each candidate is equally likely to get a vote, then the probability that through the counting $A$ always leads $B$ is $(a-b)/(a+b)$. What about now we assume each time $A$ gets a vote with probability $p$ while $B$ gets a vote with probability $1-p ~(~p \neq 1/2)$? In this situation, what is the probability that through the counting $A$ always leads $B$?

Answer 1

I once thought that apparently the answer shouldn't be the same. It turned out to be completely wrong.

The reflection technique, as we used in the proof of Ballot theorem when $p=\frac{1}{2}$ can be adopted here too. Let $x=a-b$ and $n=a+b$.

\item Use $S^x(k)$ to denote the simple random walk starting at $x$. Here we assume the same setting as in the Ballot theorem except for the probability of $\{S^0(k+1)-S^0(k)=1\}$ is $p$ instead of $\frac{1}{2}$. \par From the definition of conditional probability, if n and x have the same parity, \begin{equation} P\left(\min_{1\le k\le n} S^0(k) > 0 \big| S^0(n)=x\right) = \frac{ P\left(\min_{1\le k\le n} S^0(k) > 0 , S^0(n)=x\right) }{P(S^0(n)=x)} .\label{3-1} \end{equation} Conditioning on $S^0(1)$, from the Markov property and time-homogeneity of $S^0(n)$, we obtain that \begin{equation} P\left(\min_{1\le k\le n} S^0(k) > 0 , S^0(n)=x\right) = p P \left(\min_{1\le k\le n-1} S^1(k) > 0 , S^1(n-1)=x\right). \end{equation} Use the reflection principle for simple random walk to count the path, \begin{align*} & P \left(\min_{1\le k\le n-1} S^1(k) > 0 , S^1(n-1)=x\right) \\ &= p^{a-1} q^b ( \# \left\{ S^1(n-1)=x \right\} - \# \left\{ S^1(n-1)=-x \right\} ) \\ &=p^{a-1}q^b (\binom{n-1}{a-1} - \binom{n-1}{a} ) \end{align*} where $q=1-p$. Plug in (\ref{3-1}), after striaght calculation, we obtain that \begin{equation} P\left(\min_{1\le k\le n} S^0(k) > 0 \big| S^0(n)=x\right) = \frac{a-b}{a+b}. \end{equation}

Remark: Of course this only holds when $p \ne 0$. Reflection principle can be used here because we didn't use it on possibility but on counting path.

Wow!