Exactly one of n keys opens a lock. Compare mean and variance of trials with random replacement versus trying keys in…
Quant ResearchLevel: IntermediateSearch with and without replacement
Exactly one of n keys opens a lock. Compare mean and variance of trials with random replacement versus trying keys in random order without reuse.
Hints
- Identify the two distributions.
- Include the successful attempt in both counts.
Answer
With replacement T is geometric with p=1/n: E=n, Var=n(n-1). Without replacement the fitting position is uniform on 1,...,n: E=(n+1)/2, Var=(n^2-1)/12. Keeping memory improves both.
Source and licence: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · answer: Quantoros editorial