Hallo zusammen ! :)

Ich recherchiere für meine Bachelorarbeit in Quantenmechanik und bin auf ein paper gestoßen, in dem es um den sogenannten Median of Means Estimator geht. Hier eine kurze Zusammenfassung, die zu dem Teil führt, bei dem ich Hilfe benötige (Seite 7 und 8):

 

Man betrachte eine Anzahl von unabhängigen, gleichverteilten Zufallsvariablen $X_1, X_2,...,X_n$ mit Erwartungswert $\mu$ und Varianz $\sigma^2$. Das empirische Mittel $\bar{X}(n)$ aller Zufallsvariablen hat dann eine Varianz $\eta^2 = \frac{\sigma^2}{n}$ und ist (nach Chebyshev's Ungleichung) nach oben hin beschränkt durch $\mathbb{P}[|\bar{X}(n)-\mu|\geq \varepsilon] \leq \frac{\eta^2}{\varepsilon^2} = \frac{\sigma^2}{n\varepsilon^2}$. Die Anzahl $n$ der Zufallsvariablen (Samples), die benötigt werden damit mit Wahrscheinlichkeit $1-p_{fail}$ gilt $|\bar{X}(n)-\mu|\leq \varepsilon$, skaliert mit $n \propto 1/ p_{fail}$, was in meinem Anwendungsfall suboptimal ist.

 

Um ein Skalieren dieser Art zu vermeiden wird ein sog. median of means estimator verwendet, d.h. man teilt die Menge aller $n$ Zufallsvariablen in $k$  Teilmengen, welche jeweils $m$ der Zufallsvariablen beinhalten, sodass $n=km$. Anschließend wird zuerst für jede Teilmenge das empirische Mittel und dann der Median aller $k$ Teilmengen-Mittel gebildet:

 

$\hat{\mu} \equiv \text{median}\left\{\bar{X}_1(m), \bar{X}_2(m),\dots, \bar{X}_k(m)\right\}$            mit         $\bar{X}_j(m)\equiv \frac{1}{m}\sum\limits_{i\in B_j} X_i$

$B_j$ bezeichnet hier die Indexmenge der $j$-ten Teilmenge. Jedes der $k$ Teilmengen-Mittel ist, wie obig diskutiert, beschränkt durch :

 

$p_{fail} \equiv \mathbb{P}\left[|\bar{X}_j(m)-\mu|\geq \varepsilon\right] \leq \frac{\sigma^2}{m\varepsilon^2}$

Die Autoren des papers legen nun $p_{fail} = 0.25$ fest, somit ist $\varepsilon = \sigma\sqrt{\frac{4}{m}}$. So weit, so gut. Die Frage von Interesse ist nun, was die Wahrscheinlichkeit für den Fall ist, dass der median of means estimator um einen gewissen Betrag $\varepsilon>0$ vom wahren Erwartungswert $\mu$ abweicht: $\mathbb{P}\left[|\hat{\mu}-\mu|\geq \varepsilon = \sigma\sqrt{\frac{4}{m}}\right]$ ?

 

Ab diesem Punkt nimmt mein Verständnis ab. Ich verstehe, dass die Aussage $|\hat{\mu}-\mu|\geq \sigma\sqrt{\frac{4}{m}}$ impliziert, dass für mindestens die Hälfte aller Teilmengen-Mittel gilt $|\hat{X}_j(m)-\mu|\geq \sigma\sqrt{\frac{4}{m}}$. Dies folgt direkt aus der Definition des Median. Die auf Seite 8 des papers postulierte Gleichung lautet 

$\mathbb{P}\left[|\hat{\mu}-\mu| \geq \sigma\sqrt{\frac{4}{m}}\right] \stackrel{*}{\leq} \mathbb{P}\left[ \text{Bin}\left( k, \frac{1}{4}\right) \geq \frac{k}{2} \right] \stackrel{**}{=} \mathbb{P}\left[ \text{Bin}\left( k, \frac{1}{4}\right) - \mathbb{E}\left[ \text{Bin} \left( k, \frac{1}{4}\right) \right] \geq \frac{k}{4} \right] \stackrel{***}{\leq} 2\exp\left( -\frac{k}{8} \right)$

 

Wobei im letzten Schritt die Hoeffdingsche Ungleichung angewendet wird. Die obige Gleichung ist mir an einigen Stellen nocht nicht ganz klar. Bevor ich zu konkreten Fragen komme, will ich wenigstens einmal mein intuitives Verständnis hinter der Gleichung schildern:

 

Da jedes Teilmengen-Mittel entweder in das gewünschte $\varepsilon$-Intervall fällt oder nicht, können wir das Problem als Bernoulli-Experiment modellieren, bei dem das Ereignis $|\bar{X}_j(m)-\mu|\geq \varepsilon$ mit Wahrscheinlichkeit kleiner oder gleich $p_{fail}$ und das Ereignis $|\bar{X}_j(m)-\mu|\leq \varepsilon$ mit Wahrscheinlichkeit $1-p_{fail}$ auftritt. Wir führen das Experiment $k$ mal durch (d.h. einmal für jedes Teilmengen-Mittel). Uns interessiert der Fall, in dem mindestens die Hälfte der Teilmengen-Mittelwerte außerhalb des gewünschten Intervalls liegen, da dies dem Fall entspricht, dass der Median ebenfalls außerhalb des gewünschten Intervalls liegt.

Gleichheit (**) ist für mich klar: Wir schreiben das Argument einfach um, um es für die Anwendung der Hoeffdingschen Ungleichung vorzubereiten. Der Erwartungswert einer Binomialverteilung ist gegeben durch $k\cdot p$ hier also $\frac{k}{4}$. Diesen Term subtrahieren wir einfach von beiden Seiten.

Hier sind also die Hauptfragen (gekennzeichnet durch die Sternchen in der Gleichung):

 

(*) Angenommen, meine Intuition ist richtig, warum die Ungleichheit? Wofür genau steht $Bin\left(k, p_{fail} = 1/4\right)$ und wie wird es berechnet?

 

(***) In dem paper wird erwähnt, dass an dieser Stelle Hoeffdings-Ungleichung verwendet wird, die eine Obergrenze für die Summe von gleichverteilten, unabhängigen Zufallsvariablen angibt. Wie genau kommen wir zum Ergebnis?

 

Vielen Dank im Voraus ! :)