We introduce probability estimation, a broadly applicable framework to certify randomness in a finite sequence of measurements subject to verifiable physical constraints and with respect to classical side information. Examples include randomness from single-photon measurements and device-independent randomness from Bell tests. Advantages of probability estimation include unproblematic early stopping when goals are achieved, optimal randomness rates, applicability to Bell tests with small violations, and unsurpassed finite-data efficiency. We greatly reduce latencies for producing random bits and formulate an associated rate-tradeoff problem of independent interest. We also show that the latency is determined by an information-theoretic measure of nonlocality rather than the Bell violation.

• Received 3 May 2018

DOI:https://doi.org/10.1103/PhysRevA.98.040304