Randomisierter-Median-Algorithmus

Problem: Bestimme den Median von n Elementen:

1.

Wähle $n^{\frac{3}{4}}$ Elemente zufällig aus dem n Elementen aus.

2.

Sortiere diese $n^{\frac{3}{4}}$ Elemente mit einem $n\log n$-Algorithmus.

3.

Setze

p₁

$:=\max \{ \frac{n^{\frac{3}{4}}}{2} -\sqrt{n},1 \}$-kleinsten Element der $n^{\frac{3}{4}}$ Elemente.

p₂

$:=\min \{ \frac{n^{\frac{3}{4}}}{2} +\sqrt{n}, n^{\frac{3}{4}} \}$-kleinsten Element der $n^{\frac{3}{4}}$ Elemente.

4.

Partitioniere n Elemente in

S₀

$:= \{ \text{Elemente} < p_1\}$

S₁

$:= \{ p_1 \leq \text{Elemente} \leq p_2\}$

S₂

$:= \{ p_2 < \text{Elemente} \}$

5.

Falls $\vert S_0\vert\geq \left\lceil\frac{n}{2}\right\rceil$ oder $\vert S_2\vert\geq \left\lceil\frac{n}{2}\right\rceil$ oder $\vert S_1\vert \geq 4 \cdot n^{\frac{3}{4}}$ dann wiederhole den Algorithmus
ansonsten sortiere S₁ und liefer das $\left\lceil\frac{n}{2}\right\rceil- \vert S_0\vert$-kleinste Element davon ab.

Beweis:

i)

Korrektheit: klar.

ii)

Anzahl der Vergleichen einer Iteration:
$\mathcal{O}(n^{\frac{3}{4}}\log{n^{\frac{3}{4}}})$ + Kosten der Partitionierung
Kosten der Partitionierung: zu naiv, bessere Ansatz:

Wähle zuerst mit der Wahrscheinlichkeit je $\frac{1}{2}$ aus, ob Element x mit p₁ oder p₂ verglichen wird, mache zwei Vergleiche nur, falls nötig. Erwartete Anzahl Vergleiche dafür ist gleich:

$$\begin{split} & = n\cdot \frac{1}{2} \left( \frac{\vert S_0... ... + 2 + 2\cdot n^{-\frac{1}{4}}) = \frac{3}{2} + o(n)\end{split}$$

Wir zeigen, daß der Algorithmus mit der Wahrscheinlichkeit $\geq 1-\mathcal{O}(n^{-\frac{1}{4}})$ nur eine Iteration benötigt (daraus folgt, daß insgesamt Anzahl der Vergleiche $\leq \frac{3}{2}n+o(n)$ ist). Dafür verwenden wir Hilfsmittel aus der Stochastik:

• Zufallsvariable (ZV): X, Werte $\in\{0,1\}$ (binäre Zufallsvariable) mit
  
  $X = \left \{ \begin{array} {ll} 1 \text{ mit WS } p \\ 0 \text{ mit WS } q=1-p \\ \end{array} \right.$
  
• Erwartungswert einer ZV: E(X) = $\sum_{x \in \text{ Wertebereich}}$WS(X=x)$\cdot x$
  (X ist diskret, d.h. der Wertebereich von X ist endlich)
  
• Markov-Ungleichung : WS($X\geq t) \leq \frac{\text{E}(X)}{t}$ für X nicht negativ
  
• Tschebyscheff-Ungleichung : WS(|X-E$(x)\vert\geq t) \leq \frac{\text{Var}(X)}{t^2}$
  
• Binomialverteilung : Seien $X_1, \cdots ,X_n$ unabhängige, identisch gleichverteilte Zufallsvariablen mit Wertebereich $\{0,1\}$, WS(X_i=1)=p;

  $$X:=\sum_{i=1}^n X_i$$

  X ist gemäß der Binomialverteilung verteilt, Wertebereich = $\{0,1,\cdots, n\}$:

  $$\begin{split} \text{WS}(X=k) & = \binom{n}{k} p^k(1-p)^{n-k... ...ar}(X) & = n\cdot p \cdot(1-p) = n\cdot p \cdot q . \end{split}$$

  X ist verteilt gemäß der Binomialverteilung mit den Parametern n und p, in Zeichen $X\sim$ B(n,p).

Auswahl der $n^{\frac{3}{4}}$ Elemente wird wiederholt, falls $\vert S_0\vert\geq \frac{n}{2}$. Dies passiert gdw. wir höchstens $\frac{1}{2}n^{\frac{3}{4}}-\sqrt{n}$Elemente aus der Hälfte der aller Elemente $\leq$ Median auswählen.
Was ist also die Wahrscheinlichkeit dafür, daß keine neue Auswahl der $n^{\frac{3}{4}}$ Elemente stattfinden muß?
Setze Binäre Zufallsvariable für jedes $X_i,\cdots,X_n$ mit:

$$X_i = \left\{ \begin{array} {ll} 1 \text{ ,falls Element $i$... ...}lfte der Wert liegt} \\ 0 \text{ ,sonst} \end{array} \right.$$

$X=\sum X_i$ binomialverteilt mit Parametern n und $\frac{1}{2}n^{-\frac{1}{4}}$
E($X)=\frac{1}{2}n^{\frac{3}{4}}$, Var($X)=n \cdot \frac{1}{2}^{-\frac{1}{4}} (1-\frac{1}{2}n^{-\frac{1}{4}})= \frac{1}{2}n^{\frac{3}{4}}(1-o(1))$

Die Wahrscheinlichkeit hierbei ist:

$$\begin{split} \text{WS}(\vert S_0\vert\geq \frac{n}{2}) & =... ...(1))}{n} \leq \frac{1}{2}n^{-\frac{1}{4}}(1-o(1))\\ \end{split}$$

Die Wahrscheinlichkeit für den Fall, daß man von vorne anfangen muß:

$$\text{WS} \Rightarrow 1-\left(\frac{1}{2}n^{-\frac{1}{4}}(1-o(1))\right)$$

Die anderen beiden Wahrscheinlichkeitsbedingungen (WS($\vert S_2\vert\geq \left\lceil\frac{n}{2}\right\rceil$) und WS($\vert S_1\vert \geq 4 \cdot n^{\frac{3}{4}}$)) ergeben analoge Abschätzungen $\Rightarrow$ Widerholung mit WS $\leq \mathcal{O}(n^{-\frac{1}{4}})$ $\Diamond$