Beweis

21.02.2007, 00:17

kingskid

Auf diesen Beitrag antworten »

Beweis

HI!
Wie kann man zeigen, dass folgendes gilt:

$\begin{eqnarray*} P\left( \bigcup\limits_{k=1}^n A_k \right) = \sum_{k=1}^n ~ (-1)^{k+1} \sum_{1\leq i_1< ...<i_k \leq n} ~ P(A_{i_1} \cap \ldots \cap A_{i_k}) \end{eqnarray*}$

(---> sorry, das auf der rechten seite müssen "geschnitten" zeichen sein, wie heißt der befehl für latex?)

wenn ( $\begin{eqnarray*} \Omega \end{eqnarray*}$ , a, P) ein Wahrscheinlichkeitsraum und $\begin{eqnarray*} A_1, A_2,..., A_n \in a \end{eqnarray*}$ .

Wegen der Vss mit Wahrscheinlichkeitsraum muss ja gelten für A_1... A_n paarweise disjunkt, dass $\begin{eqnarray*} P( \bigcup A_j)= \sum_{j=1}^{\infty} ~ P(A_j) \end{eqnarray*}$ .

kann man das damit zeigen oder bin ich ganz auf dem falschen weg? ist es wirklich so kompliziert wie es aussieht...?? habt ihr ein tipp für mich?

viele grüße
kingskid

edit: formel verbessert, danke!

21.02.2007, 00:19

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis
$\begin{eqnarray*} \bigcap \end{eqnarray*}$

21.02.2007, 00:39

AD

Auf diesen Beitrag antworten »

Das komplizierteste an der Geschichte ist das Aufschreiben dieses Formelmonsters, bekannt auch als Siebformel oder vornehm "Prinzip von Inklusion und Exklusion".

Den Beweis an sich führt man mit Vollständiger Induktion, im Induktionsschritt muss man nur die Übersicht über die Summen wahren, ansonsten besteht der nur im Einsetzen. Augenzwinkern

Augenzwinkern

EDIT: Ich sehe gerade einen Fehler in deinem Aufschrieb - rechts stehen nur Durschschnitte, keine Vereinigungen!!!

$\begin{eqnarray*} P\left( \bigcup\limits_{k=1}^n A_k \right) = \sum_{k=1}^n ~ (-1)^{k+1} \sum_{1\leq i_1< ...<i_k \leq n} ~ P(A_{i_1} \cap \ldots \cap A_{i_k}) \end{eqnarray*}$

22.02.2007, 22:15

kingskid

Auf diesen Beitrag antworten »

HI!
Danke für den tip, aaber wie kann man da den überblick wahren *help* ??

also bis hier her ist klar:

$\begin{eqnarray*} \left( \bigcup\limits_{k=1}^{n+1} A_k \right) = ... = \ {\sum\limits_{k = 1}^n {\left( { - 1} \right)^{k - 1} \sum\limits_{1 \leqslant i_1 < \cdots < i_k \leqslant n} {P\left( {A_{i_1 } \cap \cdots \cap A_{i_k } } \right)} } } + P\left( {A_{n + 1} } \right) - P\left( { {\bigcup\limits_{k = 1}^n \left( {A_k } \cap A_{n + 1} \right)} } \right) \end{eqnarray*}$

Jetzt müsste ich ja für den letzten summand auch noch die IV einsetzen,

also $\begin{eqnarray*} \ {\sum\limits_{k = 1}^n {\left( { - 1} \right)^{k - 1} \sum\limits_{1 \leqslant i_1 < \cdots < i_k \leqslant n} {P\left( {B_{i_1 } \cap \cdots \cap B_{i_k } } \right)} } } \end{eqnarray*}$

mit $\begin{eqnarray*} B_i = \left( { {\bigcup\limits_{k = 1}^n \left( {A_k } \cap A_{n + 1} \right)} } \right) \end{eqnarray*}$

aber wie kann man das vereinfachen... ?? *confused*

viele grüße
kingskid

23.02.2007, 07:21

AD

Auf diesen Beitrag antworten »

Zitat:

