  We introduce probability estimation, a broadly applicable framework to
certify randomness in a finite sequence of measurement results without assuming
that these results are independent and identically distributed. Probability
estimation can take advantage of verifiable physical constraints, and the
certification is 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 adaptability to
changing experimental conditions, 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.
