A team proposes replacing an exact tally over a stream with a bounded-error randomized estimator; when is that trade defensible?

## First, name the guarantee precisely Before anything can be decided, the promise has to be stated in the form it is actually made: - The probability is over **the algorithm's own coin flips**, not over a distribution of inputs. The bound holds for every single input, which means there is no adversarial input that defeats it and no "typical workload" assumption hiding underneath. - It is a **per-run** bound. It never certifies a particular answer; it describes how often the procedure is right on that input. - An estimator usually carries **two** parameters, and they are different things: how far the value may be from the truth, and how likely it is to be outside that interval. The second is the bounded-error probability discussed here; the first is an accuracy promise and is negotiated separately. A proposal that cannot state which of these it offers is not yet a proposal. ## Second, set the error budget, then derive the cost The economics of amplification are unusually friendly, and that is the strongest argument in favour of the trade. Independent repeats with a majority vote, or repeats until a one-sided proof appears, drive the failure probability down exponentially while cost grows linearly: 1. Decide the failure probability the system may carry for this answer. 2. Derive the repeat count from the per-run error and that target. 3. Compare the cost of that many repeats with the cost of the exact computation. 4. Compare the resulting probability with the failure rates already present — undetected storage or transmission corruption, a machine failing mid-computation, a defect in the exact implementation. Step 4 is the one that is usually skipped and usually decides the argument. A residual probability far below the rate at which the surrounding system fails anyway is not a real risk; it is a rounding error in the risk the system already accepts. ## Third, refuse the wrong justification The weakest argument for a randomized procedure is that it is "asymptotically faster". Randomness is widely believed to add **no** asymptotic power to polynomial-time computation: under standard assumptions about the circuit complexity of hard problems, pseudorandom generators exist that let any bounded-error polynomial-time procedure be simulated deterministically, which would make `BPP` equal `P`. It is a conjecture, not a theorem, but it is the working expectation, and it means a randomized algorithm's advantage should be argued on constants, memory, implementation simplicity, or on the exact problem being `#P`-hard — never on a complexity class it escapes. What is known outright helps to place it: `P` sits inside `ZPP`, inside `RP`, inside `BPP`, and `BPP` sits inside `PSPACE`, since a deterministic machine can walk every possible coin sequence in reusable space. Whether `BPP` sits inside `NP` is open. ## Fourth, audit the randomness itself The guarantee is a theorem about independent coins, and an implementation is where independence is lost: - Repeats derived from a single seed are one run performed several times, and the exponent in the error bound then describes an experiment that never happened. - Many instances started from the same source fail **together**, which turns an independent per-answer probability into a correlated fleet-wide event. - An unrecorded seed makes a wrong answer unreproducible. Record it, and the run becomes replayable evidence rather than an anecdote. ## Fifth, decide what the organisation promises This is the part only a lead can settle, because it leaves engineering and becomes a commitment: | decision | the question to answer | |---|---| | what the interface returns | an integer that looks exact, or a value with its error and confidence attached | | what consumers may assume | whether a downstream system is allowed to treat the figure as exact and reconcile against it | | when the exact path runs | never, on demand, or as a periodic audit against the estimate | | how a miss is detected | what evidence exists afterwards that a particular answer was one of the unlucky ones | An estimate exposed through an interface that looks exact is the failure mode that outlives the decision: consumers build reconciliation on it, and the error budget that justified the trade is never visible to the people relying on it. ## The short form of the judgment Take the trade when the exact answer is genuinely hard or disproportionately expensive, the failure probability is explicit and dominated by existing failure rates, the randomness is independent and recorded, and the interface tells the truth about what it returns. Refuse it when the argument is speed alone, when nobody has written down the budget, or when a downstream consumer needs an exact figure that the system would then be quietly failing to provide.