Original von kingskid
mit $\begin{eqnarray*} B_i = \left( { {\bigcup\limits_{k = 1}^n \left( {A_k } \cap A_{n + 1} \right)} } \right) \end{eqnarray*}$

Wie kommst du denn auf dieses $\begin{eqnarray*} B_i \end{eqnarray*}$ ?

Nein, einfach $\begin{eqnarray*} B_i = A_i \cap A_{n+1} \end{eqnarray*}$ , damit stimmt dann soweit alles was du aufgeschrieben hast.

23.02.2007, 08:21

Leopold

Auf diesen Beitrag antworten »

Anzeige

23.02.2007, 13:48

kingskid

Auf diesen Beitrag antworten »

danke für die korrektur und den link!

ich versteh die zweite summe auf der rechten seite noch nicht ganz. über was wird summiert, d.h. von wo bis so läuft dieses i ??

wir haben in der VL als Bsp für n=3 aufgeschrieben:

$\begin{eqnarray*} P(A \cup B \cup C) = P(A \cap B) - P (A \cap C) - P( B \cap C) + P( A \cap B \cap C) \end{eqnarray*}$
anschaulich hat man ja die im schnitt von allen drei mengen zu viel abgezogen und muss sie wieder dazuaddieren. aber warum nur einmal?

wie ist das aber mit den indizes wenn man $\begin{eqnarray*} A_1, A_2, A_3 \end{eqnarray*}$ nimmt ? warum bekommt man für k =3 nur einen summanden und nicht $\begin{eqnarray*} P(A_1 \cap A_2 \cap A_3) + P(A_1 \cap A_2 \cap A_3) + P(A_1 \cap A_2 \cap A_3) \end{eqnarray*}$ ??

weil bei k=1 und k=2 erhält man ja auch eine summe ??

viele grüße

23.02.2007, 13:50

AD

Auf diesen Beitrag antworten »

Zitat:

Original von kingskid
wir haben in der VL als Bsp für n=3 aufgeschrieben:

$\begin{eqnarray*} P(A \cup B \cup C) = P(A \cap B) - P (A \cap C) - P( B \cap C) + P( A \cap B \cap C) \end{eqnarray*}$

Ganz gewiss nicht so! Sondern:

$\begin{eqnarray*} P(A \cup B \cup C) = P(A)+P(B)+P(C)-P(A \cap B) - P (A \cap C) - P( B \cap C) + P( A \cap B \cap C) \end{eqnarray*}$

23.02.2007, 14:05

kingskid

Auf diesen Beitrag antworten »

ja sorry, hab den anfang vergessen einzutippen...

aber wie ist das nun mit diesen i_k ??

23.02.2007, 14:10

AD

Auf diesen Beitrag antworten »

Weil $\begin{eqnarray*} \binom{3}{3}=1 \end{eqnarray*}$ ist und nicht $\begin{eqnarray*} \binom{3}{3}=3 \end{eqnarray*}$ . Oder einfacher gesagt: Jeder Durchschnitt geht genau einmal in die Formel ein, warum sollte der Durchschnitt $\begin{eqnarray*} A_1 \cap A_2 \cap A_3 \end{eqnarray*}$ dreimal auftauchen??? unglücklich

unglücklich

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

Die Siebformel ist doch sehr logisch aufgebaut: Rechts erscheinen die Wahrscheinlichkeiten sämtlicher $\begin{eqnarray*} 2^n-1 \end{eqnarray*}$ Durchschnitte der beteiligten $\begin{eqnarray*} n \end{eqnarray*}$ Mengen:

