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

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?

• Do you need a formal proof for a CS class or just an educated guess? Jul 20, 2016 at 20:04
• If you only need the correct number of items: the binomial distribution can be used to calculate it. Jul 20, 2016 at 20:08
• I just tested an unoptimized naive Javascript function that generates `n` random numbers (0-1), returning how many were less than `0.7`. It handles `n=100000000` (one hundred million) in about 20 seconds. What are you trying to use this for? What are your actual performance requirements? Jul 20, 2016 at 20:43
• what you say theoretically only applies to a small amount of items. if you roll a cube 6 times and dont get 6 different results and therfor call the cube unfair you just dont understand the game in reality when you will do over 10 items you will start to see that the end result will be around 70% discarded items. so just do it from the start to save some computing time if the question allows it Jul 20, 2016 at 21:15
• You are going to remove 30% of a million items, that's part can't possibly be constant. Jul 21, 2016 at 1:24

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.

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.

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

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.

• Good points both. Jul 21, 2016 at 16:35

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.

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.

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.

• Shouldn't the comparison be `<` instead of `<=`? This removes 80%.
– Hulk
Jul 21, 2016 at 8:26
• a) its pseudo code, b) the rand is 1-10, not 0-9 Jul 21, 2016 at 15:17
• The problem is more with the `mod` - this will delete values when `n mod 10` is one of `[0, 1, 2, 3, 4, 5, 6, 7]` and only skip `[8, 9]` unless your `mod` does something different.
– Hulk
Jul 21, 2016 at 16:16