Chernoff-Ungleichung

09.10.2016, 12:04	miss_jellyfish2	Auf diesen Beitrag antworten »
Chernoff-Ungleichung Hallo zusammen, neues Beispiel - neue Frage Wir werfen zwei Münzen, a und b jeweils n-mal. Münze a hat zu 1/4 Kopf und zu 3/4 Zahl, Münze b zeigt jede Seite gleich oft (also 1/2). Die Würfe sind unabhängig. Die Zufallsvariable $\begin{eqnarray} X_n \end{eqnarray}$ bezeichnet die Gesamtzahl der Würfe, die Kopf gezeigt haben. Zeigen Sie mithilfe einer Chernoff-Ungleichung, dass $\begin{eqnarray} \mathrm{Pr}[X_n \ge n] \le e^{-n/36} \end{eqnarray}$ . Mein Lösungsansatz ist, die Formel für Upper Tail herzunehmen. In jedem Fall benötigen wir erstmal den Erwartungswert: $\begin{eqnarray} \mathbb{E}[X_n] = \frac{3}{4}n \end{eqnarray}$ . Formel laut Blatt: $\begin{eqnarray} \mathrm{Pr} [X_n \ge (1+t)\mathbb E [X_n]] \le \left( \frac{e^t}{(1+t)^{(1+t)}} \right )^{\mathbb E [X_n]} \end{eqnarray}$ Dann einsetzen: $\begin{eqnarray} \mathrm{Pr} [X_n \ge (1+t)\frac{3}{4}n] \le \left( \frac{e^t}{(1+t)^{(1+t)}} \right )^{\frac{3}{4}n} \end{eqnarray}$ Nun kann ich mir $\begin{eqnarray} t \end{eqnarray}$ bestimmen: $\begin{eqnarray} (1+t)\frac{3}{4}n = n \rightarrow t = \frac{1}{3} \end{eqnarray}$ Wiederum einsetzen: $\begin{eqnarray} \mathrm{Pr} [X_n \ge n] \le \left( \frac{e^\frac{1}{3}}{\left(\frac{4}{3}\right)^{\frac{4}{3}}} \right )^{\frac{3}{4}n} \end{eqnarray}$ Dann kann ich die äußere Klammer auflösen: $\begin{eqnarray} \mathrm{Pr} [X_n \ge n] \le \frac{e^{\frac{1}{3}\frac{3}{4}n}}{\left(\frac{4}{3}\right)^{\frac{4}{3}\frac{3}{4}n}} \end{eqnarray}$ und kürzen: $\begin{eqnarray} \mathrm{Pr} [X_n \ge n] \le \frac{e^{\frac{1}{4}n}}{\left(\frac{4}{3}\right)^{n}} \end{eqnarray}$ Nun kann ich noch den Bruch los werden: $\begin{eqnarray} \mathrm{Pr} [X_n \ge n] \le e^{\frac{n}{4}} \left(\frac{3}{4}\right)^{n} \end{eqnarray}$ Jetzt setze ich in die ursprüngliche, zu zeigende Forderung ein: $\begin{eqnarray} e^{\frac{n}{4}} \left(\frac{3}{4}\right)^{n} \le e^{-n/36} \end{eqnarray}$ Naheliegend wäre jetzt, einfach mal ln über das Ganze zu schieben: $\begin{eqnarray} \frac{n}{4} ln(\frac{3}{4}^n) \le - \frac{n}{36} \end{eqnarray}$ Und jetzt stehe ich irgendwie an... Bin ich schon fertig, kann ich irgendwie noch weiter umformen? Ich habe mir beide Seiten mal geplottet, das müsste eigentlich schon passen soweit. Aber es fühlt sich noch nicht fertig an. Liebe Grüße, miss_jellyfish
09.10.2016, 12:07	miss_jellyfish2	Auf diesen Beitrag antworten »
Korrektur: die letzte Formel muss natürlich $\begin{eqnarray} \frac{n}{4}+ ln \left(\left(\frac{3}{4} \right)^n \right) \end{eqnarray}$ lauten. Sorry Liebe Grüße, miss_jellyfish

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »