What is the best way to sample given a constraint over multiple items?

Question

This seems like a simple problem but I don't know of a way to efficiently solve it:

Suppose I want to generate random samples of 100 numbers, which satisfy the constraint that the sum is less than a certain number:

import random
import numpy as np

#numbers to sample from, could be a more complicated distribution
list_of_numbers = np.random.rand(1000) * 50 

valid_samples = list()

while(len(valid_samples) < required_length):
    sample = [random.choice(list_of_numbers) for _ in range(100)]
    if (sum(sample) < 1000):
        valid_samples.append(sample)

The problem is that I end up generating a vast majority of samples that just get thrown away. However, it doesn't seem clear how to implement the constraint on the list of numbers, since there would be mutual dependencies involved. I can't throw out any of the original list, since none of the numbers exceeds the threshold for the sample (1000). Right now, it takes a very long time to obtain the sample, and I would like to find a faster way to do so.

Answer 1

One way to speed up your code is to use np.random.choice instead of random.choice. See documentation here. https://numpy.org/doc/stable/reference/random/generated/numpy.random.choice.html. The advantage is you can sample 100 numbers by just specifying the appropriate parameter as below

import random
import numpy as np

#numbers to sample from, could be a more complicated distribution
list_of_numbers = np.random.rand(1000) * 50 

valid_samples = list()

while(len(valid_samples) < required_length):
    # sample = [random.choice(list_of_numbers) for _ in range(100)]
    sample = np.random.choice(list_of_numbers, size=100)
    if (sum(sample) < 1000):
        valid_samples.append(sample)

This should be faster than list comprehension. I have not tested this, but am reasonably certain it will speed up. And you can always parallelize the code if you want faster sampling if that is an option.