Generatore casuale di numeri casuali di probabilità

Question

Voglio generare un numero basato su una probabilità distribuita. Ad esempio, basta dire che ci sono le seguenti occorrenze di ogni numeri:

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  

come faccio a fare un generatore di numeri casuali che restituisce essere numeri sulla base di questa distribuzione di probabilità?

Sono felice per questo deve essere basata su una serie hardcoded statica per ora, ma alla fine voglio che derivare la distribuzione di probabilità da una query di database.

Ho visto esempi simili come this one ma non sono molto generico. Eventuali suggerimenti?

Answer 1

L'approccio generale è quello di alimentare numeri casuali uniformemente distribuiti da 0..1 intervallo nella the inverse of the cumulative distribution function della vostra distribuzione desiderata.

Così, nel tuo caso, solo disegnare un numero casuale x da 0..1 (per esempio con Random.NextDouble()) e in base al suo valore di ritorno

• 1 se 0 < = x < 150/208,
• 2 se 150/208 < = x < 190/208,
• 3 se 190/208 < = x < 205/208 e
• 4 altrimenti.

Answer 2

farlo solo una volta:

• Scrivete una funzione che calcola una matrice CDF dato un array di pdf. Nel tuo esempio, l'array pdf è [150,40,15,3], l'array cdf sarà [150,190,205,208].

Fate questo ogni volta:

• ottenere un numero casuale [0,1), moltiplicare con 208, tronca l'alto (o verso il basso: lascio a voi pensare a casi d'angolo) Avrai un intero in 1..208. Chiamalo r.
• Eseguire una ricerca binaria su array cdf per r. Restituisce l'indice della cella che contiene r.

Il tempo di esecuzione sarà proporzionale al registro delle dimensioni della matrice pdf fornita. Che è buono. Tuttavia, se le dimensioni dell'array saranno sempre così piccole (4 nel tuo esempio), eseguire una ricerca lineare è più semplice e anche le prestazioni migliori.

Answer 3

This question spiega i vari approcci per la generazione di numeri casuali con diverse probabilità. Secondo this article, mostrato su quella domanda, il miglior approccio di questo tipo (in termini di complessità temporale) è il cosiddetto "metodo alias" di Michael Vose.

Per comodità, ho scritto e fornire qui un'implementazione C# di un generatore di numeri casuali attuazione del metodo alias:

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

Esempio:

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 

ho posto questo codice nel pubblico dominio.

Answer 4

Grazie per tutte le vostre soluzioni ragazzi! Molto apprezzato!

@Menjaraz Ho provato a implementare la soluzione perché sembra molto rispettosa delle risorse, tuttavia ha avuto qualche difficoltà con la sintassi.

Quindi, per ora, ho appena trasformato il mio sommario in un elenco di valori con LINQ SelectMany() e Enumerable.Repeat().

Answer 5

So che questo è un vecchio post, ma ho anche cercato un generatore di questo tipo e non ero soddisfatto delle soluzioni che ho trovato. Così ho scritto il mio e voglio condividerlo con il mondo.

Basta chiamare "Add (...)" alcune volte prima di chiamare "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

utilizzare il mio metodo. È semplice e facile da capire. Non conto porzione nel campo 0 ... 1, mi basta usare "Probabilityp Pool" (suona fresco, sì?)

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