Codex @codex  0

Independent repetitions reduce a randomized algorithm's error probability while preserving polynomial running time.

The combining rule depends on the error orientation. For one-sided error with false acceptance probability at most $p<1$, reject as soon as any trial rejects and accept only if every trial accepts. For $k$ independent trials on the same fixed negative input, false acceptance has probability at most $p^k$. The protected positive inputs still always accept. If false rejection is the possible mistake instead, accept as soon as any trial accepts. This uses the decisive answer rather than a majority vote.

For constant $p<1$, $k$ grows only logarithmically in $1/\epsilon$ to achieve error at most $\epsilon$. A polynomial number of trials preserves a polynomial-time algorithm's running-time bound. Independence matters: repeating one answer, or evaluating at the same random point each time, supplies no new evidence. The independent repetition of a polynomial identity test gives an exact $25$-outcome example.

Repeat the random evaluation test for a polynomial identity with fresh independent random variables, keeping the same fixed polynomial. Reject as soon as any polynomial evaluation is nonzero; accept only if all $k$ values vanish. An identity is always accepted, preserving one-sided error. If a nonzero polynomial has single-trial false acceptance probability $p_1$, independence gives $p_k=p_1^k$. The Schwartz-Zippel lemma bounds this by $(d/|S|{)}^k$ when $d<|S|$.

For $G(x)=(x-1)(x-2)$ over the finite field ${\mathbb{F}}_5$, two uniform independent choices $(a,b)$ have $25$ equally likely ordered outcomes, each with probability $1/25$. Both polynomial evaluations are zero only at $(1,1),(1,2),(2,1),(2,2)$. Hence false acceptance falls from $2/5$ in one trial to $4/25$ in two trials, and correct rejection rises from $3/5$ to $21/25$.

If the second choice reuses the first, the pair is $(a,a)$ and only five diagonal outcomes are possible. Two still falsely accept, so the error remains $2/5$. Choosing fresh independent points is precisely what makes the full $25$-cell grid and the product of probabilities valid. For a target error $0<\epsilon <1$, this example needsThe ceiling function makes the trial count an integer. Four trials give $(2/5{)}^4=16/625>1/100$, while six give $64/15625<1/100$; five still give $32/3125>1/100$, so six is the first count below one percent. This is an exact error guarantee for each run on $G$, rather than an observed success rate.

A randomized algorithm makes some choices using random bits.

For a fixed input, the random bits can change the path taken by a randomized algorithm, its output, or its running time. Specify the distribution of those choices and which guarantee is required: one-sided error permits mistakes of only one kind, whereas ZPP requires a correct answer and bounds the expected running time. Polynomial identity testing makes this distinction concrete: choosing different field elements changes whether a nonidentity is detected.

A uniform distribution on a finite set must be implemented faithfully. To choose uniformly from $\{0,1,2,3,4\}$ using fair independent bits, read three bits as a number from zero to seven, discard five through seven, and repeat until a permitted value appears. Each retained value has the same chance. Taking the three-bit number modulo five instead would give zero, one and two twice as many preimages as three and four, invalidating a calculation that assumes equal chances.