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

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 f开发者_如何学Pythonair 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?

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;
}

How about this:
1. Find out the binary representation of n
2. Flip the fair coin logn times. Each flip corresponds to a bit.
3. If the result of the flip is greater than the value of n, reroll.
4. If the result is 0, return heads.
5. Otherwise, return tails.

Since most values of N are not powers of 2 it's not strictly possible to guarantee a probability of 1/N from any number of coin tosses. Instead you'll have to settle for something which approaches 1/N to your desired accuracy. But hey, that's coin tossing for you anyway.

Draw yourself a decision tree with 2 branches at the root (labelled H and T), then 2 branches at each node (also labelled H and T), until you reach enough leaf nodes to satisfy your accuracy requirements. Label the right (for you) fraction of leaves with the values you want, eg 1,2,3 if N=3. Each leaf then defines a route from the root, such as HHHTTHH (or whatever). These define the sequence of tosses which result in a '3'.

I'll leave the coding to you.