Grenzverhalten von der Binomialverteilung

17.06.2015, 19:41

fernsehen

Grenzverhalten von der Binomialverteilung

Guten Tag,

ich habe hier ein Problem:
Sei $\begin{eqnarray*} Z \sim Bin \left( N = \frac{n(n-1)/2}{2}, p = 2c/n \right) \end{eqnarray*}$ .
Nun gilt $\begin{eqnarray*} EZ = Np = (n-1)c \end{eqnarray*}$ und die Zufallsvariable $\begin{eqnarray*} Z \end{eqnarray*}$ nimmt häufiger mal Werte an, die relativ dicht am Erwartungswert sind.

Meine Aufgabe: Finde ein (möglichst kleines) Intervall (in Abhängigkeit von $\begin{eqnarray*} n \end{eqnarray*}$ ), sodass $\begin{eqnarray*} Z \end{eqnarray*}$ fast sicher darin liegt?

Ich würde da gerne vorhandene Formeln/Sätze/Literatur zu lesen, weiß aber nicht so recht wo ich gucken soll.
Eine Normalverteilung/Poissonverteilung kann man da als Randverteilung nicht annehmen, wenn ich das richtig sehe, weil dafür die Voraussetzungen fehlen.

Vielleicht hat ja jemand eine Idee, einen Hinweis, oder sonstige Ratschläge für mich smile

Viele Grüße,
Patrick

PS. das Problem ist aufgetaucht bei der Bearbeitung meiner Masterarbeit über Zufällige Graphen.

17.06.2015, 20:35

fernsehen

Auf diesen Beitrag antworten »

es geht dabei natürlich nur um den fall $\begin{eqnarray*} n \rightarrow \infty \end{eqnarray*}$ .
Für endliche Werte $\begin{eqnarray*} n \end{eqnarray*}$ kann man natürlich kein kleines Intervall angeben.....

Außerdem ist oben einmal zu oft durch $\begin{eqnarray*} 2 \end{eqnarray*}$ geteilt worden.

17.06.2015, 23:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von fernsehen
Eine Normalverteilung/Poissonverteilung kann man da als Randverteilung nicht annehmen, wenn ich das richtig sehe, weil dafür die Voraussetzungen fehlen.

Randverteilung ist was anderes, anscheinend meinst du hier Grenzverteilung. Und über einen Kunstkniff kann man das eigentlich doch:

Man kann $\begin{align*} Z_n\sim \operatorname{Bin}\left( \frac{n(n-1)}{2}, \frac{2c}{n} \right) \end{align*}$ zumindest für ungerade $\begin{align*} n \end{align*}$ darstellen als Summe $\begin{align*} Z_n = \sum_{k=1}^{\frac{n-1}{2}} Y_{n,k} \end{align*}$ mit unabhängigen $\begin{align*} Y_{n,k}\sim \operatorname{Bin}\left( n, \frac{2c}{n} \right) \end{align*}$ . Für festes $\begin{align*} k \end{align*}$ und $\begin{align*} n\to\infty \end{align*}$ konvergiert diese letztgenannte Verteilung gegen $\begin{align*} \operatorname{Poisson}(2c) \end{align*}$ .

Zumindest approximativ hat man es also bei $\begin{align*} Z_n \end{align*}$ mit der Summe von $\begin{align*} \frac{n-1}{2} \end{align*}$ unabhängigen $\begin{align*} \operatorname{Poisson}(2c) \end{align*}$ -verteilten Zufallsgrößen zu tun - was letztendlich approximativ dann doch auf eine Normalverteilung führt.

----------------------

Seriös könnte man das ganze auch über die charakteristische Funktion von $\begin{align*} Z_n \end{align*}$ diskutieren, die lautet ja $\begin{align*} \varphi_{Z_n}(t) = \left( \frac{2c}{n} (\exp(it)-1)+1 \right)^{\frac{n(n-1)}{2}} \end{align*}$ .

Für die Zufallsgröße $\begin{align*} Y_n = \frac{Z_n-(n-1)c}{\sqrt{(n-1)c}} \end{align*}$ bekommen wir dann $\begin{align*} \varphi_{Y_n}(t) = \exp(-it\sqrt{(n-1)c}) \varphi_{Z_n}\left( \frac{t}{\sqrt{(n-1)c}} \right) \end{align*}$ ,

