Probability of $5$ fair coin flips having strictly more heads than $4$ fair coin flips

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$.

The sample space is the grid of points $\{0,1,2,3,4,5\} \times \{0,1,2,3,4\}$, corresponding to $(H_A, H_B)$. Orange dots are those where $A$ wins. There are as many gray dots as orange dots.

$H_A$ and $H_B$ are independent symmetric binomial random variables, hence $$\begin{eqnarray} \mathbb{P}(H_A = h_a, H_B = h_b) &\stackrel{\text{independent}}{=}& \mathbb{P}(H_A = h_a)\mathbb{P}( H_B = h_b) \\ &\stackrel{\text{symmetry}}{=}& \mathbb{P}(H_A = 5-h_a)\mathbb{P}( H_B =4- h_b) \\ &=& \mathbb{P}(H_A = 5-h_a, H_B = 4-h_b) \end{eqnarray}$$ But $(h_a, h_b) \mapsto (5-h_a, 4-h_b)$ interchanges orange and gray dots, therefore the total probability of $A$ winning (orange dots) is $\frac{1}{2}$.

Here is the plodding method, using the definition and -- as it turns out -- more computation than is necessary.

As random variables, we could say that $A\sim\operatorname{Binom}\left(5,~\tfrac12\right)$ and $B\sim\operatorname{Binom}\left(4,~\tfrac12\right)$ are independent (but not identically distributed) binomial with $n=5,4$ respectivly and both with $p=\tfrac12$. Since they are independent, we can calculate the probability that $A>B$ thus: $$ \mathbb{P}\left(A > B\right) =\sum_{a=1}^5 {5\choose a}\frac1{2^5} \sum_{b=0}^{a-1}{4\choose b}\frac1{2^4} =\frac1{2^9}\sum_{a=1}^5\sum_{b=0}^{a-1}{5\choose a}{4\choose b} =\frac{256}{2^9}=\frac12 $$ The trick to finding this sum without computation is Sasha's nice diagram, with the symmetry $(a,b)\leftrightarrow(5-a,4-b)$; using this transformation, the above sum has a complementary sum, which is equal, and the two of which together must sum to unity.

Assume A and B used 4 coins each only, getting a and b heads respectively. If a>b, A has already more heads than B hence A has more heads than B once the result of the 9th coin is added, and A wins. If b>a, B still has at least as many heads as A once the result of the 9th coin is added hence B wins. If a=b, A wins if the last coin is head and loses otherwise.

Since a and b are i.i.d., A wins with probability one-half.