Reservoir Replacement Expectation

Problem

Return the expected number of times the reservoir is overwritten while streaming stream_len items through a reservoir of size k.

Item i (1-based) triggers a replacement with probability k / i once i exceeds k, so by linearity of expectation the answer is the sum of k / i for i from k + 1 to stream_len. Return 0.0 when k is non-positive or the stream is no longer than the reservoir.

Hint

Each stream position past k replaces a slot with probability k / i; add those probabilities.

Test cases

case 1

in: [5,2]

expected: 1.5666666666666667

case 2

in: [3,3]

expected: 0

case 3

in: [10,1]

expected: 1.928968253968254

case 4

in: [1,5]

expected: 0

case 5

in: [7,3]

expected: 2.2785714285714285

Starter codePython

def expected_reservoir_replacements(stream_len, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor