A coin that comes up heads with probability $p$ is flipped $n$ consecutive times. What is the probability that starting with the first flip there are always more heads than tails that have appeared?

I have seen hints that this is Bertrand's ballot problem in disguise .

Here is my attempt:

Let $X$ be the number of heads in $n$ tosses with a coin of probability $p$. Let $Y$ be the number of tails. Let $s=\text{floor}(n/2)+1$

$\begin{align*}P(\text{Always more heads}) &= \sum_{k=0}^n P(\text{Always more heads}|X=k)P(X=k)\\ &= \sum_{k=s}^n P(\text{Always more heads}|X=k)P(X=k)\\ &= \sum_{k=s}^n \dfrac{k-(n-k)}{k+n-k}{n \choose k}p^k(1-p)^{n-k}\\ &= \sum_{k=s}^n \dfrac{2k-n}{n}{n \choose k}p^k(1-p)^{n-k} \end{align*}$

That doesn't seem very simple too me. Is there a better way to do this? Thanks.

  • $\begingroup$ I don't think it becomes any simpler. $\endgroup$ Oct 6, 2013 at 12:46

1 Answer 1


For a fixed value of $n$, I'm not sure that a simpler formula exists. However, for $n=\infty$, the probability that there will be more heads than tails permanently is simply equal to $2p-1$. We can show this as follows.

Let $x_k$ denote the probability of success conditional on the current state being $k$ heads. We have the simple recurrence $x_k=p x_{k+1}+(1-p)x_{k-1}$, which we can rewrite as $$x_k=\frac{1}{p}x_{k-1} - \frac{1-p}{p}x_{k-2}.$$ Solutions to this recurrence have the form $x_k = a_1\lambda_1^k+a_2\lambda_2^k$, where the $\lambda_i$ are roots of the characteristic polynomial $z^2-\frac{1}{p}z+\frac{1-p}{p}$: \begin{align} \lambda_1=1, ~~~~~~\lambda_2=\frac{1-p}{p}, \end{align} We also have the constraints that $x_0=0$ and for $p>1/2$, $\lim_{k\rightarrow \infty}x_k=1$ (see below). It follows that the only possible solution is $$x_k=1-\left(\frac{1-p}{p}\right)^k.$$ Since we start with $0$ heads, then in order to survive forever, we must toss a head in the first toss, and then survive from the state of one head. The probability is therefore $$px_1=p\left(1-\frac{1-p}{p}\right)=p-(1-p)=2p-1.$$

Now the answer to the question "how do we know that $\lim_{k\rightarrow \infty}x_k=1$?" There are two ways to go about this. The first is to start from the Borel-Cantelli lemma as in this answer. But there is also a direct proof.

Let $x_{k,n}$ denote the probability that, starting from a state of $k$ heads, we survive at least $n$ more rounds. Note that $x_{k,0}=1$ for $k>0$, and $x_{0,0}=0$. Note also that the $x_{k,n}$ must satisfy $$x_{k,n}=p x_{k+1,n-1}+(1-p)x_{k-1,n-1}.$$ Since our values of $x_k$ computed above satisfy this same recurrence, then by monotinicity we may deduce that $$\left(x_{k,n-1}\geq x_k \forall k\right)\implies \left(x_{k,n}\geq x_k \forall k\right),$$ and since this inequality holds for $n=0$, then by induction it must hold for all $n$. From this it follows that $\lim_{n\rightarrow\infty}x_{k,n}\geq x_k$ for all $k$, which in turn implies that $\lim_{k\rightarrow \infty}\lim_{n\rightarrow\infty}x_{k,n}=1$. This in turn implies that $\lim_{n\rightarrow\infty}x_{k,n}=x_k$ for all $k$, as deduced above.

  • 1
    $\begingroup$ $2p-1$ is only positive for $p\geq 1/2$, so the result $2p-1$ does not seem correct for a probability. $\endgroup$
    – bdeonovic
    Oct 7, 2013 at 20:54
  • 1
    $\begingroup$ For $p<1/2$ the probability is zero. $\endgroup$
    – mpr
    Oct 7, 2013 at 21:01
  • $\begingroup$ ah that makes sense with the law of large numbers. $\endgroup$
    – bdeonovic
    Oct 7, 2013 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.