0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ What thoughts do you have on it? $\endgroup$
    – Harry Alli
    Oct 23, 2017 at 4:01
  • $\begingroup$ I think the answer should be the same, that is (a-b)/(a+b). $\endgroup$
    – Cohen Lu
    Oct 23, 2017 at 4:10

1 Answer 1

1
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Cohen Lu
    Oct 24, 2017 at 0:30
  • $\begingroup$ Dude you are awesome. I will correct in minutes. $\endgroup$ Oct 24, 2017 at 2:01
  • $\begingroup$ Awesome, your method is cool! $\endgroup$
    – Cohen Lu
    Oct 24, 2017 at 2:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .