如何不断调整随机数生成器的权重，使结果分布更均匀？

Question

我试图想出一个解决方案，可以生成具有更均匀分布结果的随机整数。

其基本思想是：

例如，我想生成一个0-9之间的随机整数。随着每个新随机数的生成，我还保留了一个列表，该列表计算每个数字生成了多少次。例如，如果第一个结果是5，那么5的计数为1，这将使数字5下次生成的可能性降低，因为其他数字的计数只有0。

起初，我想做这件事就像一个常规加权随机数生成器一样，它将所有权重相加，并在总和范围内创建一个随机数，然后查看随机数属于哪个结果。

但是，权重列表仍然与选择的顺序相同。例如，如果我们有4个选择：0、1、2、3，它们的权重为1、2、3、4。每个选择的归一化非加权概率为25%，归一化加权概率为10%, 20%, 30%和40%。这意味着归一化随机数必须为0-0.1才能滚动0,0.1-0.3才能滚动1，依此类推。

这样做的问题是，因为从长远来看，随机数生成器应该或多或少具有均匀分布的结果，如果权重仍然按照可用结果的相同顺序对齐，则可能会产生不太理想的结果。使用上面的示例。假设随机数生成器滚动0.59，这将导致数字2被选中。现在，由于选择了数字2，其他选择的权重应该增加（因此下次选择2的可能性较小）。这意味着现在选择数字3的权重范围将从0.6-1.0增加，可能会覆盖0.59，这在上次操作中是在数字2的范围内。根据设计，权重范围越大，所代表的结果被选择的机会就越大。然而，由于上次滚动了0.59，根据可靠的随机数生成器的性质，这次获得0.59的几率应该小于获得0-1之间的另一个浮点数，这反过来会降低选择数字3（如果滚动0.59，现在将选择）的几率。

我想我目前有一个解决方案，它将涉及创建一个非常大的列表，它感觉非常不优雅，并且可能很容易达到列表的大小限制。所以我想知道一个更优雅的解决方案来解决这个问题。

顺便说一下，这里（单位C#）是我目前计算权重的方式（这可能并不重要）：

// Get the largest weight number
int largestWeight = Mathf.Max(weightList.ToArray()); 

// Get list for weights adjusted based on the weight factor
List<int> adjustedWeights = new List<int>(weightList);
adjustedWeights.ForEach(w => w = Mathf.RoundToInt(Mathf.Pow((largestWeight - w + 1), weightFactor)));

此权重列表是每个结果被选择多少次的计数列表，并被维护为如果每个计数大于0，则所有计数将-1，其中保持最低计数始终为0。

Answer 1

除了Peter O的想法，使用正增长的重量，从计数1开始，并增加每个样本的计数，但使用计数的倒数作为重量。因此，计数越多的值就越不可能被选择，这与反向加权的思想类似。

一些代码（未测试！基于Math.Net numerics）

import MathNet.Numerics.Distributions;

static void Main() {

    const int N = 4;

    var counts  = new int [N] {1, 1, 1, 1};
    var weights = new double [N] {1.0, 1.0, 1.0, 1.0};

    while (true) {
        int v = Categorical.Sample(weights[k]); // sample one value in [0...N)
        // update counts and weights
        counts[v] += 1;
        weights[v] = 1.0/(double)counts[v];
        
        // use v here for something
        ...
    }
}

你可以发明更通用的权重，有一件重要的事情要记住，计数归分母。

F、 e.这样可能会更好

weights[v] = 1.0/(1.0 + .5*(double)counts[v]);

或者那个

var squared => (x) => x*x;

weights[v] = 1.0/(7.0 + .25*squared((double)counts[v]));

或者那个

weights[v] = 1.0/(3.0 + Math.Sqrt((double)counts[v]));

当它是权重分母公式中计数的单调增长函数时，它将以期望的方式改变概率

Answer 2

您似乎想要模拟我的“无替换加权选择（多个副本）”一节中描述的加权选择。在您的情况下，它可以按如下方式工作：

>

给每个项目赋予相同的权重，指定为正整数。例如，给每个项目赋予20的权重。

使用带替换算法的加权选择。也许最简单的是拒绝采样，如下所述。假设最大权重为max，每个权重为0或更大。要使用拒绝采样在[1，<代码>权重.计数]中选择整数，请执行以下操作：

1. 在[1，权重.计数]中选择一个均匀的随机整数
2. 使用概率权重[i]/max，返回i。否则，转至步骤1

除了拒绝抽样之外，还有许多其他方法可以进行加权选择；请参阅我关于加权选择算法的说明。

当每个项目被选中时，将其重量减少1，以减少被选中的可能性。

如果所有权重均为0，则为每个项目分配步骤1中选择的相同权重（在本例中为20）。

既然你提到了统一，你的目标可能是制作一个控制随机数字出现的游戏，让随机结果对玩家来说显得“更公平”。然而，你也应该考虑做出独立的统一随机选择是否会更好，尤其是如果你关心玩家是否会通过预测随机结果获得不公平的优势。