The ceiling imposed by a fallible verifier

ProofAdvanced⏱ 30 minAgentsverifierprecisionreward hacking

Problem

Prove that with false-positive rate $\varphi$ and perfect recall, the large- $n$ accuracy of uniform selection from the accepted pool tends to $p/(p+(1-p)\varphi)$ .
Compute the ceiling for $p=0.2$ and $\varphi\in\{0.01, 0.05, 0.2\}$ .
Suppose the verifier instead ranks and you take the top-scored sample. Explain why the large- $n$ behaviour can be worse than the bound in part 1.

Write a complete argument. Every inequality you use should be one you could state precisely.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Sizing best-of-n	Agents	Numerical	Beginner	15 min
The pass@k estimator	Agents	Proof	Intermediate	30 min
The KL divergence of best-of-n abyss	Agents	Proof	Graduate	1 hour