Median-Trick

Angenommen, wir haben einen randomisierten Algorithmus, mit dem wir einen gesuchten aber nicht bekannten Wert $k$ abschätzen wollen. Der Algorithmus gibt einen Schätzwert $\hat{k}$ aus. Durch die Analyse des Algorithmus wissen wir, dass $\hat{k}$ mit guter Wahrscheinlichkeit ein guter Schätzwert ist; genauer, wir wissen, dass

\begin{align*} \Pr[\hat{k} \leq c_1 k ] \leq p \\ \Pr[\hat{k} \geq c_2 k ] \leq p \\ \end{align*}

für Parameter $c_1 \lt 1 \lt c_2$.