Question: You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.
Answer: Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it?
Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time.
When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After picking one, we replace the current stored byte with the one we picked. Now it gets interesting. When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked. We pick one of the two bytes based on this probability. We can keep doing this forever.
Just generalizing, when we get the nth byte, it has a 1/n probability of being picked and the byte we have stored has (n-1)/n probability of being picked.
Sometimes, this question is a little confusing. The question said you have only space to store one byte but there is an assumption that you have space to store variables to track the number of bytes and so on. Another assumption is that the stream of bytes is not infinite. If not, we won’t be able to calculate (n-1)/n.
If you have suggestions or comments, they are always welcome.
Like this post? Please Digg it or Stumble it.
With only one byte to choose, and no determination of when the bytes end, the probability of any byte being random would be equal for any byte being chosen, the first byte given would be just as random as any other byte. Since there was no requirement (that I inferred) that this test will need to be continued to randomize equally among all the bytes received over many tests over time, then simply choosing the first byte in the series is statistically random for this one answer.
What rule is there that some great randomizer algorithm wouldn’t choose the first byte anyway?
This would be the wrong answer if the tests needs to return randome bytes over multiple instances.
Another vague question… Assuming that at least 256 bytes are processed and processing size is limited to one byte, the probability should be 1/256. Ideas?
This problem is poorly stated.
You only have space for 1 byte. So you can always choose 1 of two: stored one or one from stream. is this correct ?
Since a lot of people are having trouble following the logic, I’ll try a different approach.
if you have 4 numbers, A B C & D, the probability of choosing each should be [1/4].
This means D has a chance of [1/4] to be selected, and the probability that A OR B OR C have been selected is [3/4].
This means that if D was NOT selected, we need to choose one of the remaining options with probability [1/3]. This is where most of you seem to get confused – it seems counter intuitive since you would expect that their probabilities should be [1/4] as well.
You have to remember that the case of A OR B OR C, has only a probability of [3/4] of coming into play. Thus a probability of [1/3] for each item, times a probability of [3/4] for the case where they “do not get replaced by D”, means a probability of [1/3*3/4]=[1/4].
Look at the case of 3 numbers A B & C.
First we get A and we pick it with p=[1].
Then we get B, and replace our pick from A to B with p=[1/2].
So far:
P(A) = [1/2]
P(B) = [1/2]
all is well.
Then we get C, and we pick it with p=[1/3].
There are three possible scenarios:
1) we picked C.
2) we didn’t pick C, and B was the previously selected number
3) we didn’t pick C, and A was the previously selected number.
Lets examine P(A), P(B) & P(C):
The only way C can be “the pick” is if it is picked to replace the previous pick. The probability of that happening is pretty straightforwardly [1/3].
P(C) = [1/3].
The only way B can be “the pick” is if:
– B was selected to replace A.
AND
– C was not selected to replace B.
Thus P(B) = P(B replaces A) * P(C does not replace B) = [1/2] * [2/3] = [1/3].
Similarly for A to be picked:
P(A) = P(B does not replace A) * P(C does not replace A) = [1/2] * [2/3] = [1/3].
As you can see, even though your intuition might tell you that the earlier numbers have a better chance to be picked … it is easy to show that this is clearly not the case.
I have a problem with that solution…
let’s say you picked the second element, at the time there were 2 elements, but as time goes on how likely is that this element will remain being picked?
It has already been picked and now the new coming elements will be reducing it.
But is it really as simple as reducing it to 1/n?
using 1/n for new elements does not take into account that this decision is made for every new element coming in.
I think in reality if you are to program this you may find that the first elements are never really being picked because they get “ambushed” by the implied future probabilities, despite the fact they were already chosen at the time.
I know couple of people tried to explain why the probability of picking the one thats already stored is n-1/n. But I still don’t get it.
Would some body be kind enough to explain this for the simple case of A, B and C. Ashwin in his response says “Since the one we stored represents all the bytes which have passed (2 bytes so far), we have to give it more probability”
Is it possible to break it down to sample spaces and events and explain why its 2/3. Maybe intuition will follow such an explanation.
thanks.
I would agree, knowing you are allowed to store an integer is an essential piece of information for this question!
In the theory of computation, the solution involves a log space random Turing machine.
The logarithmic space is for storing the counter that counts the number of byte seen.
Ok Let’s walk through the probability calculations for picking A.
P(A out of AB) = 1/2 (probability of picking A is 1/2 and B is 1/2)
Once we move on to the next round. P(A out of AC) is 2/3 and P(C out of AC) = 1/3 since A carries the weight of B as well.
P(A) = P(A out of AB)*P(A out of AC) = 1/2 * 2/3 = 1/3
Similarly,
P(B) = P(B out of AB)*P(B out of BC) = 1/2 * 2/3 = 1/3
P(C) = P(A out of AB)*P(C out of AC) + P(B out of AB)*P(C out of BC) = 1/2 * 1/3 + 1/2 * 1/3 = 1/3
Still having doubts?
Hi
I still have doubt:
when we have A B and C.
P(A)c = (when A is stored and C is the new byte, A has been stored then there are only 2 bytes that A and C) = 1/2
P(A)abc = P(A)b * P(A)c
= 1/2 * 1/2
Similarly P(B)abc = 1/2 * 1/2
And P(C) = 1/2
P(A) = 1/2(probability of A being chosen of A and B)* 1/2(now)
Just to make it clear. (n-1)/n is not undefined when n tends to infinity. it is
1 – 1/n = 1
In words it means that the previous byte always gets picked as n tends to infinity. So no assumptions are necessary.
Pavan,
Since the one we stored represents all the bytes which have passed (2 bytes so far), we have to give it more probability. Let’s label the bytes, A, B and C (where A and B are the first two bytes).
P(A) = (Probability of A being picked in the first round and then again in the next round) = 1/2 (A out of A,B) * 2/3 ( A out of A/B and C ) = 1/3
P(B) = (Probability of B being picked in the first round and then again in the next round) = 1/2 (B out of A,B) * 2/3 ( B out of A/B and C ) = 1/3
P(C) = (Probability of C being picked in the second round) = 1/3 ( C out of A/B and C ) = 1/3
Does that make it clear?
———–
When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked.
———–
Why do you think the probability of being picked for the one already stored is 2/3 ? All the 3 bytes should have equal prob. of 1/3 each being picked rt ?
– Pavan
Yes this should state that there is space for other calculations, as you need to store n !