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

• If $X$ and $Y$ are independent then
  $$E[ X Y ] = E[ X ] E[ Y ].$$
  Let $\mu_X = E[X]$.

• $\mathop{\mathrm{var}}[X] = E[ (X -\mu_X)^2 ] = E[X^2] - \mu_X^2$ - this is the variance. Intuitively, this tells us how concentrated is the distribution of $X$.

• $\sigma_X = \sqrt{\mathop{\mathrm{var}}[X]}$: standard deviation. (i.e., variance is inconvenient to work with because it is a squared quantity).

• $\mathop{\mathrm{var}}[c X] = c^2 \mathop{\mathrm{var}}[X]$.

• $\mathop{\mathrm{var}}[X + Y ] = \mathop{\mathrm{var}}[X] + \mathop{\mathrm{var}}[Y]$.

• Bernoulli distribution

  We flip a coin, get $1$ (heads) with probability $p$, and 0 (i.e., tail) with probability $q = 1-p$. Let $X$ be this random variable. The variable $X$ is has Bernoulli distribution with parameter $p$. Then $E[X] = p$, and $\mathop{\mathrm{var}}[X] = p q$.

• Binomial distribution

  Assume that we repeat a Bernoulli experiments $n$ times (independently!). Let $X_1, \ldots, X_n$ be the resulting random variables, and let $X = X_1 + \cdots + X_n$. The variable $X$ has the binomial distribution with parameters $n$ and $p$. We have

  $$b(k;n,p) = \Pr[ X = k ] = \binom{n}{k} p^{k} q^{n-k}.$$
  Also, $E[X] = n p$, and $\mathop{\mathrm{var}}[X] = n p q$.

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

$$\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:

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)}$.

Proof.

• Bad event $a > S_{(k)}$:
  • $X_i$ - $1$ if the $i$-th sample smaller equal to $S_{(k)}$, otherwise 0.

  • $p = \Pr[X_i] = k/n$, $q = 1-k/n$.

  • $X = \sum_{i=1}^{n^{3/4}} X_i$.

  • $X$ has binomial distribution with $p=k/n$, and parameter $n^{3/4}$.

    Chebyshev inequality tells us:

    $$\Pr\pbrc{\vert X - p n^{3/4}\vert \geq t \sqrt{n^{3/4}p q}} \leq \frac{1}{t^2}.$$

  • $p n^{3/4} = k n^{-1/4}$, $\sqrt{n^{3/4}(k/n)(1-k/n)} \leq n^{3/8}/2$. In particular, the probability of $a > S_{(k)}$ is
    $$\Pr \pbrc{ X < (k n^{-1/4} - \sqrt{n} ) } \leq \Pr\pbrc{ \vert X ... ...dot \frac{n^{3/8}}{2} } \leq \frac{1}{\pth{2 n^{1/8}}^2} = \frac{1}{4n^{1/4}}.$$

• Similar analysis to bound the bad event $b < S_{(k)}$.

• Finally, the only other possible bad event, is that $P$ is too large. Let $k_l = k -2n^{3/4}$. Arguing as above, we show that with probability at least $1 - O(1/n^{1/4})$ at least $k n^{-1/4} - \sqrt{n}$ were picked from the range $S_{(1)} \ldots, S_{(k_l)}$. Namely, with probability at least $1 - O(1/n^{1/4})$ the element $a$ is larger than $S_{(k_l)}$. Similar analysis shoes that $b$ is smaller than $S_{(k_h)}$ where $k_h = k +2n^{3/4}$ with same probability bound.

  Thus, $\vert P\vert \leq 4n^{3/4}$ with probability at least $1 - O(n^{-1/4})$.

$\qedsymbol$

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

Home

Bookmarks

Papers

Blog