How can you get a fair coin toss if someone hands you a coin that is weighted to come up heads more often than tails?
This is @luismartingil solution. Please check all the Python source code here. This solution uses matplotlib
for the plots.
We can have two different types of results when throwing the coin: {heads, tails}
player-heads
, player-tails
}player-heads
is the player that chooses heads. player-tails
the one choosing tails.We first need to know how unfair the game is in order to make it fair. We have to know how many times the coin comes up heads vs the times it comes up tails. We do this throwing the coin N times, where N is a huge number. After doing this we have a percentage of the times the coin comes up heads, lets call it p1
. We can define the percentage of times the coin comes up tails as p2
.
Based on the problem:
- p1
and p2
are in this range [0, 100]
- p1
will be bigger than p2
. p1 > p2
We can assume that p2 = 100 - p1
.
In order the game to be fair, player-heads
has to win more than the p1
times of the times played in order to win the game. The bigger N is, the fairer the game is.
Always back what you are saying!. A neat way to back my solution is to write some code and perform a simulation. That’s what I did.
1 class Game(object):
2 coin = None
3 simulation = None
4 def __init__(self, c):
5 self.coin = c
6 def simulate(self, n):
7 self.simulation = {HEADS : 0, TAILS : 0}
8 for i in range(n):
9 self.simulation[self.coin.throw()] += 1
10 return self.whoWon()
11 def whoWon(self):
12 if self.simulation:
13 # PLAY_TAILS wins in case of even
14 return self.simulation, PLAY_HEADS if self.getCondHeads() else PLAY_TAILS
Original game. It doesn’t know if the coin is weighted or not.
1 class UnfairGame(Game):
2 def getCondHeads(self):
3 return self.simulation[HEADS] > self.simulation[TAILS]
A handicap is applied to the player-tails
. Takes into account thw weight of the coin (coin.getPercent()
).
1 class FairGame(Game):
2 def getCondHeads(self):
3 # PLAY_HEADS needs to win more to win the game. Handicap ;-)
4 # @luismartingil solution to the problem.
5 total = self.simulation[HEADS] + self.simulation[TAILS]
6 return (self.simulation[HEADS] > (self.coin.getPercent() * total))
Both FairGame
and UnfairGame
will be played with different coins.
Coin 1) 50% - 50%
Coin 2) 60% - 40%
Coin 3) 80% - 20%
These plots contains information about the wins of the player-head
in a percentage based. Whether we have a fair or unfair {game, coin} the goal for a fair game is to see the points right in the 50% horizontal line, which would be the fairest game possible.
Some comments,
UnfairGame
is always a looser game for player-tails
using unweighted coin. This means that player-tails
is likely to win in the beginning, but if he plays a bunch of times he will loose.FairGame
solution works, it converges to 50% in all the cases.I was curious about the fact of grading a fair solution. I came up with a function which returns how fair the solution is based on how close it is from the 50% percent. You can see the code and some plots below.
1 def processFairness(percent):
2 """ Return a value in [0, 1] defining how fair is the percent.
3 0, worst.
4 1, best.
5
6 Applies the fairness function based on:
7 if x == 50 , y = 1
8 if 0 <= x < 50, y = x/50.0
9 if 50 < x <= 100, y=-x/50.0 + 2
10
11 |
12 | (50,1)
13 | _
14 | /|\
15 | / | \
16 | / | \
17 | / | \
18 | / | \
19 | / | \
20 | / | \
21 | / | \
22 |/ | \
23 ---------------------------------------------------------------
24 (0,0) (50,0) (100,0)
25
26 """
27 if (percent == 50): ret = 1.0
28 elif (0 <= percent < 50): ret = float(percent) / 50.0
29 elif (50 < percent <= 100): ret = (float(-percent) / 50.0) + 2.0
30 else: raise percentOutOfRange('Error calculating fairness. percent:%s' % percent)
31 return ret
Some comments,
UnfairGame
always converges to rate 0 when using an unfair coin.FairGame
solution rates very good for a med-high N. Nothing that we didn’t know.Bet your money in heads
when the coin is weighted to come up heads more often than tails. Save your money in all other cases. Better than a casino.