给定一个公平硬币的功能,为有偏见的硬币写一个函数？

Question

我在做一些评审时遇到了这个报道的面试问题(以下引用是我发现的关于这个问题的所有信息):

给定一个公平的硬币的功能,写一个有偏见的硬币的功能,返回头1/n次(n是一个参数)

乍一看我写道:

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

但这显然不起作用.例如,对于n = 4,它确实起作用:因为给出4个投掷的单个头的概率是4 /(2 ^ 4)= 1/4.但是对于说n = 3,3 /(2 ^ 3)!= 1/3.

假设你不能使用随机数生成器,实现这样的东西的正确方法是什么？

Answer 1

假设:

int fairCoinToss();

头部返回1,尾部返回2,写入:

int biasedCoinToss(int n);

其中head(1)将出现1/n的时间应该起作用:

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

其中random_number(n)生成一个公平的随机整数i 0 <= i < n.所以random_number(3)是0,1或2.假设均匀分布,值0将在1/3的时间出现.

当然我们不能使用本机随机数生成器,但我们无论如何都可以创建一个.fairCoinToss()随机生成1或0.可以组合多个硬币投掷以生成更大的数字.例如:

fairCoinToss() << 1 | fairCoinToss()

会产生:

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

根据定义,它是0到3的随机数(n = 4).

如果n是2的幂,那就没关系,但不一定如此.然而,这很容易满足.假设n = 5.最多我们可以生成一个从0到7的随机数.如果你"重新"5,6或7,直到得到一个0到4范围内的数字,那么你(非确定性地)构造了一个随机数公平分布在0到4之间,满足要求.

代码看起来像这样:

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