= Integer-valued expectation threshold restart bound
{title2=$\Pr(Z\leq A/q)\geq1/(A+1)$}
Let $Z$ be a nonnegative integer-valued <random variable> with $\mathbb EZ=A/q$, where $A\geq0$ and $q\geq1$ are <integers>. On $Z>A/q$, the integer $qZ$ is at least $A+1$. <Markov's inequality> gives $\Pr(Z>A/q)\leq A/(A+1)$. Independent restarts therefore need at most $A+1$ attempts in <expected value> to achieve $Z\leq\mathbb EZ$. The denominator bound on the <expected value> matters for this runtime guarantee.
Back to article page
