\documentclass[11pt]{article} \usepackage{common} \begin{document} \notehead{0203}{pass@$k$: the unbiased estimator, its variance, and why pass@1 and pass@$k$ disagree}{Batch M2. Companion notebook: \texttt{notebooks/0203-pass-at-k.ipynb} (exact rational arithmetic and fp64, executed).} \begin{problem} \question{How do we estimate pass@$k$ without bias from $n\ge k$ samples, and why is optimising pass@$k$ not the same as optimising pass@1?} A prover is judged by pass@$k$: the probability that at least one of $k$ sampled proofs is accepted. We sample $n\ge k$ proofs per problem (a few hundred is typical), count the $c$ accepted ones, and need a number. The obvious guess $1-(1-c/n)^k$ is biased. And once pass@$k$ is a training or model-selection target it is \emph{not} the same target as pass@1: later-stage RL typically raises pass@1 while pass@$N$ for large $N$ falls \cite{gps,yue}. This note (i) derives the unbiased estimator and its variance, (ii) shows precisely where the two objectives differ, and (iii) derives an unbiased \emph{gradient} estimator for pass@$k$. \end{problem} \stepcounter{section}% the problem box counts as section 1: keeps every \S and notebook cross-reference stable \section{Notation} \begin{center} \begin{tabular}{@{}p{0.36\linewidth}p{0.60\linewidth}@{}} \toprule Symbol & Meaning \\ \midrule $p=p_\theta(x)$ & per-problem pass@1 (note 0201) \\ $n,\ k,\ c$ & samples drawn ($n\ge k$), attempts in the metric, number accepted; $c\sim\mathrm{Bin}(n,p)$ \\ $\rho_{n,k}(c)=1-\binom{n-c}{k}\big/\binom nk$ & the estimator of pass@$k$ \\ $J_k(\theta)=\E_x[1-(1-p_\theta(x))^k]$ & pass@$k$ objective ($J_1=J$) \\ $w_k(p)=k(1-p)^{k-1}$ & per-problem weight of $J_k$ relative to $J_1$ \\ $\rho_{-i}$ & unbiased pass@$(k{-}1)$ estimate from the $n-1$ samples other than $i$ \\ $s_i=\nabla_\theta\log\pi_\theta(y_i|x)$ & score of sample $i$ \\ \bottomrule \end{tabular} \end{center} \section{Derivation} \subsection{Definition} Draw $k$ i.i.d.\ proofs from $\pi_\theta(\cdot|x)$. All fail with probability $(1-p)^k$, so \begin{equation}\label{eq:passk} \pk(x)=1-(1-p)^k,\qquad \pk=\E_x\bigl[1-(1-p_\theta(x))^k\bigr]=J_k . \end{equation} $p$ is unknown; we have only $c\sim\mathrm{Bin}(n,p)$. \subsection{The plug-in estimator is biased} $\hat p=c/n$ is unbiased for $p$, but $u\mapsto(1-u)^k$ is convex, so by Jensen $\E(1-\hat p)^k\ge(1-p)^k$ and $1-(1-\hat p)^k$ \emph{under}estimates pass@$k$. For $k=2$ the bias is exact: $\E(1-\hat p)^2=(1-p)^2+\Var(\hat p)=(1-p)^2+p(1-p)/n$, so the estimate is low by $p(1-p)/n$. Notebook, $n{=}8$, $p{=}0.3$: bias $-0.026$ ($k{=}2$), $-0.075$ ($k{=}4$), $-0.104$ ($k{=}8$), as exact rationals. Codex notes the same underestimate (Appendix A, Fig.~13) \cite{codex}. \subsection{The unbiased estimator} \begin{proposition} For $n\ge k$, $\ \rho_{n,k}(c)=1-\binom{n-c}{k}/\binom nk$ satisfies $\E_{c\sim\mathrm{Bin}(n,p)}\rho_{n,k}(c)=1-(1-p)^k$ for all $p$. \end{proposition} \emph{Proof 1 (probabilistic).} Condition on $c$. Choose a uniformly random $k$-subset of the $n$ samples. It contains no correct sample with probability $\binom{n-c}{k}/\binom nk$ (hypergeometric). Unconditionally, a uniformly random $k$-subset of $n$ i.i.d.\ samples is itself $k$ i.i.d.\ samples, which are all wrong with probability $(1-p)^k$. By the tower property $\E_c[\binom{n-c}{k}/\binom nk]=(1-p)^k$. $\square$ \emph{Proof 2 (algebraic, nothing skipped).} First the identity \[ \binom nc\binom{n-c}{k}\Big/\binom nk=\frac{n!}{c!\,(n-c)!}\cdot\frac{(n-c)!}{k!\,(n-c-k)!}\cdot\frac{k!\,(n-k)!}{n!}=\frac{(n-k)!}{c!\,(n-c-k)!}=\binom{n-k}{c}. \] Then \[ \E_c\frac{\binom{n-c}{k}}{\binom nk}=\sum_{c=0}^{n-k}\binom nc\frac{\binom{n-c}{k}}{\binom nk}p^c(1-p)^{n-c}=\sum_{c=0}^{n-k}\binom{n-k}{c}p^c(1-p)^{n-c}=(1-p)^k\underbrace{\sum_{c=0}^{n-k}\binom{n-k}{c}p^c(1-p)^{n-k-c}}_{=1}, \] where terms $c>n-k$ vanish because $\binom{n-c}{k}=0$ there. $\square$ The notebook verifies this as an \emph{equality of rational numbers} for all $n\le40$, all $1\le k\le n$ and four values of $p$ (error exactly $0$), and the binomial identity for all $n<30$. \subsection{A numerically stable form} Cancel factorials: \[ \frac{\binom{n-c}{k}}{\binom nk}=\frac{(n-c)!}{(n-c-k)!}\cdot\frac{(n-k)!}{n!}=\frac{(n-k)!/(n-k-c)!}{n!/(n-c)!}=\prod_{i=n-c+1}^{n}\frac{i-k}{i}=\prod_{i=n-c+1}^{n}\Bigl(1-\frac ki\Bigr), \] and the whole quantity is $0$ when $n-cn$} An estimator $f(c)$ is unbiased for $g(p)$ iff $g(p)=\sum_{c=0}^nf(c)\binom ncp^c(1-p)^{n-c}$, a polynomial of degree at most $n$ (Kolmogorov, quoted as Theorem~8 of \cite{pkpo}). $1-(1-p)^k$ has degree $k$. The notebook projects it on the degree-$n$ Bernstein basis: residual $\le3\times10^{-15}$ for $k\le n$, and $4\times10^{-3}$ ($n{=}4,k{=}5$), $4\times10^{-2}$ ($n{=}4,k{=}8$) for $k>n$. \section{Boxed result} \begin{result} \begin{align*} \pk&=\E_x\bigl[1-(1-p)^k\bigr],\qquad \hatpk=\E_{\text{problems}}\Bigl[1-\tbinom{n-c}{k}\big/\tbinom nk\Bigr]\ \ (\text{unbiased, }n\ge k),\\ &\tbinom{n-c}{k}\big/\tbinom nk=\prod_{i=n-c+1}^{n}\bigl(1-\tfrac ki\bigr),\\ \Var\bigl(\rho_{n,k}\bigr)&=\sum_{j=1}^{k}\frac{\binom kj\binom{n-k}{k-j}}{\binom nk}\bigl[(1-p)^{2k-j}-(1-p)^{2k}\bigr]\ \simeq\ \frac{k^2p(1-p)^{2k-1}}{n},\\ \nabla J_k&=\E_x\bigl[k(1-p)^{k-1}\nabla p\bigr],\\ \hat g_k^{\mathrm{LOO}}&=\frac kn\sum_iV_i\bigl(1-\rho_{-i}\bigr)\nabla\log\pi_\theta(y_i|x)\quad(\text{unbiased for i.i.d.\ samples and }n\ge k). \end{align*} \end{result} \section{What breaks} \begin{breaks} \begin{tabular}{@{}p{0.29\linewidth}p{0.29\linewidth}p{0.36\linewidth}@{}} \toprule Failure & Assumption violated & Consequence \\ \midrule Samples are not i.i.d.\ (shared prefix cache, fixed seed, beam/top-$k$ without replacement, deduplication) & $c\sim\mathrm{Bin}(n,p)$ & $\rho$ is no longer unbiased; deduplicated samples \emph{over}state diversity, correlated ones understate it \\ $n