What is the probability to get more heads in n-1 tosses than in n tosses ? (fair coin)

Question

My approach so far is as follows:

If $X_{n-2}$ is the number of heads in $n-2$ tosses then $E[X_{n-2}] = \frac{n-2}{2}$. So up to the $n-2$ toss it is all the same regardless if we end our experiment in $n$ or $n-1$ tosses. Then if we want to ensure that we get more heads in $n-1$ than in $n$ tosses:

$P(X_{n-1} > X_{n}) = \frac{1}{2} \frac{1}{2.2} = \frac{1}{8}$

where $\frac{1}{2}$ is the probability of obtaining heads in the last toss out of $n-1$ and $\frac{1}{2.2}$ is the probability of obtaining two tails in the last two of $n$ tosses ?

Does this make any sense ? And what is the general approach for problems like this ?

Thanks in advance!

Answer 1

Consider $X$ and $Y$ i.i.d. binomial $(n-1,\frac12)$ and $Z$ Bernoulli $\frac12$ independent of $(X,Y)$, then the desired probability is

$$p=P(X>Y+Z)$$

To compute $p$, note that the event $[X\leqslant Y+Z]$ occurs when either $X\leqslant Y$, or $X=Y+1$ and $Z=1$, thus, $$P(X\leqslant Y+Z)=P(X\leqslant Y)+\frac12P(X=Y+1)$$ Using the fact that $P(X<Y)+P(X=Y)+P(X>Y)=1$ by the law of total probability and that $P(X<Y)=P(X>Y)$ by symmetry, one gets $$2p=1-P(X=Y)-P(X=Y+1)$$ Now, $$P(X=Y)=\sum_kP(X=k)P(Y=k)=\frac1{4^n}\sum_k{n\choose k}^2$$ and a classical trick yields $$\sum_k{n\choose k}^2=\sum_k{n\choose k}{n\choose n-k}=[t^n](1+t)^n(1+t)^n={2n\choose n}$$ Likewise, $$P(X=Y+1)=\sum_kP(X=k+1)P(Y=k)=\frac1{4^n}\sum_k{n\choose k+1}{n\choose k}$$ and the same trick yields $$\sum_k{n\choose k+1}{n\choose k}=\sum_k{n\choose k}{n\choose n-k-1}=[t^{n-1}](1+t)^n(1+t)^n={2n\choose n-1}$$ Thus, $$2p=1-\frac1{4^n}{2n\choose n}-\frac1{4^n}{2n\choose n-1}$$ or, equivalently,

$$p=\frac12-\frac1{2^{2n+1}}\frac{2n+1}{n+1}{2n\choose n}$$

In terms of Catalan numbers, this reads $$p=\frac12-\frac{2n+1}{2^{2n+1}}C_n$$

Answer 2

I do not think that your approach is correct. A general approach to a problem like this would be the following.

We know that the binomial distribution counts the number of heads in $n$ coin tosses. Let $X_{n} \sim Bin(n,\frac{1}{2})$ (so the number of heads in $n$ coin tosses). You want the probability that $X_{n-1} > X_{n}$. This can be written as \begin{align*} & \mathbb{P}(X_{n-1} > X_{n}) \\ = & \sum_{k=1}^{n-1} \mathbb{P}(X_{n-1} > X_{n} \mid X_{n-1} = k) \mathbb{P}(X_{n-1} = k) \\ = & \sum_{k=1}^{n-1} \mathbb{P}(X_{n} < k) \mathbb{P}(X_{n-1} = k) \\ = & \sum_{k=1}^{n-1} \left[ \sum_{m = 0}^{k-1} \binom{n}{m} \left(\frac{1}{2}\right)^{n} \right] \binom{n-1}{k} \left(\frac{1}{2}\right)^{n-1}\\ = & \left(\frac{1}{2}\right)^{2n-1} \sum_{k=1}^{n-1} \sum_{m = 0}^{k-1} \binom{n}{m} \binom{n-1}{k} \end{align*} I do not know how this sum can simplified or if this even is possible.

Filling in some small $n$ we get that $\mathbb{P}(X_{1} > X_{2}) = \frac{1}{8}$ and $\mathbb{P}(X_{2} > X_{3}) = \frac{3}{16}$