Efficient way to calculate how many items to destroy if each has a 70% chance to be destroyed

Question

We start with a variable that holds an integer for the "number of items" that we have somewhere, somehow.

Then, the algorithm is applied: each one of those items have a 70% chance to be destroyed.

If the algorithm was something like round( num_of_items * 0.7 ), that wouldn't work as expected, for obvious reasons (one would be that items=1 would always return 0, instead of 70% times 0 and 30% times 1).

I can't afford calculating a chance of 70% one time for each item, because there might be millions.

Is there any algorithm that could do this with a constant cost?

Answer 1

To get the number of items remaining, you need to sample from a binomial distribution, namely the distribution B(n, 0.3) where n is the original number of items. You can do this using only a single random number using the inverse transform method.

A problem you might encounter is that computing the inverse CDF for the binomial distribution explicitly is (I'm pretty sure) also linear in the value of n, so it might be too slow for very large n. But you can take advantage of the fact that for large n, the binomial distribution is well-approximated by a normal distribution, in your case N(0.3*n, 0.21*n). The inverse CDF of the normal distribution is a nasty formula, but it's provided by various libraries (for example norminv in matlab, or scipy.stats.norm.ppf in SciPy). By switching from one to the other at an appropriate value of n (Wikipedia suggests that the approximation is good enough for n >= 24 when p is 0.3, but "good enough" is a matter of opinion), you can get a good approximate solution with a bounded running time independent of n.

All that said, you should try doing it the simple way before you dismiss it. Generating a billion random numbers per second is possible on modern systems, so millions of items may not be as much of a problem as you think.

Answer 2

As others have noted, you can use the binomial distribution. But I suggest you avoid trying to write your own algorithm, it is easy to screw that up. Instead, many languages have libraries that can generate binomial random variables.

C++ has Boost.Random: http://www.boost.org/doc/libs/1_61_0/doc/html/boost/random/binomial_distribution.html

Python has has numpy.random.binomial: http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.binomial.html

Node has random-distributions: https://www.npmjs.com/package/probability-distributions

Java has apache commons: http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/distribution/BinomialDistribution.html

But to add another approach, you can generate a variable from an exponential distribution with lambda=1/.3. This distribution will give you the time between two deletions. So you'd use it something like:

while(true) {
    int nextDeletion = exponential(1/.3)
    moveForward(nextDeletion);
    deleteCurrent();
}

I've used this in cases where my probability was very low, something like .00000001, and it was much faster than a naive approach. I don't know if it can help you.

Answer 3

You would generate a random number between 1 and 10. If random integer is less than or equal to 7 then do nothing, else add 1 to a running sum. Iterate this function n times for the size of the input parameter n. The result is the number of objects destroyed which can be used to derive the number survived.

This O(n) operational complexity and O(1) memory complexity. This is because the number of operations you have to perform are constant in relative to n your input parameter.

Unless you just subtract .7 from the integer, this won't be constant time. It is linear time.

Answer 4

If you want to simulate a random variable with binomial distribution, just go ahead and do that.

If you just want a quick and dirty number whose average approaches the expected number of deleted items, just use a uniform random variable with a suitable range, e.g.:

(rand() * 0.6 + 0.4) * num_of_items

Where rand() is uniform on [0; 1], rand() * 0.6 is uniform on [0; 0.6], rand() * 0.6 + 0.4 is uniform on [0.4; 1] and with 0.7 as mean, and finally we have a random variable that is uniform on [0.4 * num_of_items; num_of_items] with a mean of 0.7 * num_of_items.

You can reduce the number 0.6 while increasing the 0.4 (maintaining the mean) to have a smaller deviation.

Answer 5

Its not clear what the purpose or requirement for this is, so I don't know if this will meet them.

But you could loop over all objects, keeping a count mod 10, and deleting on 1-7. To add randomness start the count at a random value between 1 and 10. That would technically give you a 70%, effectively random deletion without a million random numbers.

pseudocode:

n = rand(1,10)
for i = 1 to objectCount
  if (n mod 10) <= 7
    doDelete(object[i])
  n++

Note that every item would have a 70% chance of deletion, and you would not know which would be deleted ahead of time... but it would be deleting consistently in groups of 7.

That said, you still might try it with a fast PRNG for each item just to see. My suspicion is you are prematurely optimizing, and that most of execution time for this process will be freeing the objects rather than the PRNG.