Imagine that A and B each toss $4$ times. There is a certain probability $p$ that A is ahead, and by symmetry the same probability $p$ that B is ahead. If A is already ahead, she will win, whatever her $5$th toss. If B is already ahead, she will win. And if they are tied, there is probability $1/2$ that A will get a head on her $5$th toss and win. Thus by symmetry the probability that A wins is $1/2$.
Or else we can compute. The probability they are tied after $4$ is $1-2p$. Thus the probability that A wins is
$$p+\frac{1}{2}(1-2p)=\frac{1}{2}.$$
Remark: The same argument applies if B has $n$ coins and A has $n+1$.
"Show that the probability of a tie (we get the same number of heads) is the same as getting exactly 4 heads and 4 tails on 8 coin flips."
Let $H,T$ denote the number of heads and tails repectively flipped
by you in $4$ flips .
Let $H',T'$ denote the number of heads and tails respectively flipped
by your friend in $4$ flips.
Then the probability of a tie is $\Pr\left(H=H'\right)$.
But $T'$has the same distribution as $H'$ and there is independence, so we observe:
$\Pr\left(H=H'\right)=\Pr\left(H=T'\right)=\Pr\left(H=4-H'\right)=\Pr\left(H+H'=4\right)$
The last probability can be recognized as the probability of $4$
heads by $8$ flips (the flips of you and your friend taken together).
"Use this answer to calculate the probability of someone winning (getting more heads than the other person)."
Now we have:
- $\Pr\left(\text{tie}\right)=\Pr\left(H+H'=4\right)=2^{-8}\binom{8}{4}$.
- $1=\Pr\left(\text{you win}\right)+\Pr\left(\text{tie}\right)+\Pr\left(\text{friend wins}\right)$
- $\Pr\left(\text{you win}\right)=\Pr\left(\text{friend wins}\right)$
leading to: $$\Pr\left(\text{you win}\right)=\frac{1}{2}\left(1-2^{-8}\binom{8}{4}\right)$$
"Also, If I toss the coin 5 times, while my friend only tosses hers 4 times, calculate the probability that I will get strictly more heads than my friend."
If you toss $5$ times then think of it as a match1 as described above that is followed by an extra toss of you, and call the whole thing match2.
Now apply that:
$$\Pr\left(\text{you win match2}\right)=$$$$\Pr\left(\text{you win match1}\right)+\Pr\left(\text{match1 ends in a tie}\wedge\text{extra toss is a head}\right)=\Pr\left(\text{you win match1}\right)+\Pr\left(\text{match1 ends in a tie}\right)\Pr\left(\text{extra toss is a head}\right)=$$$$\frac{1}{2}\left(1-2^{-8}\binom{8}{4}\right)+2^{-8}\binom{8}{4}\times\frac12=\frac12$$
There is another (more elegant) route to this result.
Let $H,T$ denote the number of heads and tails repectively flipped
by you in $5$ flips .
Let $H',T'$ denote the number of heads and tails respectively flipped
by your friend in $4$ flips.
The probability of winning for you is $\Pr(H>H')$ and just as above we find:
$\Pr\left(H>H'\right)=\Pr\left(H>T'\right)=\Pr\left(H>4-H'\right)=\Pr\left(H+H'>4\right)$
The RHS is the probability that by $9$ flips there are more heads than tails. Symmetry then tells us that this equals $\frac12$.
Best Answer
Consider the simpler problem of HH vs HT in 3 coin tosses. \begin{array} 3Flips & HH & HT \\ \hline HHH & 1 & 0 \\ \hline HHT & 1 & 1 \\ \hline HTH & 0 & 1 \\ \hline HTT & 0 & 1 \\ \hline THH & 1 & 0 \\ \hline THT & 0 & 1 \\ \hline TTH & 0 & 0 \\ \hline TTT & 0 & 0 \\ \hline Total & 3 & 4 \\ \hline \end{array}
Why does this happen? One explanation is that in HHH we have two counts of HH, but we only count it once. This is slightly similar to the explanation given by Peter that after an HHH, you have to start counting from scratch for HHHH, in case a T occurs, but for HHHT, even if another H occurs, you can reuse 3 H's.
You can now extend the explanation to larger flip-sets (3 throws vs n throws) and larger patterns (HH vs HHHH)