wofür man (per mittellanger Rechnung) dann die Konvergenz $\begin{align*} \lim_{n\to\infty} \varphi_{Y_n}(t) = \exp\left(-\frac{t^2}{2}\right) \end{align*}$ nachweisen kann, d.h. $\begin{align*} Y_n \end{align*}$ ist asymptotisch standardnormalverteilt.

Und hier noch als Ergänzung die "mittellange" Rechnung:

$\begin{align*} \varphi_{Y_n}(t) = \exp\left(-it\sqrt{(n-1)c} + \frac{n(n-1)}{2} \ln\left( \frac{2c}{n} \left({\color{red}\exp}\left( \frac{it}{\sqrt{(n-1)c}} \right)-1\right)+1 \right) \right) \end{align*}$ .

Zunächst nutzen wir $\begin{align*} {\color{red}\exp}(z) = 1+z+\frac{z^2}{2} + O(|z|^3) \end{align*}$ für $\begin{align*} z\to 0 \end{align*}$ :

$\begin{align*} \varphi_{Y_n}(t) &= \exp\left(-it\sqrt{(n-1)c} + \frac{n(n-1)}{2} \ln\left( \frac{2c}{n} \left(1+\frac{it}{\sqrt{(n-1)c}}-\frac{t^2}{2(n-1)c}+O\left(n^{-3/2}\right)-1\right)+1 \right) \right) \\ &= \exp\left(-it\sqrt{(n-1)c} + \frac{n(n-1)}{2} {\color{blue}\ln}\left( 1+\frac{i2t\sqrt{c}}{n\sqrt{n-1}}-\frac{t^2}{n(n-1)}+O\left(n^{-5/2}\right) \right) \right) \end{align*}$ .

Nun nutzen wir noch $\begin{align*} {\color{blue}\ln}(1+z) = z+ O(|z|^2) \end{align*}$ für $\begin{align*} z\to 0 \end{align*}$ :

$\begin{align*} \varphi_{Y_n}(t) = \exp\left(-it\sqrt{(n-1)c} + \frac{n(n-1)}{2} \left( \frac{i2t\sqrt{c}}{n\sqrt{n-1}}-\frac{t^2}{n(n-1)}+O\left(n^{-5/2} \right) \right) \right) = \exp\left(-\frac{t^2}{2}+O\left(n^{-1/2} \right) \right) \end{align*}$ .

03.07.2015, 20:53

fernsehen

Auf diesen Beitrag antworten »

vielen, vielen dank dafür schonmal !!

doch nun bin ich irgendwie unfähig damit das zu zeigen, was ich eigentlich will, nämlich dass

$\begin{eqnarray*} <br /> cn-n^{2/3} \leq Z_n \leq cn+n^{2/3} \quad \text{a.a.s.}<br /> \end{eqnarray*}$

gilt.

viele grüße

edit: also irgendwie ist es trivial. um "schön" zu argumentieren, fehlen mir da wohl basics mit der normalverteilung :O

ansonsten habe ich alles verstanden und es ist klar, dass man das problem so gut angegangen ist.
echt großen respekt und dank dafür nochmal Freude

03.07.2015, 22:11

HAL 9000

Auf diesen Beitrag antworten »

a.a.s. = asymptotically almost sure ? verwirrt

Weiß nicht so richtig, was das bedeutet. Jedenfalls lässt sich

$\begin{align*} \lim_{n\to\infty} P\left(cn - n^{2/3} \leq Z_n \leq cn + n^{2/3}\right) = 0 \end{align*}$

mit der asymptotischen Standardnormalverteilung von $\begin{align*} \frac{Z_n-(n-1)c}{\sqrt{(n-1)c}} \end{align*}$ begründen.

06.07.2015, 12:31

fernsehen

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
a.a.s. = asymptotically almost sure ? verwirrt

ja, genau!
also das da unten ist fast richtig; da müsste nur " = 1 " stehen.

Zitat:

Original von HAL 9000Jedenfalls lässt sich

$\begin{align*} \lim_{n\to\infty} P\left(cn - n^{2/3} \leq Z_n \leq cn + n^{2/3}\right) = 0 \end{align*}$

mit der asymptotischen Standardnormalverteilung von $\begin{align*} \frac{Z_n-(n-1)c}{\sqrt{(n-1)c}} \end{align*}$ begründen.

also ich denke, dass man da " = 1 " begründen kann. ich probiere das nun einmal so gut es geht:

man hat auf der linken seite

$\begin{eqnarray*} cn-n^{2/3} \leq Z_n \end{eqnarray*}$

das ist umgeformt dann

$\begin{eqnarray*} -n^{1/6} \leq \frac{Z_n - cn}{\sqrt n} \end{eqnarray*}$

die rechte seite ist nun in etwa asymptotisch normalverteilt. die linke seite geht gegen -unendlich. also gilt die ungleichung im grenzwert mit P = 1

für die andere seite sollte das analog gehen. oder übersehe ich etwas, wodurch doch " = 0 " rauskommt?

06.07.2015, 12:45

HAL 9000

Auf diesen Beitrag antworten »

Natürlich =1 statt =0, na klar, da hatte ich mich verschrieben (hatte wohl die Außenbereiche im Sinn). Augenzwinkern

$\begin{align*} \lim_{n\to\infty} P\left(cn - n^{2/3} \leq Z_n \leq cn + n^{2/3}\right) = 1 \end{align*}$ kann man übrigens auch ohne Normalverteilung einfach mit Tschebyscheff beweisen.

06.07.2015, 12:58

fernsehen

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Natürlich =1 statt =0, na klar, da hatte ich mich verschrieben (hatte wohl die Außenbereiche im Sinn). Augenzwinkern

$\begin{align*} \lim_{n\to\infty} P\left(cn - n^{2/3} \leq Z_n \leq cn + n^{2/3}\right) = 1 \end{align*}$ kann man übrigens auch ohne Normalverteilung einfach mit Tschebyscheff beweisen.

oh mann

das hätte bestimmt viel mühe erspart^^aber nun hab ich alles schon fertig geschrieben so mit der normalverteilung

06.07.2015, 13:08

HAL 9000

Auf diesen Beitrag antworten »

Es gilt

$\begin{align*} P\left(cn - n^{2/3} \leq Z_n \leq cn + n^{2/3}\right) = P\left(c - n^{2/3} \leq Z_n-(n-1)c \leq c + n^{2/3}\right) \geq P\left( \left| Z_n-(n-1)c \right| < n^{2/3}-c\right) \end{align*}$

Und laut Tschebyscheff gilt für die Komplementwahrscheinlichkeit des letzten Ausdrucks

$\begin{align*} P\left( \left| Z_n-(n-1)c \right| \geq n^{2/3}-c\right) \leq \frac{\operatorname{var}(Z_n)}{\left( n^{2/3}-c\right)^2} = \frac{(n-1)c(1-2c/n)}{\left( n^{2/3}-c\right)^2} \to 0 \end{align*}$ für $\begin{align*} n\to\infty \end{align*}$ .

06.07.2015, 14:05

fernsehen

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Es gilt

$\begin{align*} P\left(cn - n^{2/3} \leq Z_n \leq cn + n^{2/3}\right) = P\left(c - n^{2/3} \leq Z_n-(n-1)c \leq c + n^{2/3}\right) \geq P\left( \left| Z_n-(n-1)c \right| < n^{2/3}-c\right) \end{align*}$

Und laut Tschebyscheff gilt für die Komplementwahrscheinlichkeit des letzten Ausdrucks

$\begin{align*} P\left( \left| Z_n-(n-1)c \right| \geq n^{2/3}-c\right) \leq \frac{\operatorname{var}(Z_n)}{\left( n^{2/3}-c\right)^2} = \frac{(n-1)c(1-2c/n)}{\left( n^{2/3}-c\right)^2} \to 0 \end{align*}$ für $\begin{align*} n\to\infty \end{align*}$ .

jau, danke!

ich halte die obige lösung aber nun irgendwie für eleganter. ich denke, dann ist hier alles geklärt und ich kann endlich weitermachen.... Wink

21.07.2015, 21:45

fernsehen

Auf diesen Beitrag antworten »

ich habe nun nochmal ein ähnliches ding...

soll ich ein neues thema aufmachen? der alte titel passt eigentlich immer noch...

es sei $\begin{eqnarray*} M = o(\sqrt{Np}), N = \binom n 2, X_n = Bin(N,p) \end{eqnarray*}$ und $\begin{eqnarray*} Y_n = Bin(N,p+\lambda M / N) \end{eqnarray*}$

ich will $\begin{eqnarray*} \lambda \end{eqnarray*}$ unabhängig von $\begin{eqnarray*} n \end{eqnarray*}$ wählen, sodass $\begin{eqnarray*} \lim P(Y_n \geq X_n + M) > 1-\epsilon \end{eqnarray*}$ gilt.

geht das überhaupt? wenn ja, reicht mir eine begründung dafür - ohne angabe von $\begin{eqnarray*} \lambda \end{eqnarray*}$

23.07.2015, 19:29

fernsehen

Auf diesen Beitrag antworten »

Zitat:

Original von fernsehen
ich habe nun nochmal ein ähnliches ding...

soll ich ein neues thema aufmachen? der alte titel passt eigentlich immer noch...

es sei $\begin{eqnarray*} M = o(\sqrt{Np}), N = \binom n 2, X_n = Bin(N,p) \end{eqnarray*}$ und $\begin{eqnarray*} Y_n = Bin(N,p+\lambda M / N) \end{eqnarray*}$

ich will $\begin{eqnarray*} \lambda \end{eqnarray*}$ unabhängig von $\begin{eqnarray*} n \end{eqnarray*}$ wählen, sodass $\begin{eqnarray*} \lim P(Y_n \geq X_n + M) > 1-\epsilon \end{eqnarray*}$ gilt.

geht das überhaupt? wenn ja, reicht mir eine begründung dafür - ohne angabe von $\begin{eqnarray*} \lambda \end{eqnarray*}$

ich habe das nun selbst widerlegt und bin mir immer noch nicht so ganz sicher, ob das alles koscher ist. hier meine argumentation:

wenn der obige satz gelten würde, so müsste das auch für die konstante funktion $\begin{eqnarray*} M = 1 \end{eqnarray*}$ und $\begin{eqnarray*} p = 1/2 \end{eqnarray*}$ gelten.
ich will das ähnlich wie HAL machen, und für beide zufallsvariablen eine normalverteilung erhalten. ich mache das, indem ich hier passend subtrahiere, dividiere, und den linken bruch erweitere:

$\begin{eqnarray*} Y_n \geq X_n + 1 \quad \Longleftrightarrow \quad \frac{Y_n - N/2 - \lambda + (\lambda - 1)}{\sqrt{N(\frac 1 2 + \frac \lambda N)(\frac 1 2 - \frac \lambda N)}} \cdot \frac{(\frac 1 2 + \frac \lambda N)(\frac 1 2 - \frac \lambda N)}{\sqrt{\left( \frac 1 2 \right) \cdot \left( \frac 1 2 \right) }} \geq \frac{X - N/2}{\sqrt{N/4}} \end{eqnarray*}$

Mit dem Satz von Moivre-Laplace sieht man dann zwei asymptotisch standardnormalverteilte zufallsvariablen: den bruch ganz rechts und den bruch links ohne $\begin{eqnarray*} (\lambda - 1) \end{eqnarray*}$ .

nun geht der $\begin{eqnarray*} (\lambda - 1) \end{eqnarray*}$ -Term nach dem dividieren gegen 0, und der mittlere Bruch geht eindeutig gegen 1, egal wie groß man $\begin{eqnarray*} \lambda \end{eqnarray*}$ gew"ahlt hat.
ich erhalte somit $\begin{eqnarray*} \lim P(Y_n \geq X_n + 1) = 1/2 \end{eqnarray*}$ .

habe ich etwas falsch gemacht?

Neue Frage »

Antworten »

Grenzverhalten von der Binomialverteilung

Verwandte Themen