How often the reservoir is rewritten
A metrics server keeps not all response-time measurements but a random sample of k of them, a reservoir. The first k measurements go into the reservoir as they are. Measurement number i > k replaces a random one of those there with probability k/i, and is otherwise thrown away. This way, at any moment the reservoir is a fair sample of everything that has arrived.
Each replacement is a write to shared memory visible to the server’s other threads, and an engineer wants to know how many such writes to expect. For each question “n k”, find the expected number of replacements after n measurements have passed through a reservoir of size k. The first k writes that fill the empty reservoir do not count as replacements.
The second example holds the stream from this article, 19,073 earthquakes, and a day of server work with a measurement every millisecond and a reservoir of 1028 elements: that is the default size of the uniform reservoir in the Dropwizard metrics library.
Input
The first line holds the number of questions q (1 ≤ q ≤ 104). Then q lines of two numbers n and k (1 ≤ k ≤ 106, k ≤ n ≤ 1018).
Output
For each question, the expected number of replacements with an absolute or relative error of at most 10−6.
Examples
Example 1
3 10 1 6 2 5 5
1.928968254 1.900000000 0.000000000
Example 2
2 19073 10 86400000 1028
75.043026271 11656.123452829
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The number of replacements is a sum of indicators “measurement number i replaced something”. The expectation of a sum equals the sum of the expectations, even if the events are dependent.
2Hint 2
You get k·(1/(k + 1) + … + 1/n). With n up to 1018 you cannot add one term at a time. What is known about the sum 1 + 1/2 + … + 1/m for large m?
3The idea
Measurement number i > k replaces something with probability k/i, so the expected number of replacements is k·(Hn − Hk), where Hm = 1 + 1/2 + … + 1/m is a harmonic number. Take small Hm from a table of a million values, and large ones from the asymptotic formula Hm = ln m + γ + 1/(2m) − 1/(12m2) + …, where γ ≈ 0.5772 is Euler’s constant.
4Walkthrough
The table H1, …, H106 is computed once and answers all Hk, since k is at most a million. For n above a million the next term of the series, 1/(120n4), is below 10−25, so three corrections are enough with a huge margin. Each question is O(1).
Check on the first example. With k = 1 and n = 10 the expectation is 1/2 + 1/3 + … + 1/10 ≈ 1.929: the reservoir’s single element changes almost twice on average over ten measurements. With k = 2 and n = 6, 2·(1/3 + 1/4 + 1/5 + 1/6) = 1.9. On the earthquake stream from the article it comes to 75.0 replacements with k = 10, which is what the scene counts on average. And over a day, 86.4 million measurements, a reservoir of 1028 elements is rewritten only about 11,656 times: one write per seven thousand-odd measurements, and the longer the server runs, the rarer they get.
Hence the back-of-the-envelope estimate k·ln(n/k). It conveys the growth correctly but loses the corrections: for small k and n it is noticeably off; in the first example it gives ln 10 ≈ 2.303 instead of 1.929. The same number is how many times Algorithm L from the article calls the generator at all: it jumps only to the elements that will enter the reservoir.
4+Solution
5Complexity
O(106) for the table and O(1) per question.
6Common mistakes
- The estimate k·ln(n/k). Right in order of magnitude, but not to 10−6: the first example already shows it.
- Adding up to n. 1018 terms cannot be added, and 104 questions of a million terms each are already 1010 operations.
- The asymptotic formula for small m. For m = 1 the series gives 1.0772 − 0.0833 ≈ 0.994 instead of 1: small values need the table.
- Counting the initial fill. The first k writes are not replacements; for n = k the answer is 0.