Given a function for a fair coin, write a function for a biased coin?

puzzle

Solution

Assuming:

int fairCoinToss();

returns 1 for heads and 2 for tails, writing:

int biasedCoinToss(int n);

where heads (1) will appear 1/n of the time this should work:

int biasedCoinToss(int n) {
  if (n == 1) {
    return 1; // 1/1 = 1 = always heads
  } else if (n == 2) {
    return fairCoinToss(); // 1/2 = 50% = fair coint oss
  }
  int r = random_number(n);
  return r == 0 ? 1 : 0;
}

where `random_number(n)` generates a fair random integer i such that `0 <= i < n`. So `random_number(3)` is 0, 1 or 2. Assuming even distribution, value 0 will come out 1/3 of the time.

Of course we can't use a native random number generator but we can create one anyway. `fairCoinToss()` randomly generates a 1 or 0. Multiple coin tosses can be combined to generate a larger number. For example:

fairCoinToss() << 1 | fairCoinToss()

will generate:

00 = 0
01 = 1
10 = 2
11 = 3

which by definition is a random number from 0 to 3 (n = 4).

That's fine if n is a power-of-2 but it isn't necessarily. That's easy enough to cater for however. Assume n = 5. At best we can generate a random number from 0 to 7. If you "reroll" 5, 6 or 7 until you get a number in the range of 0 to 4 then you have (non-deterministically) constructed a random number fairly distributed from 0 to 4 inclusive, satisfying the requirement.

Code for that looks something like this:

int random_number(int n) {
  int ret;
  do {
    int limit = 2;
    ret = fairCoinToss();
    while (limit < n) {
      ret <<= 1;
      ret |= fairCoinToss();
      limit <<= 1;
    }
  } while (ret >= n);
  return ret;
}

Problem

I came across this reported interview question when doing some reviewing (the following quote is all the info I found about the problem): Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param) At first glance I wrote: ``` int biased_coin(n) { //0=Tails, 1=Heads int sum = 0; if(n==1) return 1; for(int i=0;i<n;i++) { sum += unbiased(); //unbiased returns 0 50% of the time and 1 50% of the time } if(sum == 1) return 1; return 0; } ``` But this obviously doesn't work. For n=4, for instance, it does work: since the probability of getting a single Head given 4 tosses is 4/(2^4)=1/4. But for say n=3, 3/(2^3)!=1/3. What is the proper way to implement something like this assuming you can't use a random number generator?

Original source