Probability of always more heads than tails 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. 
 A: 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.
