Probability of always more heads than tails

Question

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.

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.