die Wkten der $\begin{eqnarray*} \binom{n}{1} \end{eqnarray*}$ Mengen an sich mit positivem Vorzeichen
die Wkten der $\begin{eqnarray*} \binom{n}{2} \end{eqnarray*}$ Durchschnitte von jeweils zwei Mengen mit negativem Vorzeichen
die Wkten der $\begin{eqnarray*} \binom{n}{3} \end{eqnarray*}$ Durchschnitte von jeweils drei Mengen mit positivem Vorzeichen
die Wkten der $\begin{eqnarray*} \binom{n}{4} \end{eqnarray*}$ Durchschnitte von jeweils vier Mengen mit negativem Vorzeichen
die Wkten der $\begin{eqnarray*} \binom{n}{5} \end{eqnarray*}$ Durchschnitte von jeweils fünf Mengen mit positivem Vorzeichen
...
die Wkten der $\begin{eqnarray*} \binom{n}{n-1} \end{eqnarray*}$ Durchschnitte von jeweils (n-1) Mengen mit Vorzeichen $\begin{eqnarray*} (-1)^n \end{eqnarray*}$
die Wkt des Durchschnittes aller n Mengen mit Vorzeichen $\begin{eqnarray*} (-1)^{n+1} \end{eqnarray*}$

23.02.2007, 14:54

kingskid

Auf diesen Beitrag antworten »

ahso... I see... smile

smile

vielen dank für die erklärung!!
weils so schön ist noch ein bsp.:
$\begin{eqnarray*} P\left( \bigcup\limits_{k=1}^4 A_k \right) \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{k=1}^4~ P(A_k) - P( A_1 \cap A_2) - .... - P(A_3 \cap A_4) + P(A_1 \cap A_2 \cap A_3) + .... + P( A_2 \cap A_3 \cap A_4)- P(A_1 \cap A_2 \cap A_3 \cap A_4) \end{eqnarray*}$

wenn das stimmt, hab ichs verstanden Augenzwinkern

Augenzwinkern

jetzt bin ich immernoch am induktionsschritt:

$\begin{eqnarray*} ...= P\left( {A_{n + 1} } \right)+ \ {\sum\limits_{k = 1}^n {\left( { - 1} \right)^{k + 1} \sum\limits_{1 \leqslant i_1 < \cdots < i_k \leqslant n} {P\left( {A_{i_1 } \cap \cdots \cap A_{i_k } } \right)} } } + \ {\sum\limits_{k = 1}^n {\left( { - 1} \right)^{k + 2} \sum\limits_{1 \leqslant i_1 < \cdots < i_k \leqslant n} {P\left( {B_{i_1 } \cap \cdots \cap B_{i_k } } \right)} } } \end{eqnarray*}$

hab jetzt auch mal dieses (-1) in die summe mit reingezogen wie es unter der beweisführung von leopolds link gemacht wurde, aber dann wird das dort ja nur mit worten weiterbeschrieben...

d.h. in der ersten Summe sind alle Beiträge ohne $\begin{eqnarray*} A_{n+1} \end{eqnarray*}$ , in der zweiten Summe alle mit $\begin{eqnarray*} A_{n+1} \end{eqnarray*}$ außer dem wo nur $\begin{eqnarray*} A_{n+1} \end{eqnarray*}$ beteiligt ist, aber der steht ganz am anfang...
kann man die terme nicht irgendwie umformen dass man direkt zu n+1 kommt ??

23.02.2007, 16:26

AD

Auf diesen Beitrag antworten »

Als nächstes gilt wegen $\begin{eqnarray*} B_i = A_i \cap A_{n+1} \end{eqnarray*}$ folgende Darstellung

$\begin{eqnarray*} B_{i_1 } \cap \cdots \cap B_{i_k } = A_{i_1 } \cap \cdots \cap A_{i_k } \cap A_{n+1} \end{eqnarray*}$ ,

und zwar für alle erdenklichen $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ sowie Index-Auswahlen $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_k\leq n \end{eqnarray*}$ . Das musst du einsetzen!

Der Rest ist dann "nur" noch zu erkennen, dass man die Summen so geeignet zusammenfassen kann, dass am Ende tatsächlich der Term aus der Induktionsbehauptung da steht.

23.02.2007, 18:16

kingskid

Auf diesen Beitrag antworten »

hm, ich frag mich nur

