分布式概率随机数生成器
本文关键字：随机数生成器 概率 分布式 | 更新日期: 2023-09-27 18:29:40
我想生成一个基于分布式概率的数字。例如，假设每个数字都出现以下情况：
Number| Count
1 | 150
2 | 40
3 | 15
4 | 3
with a total of (150+40+15+3) = 208
then the probability of a 1 is 150/208= 0.72
and the probability of a 2 is 40/208 = 0.192
我如何制作一个随机数生成器，根据这个概率分布返回随机数？
我很高兴现在这是基于一个静态的硬编码集，但我最终希望它能从数据库查询中导出概率分布。
我见过类似的例子，但它们不是很通用。有什么建议吗？
一般方法是将0..1区间的均匀分布随机数输入到所需分布的累积分布函数的倒数中。
因此，在您的情况下，只需从0..1中抽取一个随机数x（例如Random.NextDouble()），并根据其值返回
- 如果0<=则为1x<150/208
- 如果150/208<=x<190/208
- 如果190/208<=x<205/208和
- 4否则
只做一次：
- 编写一个函数，在给定pdf数组的情况下计算cdf数组。在您的示例中，pdf数组为[150,40,15,3]，cdf数组为[150190250208]
每次都这样做：
- 在[0,1）中得到一个随机数，乘以208，向上截断（或向下截断：我让你想想角的情况）。你会得到一个1…208中的整数。把它命名为r
- 对r的cdf数组执行二进制搜索。返回包含r的单元格的索引
运行时间将与给定pdf数组大小的对数成比例。这很好。但是，如果您的数组大小总是很小（在您的示例中为4），那么执行线性搜索会更容易，也会更好。
有很多方法可以通过自定义分布（也称为离散分布）生成随机整数。选择取决于许多因素，包括可供选择的整数数量、分布的形状以及分布是否会随时间变化。有关详细信息，请参阅以下问题，尤其是我的答案：
- 加载骰子的数据结构
下面的C#代码实现了Michael Vose版本的别名方法，如本文所述；另请参阅此问题。我写这个代码是为了方便您，并在这里提供它。
public class LoadedDie {
// Initializes a new loaded die. Probs
// is an array of numbers indicating the relative
// probability of each choice relative to all the
// others. For example, if probs is [3,4,2], then
// the chances are 3/9, 4/9, and 2/9, since the probabilities
// add up to 9.
public LoadedDie(int probs){
this.prob=new List<long>();
this.alias=new List<int>();
this.total=0;
this.n=probs;
this.even=true;
}
Random random=new Random();
List<long> prob;
List<int> alias;
long total;
int n;
bool even;
public LoadedDie(IEnumerable<int> probs){
// Raise an error if nil
if(probs==null)throw new ArgumentNullException("probs");
this.prob=new List<long>();
this.alias=new List<int>();
this.total=0;
this.even=false;
var small=new List<int>();
var large=new List<int>();
var tmpprobs=new List<long>();
foreach(var p in probs){
tmpprobs.Add(p);
}
this.n=tmpprobs.Count;
// Get the max and min choice and calculate total
long mx=-1, mn=-1;
foreach(var p in tmpprobs){
if(p<0)throw new ArgumentException("probs contains a negative probability.");
mx=(mx<0 || p>mx) ? P : mx;
mn=(mn<0 || p<mn) ? P : mn;
this.total+=p;
}
// We use a shortcut if all probabilities are equal
if(mx==mn){
this.even=true;
return;
}
// Clone the probabilities and scale them by
// the number of probabilities
for(var i=0;i<tmpprobs.Count;i++){
tmpprobs[i]*=this.n;
this.alias.Add(0);
this.prob.Add(0);
}
// Use Michael Vose's alias method
for(var i=0;i<tmpprobs.Count;i++){
if(tmpprobs[i]<this.total)
small.Add(i); // Smaller than probability sum
else
large.Add(i); // Probability sum or greater
}
// Calculate probabilities and aliases
while(small.Count>0 && large.Count>0){
var l=small[small.Count-1];small.RemoveAt(small.Count-1);
var g=large[large.Count-1];large.RemoveAt(large.Count-1);
this.prob[l]=tmpprobs[l];
this.alias[l]=g;
var newprob=(tmpprobs[g]+tmpprobs[l])-this.total;
tmpprobs[g]=newprob;
if(newprob<this.total)
small.Add(g);
else
large.Add(g);
}
foreach(var g in large)
this.prob[g]=this.total;
foreach(var l in small)
this.prob[l]=this.total;
}
// Returns the number of choices.
public int Count {
get {
return this.n;
}
}
// Chooses a choice at random, ranging from 0 to the number of choices
// minus 1.
public int NextValue(){
var i=random.Next(this.n);
return (this.even || random.Next((int)this.total)<this.prob[i]) ? I : this.alias[i];
}
}
示例：
var loadedDie=new LoadedDie(new int[]{150,40,15,3}); // list of probabilities for each number:
// 0 is 150, 1 is 40, and so on
int number=loadedDie.nextValue(); // return a number from 0-3 according to given probabilities;
// the number can be an index to another array, if needed
我把这个代码放在公共领域。
我知道这是一篇老帖子，但我也搜索过这样一个生成器，对我找到的解决方案不满意。所以我写了我自己的，想把它分享给全世界。
在调用"NextItem（…）"之前，只需多次调用"Add（…）
/// <summary> A class that will return one of the given items with a specified possibility. </summary>
/// <typeparam name="T"> The type to return. </typeparam>
/// <example> If the generator has only one item, it will always return that item.
/// If there are two items with possibilities of 0.4 and 0.6 (you could also use 4 and 6 or 2 and 3)
/// it will return the first item 4 times out of ten, the second item 6 times out of ten. </example>
public class RandomNumberGenerator<T>
{
private List<Tuple<double, T>> _items = new List<Tuple<double, T>>();
private Random _random = new Random();
/// <summary>
/// All items possibilities sum.
/// </summary>
private double _totalPossibility = 0;
/// <summary>
/// Adds a new item to return.
/// </summary>
/// <param name="possibility"> The possibility to return this item. Is relative to the other possibilites passed in. </param>
/// <param name="item"> The item to return. </param>
public void Add(double possibility, T item)
{
_items.Add(new Tuple<double, T>(possibility, item));
_totalPossibility += possibility;
}
/// <summary>
/// Returns a random item from the list with the specified relative possibility.
/// </summary>
/// <exception cref="InvalidOperationException"> If there are no items to return from. </exception>
public T NextItem()
{
var rand = _random.NextDouble() * _totalPossibility;
double value = 0;
foreach (var item in _items)
{
value += item.Item1;
if (rand <= value)
return item.Item2;
}
return _items.Last().Item2; // Should never happen
}
}
感谢所有的解决方案人员！非常感谢！
@Menjaraz我尝试实现您的解决方案，因为它看起来非常资源友好，但在语法方面遇到了一些困难。
所以现在，我只是使用LINQ SelectMany（）和Enumerable.Reative（）.将我的摘要转换为一个值的平面列表
public class InventoryItemQuantityRandomGenerator
{
private readonly Random _random;
private readonly IQueryable<int> _quantities;
public InventoryItemQuantityRandomGenerator(IRepository database, int max)
{
_quantities = database.AsQueryable<ReceiptItem>()
.Where(x => x.Quantity <= max)
.GroupBy(x => x.Quantity)
.Select(x => new
{
Quantity = x.Key,
Count = x.Count()
})
.SelectMany(x => Enumerable.Repeat(x.Quantity, x.Count));
_random = new Random();
}
public int Next()
{
return _quantities.ElementAt(_random.Next(0, _quantities.Count() - 1));
}
}
使用我的方法。它简单易懂。我不计算0…1范围内的部分，我只使用"概率池"（听起来很酷，是吗？）
在圆形图中，您可以看到池中每个元素的重量
在这里你可以看到轮盘累积概率的实现
`
// Some c`lass or struct for represent items you want to roulette
public class Item
{
public string name; // not only string, any type of data
public int chance; // chance of getting this Item
}
public class ProportionalWheelSelection
{
public static Random rnd = new Random();
// Static method for using from anywhere. You can make its overload for accepting not only List, but arrays also:
// public static Item SelectItem (Item[] items)...
public static Item SelectItem(List<Item> items)
{
// Calculate the summa of all portions.
int poolSize = 0;
for (int i = 0; i < items.Count; i++)
{
poolSize += items[i].chance;
}
// Get a random integer from 0 to PoolSize.
int randomNumber = rnd.Next(0, poolSize) + 1;
// Detect the item, which corresponds to current random number.
int accumulatedProbability = 0;
for (int i = 0; i < items.Count; i++)
{
accumulatedProbability += items[i].chance;
if (randomNumber <= accumulatedProbability)
return items[i];
}
return null; // this code will never come while you use this programm right :)
}
}
// Example of using somewhere in your program:
static void Main(string[] args)
{
List<Item> items = new List<Item>();
items.Add(new Item() { name = "Anna", chance = 100});
items.Add(new Item() { name = "Alex", chance = 125});
items.Add(new Item() { name = "Dog", chance = 50});
items.Add(new Item() { name = "Cat", chance = 35});
Item newItem = ProportionalWheelSelection.SelectItem(items);
}
下面是一个使用逆分布函数的实现：
using System;
using System.Linq;
// ...
private static readonly Random RandomGenerator = new Random();
private int GetDistributedRandomNumber()
{
double totalCount = 208;
var number1Prob = 150 / totalCount;
var number2Prob = (150 + 40) / totalCount;
var number3Prob = (150 + 40 + 15) / totalCount;
var randomNumber = RandomGenerator.NextDouble();
int selectedNumber;
if (randomNumber < number1Prob)
{
selectedNumber = 1;
}
else if (randomNumber >= number1Prob && randomNumber < number2Prob)
{
selectedNumber = 2;
}
else if (randomNumber >= number2Prob && randomNumber < number3Prob)
{
selectedNumber = 3;
}
else
{
selectedNumber = 4;
}
return selectedNumber;
}
验证随机分布的一个例子：
int totalNumber1Count = 0;
int totalNumber2Count = 0;
int totalNumber3Count = 0;
int totalNumber4Count = 0;
int testTotalCount = 100;
foreach (var unused in Enumerable.Range(1, testTotalCount))
{
int selectedNumber = GetDistributedRandomNumber();
Console.WriteLine($"selected number is {selectedNumber}");
if (selectedNumber == 1)
{
totalNumber1Count += 1;
}
if (selectedNumber == 2)
{
totalNumber2Count += 1;
}
if (selectedNumber == 3)
{
totalNumber3Count += 1;
}
if (selectedNumber == 4)
{
totalNumber4Count += 1;
}
}
Console.WriteLine("");
Console.WriteLine($"number 1 -> total selected count is {totalNumber1Count} ({100 * (totalNumber1Count / (double) testTotalCount):0.0} %) ");
Console.WriteLine($"number 2 -> total selected count is {totalNumber2Count} ({100 * (totalNumber2Count / (double) testTotalCount):0.0} %) ");
Console.WriteLine($"number 3 -> total selected count is {totalNumber3Count} ({100 * (totalNumber3Count / (double) testTotalCount):0.0} %) ");
Console.WriteLine($"number 4 -> total selected count is {totalNumber4Count} ({100 * (totalNumber4Count / (double) testTotalCount):0.0} %) ");
示例输出：
selected number is 1 selected number is 1 selected number is 1 selected number is 1 selected number is 2 selected number is 1 ... selected number is 2 selected number is 3 selected number is 1 selected number is 1 selected number is 1 selected number is 1 selected number is 1 number 1 -> total selected count is 71 (71.0 %) number 2 -> total selected count is 20 (20.0 %) number 3 -> total selected count is 8 (8.0 %) number 4 -> total selected count is 1 (1.0 %)
根据@Adam Zalcman的回答，这里有一个简单的DiscreteDistribution类，也使用了一些流利的语法，它使用了累积分布函数的倒数技巧，因为我注意到有些人希望看到一些代码实现。
public class DiscreteDistribution
{
private (double Value, int Index)[] distribution;
private Random random;
public DiscreteDistribution(Random? random = null)
{
this.random = random ?? new Random();
distribution = new (double, int)[0];
}
public DiscreteDistribution BasedOn(double[] distribution)
{
this.distribution = distribution.Select((value, i) => (value, i)).ToArray();
Array.Sort(this.distribution, (p1, p2) => p1.Value.CompareTo(p2.Value));
return this;
}
public T Sample<T>(T[] data)
{
double r = random.NextDouble() * distribution.Last().Value;
for (int i = 0; i < distribution.Length - 1; i++)
{
if(distribution[i].Value < r && r <= distribution[i + 1].Value)
{
return data[distribution[i + 1].Index];
}
}
return data[distribution.First().Index];
}
}
示例用法：
DiscreteDistribution distribution = new();
double[] distrubutionValues = { 0.2, 0.7, 0.1 };
int elements = { 1, 2, 3 };
int element = distribution.BasedOn(distributionValues).Sample(elements);
注意，elements和distributionValues需要具有相同的长度。对于生产用途，您应该添加自己的检查。