加权随机数

Question

我正在尝试实施加权随机数.我现在只是把头靠在墙上,无法解决这个问题.

在我的项目(德州扑克手牌范围,主观全权证券分析)中,我正在使用Boost的随机函数.所以,假设我想选择1到3之间的随机数(所以要么是1,2或3).Boost的mersenne twister发电机就像这样的魅力.但是,我希望选择加权,例如:

1 (weight: 90)
2 (weight: 56)
3 (weight:  4)

Boost是否具有某种功能？

Answer 1

有一个简单的随机选择项目的算法,其中项目具有单独的权重:

1)计算所有权重的总和

2)选择0或更大且小于权重之和的随机数

3)一次一个地查看项目,从随机数中减去它们的重量,直到得到随机数小于项目重量的项目为止

伪代码说明了这一点:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

这应该很容易适应你的增压容器等.

如果您的权重很少改变,但您经常随机选择一个,并且只要您的容器存储指向对象的指针或长度超过几十个项目(基本上,您必须剖析以了解这是否有帮助或阻碍) ,然后有一个优化:

通过在每个项目中存储累积权重总和,您可以使用二分搜索来选择与拾取权重相对应的项目.

如果您不知道列表中的项目数,那么有一个非常简洁的算法,称为水库采样,可以调整为加权.

Answer 2

更新了旧问题的答案.您可以使用std :: lib在C++ 11中轻松完成此操作:

#include <iostream>
#include <random>
#include <iterator>
#include <ctime>
#include <type_traits>
#include <cassert>

int main()
{
    // Set up distribution
    double interval[] = {1,   2,   3,   4};
    double weights[] =  {  .90, .56, .04};
    std::piecewise_constant_distribution<> dist(std::begin(interval),
                                                std::end(interval),
                                                std::begin(weights));
    // Choose generator
    std::mt19937 gen(std::time(0));  // seed as wanted
    // Demonstrate with N randomly generated numbers
    const unsigned N = 1000000;
    // Collect number of times each random number is generated
    double avg[std::extent<decltype(weights)>::value] = {0};
    for (unsigned i = 0; i < N; ++i)
    {
        // Generate random number using gen, distributed according to dist
        unsigned r = static_cast<unsigned>(dist(gen));
        // Sanity check
        assert(interval[0] <= r && r <= *(std::end(interval)-2));
        // Save r for statistical test of distribution
        avg[r - 1]++;
    }
    // Compute averages for distribution
    for (double* i = std::begin(avg); i < std::end(avg); ++i)
        *i /= N;
    // Display distribution
    for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i)
        std::cout << "avg[" << i << "] = " << avg[i-1] << '\n';
}

我的系统输出:

avg[1] = 0.600115
avg[2] = 0.373341
avg[3] = 0.026544

请注意,上面的大部分代码都专门用于显示和分析输出.实际生成只是几行代码.输出表明已获得所请求的"概率".您必须将请求的输出除以1.5,因为这是请求加起来的.

Answer 3

如果你的权重变化比绘制的慢,C++ 11 discrete_distribution将是最简单的:

#include <random>
#include <vector>
std::vector<double> weights{90,56,4};
std::discrete_distribution<int> dist(std::begin(weights), std::end(weights));
std::mt19937 gen;
gen.seed(time(0));//if you want different results from different runs
int N = 100000;
std::vector<int> samples(N);
for(auto & i: samples)
    i = dist(gen);
//do something with your samples...

但请注意,c ++ 11 discrete_distribution计算初始化时的所有累积和.通常,您需要这样做,因为它会加快一次O(N)成本的采样时间.但是对于快速变化的分布,它将导致繁重的计算(和存储器)成本.例如,如果权重表示有多少项目,并且每次绘制一个项目,则删除它,您可能需要自定义算法.

Will的回答/sf/answers/123315251/避免了这种开销,但是比C++ 11更慢,因为它不能使用二进制搜索.

要看到它这样做,你可以看到相关的行(/usr/include/c++/5/bits/random.tcc在我的Ubuntu 16.04 + GCC 5.3上安装):

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }

Answer 4

当我需要加权数字时我所做的是使用随机数作为重量.

例如:我需要使用以下权重生成1到3的随机数:

• 随机数的10%可以是1
• 随机数的30%可能是2
• 60%的随机数可能是3

然后我用:

weight = rand() % 10;

switch( weight ) {

    case 0:
        randomNumber = 1;
        break;
    case 1:
    case 2:
    case 3:
        randomNumber = 2;
        break;
    case 4:
    case 5:
    case 6:
    case 7:
    case 8:
    case 9:
        randomNumber = 3;
        break;
}

有了它,随机它有10%的概率为1,30%为2和60%为3.

您可以根据需要使用它.

希望我能帮助你,祝你好运!