07 Jan 05
5 edits
Suppose somebody approaches you on the street and wants to flip a coin for money. He offers you better than even odds (say 2:1, but the actual odds are irrelvant to this problem) to choose tails. The coin may be biased by an unknown amount; that is, it may land heads, say, 60% of the time (again, an arbitrary and irrelevant figure). Finally, he will only play once, and you are not allowed to experiment with the coin beforehand - you can't flip the coin an arbitrary number of times in order to empirically estimate its bias.
Construct rules for playing a coin-flipping game, one time, such that you receive your advertised odds (for example, 2:1) in expected value. That is, create rules for flipping the biased coin that effectively eliminate the coin's bias. (The restriction that you may only play the game one time should not be construed to mean that the coin may only be flipped one time, but it should be construed to mean that the game is required to terminate with a winner being declared with each player being equally likely to win.)
Of course, your solution should be a mathematical one, not a physical one like trying to influence which side the coin actually lands on.
I offer mad props to anybody who can solve this without having seen the solution before. This problem was first told to me by a former colleague of mine and I was unable to solve it on the spot.
Dr. S
07 Jan 05
1 edit
Originally posted by DoctorScribblesI foresee a difficulty: what if the coin is guaranteed to land on heads? Then any game I could conceive of would have only one possible outcome (assuming we don't play papers/scissors/stone or something else to somehow randomise things) so there's no way each player could be equally likely to win.
Suppose somebody approaches you on the street and wants to flip a coin for money. He offers you better than even odds (say 2:1, but the actual odds are irrelvant to this problem) to choose tails. The coin may be biased by an unkno ...[text shortened]... lleague of mine and I was unable to solve it on the spot.
Dr. S
Of course, this is an extreme case - my hunch is that all effective methods run into a kind of halting problem, where they stop in finite time with probability 1 UNLESS the coin is guaranteed to land heads or tails, in which case the game cannot end.
Edit: Having said this, I've thought of a game which would work, but has exactly the difficulty I foresaw:
1. Player A tosses the coin until he gets heads, and records the number of tosses required. Player B does the same.
2. If one player requires fewer tosses than the other, he wins. Otherwise, go back to 1.
I won't bother working out the probabilities, but it should be clear that this game will end sooner or later if and only if the coin's chance of landing on heads is not 0 or 1.
07 Jan 05
Originally posted by AcolyteGood observation. Let us assume that each of Heads and Tails has a non-zero probability of landing. If this is not the case, then the method I have in mind does not halt, and I believe you are correct that any method that meets the fairness crieria won't halt given a coin that always lands on one side.
I foresee a difficulty: what if the coin is guaranteed to land on heads? Then any game I could conceive of would have only one possible outcome (assuming we don't play papers/scissors/stone or something else to somehow randomise things) so there's no way each player could be equally likely to win.
Of course, this is an extreme case - my hunch is that a ...[text shortened]... ility 1 UNLESS the coin is guaranteed to land heads or tails, in which case the game cannot end.
07 Jan 05
Originally posted by DoctorScribblesSorry about the sneaky edit. Tell me, what's the exchange rate these days between mad props and metaphorical biscuits (aka cookies)?
Good observation. Let us assume that each of Heads and Tails has a non-zero probability of landing. If this is not the case, then the method I have in mind does not halt, and I believe you are correct that any method that meets the fairness crieria won't halt given a coin that always lands on one side.
07 Jan 05
1 edit
Originally posted by AcolyteThis is not the method I had in mind. Would you humor me with a proof that the players are equally likely to win?
Sorry about the sneaky edit. Tell me, what's the exchange rate these days between mad props and metaphorical biscuits (aka cookies)?
The method I have in mind is simpler to play and has a straightforward proof.
08 Jan 05
Originally posted by DoctorScribblesBy symmetry: let's say in round n, player A needs A(n) tosses to get heads, and player B needs B(n). Then all the A(n),B(n) are independent and identically distributed. This means:
Actually, I retract this. I suppose your solution is just as good as mine, provided you can show a proof.
1. P(A(n)<B(n)) = P(B(n)<A(n)), ie, if round n occurs, P(A wins in round n) = P(B wins in round n). Since this is true in every round, P(A wins) = P(B wins).
2. P(A(n)=B(n)) = c, some constant independent of n (and clearly less than 1 if and only if the coin isn't guaranteed to land the same way every time). This means that P(at least n + 1 rounds are needed) is c^n, which tends to zero as n tends to infinity for any |c| less than 1, and is always 1 for c = 1. So P(no-one wins) = 0 under your condition.
Hence P(A wins) = P(B wins) = 1/2.
I'd be interested to see how much simpler your solution is - had you not asked me to write a proof, I would have thought 'by symmetry' would suffice as a justification for mine.
08 Jan 05
Originally posted by AcolyteI mainly wanted to see your proof just to contrast it with that of my solution.
By symmetry: let's say in round n, player A needs A(n) tosses to get heads, and player B needs B(n). Then all the A(n),B(n) are independent and identically distributed. This means:
1. P(A(n)<B(n)) = P(B(n)<A(n)), ie, if round n occurs, P(A wins in round n) = P(B wins in round n). Since this is true in every round, P(A wins) = P(B wins).
2. P(A(n)=B ...[text shortened]... o write a proof, I would have thought 'by symmetry' would suffice as a justification for mine.
My solution is this:
1. Toss the coin twice.
2. If the observed sequence is HT, stop, declaring player A the winner.
3. If the observed sequence is TH, stop, declaring player B the winner.
4. If the observed sequence is HH or TT, go to step 1.
Proof of equilikelihood:
Let h be the probability that heads lands on any one throw.
Let t be the probability that tails lands on any one throw.
Any iteration of the above algorithm terminates with A the winner with probability h*t.
Any iteration of the above algorithm terminates with B the winner with probabilty t*h=h*t.
For termination, note that any iteration of the algorithm results in an additional iteration with probability 1 - 2*h*t, which tends to vanish as the number of iterations approaches infinity.
I believe that on average, my method expects to require fewer coin tosses than your method, independent of h.
10 Jan 05
Originally posted by DoctorScribblesYep, that looks like a more efficient solution - I suspect the efficiency of mine approaches yours in the limit as the proportion of tails tends to zero. They're both fairly simple though.
I mainly wanted to see your proof just to contrast it with that of my solution.
My solution is this:
1. Toss the coin twice.
2. If the observed sequence is HT, stop, declaring player A the winner.
3. If the observed sequence is TH, stop, declaring player B the winner.
4. If the observed sequence is HH or TT, go to step 1.
Proof of equ ...[text shortened]... t on average, my method expects to require fewer coin tosses than your method, independent of h.