Estimating pass@k

A model attempts 20 problems n times each. From the counts of correct attempts, estimate the chance that at least one of k attempts passes.

Correct attempts per problem, out of 10 (this draw)

Problem 1: 0 of 10
Problem 2: 0 of 10
Problem 3: 9 of 10
Problem 4: 5 of 10
Problem 5: 2 of 10
Problem 6: 1 of 10
Problem 7: 2 of 10
Problem 8: 0 of 10
Problem 9: 2 of 10
Problem 10: 4 of 10
Problem 11: 0 of 10
Problem 12: 1 of 10
Problem 13: 7 of 10
Problem 14: 3 of 10
Problem 15: 0 of 10
Problem 16: 1 of 10
Problem 17: 1 of 10
Problem 18: 0 of 10
Problem 19: 1 of 10
Problem 20: 10 of 10

Samples per problem (n)10

Attempts allowed (k)5

draw 1

True pass@557.4%

Unbiased estimate, this draw53.6%

Plug-in estimate, this draw48.9%

Plug-in error, averaged over all draws−4.7 points

Challenges

0 of 3 complete

Find a number of samples and a k where the plug-in estimate, averaged over every possible draw, is more than 8 points below the true pass@k. (not yet)
With k of 2 or more, draw new samples until the unbiased estimate lands above the true pass@k. (not yet)
At k = 10, take enough samples that the plug-in estimate's average error is under 1 point. (not yet)

Try this

Slide k from 1 to n and watch the gap between the true curve and the plug-in average.
Draw new samples several times. Which estimate is noisy, and which is biased?
At k = 10, raise n until the plug-in bias almost vanishes.

The unbiased pass@k estimator and the plug-in shortcutPython with NumPy

import numpy as np
from math import comb

def pass_at_k(n, c, k):
    """Unbiased estimator from Chen et al. (2021): 1 - C(n-c, k) / C(n, k)."""
    if n - c < k:
        return 1.0
    return 1.0 - np.prod(1.0 - k / np.arange(n - c + 1, n + 1))

def plug_in(n, c, k):
    """The tempting shortcut: estimate p = c/n, then 1 - (1 - p)^k."""
    return 1.0 - (1.0 - c / n) ** k

# One problem the model solves 10% of the time, n = 10 samples.
p, n = 0.1, 10
chance = [comb(n, c) * p**c * (1 - p) ** (n - c) for c in range(n + 1)]
print(" k   true   unbiased (avg)   plug-in (avg)")
for k in [1, 5, 10]:
    true = 1 - (1 - p) ** k
    unbiased = sum(w * pass_at_k(n, c, k) for c, w in enumerate(chance))
    naive = sum(w * plug_in(n, c, k) for c, w in enumerate(chance))
    print(f"{k:2d}  {true:.3f}       {unbiased:.3f}           {naive:.3f}")

 k   true   unbiased (avg)   plug-in (avg)
 1  0.100       0.100           0.100
 5  0.410       0.410           0.349
10  0.651       0.651           0.494