Генератор случайных чисел с распределенной вероятностью

Question

Я хочу сгенерировать число, основанное на распределенной вероятности. Например, только говорят, что есть следующие вхождений каждого номера:

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  

Как сделать генератор случайных чисел, который возвращает быть числа, основанные на таком распределении вероятностей?

Я доволен тем, что на данный момент это основано на статическом, жестком коде, но в конечном итоге я хочу, чтобы он получил распределение вероятности из запроса к базе данных.

Я видел похожие примеры, такие как this one, но они не очень общие. Какие-либо предложения?

Answer 1

Общий подход состоит в том, чтобы подавать равномерно распределенные случайные числа от 0..1 до the inverse of the cumulative distribution function вашего желаемого распределения.

Таким образом, в вашем случае, просто сделать случайное число х из 0..1 (например, с Random.NextDouble()) и на основе ее возвращаемое значение

• 1, если 0 = < < х 150/208,
• 2, если 150/208 < < = х 190/208,
• 3, если 190/208 < < = х 205/208 и
• 4 в противном случае.

Answer 2

ли это только один раз:

• Написать функцию, которая вычисляет CDF массив по заданному PDF массив. В вашем примере массив pdf [150,40,15,3], массив cdf будет [150, 190, 205, 208].

Делайте это каждый раз, когда:

• Получить случайное число в [0,1), умножить на 208, усечение вверх (или вниз: Я оставляю вам думать о случаях угловых) У вас будет целое число в 1..208. Назовите его r.
• Выполнить a бинарный поиск на cdf массив для r. Верните индекс ячейки, содержащей r.

Время работы будет пропорционально log размера данного массива pdf. И это хорошо. Однако, если размер вашего массива всегда будет таким маленьким (4 в вашем примере), то выполнение линейного поиска будет проще, а также будет работать лучше.

Answer 3

This question объясняет различные подходы к генерации случайных чисел с различными вероятностями. Согласно this article, показанному на этом вопросе, лучшим подобным подходом (с точки зрения временной сложности) является так называемый «метод псевдонимов» Майкла Восе.

Для вашего удобства я написал и представить здесь 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<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 

я помещаю этот код в обществе домен.

Answer 4

Спасибо за все ваши решения, ребята! Очень признателен!

@Menjaraz Я попытался реализовать ваше решение, поскольку оно выглядит очень дружелюбным к ресурсам, однако имело некоторые трудности с синтаксисом.

Итак, теперь я просто преобразовал сводку в плоский список значений, используя LINQ SelectMany() и Enumerable.Repeat().

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

Answer 5

Я знаю, что это старый пост, но я также искал такой генератор и не был удовлетворен решениями, которые я нашел. Поэтому я написал свои собственные и хочу поделиться им с миром.

Просто позвоните "Добавить (...)" несколько раз, прежде чем вы называете "NextItem (...)"

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

Answer 6

Используйте мой метод. Это просто и легко понять. я не почитаю часть в диапазоне 0 ... 1, я просто использовать "Pool" вероятность р (звучит круто, да?)

At circle diagram you can see weight of every element in pool

Here you can see an implementing of accumulative probability for roulette

` 

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