Expected Distinct Values in Draws

Problem

When k draws with replacement come from m equally likely values, the expected number of distinct values seen is m * (1 - (1 - 1/m)^k).

Given m >= 1 and k >= 0, return the expectation.

Hint

Linearity of expectation over indicator variables for each value.

case 1

in: [6,3]

expected: 2.527777777777777

case 2

in: [2,1]

expected: 1

case 3

in: [10,200]

expected: 9.999999992944922

Starter codePython

def expected_distinct_values_in_draws(m, k):
    # Your code here
    pass

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