0
$\begingroup$

Hello I have the following task (no homework).

You are using the Reservoir Sampling algorithm. You process the 2000th element in the data stream and are maintaining a sample of size 500. What is the probability of the first element in the sample being replaced by the current element?

My problem is, that I have no idea how to find this probability. I know how the algorithm works but I can't solve this task.

I hope someone can help me here.

Improve this question
$\endgroup$
9
  • $\begingroup$ Note the question is asking you for the probability that the first element in the current sample is replaced by the new element. This probability is part of the definition of the reservoir sampling algorithm. $\endgroup$ – Yuval Filmus Jun 17 '19 at 19:45
  • $\begingroup$ @Yuval Filmus Hello, I believe I'm blind, or too uneducated because I do not see it. Isn't the probability random? So we can't calculate it? Is that what you want to tell me? $\endgroup$ – Kata110 Jun 17 '19 at 19:59
  • $\begingroup$ I'm not sure you understand the meaning of probability. $\endgroup$ – Yuval Filmus Jun 17 '19 at 20:23
  • $\begingroup$ I'm sorry i was wrong, I just confused something. But in the definition on wikipedia I can't find what could help me here. Could you give me some more details ? Im so sorry, but I'm not that smart:( $\endgroup$ – Kata110 Jun 17 '19 at 20:30
  • $\begingroup$ @Yuval Filmus I think i have the answer. Could it be $\frac{1}{4}$? $\endgroup$ – Kata110 Jun 17 '19 at 20:44

Your Answer

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

Browse other questions tagged or ask your own question.