2

我遇到了以下问题：

使用 rand() 函数，生成一个期望值为 k 的数字。选项是：

1)

   int GetRandom(int k)
   {
       v=0;
       while(rand()<1.0f/(float)k)
           v++; 
       return v;
    }

2)

   int GetRandom(int k)
   {
       v=0;
       while(rand()<(1-1.0f/(float)k))
           v++; 
       return v;
    }

3)

   int GetRandom(int k)
   {
       v=0;
       while(rand() > (1-1.0f/(float)(k+1)))
           v++; 
       return v;
    }

1）似乎是正确的答案。检查特定值的结果k似乎表明情况并非如此。（我设置k=3。100000试验值的频率分布如下图所示）

如何做到这一点？

这个问题有点类似于这个问题。

4

1 回答 1

3

你想要（2）。这对带有 mean的Geometric Distribution（链接）进行采样k。

几何分布代表这种实验：

  • 某个事件重复发生，结果为 0 或 1
  • 事件的结果是概率为 1，概率为p01-p
  • 第一个结果为 1 的事件的索引是多少？

因此X ~ G(p)，如果X是随机变量并且p是上述概率，则X表示“结果为 1 的第一个事件的索引是多少？” 期望是E[X] = 1/p。

鉴于此信息，现在应该清楚以下表示随机变量的采样X（p = 1/k并且等效于（2））。

int Sample(int k)
{
    int v = 1;
    while (true)
    {
        //outcome is true with probability p = 1/k
        bool outcome = rand() < 1 / (double)k;
        if (outcome)
            return v;
        else
            v++;
    }
}

请注意，查看峰值（模式）和分布的期望不是一回事。几何分布的峰值总是在 1！

于 2013-06-20T20:51:36.113 回答