# Biased Ballot Theorem

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

• What thoughts do you have on it? Oct 23, 2017 at 4:01
• I think the answer should be the same, that is (a-b)/(a+b). Oct 23, 2017 at 4:10

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, $$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}$$ Conditioning on $S^0(1)$, from the Markov property and time-homogeneity of $S^0(n)$, we obtain that $$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).$$ 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 $$P\left(\min_{1\le k\le n} S^0(k) > 0 \big| S^0(n)=x\right) = \frac{a-b}{a+b}.$$

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!

• Hi Zhengyi, thanks so much for your answer. But here the answer seems a little strange. For example, when p is sufficiently small, smaller than a positive constant C(n, x), then the probability in your answer will be non positive, which is contradictory to the fact that this can happen as long as p>0. I am not sure whether we can use reflection principle in this situation. Oct 24, 2017 at 0:30
• Dude you are awesome. I will correct in minutes. Oct 24, 2017 at 2:01
• Awesome, your method is cool! Oct 24, 2017 at 2:38