Distributed Wahrscheinlichkeits-Zufallsgenerator

Question

Ich möchte eine Zahl basierend auf einer verteilten Wahrscheinlichkeit generieren. Zum Beispiel, sagen Sie einfach die folgenden Vorkommnissen jeder Zahlen gibt es:

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  

Wie mache ich einen Zufallszahlengenerator, die Zahlen auf der Grundlage dieser Wahrscheinlichkeitsverteilung zurückgibt?

Ich freue mich, dass dies jetzt auf einem statischen, fest codierten Set basiert, aber ich möchte schließlich, dass es die Wahrscheinlichkeitsverteilung aus einer Datenbankabfrage ableitet.

Ich habe ähnliche Beispiele wie this one gesehen, aber sie sind nicht sehr allgemein. Irgendwelche Vorschläge?

Answer 1

Der allgemeine Ansatz besteht darin, gleichmäßig verteilte Zufallszahlen von 0..1 Intervall in the inverse of the cumulative distribution function Ihrer gewünschten Verteilung zu liefern.

So in Ihrem Fall zieht nur eine Zufallszahl x von 0..1 (zum Beispiel mit Random.NextDouble()) und auf der Grundlage seines Rückgabewert

• 1 wenn 0 < = x < 150/208,
• 2, wenn 150/208 < = x < 190/208,
• 3, wenn 190/208 < = x < 205/208 und
• 4 anders.

Answer 2

dies nur einmal tun:

• Schreiben Sie eine Funktion, die einen CDF-Array eines pdf-Arrays berechnet. In Ihrem Beispiel ist das pdf-Array [150,40,15,3], das cdf-Array wird [150,190,205,208] sein.

Tun Sie dies jedes Mal: ​​

• eine Zufallszahl in [0,1) holen mit 208 multiplizieren, gestutzt oben (oder unten: Ich kann es Ihnen überlassen, um die Ecke Fälle zu denken) Sie haben eine ganze Zahl in 1..208. Nenne es r.
• Führen Sie eine binäre Suche auf cdf-Array für r. Gibt den Index der Zelle zurück, die r enthält.

Die Laufzeit wird proportional zum Protokoll der Größe des gegebenen pdf-Arrays sein. Was gut ist. Wenn Ihre Array-Größe jedoch immer so klein ist (4 in Ihrem Beispiel), ist die Durchführung einer linearen Suche einfacher und wird auch besser funktionieren.

Answer 3

This question erläutert die verschiedenen Ansätze zum Generieren von Zufallszahlen mit unterschiedlichen Wahrscheinlichkeiten. Gemäß der in dieser Frage gezeigten this article ist der beste derartige Ansatz (hinsichtlich der zeitlichen Komplexität) die sogenannte "Alias-Methode" von Michael Vose.die Alias-Methode

Für Ihre Bequemlichkeit habe ich geschrieben und hier eine C# -Implementierung von einem Zufallszahlengenerator liefern Implementierung:

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

Beispiel:

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 

ich in der Öffentlichkeit diesen Code platzieren Domain.

Answer 4

Vielen Dank für all Ihre Lösungen Jungs! Sehr geschätzt!

@Menjaraz Ich habe versucht, Ihre Lösung zu implementieren, da es sehr Ressourcen freundlich aussieht, hatte jedoch einige Schwierigkeiten mit der Syntax.

Also für jetzt, habe ich nur meine Zusammenfassung in eine flache Liste von Werten mit LINQ SelectMany() und Enumerable.Repeat() umgewandelt.

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

Ich weiß, das ist ein alter Beitrag, aber ich suchte auch nach einem solchen Generator und war nicht zufrieden mit den Lösungen, die ich gefunden habe. Also habe ich mein eigenes geschrieben und möchte es mit der Welt teilen.

Rufen Sie "Add" (...) ein paar Mal, bevor Sie "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

meine Methode verwenden nennen. Es ist einfach und leicht zu verstehen. Ich zähle nicht Teil im Bereich 0 ... 1, i verwenden "Probabilityp Pool" nur (klingt cool, ja?)

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