Define flip(p) that returns True with probability p and False with probability (1-p).

Criteria

The only built-in you can use is radoom.random:

>>> import random
>>> random.random() # returns a number in [0,1)
0.4013560344771465

which returns a uniformly distributed number in the interval [0,1). You cannot specify any parameters to random.random().

Define a function geometric(p) that flips with probability p until it succeeds and returns the number of failed trials before that.

Criteria

If you are at a stage where we covered recursion, use recursion. Otherwise, use iteration.

You need to make a toss with equal chance for heads and tails, but you have a coin that you know is biased, but don’t know by how much and in which way. Using only this biased coin, design an experiment that is equivalent to making a fair toss. You can assume that the outcomes of successive tosses of the coin are independent.

Solution

The example is due to John von Neumann, taken from his 1951 paper Various Techniques Used in Connection with Random Digits.

The experiment consists of two tosses of the biased coin. If the result is HT you agree to count it as “heads”; if the result is TH you agree to count it as “tails”, or vice versa. If the result is HH or TT you ignore the result and start over. This is equivalent to a fair toss under the assumption that the outcomes of the successive tosses are independent.