Median of Means Estimator (Median aus empirischen Mitteln) - Herleitung

Erste Frage Aufrufe: 71     Aktiv: 15.01.2023 um 02:09
1
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 ! :)

EDIT vom 15.01.2023 um 00:08:

hier nachträglich noch einmak der Link zum Paper:
Diese Frage melden
gefragt

Punkte: 17

 
Kommentar schreiben
1 Antwort
0
Erstmal ein Lob für die sehr schön ausgearbeitete Fragestellung. Der Link zum Paper geht nicht. 

Die Ungleichung bei $(*)$ kann ich dir gerade spontan nicht erläutern, aber $Bin(k,p)$ steht für die Binomialverteilung mit den Parametern $k$ und $p$. Wie man diese berechnet, sollte dir aus der Schule noch bekannt sein (Stichwort Bernouilli-Formel). Das entspricht aber genau deiner Interpretation. $k$ Versuche bei einer Erfolgswahrscheinlichkeit von $p=\frac{1}{4}$, was ja vorgegeben war. 

Bei $(***)$ passiert dir allerdings ein Gedankenfehler: Hoeffdingsche Ungleichung gilt für unabhängig verteilte Zufallsvariablen. Von gleichverteilt oder identisch verteilt ist da nicht die Rede. In diesem Fall hast du aber keine Summe von ZV, sondern nur die Eine Zufallsvariable, die binomialverteilt ist, mit den angegebenen Parametern. Im Abschnitt "Confidence intervalls" findest du die passende Abschätzung für die Binomialverteilung.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 26.7K

 
Guten Abend, danke für die schnelle Antwort !

(*) Die Bernoulli-Gleichung liefert mir meines Wissens ja die Wahrscheinlichkeit aus z.B. k aufeinanderfolgenden Münzwürfen (p=1/2) genau n mal Kopf zu erhalten. Somit wäre das Ergebnis aus dem Intervall [0,1]. In der fraglichen Formel steht

... $\mathbb{P} \left[\text{Bin}\left(k, \frac{1}{4}\right) \geq \frac{k}{2}\right]$ ...
wenn aber $\text{Bin}\left(k,\frac{1}{4}\right) \in [0,1]$ und $k>2,$, dann kann die Ungleichung im Argument der Wahrscheinlichkeitsfunktion doch überhaupt nicht erfüllt werden... In diesem Kontext müsste $\text{Bin}\left(k, \frac{1}{4}\right)$ eher sowas sein, wie die Anzahl der "Erfolge", nach k Versuchen. Oder habe ich gerade ein Brett vorm Kopf, was die Binomialverteilung angeht?
(Könnte es eventuell $ \mathbb{P} \left[k\cdot\text{Bin}\left(k, \frac{1}{4}\right) \geq \frac{k}{2}\right]$ heißen?)

(***) das stimmt, da habe ich tatsächlich einen Gedankendreher gehabt, danke ! Dennoch wird im Paper (der Link ist als Edit im originalen post beigefügt) explizit gesagt "by Hoeffdings Inequality"... ich habe den Abschnitt zum confidence interval gelesen & könnte das Ergebnis natürlich einfach so hinnehmen ;)
Eine Erklärung, wie genau man auf diesen letzten Schritt kommt, wäre aber natürlich auch toll für das tiefere Verständnis ! :)   ─   coryn7 15.01.2023 um 00:27
Es handelt sich natürlich um die Zufallsvariable, nicht um die Wahrscheinlichkeit. Das steht aber auch im Paper.

Welchen letzten Schritt meinst du jetzt konkret?   ─   cauchy 15.01.2023 um 00:47
Ich glaube, es jetzt begriffen zu haben - die Frage hat sich somit erledigt. Vielen Dank nochmal für die Hilfe !! :)   ─   coryn7 15.01.2023 um 00:55
1
Das ist schön. Und sehr gerne. Viel Erfolg für deine Arbeit!   ─   cauchy 15.01.2023 um 02:09

Kommentar schreiben