# Checking if a random number exist within an interval efficiently

I have a problem where you have a bunch of probabilities associated with a number.

In this case:

• any number between 0 - 0.3 should return 0,
• any number between 0.3 - 0.7 should return 1,
• any number between 0.7 - 1.0 should return 2

Is there a better way I can achieve this?

import random

class ProbChecker(object):

def __init__(self, nums, prob):
self._nums = nums
self._prob = prob

def next_val(self):
if sum(self._prob) != 1.0:
raise ValueError("Probabilities does not sum up to 1.0")

accumulate = [sum(self._prob[: idx+1]) for idx in range(len(self._prob))]
randomVal = random.random()

for idx, x in enumerate(accumulate):
if randomVal < x :
return randomVal, self._nums[idx]

if  __name__ =='__main__':
random_nums = [0, 1, 2]
probabilities = [0.3, 0.4, 0.3]
gen = ProbChecker(random_nums, probabilities)
for i in xrange(100):
print gen.next_val()

# EXAMPLE OUTPUT
#(0.9771170760903612, 2)
#(0.738653579103415, 2)
#(0.33448331523062824, 1)
#(0.6458688675258738, 1)
#(0.7062504910283919, 2)
#(0.4159743894291702, 1)
#(0.2636825176117218, 0)
• I would advise inverting your probabilities and having a random number generator that picks between 0, 1, 2 with weights of 3, 4, 3 respectively. The random module has a small example for how to do this. If you would like me to elaborate on this approach, I can extend this to an answer. Aug 3, 2014 at 19:36
• @ mleyfman any chance you could elaborate on the approach you mentioned Aug 3, 2014 at 19:39

## Validation

Equality comparisons of floating-point numbers is usually a bad idea. Here is an example of how it can fail:

>>> ProbChecker(list(range(10)), [0.1] * 10).next_val()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "probcheck.py", line 11, in next_val
raise ValueError("Probabilities does not sum up to 1.0")
ValueError: Probabilities does not sum up to 1.0

The problem stems from the fact that 0.1 cannot be represented exactly in IEEE 754 floating point.

Recommended remedy:

from sys import float_info

…
if not -float_info.epsilon < sum_prob - 1.0 < float_info.epsilon:
raise ValueError("Probabilities do not sum up to 1.0")

## Pythonicity

for idx in range(len(self._prob)) is usually better expressed using enumerate().

An object like this should be written as an iterator. All you have to do is rename next_val() to next(), and provide a trivial __iter__() method.

## Class design

There is no reason for next_val() to fail validation, as it takes no input. For that matter, validation and the building of the accumulate array should have been done in the constructor, so that it doesn't have to do that work repeatedly.

I would have preferred to see the nums and prob specified as a list of value–probability pairs rather than as two separate parameters. That forces the caller to ensure that the number of values and probabilities match up. The caller's code will probably be more readable as well. Furthermore, it prettifies your next_val() slightly by removing the use of list indexes.

There is no reason why nums have to be numeric. I'd use the term "value" instead.

import random
from sys import float_info

class ProbChecker(object):
def __init__(self, values_and_probabilities):
"""values_and_probabilities is a list of (value, probability) tuples.
The sum of all probabilities must be 1.0."""
self.thresholds = [
(val, sum(prob for _, prob in values_and_probabilities[:i + 1]))
for i, (val, prob) in enumerate(values_and_probabilities)
]
sum_prob = self.thresholds[-1][1] if self.thresholds else 0
if not -float_info.epsilon < sum_prob - 1.0 < float_info.epsilon:
raise ValueError("Probabilities do not sum up to 1.0")

def __iter__(self):
return self

def next(self):
randomVal = random.random()
for value, cumul_prob in self.thresholds:
if randomVal < cumul_prob:
return randomVal, value

What you are basically asking is for a way to generate values with different weights.

