4

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?

  • 2
    Do you need a formal proof for a CS class or just an educated guess? – maple_shaft Jul 20 '16 at 20:04
  • 3
    If you only need the correct number of items: the binomial distribution can be used to calculate it. – Patrick Jul 20 '16 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? – 8bittree Jul 20 '16 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 – downrep_nation Jul 20 '16 at 21:15
  • You are going to remove 30% of a million items, that's part can't possibly be constant. – Winston Ewert Jul 21 '16 at 1:24
10

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.

3

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.

  • Good points both. – hobbs Jul 21 '16 at 16:35
1

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.

1

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.

0

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 '16 at 8:26
  • a) its pseudo code, b) the rand is 1-10, not 0-9 – GrandmasterB Jul 21 '16 at 15:17
  • 1
    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 '16 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.