# Deamortizing a Las-Vegas randomized algorithm

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?

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$.
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}$.
• That's covered by my answer: you hope that the algorithm terminates in $n$ steps, and if not, you wait in the last step for the algorithm (or one of its copies) to finish. – Yuval Filmus Dec 7 '15 at 18:17