分布式概率随机数发生器

我想根据分布式概率生成一个数字。 例如，只是说每个数字有以下几种情况：

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 

如何根据此概率分布创建一个返回数字的随机数生成器？

我很高兴现在基于静态的硬编码集，但我最终希望它从数据库查询中获得概率分布。

我见过类似这样的例子，但它们不是很通用。 有什么建议？

Answer 1

一般方法是将从0..1间隔的均匀分布的随机数馈送到所需分布的累积分布函数的倒数 。

因此，在您的情况下，只需从0..1中绘制一个随机数x（例如使用Random.NextDouble() ）并根据其值返回

• 1如果0 <= x <150/208，
• 2如果150/208 <= x <190/208，
• 3如果190/208 <= x <205/208和
• 否则为4。

Answer 2

该问题解释了生成具有不同概率的随机数的各种方法。 根据这篇文章 ，在这个问题上显示，最好的方法（在时间复杂度方面）是Michael Vose所谓的“别名方法”。

为方便起见，我编写并提供了一个实现别名方法的随机数生成器的C＃实现：

 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(); this.alias=new List(); this.total=0; this.n=probs; this.even=true; } Random random=new Random(); List prob; List alias; long total; int n; bool even; public LoadedDie(IEnumerable probs){ // Raise an error if nil if(probs==null)throw new ArgumentNullException("probs"); this.prob=new List(); this.alias=new List(); this.total=0; this.even=false; var small=new List(); var large=new List(); var tmpprobs=new List(); 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 || p0 && 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 

例：

  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 

我将此代码放在公共域中。

Answer 3

这只做一次：

• 编写一个函数，在给定pdf数组的情况下计算cdf数组。 在你的例子中，pdf数组是[150,40,15,3]，cdf数组将是[150,190,205,208]。

每次都这样做：

• 获取[0,1]中的随机数，乘以208，截断（或者向下：我留给你考虑角点情况）你将在1..208中得到一个整数。 把它命名为r。
• 对cd执行cdf数组的二进制搜索 。 返回包含r的单元格的索引。

运行时间将与给定pdf数组的大小的对数成比例。 这很好。 但是，如果您的数组大小总是如此之小（在您的示例中为4），则执行线性搜索会更容易，并且性能也会更好。

Answer 4

我知道这是一个老post，但我也搜索了这样一个发生器，并且对我发现的解决方案不满意。 所以我写了自己的想法并希望与全世界分享。

在调用“NextItem（…）”之前，只需调用“添加（…）”一段时间

 /// 
 A class that will return one of the given items with a specified possibility. 
 ///  The type to return.  ///  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.  public class RandomNumberGenerator { private List> _items = new List>(); private Random _random = new Random(); /// 
 /// All items possibilities sum. /// 
 private double _totalPossibility = 0; /// 
 /// Adds a new item to return. /// 
 ///  The possibility to return this item. Is relative to the other possibilites passed in.  ///  The item to return.  public void Add(double possibility, T item) { _items.Add(new Tuple(possibility, item)); _totalPossibility += possibility; } /// 
 /// Returns a random item from the list with the specified relative possibility. /// 
 ///  If there are no items to return from.  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 } } 

Answer 5

谢谢你所有的解决方案！ 非常感激！

@Menjaraz我尝试实现你的解决方案，因为它看起来非常资源友好，但是语法有些困难。

所以现在，我只是使用LINQ SelectMany（）和Enumerable.Repeat（）将我的摘要转换为一个平面的值列表。

 public class InventoryItemQuantityRandomGenerator { private readonly Random _random; private readonly IQueryable _quantities; public InventoryItemQuantityRandomGenerator(IRepository database, int max) { _quantities = database.AsQueryable() .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)); } } 

Answer 6

使用我的方法。 它简单易懂。 我不计算范围0 … 1中的部分，我只使用“Probabilityp Pool”（听起来很酷，是吗？）

在圆图中，您可以看到池中每个元素的权重

在这里你可以看到轮盘赌的累积概率的实现

 ` // 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 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 items = new List(); 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); } 

Answer 7

这是使用反向分布函数的实现 ：

 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; } 

validation随机分布的示例：

  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 %)