Deamortizing a Las-Vegas randomized algorithm

Question

Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound.

For example, assuming you need to find the median of an array once every $n$ operations of type $X$ (which does not change the array).

You could take a specific algorithm, such as the median of medians selection algorithm, which takes at most $c\cdot n$ time, and perform $c$ of its operations every time $X$ is performed. This guarantees that the worst case run time of finding the median in each $X$ call is constant.

But now assume we'd like to use a randomized Las-Vegas algorithm (always correct, runtime is computed in expectation), such as computing the median by selection with random pivot.

Now we know that the algorithm is expected to take $c'\cdot n$ operations, but it might take more, or less.

• How do you determine how many of the iterations you run every time $X$ is performed?
• Can we say that by performing, say, $2c'$ operations every time we will finish computing the median with high probability?
• Can we adaptively select how many operations of the selection algorithms to perform at each of $X_1,X_2\ldots X_n$ calls such that we will finish computing the median with probability $1$, but so that with high probability, the number of operations in each $X$ call is constant?

Answer 1

If the expected running time of the algorithm is $c'n$, then Markov's inequality shows that for all $A$, the probability that the algorithm takes more than $Ac'n$ operations is at most $1/A$. If you run $Ac'$ operations each time then you will finish computing with probability $1-1/A$, and if you run $Ac'$ operations each time until the last step, at which you let the algorithm loose, then the number of operations will be at most $Ac'$ with probability $1-1/A$.

In some cases you know more about the distribution of the running time of the algorithm – say its variance. In that case you can get better bounds using (for example) Chebyshev's inequality.

Another trick to try is to run several instances of the algorithm in parallel with fresh coins. For example, suppose that we run $B$ independent instances of the algorithm, each for $(A/B)c'$ operations at each step. The probability that none of them finishes is at most $(B/A)^B$, compared to $1/A$ we had before. Choosing $B \approx A/e$, this improves the failure probability from $1/A$ to roughly $e^{-A/e}$.