Coin Paradox Re-Demystified
Let me provide another approach to demystify The Coin Paradox.
For the sake of convenience, let me restate the cited description of The Coin Paradox copied from the Quanta Magazine article [1]:
”[…] If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses (try this at home!), even though head-tail and head-head have an equal chance of appearing after two coin tosses. […]” – Mathematicians Discover Prime Conspiracy, Quanta Magazine (2016/03/13)
Let me also reintroduce a simple terminology: H = heads; T = tails, H, T = last toss completing required result. And some additional terminology: α = game favorite; β = game underdog; Ω = sample space of relevant outcome tuples; Ψ = sample space of relevant outcome tuples representing tuples either as ε or ο whereas ε = (T,T) or (H,H) (tuple of same values) and ο = (H,T) or (T,H) (tuple of different values).
From a first principles perspective
Since “head-tail and head-head have an equal chance of appearing after two coin tosses”, which is an irrefutable fact, it inevitably follows that the rules of the game create unequal chances for individual players.
This basically resolves any strange phenomena or paradox perceived.
The Rules of the Game
Given from the game rules stated above, there are four ways to translate the given rules to play the game in terms of relevant combined outcomes for respective players, which in terms of consolidated tuple type tuple permutations produce equal chances in two cases and unequal chances in the the two remaining cases. Let me elaborate.
The relevant combined outcomes from the original rules of the game translated into our terminology are:
Alice (α) = H T, Bob (β) = H H; Ω = {(H,T), (H,H)}; Ψ = {ο, ε} |
… which produces unequal chances in favor of Alice.
However, we can turn the tables in favor of Bob …
Alice (β) = H H, Bob (α) = H T; Ω = {(H,H), (H,T)}; Ψ = {ε, ο} |
… and if we exchange T for H in the game rules above, the following relevant outcomes all become synonymous in producing unequal chances:
Alice (α) = H T, Bob (β) = H H; Ω = {(H,T), (H,H)}; Ψ = {ο,ε} |
Alice (β) = H H, Bob (α) = H T; Ω = {(H,H), (H,T)}; Ψ = {ε,ο} |
Alice (α) = T H, Bob (β) = T T; Ω = {(T,H), (T,T)}; Ψ = {ο,ε} |
Alice (β) = T T, Bob (α) = T H; Ω = {(T,T), (T,H)}; Ψ = {ε,ο} |
Please note: From a combinatorial perspective, all four states for Ψ as given above are equal whereas each consists of exactly one tuple of same values and one tuple of different values.
Let us count
There are 2×2=4 ways to combine H and T into a tuple, giving us the following sample space for all possible tuples (Ω redeclared):
Ω = {(H,T), (H,H), (T,H), (T,T)} |
The sample space above formalized as tuple type tuples (Ψ redeclared):
Ψ = {ο, ε, ο, ε} |
There are 4×4=16 ways to combine two tuples into a set thereof (Ω redeclared):
Ω = {〈(H,T), (H,T)〉, 〈(H,T), (H,H)〉, 〈(H,T), (T,H)〉, 〈(H,T), (T,T)〉, 〈(H,H), (H,T)〉, 〈(H,H), (H,H)〉, 〈(H,H), (T,H)〉, 〈(H,H), (T,T)〉, 〈(T,H), (H,T)〉, 〈(T,H), (H,H)〉, 〈(T,H), (T,H)〉, 〈(T,H), (T,T)〉, 〈(T,T), (H,T)〉, 〈(T,T), (H,H)〉, 〈(T,T), (T,H)〉, 〈(T,T), (T,T)〉} |
However, expressed as tuple types tuple permutations, we can reduce the above expression to only four tuple type tuple permutations by removing all duplicates (Ψ redeclared):
Ψ = {〈ο,ο〉, 〈ε,ε〉, 〈ε,ο〉, 〈ο,ε〉} |
Note: There are no more ways to express tuple type tuple permutations.
The last two versions of Ω and Ψ express the exact same sample space in different ways, whereas Ψ is an optimization of Ω.
From Ω to Ψ
You might ask why the formalization as tuple type tuple permutations found in Ψ is more relevant than the formalization as tuple tuple permutations found in Ω, or relevant at all. Well, let me elaborate …
As a simple answer: In order to understand the mechanics of the game rules, we need a better, more suitable language.
We need a better way to frame the game rule pattern into a super-pattern that is able to show us (1) that some sub-patterns of the pattern are responsible for unequal chances and others for equal chances, and (2) which of those respectively.
In terms of sample space as expressed by tuple types, tuple permutations from Ω consolidate into tuple type tuple permutations found in Ψ in the following way:
〈(H,T), (H,H)〉 ⇒ 〈ο,ε〉 |
〈(H,T), (H,H)〉 + 〈(T,H), (T,T)〉 ⇒ 〈ο,ε〉 + 〈ο,ε〉 ⇒ 〈ο,ε〉 |
Hence, the sample space expressed in Ω consolidates into Ψ as follows:
〈(H,T), (T,H)〉+〈(T,H), (H,T)〉+〈(H,T), (H,T)〉+〈(T,H), (T,H)〉 ⇒ 〈ο,ο〉 |
〈(H,H), (H,H)〉+〈(T,T), (T,T)〉+〈(H,H), (T,T)〉+〈(T,T), (H,H)〉 ⇒ 〈ε,ε〉 |
〈(H,H), (H,T)〉+〈(H,H), (T,H)〉+〈(T,T), (H,T)〉+〈(T,T), (T,H)〉 ⇒ 〈ε,ο〉 |
〈(H,T), (H,H)〉+〈(T,H), (H,H)〉+〈(H,T), (T,T)〉+〈(T,H), (T,T)〉 ⇒ 〈ο,ε〉 |
The Rules of the Game Revisited
From all four possible tuple type tuple permutations given in Ψ, each either produces unequal or equal chances. The original rules of the game played by Bob and Alice translates as follows into our terminology:
Alice (α) = H T, Bob (β) = H H; Ω = {(H,T), (H,H)}; Ψ = {ο, ε} |
Since we know this produces unequal chances in favor of Alice, the reverse must produce unequal chances in favor of Bob:
Alice (β) = H H, Bob (α) = H T; Ω = {(H,H), (H,T)}; Ψ = {ε, ο} |
The scoring system: Let us define that the completing toss has a score of 2, and the toss immediately before the completing toss has a score of 1. Let us further account for the current score by putting it in between round brackets right next to the respective coin-toss.
Given the rules of the game were that Alice had to toss a coin until she saw a tail followed by a head, and Bob had to toss a coin until he saw two heads in a row, the same chances of winning the game applied here as with the original rules of the game, because H T and T H are equal in terms of being a favorite in context to the unchanged H H:
Alice = T(1) T(1) H(2) |
Bob = H(1) T(0) T(0) H(1) T(0) T(0) H(1) H(2) |
However, it wouldn’t make a difference if we had Bob to toss a coin until he saw two tails in a row instead of two heads while Alice had to toss a coin until she saw a tail followed by a head.
Thus, all the following games produce unequal chances in favor of Alice:
Alice (α) = H T, Bob (β) = H H; Ω = {(H,T), (H,H)}; Ψ = {ο, ε} |
Alice (α) = H T, Bob (β) = T T; Ω = {(H,T), (T,T)}; Ψ = {ο, ε} |
Alice (α) = T H, Bob (β) = H H; Ω = {(T,H), (H,H)}; Ψ = {ο, ε} |
Alice (α) = T H, Bob (β) = T T; Ω = {(T,H), (T,T)}; Ψ = {ο, ε} |
And all the following games produce unequal chances in favor of Bob:
Alice (β) = H H, Bob (α) = H T; Ω = {(H,H), (H,T)}; Ψ = {ε, ο} |
Alice (β) = T T, Bob (α) = H T; Ω = {(T,T), (H,T)}; Ψ = {ε, ο} |
Alice (β) = H H, Bob (α) = T H; Ω = {(H,H), (T,H)}; Ψ = {ε, ο} |
Alice (β) = T T, Bob (α) = T H; Ω = {(T,T), (T,H)}; Ψ = {ε, ο} |
That’s eight out of the sixteen possible games. What about the other possible games of this kind?
Given the rules of the game were that Alice had to toss a coin until she saw two heads in a row, and Bob had to toss a coin until he saw two tails in a row, we knew that the game wouldn’t favor one of the two players, because the game scoring could move either player back to zero:
Alice = H(1) T(0) H(1) H(2) |
Bob = T(1) H(0) H(0) T(1) H(0) H(0) T(1) T(2) |
Thus, all the following games produce equal chances for both players:
Alice = H H, Bob = H H; Ω = {(H,H), (H,H)}; Ψ = {ε, ε} |
Alice = T T, Bob = T T; Ω = {(T,T), (T,T)}; Ψ = {ε, ε} |
Alice = H H, Bob = T T; Ω = {(H,H), (T,T)}; Ψ = {ε, ε} |
Alice = T T, Bob = H H; Ω = {(T,T), (H,H)}; Ψ = {ε, ε} |
Given the rules of the game were that Alice had to toss a coin until she saw a head followed by a tail, and Bob had to toss a coin until he saw a tail followed by a head, we knew that the game wouldn’t favor one of the two player, because the game scoring could move neither player back to zero:
Alice = T(0) H(1) H(1) H(1) T(2) |
Bob = H(0) H(0) T(1) T(1) T(1) H(2) |
Thus, all the remaining games produce equal chances for both players:
Alice = H T, Bob = T H; Ω = {(H,T), (T,H)}; Ψ = {ο, ο} |
Alice = T H, Bob = H T; Ω = {(T,H), (H,T)}; Ψ = {ο, ο} |
Alice = H T, Bob = H T; Ω = {(H,T), (H,T)}; Ψ = {ο, ο} |
Alice = T H, Bob = T H; Ω = {(T,H), (T,H)}; Ψ = {ο, ο} |
The Takeaway
That’s why we can say that out of four game patterns consolidated and expressed as patterns of tuple type tuple permutations, two produce unequal chances and two produce equal chances:
Unequal chances: 〈ο,ε〉, 〈ε,ο〉; Equal chances: 〈ε,ε〉, 〈ο,ο〉 |
Footnotes:
[1] https://www.quantamagazine.org/20160313-mathematicians-discover-prime-conspiracy/