$\begin{eqnarray*} ...= P\left( {A_{n + 1} } \right)+ \ {\sum\limits_{k = 1}^n {\left( { - 1} \right)^{k + 1} \sum\limits_{1 \leqslant i_1 < \cdots < i_k \leqslant n} {P\left( {A_{i_1 } \cap \cdots \cap A_{i_k } } \right)} } } + \ {\sum\limits_{k = 1}^n {\left( { - 1} \right)^{k + 2} \sum\limits_{1 \leqslant i_1 < \cdots < i_k \leqslant n} {P( A_{i_1 } \cap \cdots \cap A_{i_k } \cap A_{n+1} }}) } \end{eqnarray*}$

also du meinst hier kann man die induktionsbeh. erkennen (mit den argumenten von dem andren beweis ?) und nichts mehr umformen bzw zusammenfassen?

23.02.2007, 18:19

AD

Auf diesen Beitrag antworten »

Dazu ist in der zweiten Summe eine Indexverschiebung ganz passend, d.h., du betrachtest dort statt $\begin{eqnarray*} k=1,\ldots,n \end{eqnarray*}$ besser $\begin{eqnarray*} k=2,\ldots,n+1 \end{eqnarray*}$ und dafür dann den Term

$\begin{eqnarray*} B_{i_1} \cap \cdots \cap B_{i_{k-1}} = A_{i_1 } \cap \cdots \cap A_{i_{k-1}} \cap A_{n+1} \stackrel{!}{=} A_{i_1 } \cap \cdots \cap A_{i_{k-1}} \cap A_{i_k} \end{eqnarray*}$

für alle $\begin{eqnarray*} k \end{eqnarray*}$ -Tupel $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_{k-1} < i_k = n+1 \end{eqnarray*}$ .

Der Vergleich mit der ersten Summe zeigt, dass dort bereits dieselben Terme, nur eben mit $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_{k-1} < i_k < n+1 \end{eqnarray*}$ erfasst wurden.

Zusammengefasst hat man dann eben alle diese Terme mit nunmehr $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_{k-1} < i_k \leq n+1 \end{eqnarray*}$ .

Wie ich schon sagte: Nur sorgfältig betrachten, über was man das so summiert!

Übrigens steht das so ähnlich in Leopolds Zusammenfassung, hast dir wohl nicht das Dokument im verlinkten Beitrag angesehen?

24.02.2007, 00:05

kingskid

Auf diesen Beitrag antworten »

danke für deine hilfe!

aber in der ersten summe, warum $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_{k-1} < i_k < n+1 \end{eqnarray*}$ ? bei mir geht das nur bis n ??

$\begin{eqnarray*} ...= P\left( {A_{n + 1} } \right)+ \ {\sum\limits_{k = 1}^n {\left( { - 1} \right)^{k + 1} \sum\limits_{1 \leqslant i_1 < \cdots < i_k \leqslant n} {P\left( {A_{i_1 } \cap \cdots \cap A_{i_k } } \right)} } } + \ {\sum\limits_{k = 2}^{n+1} {\left( { - 1} \right)^{k + 1} \sum\limits_{1 \leqslant i_1 < \cdots < i_k \leqslant n+1} {P( A_{i_1 } \cap \cdots \cap A_{i_{k-1} } \cap A_{i_k} }}) } \end{eqnarray*}$

klar hab ich das dokument gelesen, sonst hätte ich ja oben nicht schon davon geschrieben...

24.02.2007, 11:01

AD

Auf diesen Beitrag antworten »

Zitat:

Original von kingskid
aber in der ersten summe, warum $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_{k-1} < i_k < n+1 \end{eqnarray*}$ ? bei mir geht das nur bis n ??

Kennst du den Unterschied zwischen $\begin{eqnarray*} i_k<n+1 \end{eqnarray*}$ und $\begin{eqnarray*} i_k \leq n+1 \end{eqnarray*}$ ? Welche der beiden Varianten habe ich geschrieben? LOL Hammer

LOL Hammer

26.02.2007, 22:11

kingskid

Auf diesen Beitrag antworten »

oops, so viel zum genauen hinsehen Hammer

Hammer

hm, aber was hilft jetzt die indexverschiebung?

kann ich dieses einzelne $\begin{eqnarray*} P(A_{n+1}) \end{eqnarray*}$ in die letzte summe mitreinbringen?

27.02.2007, 08:01

AD

Auf diesen Beitrag antworten »

