Mark x% items in stream

There are n items (n is known and > 1,000,000,000).

I want to randomly 'mark' x% of n-items in stream.
(n and x are known)

Items are in stream ,one directional (you can't go back) processed item goes to output stream. Items should be picked randomly as well, meaning I can't take the first %x of items in stream.

complexity should be <= O(n).

My question:
Will it be correct to "test" each item independently?
Meaning, take item from stream -> x% to mark it... Take next item...

• How exact does it need to be? – raptortech97 Nov 19 '14 at 12:57
• @raptortech97: see my answer below for a 100% exact solution in O(n). – Doc Brown Nov 19 '14 at 13:06

Lets say you have n items and know you want to mark m items, m<=n (according to the % value). Now you mark the items one-by-one, starting with a random probability of m/n for marking the first item. But instead of keeping that probability fixed, after each step you adapt the actual probability to what is needed now!

So when after k steps you have marked l items, you will have to process (n-k) remaining items, and you want to have (m-l) of them marked. So choose the probability of the next item as (m-l)/(n-k).

As you see, the more l approaches m, the smaller the probability of marking will become. When l is equal to m, the probability is 0. On the other hand, when the number of remaining items reaches the number of remaining items to marked, the probability will become 1. Finally, you will end up with exactly m marked items.

It should be obvious that the run time is O(n), since each element is processed once, and the only thing you have to keep track is the both numbers (m-l) and (n-k).

• I think I like this, will take some time to process this answer :) – user3882291 Nov 19 '14 at 13:05
• Will it also work when n is small? – user3882291 Nov 19 '14 at 13:06
• @user3882291: why not? Make a pencil-and-paper test by yourself. – Doc Brown Nov 19 '14 at 13:08
• @user3882291 the whole point of this system is that it works when n is small. Think about any possible system that doesn't store items but takes them from the stream - when it has already processed n-1 items, there's no random decision to make: if x% of n (=m) have been taken, you must discard the item, if m-1 items have been taken you must take the item; and if any other number of items have been taken then you've already done something wrong. Similarly, if 2 items are remaining, then you should use 0%, 50% or 100% but not any other probabilities. – Peteris Nov 19 '14 at 17:11

It will be asymptotically correct, i.e. it will provably tend to approach the specification as time goes on. However, for an unspecified amount of time, it will deviate from the specification, possibly quite severely (and possibly much more than it would have to, given that you can't partially mark an item).

Whether that is good enough for your use case is a question that only you can answer. If you do have to approximate the specified percentage as closely as possible, then your suggestions is not good enough, and you'll have to maintain additional counters as well. (However, that shouldn't take you out of the realm of linear-time solutions.)

• I see, what approach can be suggested to solve it in <= O(n), and without storing processed items? – user3882291 Nov 19 '14 at 12:32

If you simply mark x% by probability independent for each item you might not end up for a fixed n with exactly x% of the n items.

I recommend something like this:

n is known, so you can calculate how many items you have to mark markSize=n*x/100.

Now take the first markSize items from the stream and while reading the rest of the stream replace them randomly by the related probability.

The simplified example, if you want to mark one out of a stream of n:

1. take the first one as mark-candidate
2. read the second one from the stream and replace your old mark-candidate by it with a probability of 1/2
3. read the third one from the stream and replace your old mark-candidate by it with a probability of 1/3
4. and so on (In this case you do not even need to know n up front.)

This idea can be generalized for any number of items to mark from a stream. Since you only read the stream once, the time complexity is O(n).

• the issue that i can't take first "markSize" items as this group can be huge! – user3882291 Nov 19 '14 at 12:48
• How a re you supposed to store the marked items? Write them to another stream? – MrSmith42 Nov 19 '14 at 12:53
• correct, output stream – user3882291 Nov 19 '14 at 13:01

It should work acceptably in your use case. The general rule is that the distribution of the number of marked items across many sample will have mean e (where e is n times x%) and standard deviation sqrt(e). This means you have 99.7% chance that the number of marked items will fall between e-3sqrt(e) and e+3sqrt(e). Let's say n=1,000,000,000 and x=1%. Then e=10,000,000 and sqrt(e) is roughly 3,000. You can have 99.7% certainty that the number of marked items will fall between 9,994,000 and 10,006,000. That's probably good enough for your purposes. As x becomes very small, though, the accuracy decreases.