The answer appears to be that the probability is ½.
Consider the case of Mary with three coins and John with two.
There are 8 (=23) outcomes for Mary: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT;
4 (=22) outcomes for John: HH, HT, TH, TT.
The frequency of heads for Mary is: 1×(3 heads), 3×(2 heads), 3×(1 head), 1×(0 heads). Note the sequence 1, 3, 3, 1, the third row of Pascal's Triangle.
The frequency of heads for John is: 1×(2 heads), 2×(1 head), 1×(0 heads). 1, 2, 1 is the second row of Pascal's Triangle.
We need to find out how many occurrences there are where the number of Mary's heads exceeds those of John's. So we use a table:
JꜜM→ |
HHH(3) |
HHT(2) |
HTH(2) |
HTT(1) |
THH(2) |
THT(1) |
TTH(1) |
TTT(0) |
HH(2) |
Y |
N |
N |
N |
N |
N |
N |
N |
HT(1) |
Y |
Y |
Y |
N |
Y |
N |
N |
N |
TH(1) |
Y |
Y |
Y |
N |
Y |
N |
N |
N |
TT(0) |
Y |
Y |
Y |
Y |
Y |
Y |
Y |
N |
Y means Mary tosses more heads than John; N means John tosses at least as many heads as Mary. There are 16 Y's in 32 outcomes. So the probability that Mary tosses more heads than John is (in this case) ½.
This table can be summarised:
JꜜM→ |
3 (1) |
2 (3) |
1 (3) |
0 (1) |
2 (1) |
1 |
0 |
0 |
0 |
1 (2) |
1 |
1 |
0 |
0 |
0 (1) |
1 |
1 |
1 |
0 |
The numbers in the top row inside the brackets are the Pascal frequencies (number of occurrences) of the number of heads outside the brackets. Mary's data labels the columns and John's labels the rows. 1s indicate that the number of Mary's heads>number of John's heads, and below is the result of multiplying the bracketed Pascal numbers. Example: 2nd column for Mary is 2 (3), 2nd row for John is 1 (2), so row 2, col 2 contains 3×2=6. Only the cells containing 1 contain this product. Add up the numbers and we get 16 out of 32 outcomes as before.
JꜜM→ |
3 (1) |
2 (3) |
1 (3) |
0 (1) |
2 (1) |
1 |
0 |
0 |
0 |
1 (2) |
2 |
6 |
0 |
0 |
0 (1) |
1 |
3 |
3 |
0 |
We can set up more summary tables like this and in every case, Mary's heads exceeds John's in half the outcomes. So for the general case when Mary has n+1 coins and John has n coins, the probability that Mary has more heads than John is ½.