Assigning probabilities to items in python
<p>I understand the question title is vague. My apologies. I have a hashmap that has the key:value <code>&lt;string&gt;:&lt;list of lists&gt;</code>. For a given list, each of the items in the list has a corresponding probability of being chosen. For example, one item in the hashmap might look like</p>

<pre><code>"NP":[['A', 'B'], ['C', 'D', 'E'], ['F']]
</code></pre>

<p>I need to choose one of the lists on the right hand side randomly. Each list has it's own probability. Here are the input strings that would generate the above item in the map.</p>

<pre><code>3 NP A B
1 NP C D E
1 NP F
</code></pre>

<p>Because the line <code>NP A B</code> has the number <code>3</code> next to it, <code>NP C D E</code> has <code>1</code> next to it, and <code>NP F</code> has <code>1</code> next to it, the probability ratio is 3:1:1, so <code>[A, B]</code> has 3/5 probability of being chosen, <code>[C, D, E]</code> has 1/5 of being chosen and same for <code>[F</code>. </p>

<p>My question is, how do I simulate those probabilities? </p>

<p>Before those numbers were introduced it was easy because I could count the length of the list (in the above example it would be 3) and then choose a random number between 0 and <code>len(list) - 1</code> inclusive with <code>random.randint()</code>, then choose that index from the list. To simulate bernoulli random variables, I know that one can check <code>if random.randint() &lt; p</code>. But that only works if you have 2 cases. I can't explicitly write if statements to check because a list might have <code>n</code> elements. </p>

<p>Here is a simple prototype which uses <strong>linear-search</strong>. The only dependency is <strong>random.random()</strong> to obtain a float within [0,1).</p>

<p>Despite the unoptimized approach, it only needs ~0.25 seconds for 100.000 samples on my PC. But keep in mind, that this performance is dependent on the statistics / probability-vector. The code could also be improved through presorting.</p>

<p>For the general idea: check <a href="https://en.wikipedia.org/wiki/Pseudo-random_number_sampling" rel="nofollow">this</a>.</p>

<h3>Code</h3>

<pre><code>import random

""" Discrete-sampling """
def cum_sum(xs):
    cum_sum = []
    total = 0
    for i in xs:
        total += i
        cum_sum.append(total)
    total_sum = sum(cum_sum)
    return cum_sum, cum_sum[-1]

def discrete_sample(items, probs):
    cum_sum_, max_ = cum_sum(probs)
    random_val = random.random() * max_
    for ind, i in enumerate(items):
        if random_val &lt; cum_sum_[ind]:
            return i
    return items[-1]  # fail-safe

def sample_from_dict(element, data, data_p):
    data_ = data[element]
    data_p_ = data_p[element]
    selection = discrete_sample(range(len(data_)), data_p_)
    return data_[selection]

""" Data """
data = {'NP': [['A', 'B'], ['C', 'D', 'E'], ['F']]}
data_p = {'NP': [3, 1, 1]}

""" Try it """
samples = []
for i in range(100000):
    samples.append(sample_from_dict('NP', data, data_p))

counts = [0, 0, 0]
for i in samples:
    if i == ['A', 'B']:
        counts[0] += 1
    elif i == ['C', 'D', 'E']:
        counts[1] += 1
    elif i == ['F']:
        counts[2] += 1

print(counts)
</code></pre>

<h3>Output</h3>

<pre><code>[60130, 19867, 20003]
</code></pre>

python probability