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.