Ja klar: Das ist der Fall $\begin{eqnarray*} k=1 \end{eqnarray*}$ und $\begin{eqnarray*} j_1=n+1 \end{eqnarray*}$ . Der wird zunächst von der zweiten Summe ja nicht erfasst, da die nach der Indexverschiebung erst mit $\begin{eqnarray*} k=2 \end{eqnarray*}$ anfängt. Somit ist $\begin{eqnarray*} k=1,j_1=n+1 \end{eqnarray*}$ gerade der fehlende Baustein, der zur Integration von $\begin{eqnarray*} P(A_{n+1}) \end{eqnarray*}$ in die Summe noch gefehlt hat. smile

smile

27.02.2007, 19:22

kingskid

Auf diesen Beitrag antworten »

okay, sehr cool. dann haben wir jetzt noch die 2 summen übrig, hmm... warum haben wir da jetzt nicht ein paar wahrscheinlichkeiten doppelt?

27.02.2007, 19:47

AD

Auf diesen Beitrag antworten »

Nein, wieso? Ich wiederhole nochmal:

Zitat:

Original von Arthur Dent
$\begin{eqnarray*} B_{i_1} \cap \cdots \cap B_{i_{k-1}} = A_{i_1 } \cap \cdots \cap A_{i_{k-1}} \cap A_{n+1} \stackrel{!}{=} A_{i_1 } \cap \cdots \cap A_{i_{k-1}} \cap A_{i_k} \end{eqnarray*}$

für alle $\begin{eqnarray*} k \end{eqnarray*}$ -Tupel $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_{k-1} < i_k = n+1 \end{eqnarray*}$ .

Der Vergleich mit der ersten Summe zeigt, dass dort bereits dieselben Terme, nur eben mit $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_{k-1} < i_k < n+1 \end{eqnarray*}$ erfasst wurden.

Zusammengefasst hat man dann eben alle diese Terme mit nunmehr $\begin{eqnarray*} 1\leq i_1<i_2< \ldots < i_{k-1} < i_k \leq n+1 \end{eqnarray*}$ .

27.02.2007, 23:06

kingskid

Auf diesen Beitrag antworten »

ja genau daran hängts, wenn in der ersten summe "bereits dieselben terme" (wenn auch nur bis < n+1) erfasst wurden, dann hab ich daraus geschlossen, dass sie bis auf die mit n+1 doppelt sind...

*grübel*aber in der zweiten summe sind soweiso nur die terme mit n+1, keine sonst, richtig? das war wohl mein denkfehler... ah so langsam dämmerts, ich hab das "=" nicht richtig beachtet.
d.h. man schiebt das "< n+1" und "= n+1" zu $\begin{eqnarray*} \leq n+1 \end{eqnarray*}$ zusammen...
und die summe mit dem Vorzeichenfaktor muss man dann halt auch noch um 1 erhöhen... und dann steht die beh. da...
kommt das so hin?

nur was meinst du mit denselben termen??

27.02.2007, 23:15

AD

Auf diesen Beitrag antworten »

Die $\begin{eqnarray*} i_1, i_2, \end{eqnarray*}$ kannst du doch nicht einzeln betrachten!!! geschockt

geschockt

geschockt

geschockt

Sondern immer nur als Tupel $\begin{eqnarray*} (i_1,i_2,\ldots,i_k) \end{eqnarray*}$ , und zwei Tupel sind genau dann verschieden, wenn sie sich in mindestens einer Komponente unterscheiden.

Sag mal, hast du das die ganze Zeit missverstanden? Worüber hast du denn gedacht, wird hier summiert?

27.02.2007, 23:54

kingskid

Auf diesen Beitrag antworten »

ahhrghs, das war mir nicht klar, jetzt macht das plötzlich sinn smile

smile

smile

*ouh*

jajaa, ich ich hab halt gedacht da wird irgendwie über die i's summiert, hatte mit solchen tupel-summen noch nichts so zu tun... gut das ich das jetzt auch mitbekommen hab...

... dann kann ich heut nacht ja beruhigt schlafen Augenzwinkern

Augenzwinkern

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »