Skip to content
Quantoros

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

Related questions