Best-of-N Expected Quality

Problem

Estimate the expected maximum quality when n samples are drawn uniformly from a finite list.

Sort the observed qualities and use the empirical CDF: E[max] = sum over k of q[k] * (F[k]^n - F[k - 1]^n) where F[k] = (k + 1) / m and F[-1] = 0. Return 0.0 for an empty list or n <= 0.

Hint

Rejection sampling improves the expected best sample, but with diminishing returns.

Test cases

case 1

in: [[0,1],1]

expected: 0.5

case 2

in: [[0,1],2]

expected: 0.75

case 3

in: [[1,2,3],2]

expected: 2.4444444444444446

case 4

in: [[],2]

expected: 0

case 5

in: [[0.5],3]

expected: 0.5

Starter codePython

def best_of_n_expected_quality(qualities, n):
    # Your code here
    pass

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