如何不断调整随机数生成器的权重，使结果分布更均匀? [英] How to constantly adjust the weight for random number generator so the results can be distributed more evenly?

问题描述

我正在尝试提出一种解决方案，该解决方案可以生成具有更均匀分布结果的随机整数.

I'm trying to come up with a solution that can generate random integers with more evenly distributed results.

基本思想是这样的:

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

For example, I want to generate a random integer between 0 - 9. As each new random number is generated, I also keep a list that counts how many times each number has been generated. And for example, if the first result is 5, then 5 will have a count of 1, which will make the number 5 less likely to be generated for the next time, because other numbers only have a count of 0.

一开始，我想这样做就像一个常规的加权随机数生成器，它将所有权重相加，并在总和范围内创建一个随机数，然后查看随机数落入哪个结果.

At first, I was thinking about doing this just like a regular weighted random number generator, which will sum up all the weights and create a random number in the range of the sum, and see which result the random number falls into.

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

However, the weight list still has the same order as the selections. For example, if we have 4 choices: 0, 1, 2, 3, and they have weights of 1, 2, 3, 4. The normalized non-weighted probabilities would be 25% for each selection, and the normalized weighted probabilities would be 10%, 20%, 30%, and 40%. This means that the normalized random number has to be 0 - 0.1 to roll 0, and 0.1 - 0.3 to roll 1, and so on.

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

The problem with this is that because a random number generator should more or less have evenly distributed results in the long run, it may produce less ideal results if the weights are still aligned in the same order of the available results. Using the example from above. Let's say the random number generator rolls a 0.59, which will result in the number 2 gets selected. And now since number 2 is selected, the weight on other selections should increase (so 2 is less likely to be selected next time). Which means that now the weight range for selecting number 3 will increase from 0.6 - 1.0, and will probably cover 0.59, which was within the range for number 2 in the last operation. By design, a larger range of weight should result in a greater chance for the represented result to be selected. However, since 0.59 was rolled last time, by the nature of a reliable random number generator, the chance of getting 0.59 this time should be less than getting another float between 0 - 1, which will in turn lower the chance of the number 3 (which will now be selected if 0.59 is rolled) get selected.

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

I think I currently have a solution that will involve creating a really big list, and it feels very inelegant, and is probably very easy to hit the size limit for a list. So I would like to know a more elegant solution to this problem.

顺便说一下，这里(在 Unity C# 中)是我目前计算权重的方式(这可能并不重要):

By the way, here (in Unity C#) is how I currently calculate the weight (which is probably not important):

// 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)));

这个 weightList 是每个结果被选中多少次的计数列表，并被维护，以便如果每个计数都大于 0，则所有计数将为 - 1，从而保持最低计数始终为 0.

This weightList is a list of counts of how many times each result has been selected, and is maintained so that if every count is greater than 0, all count will - 1, which keeps the lowest count always be 0.

推荐答案

您似乎想要模拟我的部分无替换的加权选择(多份)".在您的情况下，它可以按如下方式工作:

It appears that you want to simulate a weighted choice described in my section "Weighted Choice Without Replacement (Multiple Copies)". In your case, it could work as follows:

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

1. Give each item the same weight, specified as a positive integer. For example, give a weight of 20 to each item.

使用加权选择替换算法.也许最简单的是拒绝采样，如下所述.假设最高权重是max.要使用拒绝采样在 [1, weights.Count] 中选择一个整数:

Use a weighted-choice-with-replacement algorithm. Perhaps the simplest is rejection sampling, described as follows. Assume that the highest weight is max. To choose an integer in [1, weights.Count] using rejection sampling:

1. 在 [1, weights.Count] 中选择一个统一的随机整数 i.
2. 以概率weights[i]/max，返回i.否则，请转到第 1 步.

1. Choose a uniform random integer i in [1, weights.Count].
2. With probability weights[i]/max, return i. Otherwise, go to step 1.

除了拒绝抽样之外，还有很多其他方式可以做出加权选择；请参阅我的关于加权选择算法的说明.

There are many other ways to make a weighted choice besides rejection sampling; see my note on weighted choice algorithms.

当每个项目被选中时，将其权重减 1，以使其不太可能被选中.

As each item is chosen, reduce its weight by 1 to make it less likely to be chosen.

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

If all the weights are 0, assign each item the same weight chosen in step 1 (in this example, 20).

既然您提到了 Unity，那么您的目标可能是制作一款控制出现哪些随机数的游戏，以使随机结果显得更公平"；给玩家.但是，您还应该考虑是否最好做出独立统一随机选择，尤其是如果您关心玩家是否可以通过预测随机结果获得不公平的优势.

Since you mention Unity, your goal is probably to make a game that controls which random numbers appear, to make the random outcomes appear "fairer" to players. However, you should also consider whether it may be better to make an independent uniform random choice instead, especially if you care whether players could gain an unfair advantage by predicting the random outcomes.

这篇关于如何不断调整随机数生成器的权重，使结果分布更均匀?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！