mercredi 11 septembre 2019

Figure out how a non-uniform random algorithm works

I am trying to figure out how an algorithm that generates pseudorandom numbers that are not uniformly distributed works. The book I am reading gives a pseudocode implementation as follows

// Pick an item from a array with given probabilities.

Item: PickItemWithProbabilities(Item: items[],
Float: probabilities[])
Float: value = <PRNG value where 0 <= value < 1>
For i = 0 To items.Length - 1
value = value – probabilities[i]
If (value <= 0) Then Return items[i]
Next i
End PickItemWithProbabilities


I have implemented the pseudocode in python and it works as expected, if I run the function a sufficient amount of rounds, the distribution is as per the fed probability values. The thing is I don't exactly understand why and how it works.

Here is the code I implemented from the pseudocode.

from random import random

colors = ["pink", "green", "yellow"]
probabilities = [0.7, 0.2, 0.1]
trials = 1000000

def non_uniform_random_picker(array, probabilities):
    rand_value = random()
    for i in range(len(array)):
        rand_value -= probabilities[i]
        if rand_value <= 0:
            return array[i]

results = dict()

for i in range(trials):
    value = non_uniform_random_picker(colors, probabilities)

    if results.get(value) == None:
        results[value] = 1
    else:
        results[value] += 1


for key in results:    
    percentage = round(((results[key]/trials) * 100), 2)
    print(f"{key}:{percentage}% ")





I need help figuring out how the algorithm is working.




Aucun commentaire:

Enregistrer un commentaire