Randomized Algorithms


Date: January 30, 2001

``Why,'' he said, ``were all the ship's computations being done on a waiter's bill pad?''

Slartibartfast said, ``Because in space travel all the numbers are awful.''

He could tell that he wasn't getting his point across.

``Listen,'' he said. ``On a waiter's bill pad numbers dance. You must have encountered the phenomenon.''

``Well ...''

``On a waiter's bill pad,'' said Slartibartfast, ``reality and unreality collide on such a fundamental level that each becomes the other and anything is possible, within certain parameters.''

 

                        -- Life, the Universe, and Everything, Douglas Adams

Some More Probability


\begin{theorem}[Markov inequality]
Let $Y$\ be a positive random variable. Then...
...th}
\Pr\pbrc{ Y \geq k E[Y] } \leq \frac{1}{k}.
\end{displaymath}\end{theorem}


\begin{theorem}[Chebyshev's Inequality]
Let $X$\ be a random variable. Let $\mu...
...ert \geq t \cdot \sigma_X } \leq
\frac{1}{t^2}.
\end{displaymath}\end{theorem}

Proof. Set $ Y = (X - \mu_X)^2$. This is a positive random variable. We have by Markov inequality

$\displaystyle \Pr \pbrc{ \vert X - \mu_X \vert \geq t \cdot \sigma_X } =
\Pr \p...
...\geq t^2 \cdot \sigma_X^2 } =
\Pr \pbrc{ Y \geq t^2 E[Y] } \leq \frac{1}{t^2}.
$

$ \qedsymbol$

Easy consequence of Chebyshev's inequality, is the following:
\begin{lemma}
Let $X$\ be the number of times we get heads in throwing
a fair ...
... p n\vert \geq t \sqrt{n p q}} \leq \frac{1}{t^2}.
\end{displaymath}\end{lemma}

LazySelect - Selecting the $ k$-th element

  1. $ S$ - $ n$ distinct elements.
  2. $ r_S(t)$ - rank of $ t \in S$ in $ S$.
  3. $ S_{(i)}$ - $ i$-th element of $ S$.
  4. We want to compute $ S_{(k)}$.

  5. $ R$ - Sample with replacement of $ n^{3/4}$ elements from $ S$.

  6. Sort $ R$.

  7. $ l = \max{1, \floor{ kn^{-1/4} - \sqrt{n}} }$
  8. $ h = \min{n^{3/4}, \floor{ k n^{-1/4} + \sqrt{n}} }$

  9. $ a = R_{(l)}$, $ b = R_{(h)}$.

  10. Assume that $ k \in [n^{1/4},n - n^{1/4}]$.

  11. Compute the rank $ r_S(a)$ of $ a$ and the rank $ r_S(b)$ of $ b$ in $ S$ ($ 2n$ comparisons).

    Exercise: Show how to do this stage in (expected) $ 1.5n$ comparisons.

  12. If $ S_{(k)}$ is not between $ a$ and $ b$ repeat the above process till success.

  13. Compute $ P = \brc{ y \in S \sep{ a \leq y \leq b}
}$ (can be done while computing the rank of $ a$ and $ b$).

  14. If $ \vert P\vert \geq 4n^{3/4} + 2$ repeat the above process till success.

  15. Sort $ P$, and compute $ P_{(j)}$, where $ j = k - r_S(a)$.

  16. return $ P_{(j)}$.


\begin{lemma}
LazySelect succeeds with probability $1 - O(n^{-1/4})$ in the first iteration. And it performs only $2n + o(n)$ comparisons.
\end{lemma}

Proof. $ \qedsymbol$

Any deterministic selection algorithm requires $ 2n$ comparisons, and LazySelect can be changes to require only $ 1.5n + o(n)$ comparisons (expected).


Sariel Har-Peled 2001-01-30
Home Bookmarks Papers Blog