puzzle - 给定一个公平硬币的函数，为一个有偏见的硬币写一个函数？

Question

我在做一些回顾时遇到了这个报告的面试问题(以下引用是我找到的关于这个问题的所有信息):

Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param)

乍一看，我写道:

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 次 throw 得到单个正面的概率是 4/(2^4)=1/4。但是对于 n=3，3/(2^3)!=1/3。

假设您不能使用随机数生成器，那么实现此类操作的正确方法是什么？

Answer 1

假设:

int fairCoinToss();

正面返回 1，反面返回 2，写作:

int biasedCoinToss(int n);

其中头 (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;
}