pythonalgorithmpython-2.7probabilitycoin-flipping

convert an unfair coin into a fair coin in Python 2.7


Using Python 2.7. Suppose I have an unfair coin and I want to turn it into a fair coin using the following way,

  1. Probability of generating head is equal for unfair coin;
  2. Flip unfair coin and only accept head;
  3. When a head is appearing, treat it as 1 (head for virtual fair coin), when another head is appearing, treat it as 0 (tail for virtual fair coin), next time when head appears, treat it as 1, next time treat as 0, ..., and so on.

Not sure if this method works? Actually I am not quite confident about the method above and also how to use equalCoinHelper() correctly (I mark my question in my code).

If anyone have any good ideas, it will be great.

from __future__ import print_function
import random
counter = 0

# 0.3 probability return head as 1
# 0.7 probability return tail as 0
def unFairCoin():
   if random.random() < 0.3:
       return 1
   else:
       return 0

# probability of generating 1 is equal, so keep 1 only
def equalCoinHelper():
    result = 0
    while result == 0:
        result = unFairCoin()

def equalDistribution():
    global counter
    # not think about how to leverage this better
    equalCoinHelper()
    counter += 1
    if counter % 2 == 0:
        return 1
    else:
        return 0

if __name__ == "__main__":
    # generate 10 random 0/1 with equal probability
    print ([equalDistribution() for _ in range(10)])

Solution

  • Getting a Fair Toss From a Biased Coin explains a simple algorithm for turning a biased coin into a fair coin:

    1. Flip the coin twice.
    2. If both tosses are the same (heads-heads or tails-tails), repeat step 1.
    3. If the tosses come up heads-tails, count the toss as heads. If the tosses come up tails-heads, count it as tails.

    In Python this would be:

    def fairCoin():
        coin1 = unfairCoin()
        coin2 = unfairCoin()
        if coin1 == coin2:
            return fairCoin() # both are the same, so repeat it
        elif coin1 == 1 and coin2 == 0:
            return 1
        else:
            return 0
    

    The elif and else blocks can be simplified to just:

        else:
            return coin1