In this case, you want 0 to be generated 30% of the time, 1 to be generated 40% of the time and 2 to be generated 30% of the time. Rather than checking intervals, it is much easier to generate a sequence that has elements that correspond to the probabilities.

For example, we could replicate the probabilities needed by having a 10-element list like so: [0, 0, 0, 1, 1, 1, 1, 2, 2, 2] and then pick 1 random element from it. How did I get 10? 10 is the minimal number of elements that evenly divides 30, 40 and 30 (the probabilities) multiplied by the sum of the weights (30 + 40 + 30)/10 = 10.

Another example is if we wanted 0 to occur 1% of the time and 1 to occur 99% of the time, then we could pick one element from [0, 1, ..., 1] where there are 99 1's. The 100 elements comes from (1 + 99 (sum of weights))/ 1 (divisor, or gcd to be precise) = 100.

Now assuming that all your probabilities are integral percentages (1%, 2%, ... 100%). Then you can always use 100 elements. Then for 5% you repeat the element 5x, 12x for 12% and so on.

Now let's do some code:

Lets say you build something like this: weighted_choices = [(0, 30), (1, 40), (2, 30)], where the 0, 1, 2 are the values and 30, 40, 30 are the percentage weights.

Then the code to select a item based on the weight is like so:

sample = [val for val, cnt in choices for i in range(cnt)]
random.choice(sample)

Note: This is code is taken straight from the random module documentation

If you want a simple, but slower version:

sample = []
for value, weight in choices:
for i in range(0, weight):
sample.append(value)
random.choice(sample)

If you want to read up on an even more general variation, go look at random's documentation

This can be solved mathematically using some native Python functions.... and some math....

int(0.25 + random.random() * 2.5)

This is because your ranges are symmetrical.... 0.3 probability, 0.4 probability, and 0.3, so, if we scale the 0.0 -> 1.0 range to be from 0.0 to 2.5, then shift that range to be from 0.25 -> 2.75, then doing an integer truncation on that, will give values 0, 1, or 2. 0.75 out of 2.5 will go to 0, 1.0 out of 2.5 will go to 1, and 0.75 of 2.5 will go to 2. These are the same ratios as your requirements

There is a small (tiny, miniscule, imperceptible) problem with this solution in that there is a very, very, very small change in the probabilities (like 1/(2-billion or so)). This shift in weight will be much less than the statistical variances to be expected in the random function... so you will never notice it.

I put together a small test on Ideone

This shows that the distributions are very reasonable (of 1 million tests - the last column is the percentage):

0 299953 29.9953
1 400044 40.0044
2 300002 30.0002
• Updated with an even simpler option. Aug 4, 2014 at 2:11

This simple code works by using an implicit if-elif approach and continues. Since we picked a random number once, it must be in a range from 0 to 1. If it's less than our window, we exit since the probability of it being less than in this instance and not previously is exactly that of the weight.

One thing here- notice the zip() function used in the for loop. This allows us to iterate over two objects at the same time and is rather helpful in this regard.

def random_number_picker(number_list,weights):
#assuming all of the weights add up to one, this works.
#Otherwise,  multiply the random number by the sum of the weights, scaling their sum to one.
less_than = 0
rand_number = random.random() * sum(weights)
for number_out,probability in zip(number_list,weights):
less_than += probability

# by the end of the loop, less_than will be the sum of the weights,
# so it can't get stuck
if rand_number <= less_than:
return rand_number,number_out

Hope this helps- This eliminates a lot of needless memory usage in making a big list, and is general in the fact that it works for any weights.

Edit: sample outputs:

for i in range(10):
print(random_number_picker([0,1,2],[0.3,0.4,0.3]))
# (0.5487001159506881, 1)
# (0.7837165580751019, 2)
# (0.04305304380667341, 0 )
# (0.10713992956594043, 0)
# (0.4543629729043448, 1)
# (0.963692147901128, 2)
# (0.853737837657539, 2)
# (0.9115030024187324, 2)
# (0.7481791760560865, 2)
# (0.6857445801116927, 1)