www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Stochastik" - beweis Inklusion/Exklusion
beweis Inklusion/Exklusion < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Stochastik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

beweis Inklusion/Exklusion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:17 Sa 29.10.2016
Autor: lisa2802

Aufgabe
Sei [mm] n\in \IN [/mm] und seien [mm] A_1,...A_n [/mm] Ereignisse in einem Ereignisraum [mm] \Omega [/mm] und P ein Wahrscheinlichkeitsmaß auf [mm] \Omega. [/mm] Setze [mm] I:=\{1,...,n\} [/mm] und zeige, dass

[mm] P(\bigcup_{i \in I}A_i) =\summe_{i\in I}P(A_i)-\summe_{i_1,i_2 \in I, i_1 < i_2} P(A_i_1 \cap A_i_2)+... [/mm]

[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) [/mm]

Hinweis :
Tipp verwende vollständige Induktion.


Hallöchen ihr Lieben.

IA)
n=2 ist klar nach Vorlesung.(n=3 haben wir da auch schon in der Vorlesung benutzt und uns das definiert)
[mm] P(A_1 \cup A_2) [/mm] = [mm] P(A_1)+P(A_2)-P(A_1\cap A_2) [/mm]
IV) Die Beh. gelte für ein n [mm] \in \IN. [/mm]
IS)
n -> n+1
[mm] P(\bigcup_{i=1}^{n+1}A_i)=P(A_1\cup ...\cup A_n\cup A_{n+1})=P((A_1\cup ...\cup A_n)\cup A_{n+1}) [/mm]
[mm] =P(\bigcup_{i=1}^{n}A_i)+P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1}) [/mm]
[mm] =\underbrace{\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j)}_{IV} +P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1}) [/mm]

so und an der Stelle hänge ich jetzt aufgrund meiner Summengrenzen. Würde das jetzt regulär umschreiben und dann müsste ich auf das richtige kommen. Könnt ihr mir da bitte einmal helfen und die Summengrenzen bearbeiten??

"J [mm] \subseteq [/mm] I , J [mm] \not= \emptyset" [/mm] heißt ja eigentlich nur J ist eine Teilmenge von [mm] I=\{1,...,n\} [/mm] und ist nicht leer. Kann man das auch umschreiben in j=1 bis n als Summengrenzen?? und statt  [mm] (-1)^{|J|-1} [/mm] dann  [mm] (-1)^{j+1}? [/mm] und dann dementsprechend auch bei [mm] P(\bigcap_{j \in J}A_j) [/mm] = [mm] P(\bigcap_{j=1}^{n}A_j)?? [/mm]

Danke :)



        
Bezug
beweis Inklusion/Exklusion: Antwort
Status: (Antwort) fertig Status 
Datum: 20:03 Sa 29.10.2016
Autor: tobit09

Hallo lisa2802!


> IA)
>  n=2 ist klar nach Vorlesung.(n=3 haben wir da auch schon
> in der Vorlesung benutzt und uns das definiert)
>  [mm]P(A_1 \cup A_2)[/mm] = [mm]P(A_1)+P(A_2)-P(A_1\cap A_2)[/mm]

Und für n=1 (oder $n=0$, falls $0$ bei euch eine natürliche Zahl ist) prüft man die Formel auch direkt nach.


>  IV) Die
> Beh. gelte für ein n [mm]\in \IN.[/mm]
>  IS)
>  n -> n+1

>  [mm]P(\bigcup_{i=1}^{n+1}A_i)=P(A_1\cup ...\cup A_n\cup A_{n+1})=P((A_1\cup ...\cup A_n)\cup A_{n+1})[/mm]
>  
> [mm]=P(\bigcup_{i=1}^{n}A_i)+P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1})[/mm]
>  
> [mm]=\underbrace{\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j)}_{IV} +P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1})[/mm]

Soweit korrekt! [ok]


Beachte, dass $I$ hier für die Menge [mm] $\{1,\ldots,n\}$ [/mm] steht.

Unser "Zielausdruck" ist hingegen

      [mm] $\summe_{J \subseteq \{1,\ldots,n+1\} , J \not= \emptyset} (-1)^{|J|-1}\cdot{}P(\bigcap_{j \in J}A_j) [/mm] $

(Beachte das [mm] $\{1,\ldots,n+1\}$ [/mm] anstelle von I.)


Es gilt [mm] $(\bigcup_{i=1}^nA_i)\cap A_{n+1}=\bigcup_{i=1}^n(A_i\cap A_{n+1})$. [/mm] Somit kannst du auf deinen hinteren Term [mm] $P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1})$ [/mm] ebenfalls die Induktionsvoraussetzung anwenden.


Die nichtleeren Teilmengen [mm] $J\subseteq\{1,\ldots,n+1\}$ [/mm] sind genau die nichtleeren Teilmengen von [mm] $\{1,\ldots,n\}$ [/mm] sowie die Mengen der Form [mm] $J'\cup\{n+1\}$ [/mm] für [mm] $J'\subseteq\{1,\ldots,n\}$. [/mm]


> "J [mm]\subseteq[/mm] I , J [mm]\not= \emptyset"[/mm] heißt ja eigentlich
> nur J ist eine Teilmenge von [mm]I=\{1,...,n\}[/mm] und ist nicht
> leer. Kann man das auch umschreiben in j=1 bis n als
> Summengrenzen?? und statt  [mm](-1)^{|J|-1}[/mm] dann  [mm](-1)^{j+1}?[/mm]

Ja, man kann die Formel in dieser Art umschreiben. Aber da sehe ich keinen Vorteil drin.

> und dann dementsprechend auch bei [mm]P(\bigcap_{j \in J}A_j)[/mm] =
> [mm]P(\bigcap_{j=1}^{n}A_j)??[/mm]

Das gilt im Allgemeinen nur im Falle [mm] $J=\{1,\ldots,n\}$. [/mm]


Viele Grüße
Tobias

Bezug
                
Bezug
beweis Inklusion/Exklusion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:53 Sa 29.10.2016
Autor: lisa2802


>  >  IS)
>  >  n -> n+1

>  >  [mm]P(\bigcup_{i=1}^{n+1}A_i)=P(A_1\cup ...\cup A_n\cup A_{n+1})=P((A_1\cup ...\cup A_n)\cup A_{n+1})[/mm]
>  
> >  

> >
> [mm]=P(\bigcup_{i=1}^{n}A_i)+P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1})[/mm]
>  
> >  

> > [mm]=\underbrace{\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j)}_{IV} +P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1})[/mm]
>  
> Soweit korrekt! [ok]

Danke!

>  
>
> Beachte, dass [mm]I[/mm] hier für die Menge [mm]\{1,\ldots,n\}[/mm] steht.
>  
> Unser "Zielausdruck" ist hingegen
>  
> [mm]\summe_{J \subseteq \{1,\ldots,n+1\} , J \not= \emptyset} (-1)^{|J|-1}\cdot{}P(\bigcap_{j \in J}A_j)[/mm]
>  
> (Beachte das [mm]\{1,\ldots,n+1\}[/mm] anstelle von I.)
>  
>
> Es gilt [mm](\bigcup_{i=1}^nA_i)\cap A_{n+1}=\bigcup_{i=1}^n(A_i\cap A_{n+1})[/mm].
> Somit kannst du auf deinen hinteren Term
> [mm]P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1})[/mm] ebenfalls die
> Induktionsvoraussetzung anwenden.

Ich versuche es mal :)
[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1}) [/mm]


[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-P(\bigcup_{i=1}^n(A_i\cap A_{n+1})) [/mm]


[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1})) [/mm]


[mm] =\summe_{J \subseteq \{1,..,n+1\} , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) -\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1})) [/mm]

im vorletzten Schritt IV. Im letzten schritt [mm] P(A_{n+1}) [/mm] mit in den ersten Summanden gezogen und dann ist J [mm] \subseteq\{1,...,n,n+1\}. [/mm] Und jetzt hänge ich wieder. Könntest du mir da vielleicht nochmal unter die arme greifen? Mein größtes Problem sind dabei wirklich die Summengrenzen.. :(

>  
>
> Die nichtleeren Teilmengen [mm]J\subseteq\{1,\ldots,n+1\}[/mm] sind
> genau die nichtleeren Teilmengen von [mm]\{1,\ldots,n\}[/mm] sowie
> die Mengen der Form [mm]J'\cup\{n+1\}[/mm] für
> [mm]J'\subseteq\{1,\ldots,n\}[/mm].
>  
>
> > "J [mm]\subseteq[/mm] I , J [mm]\not= \emptyset"[/mm] heißt ja eigentlich
> > nur J ist eine Teilmenge von [mm]I=\{1,...,n\}[/mm] und ist nicht
> > leer. Kann man das auch umschreiben in j=1 bis n als
> > Summengrenzen?? und statt  [mm](-1)^{|J|-1}[/mm] dann  [mm](-1)^{j+1}?[/mm]
>  Ja, man kann die Formel in dieser Art umschreiben. Aber da
> sehe ich keinen Vorteil drin.
>  
> > und dann dementsprechend auch bei [mm]P(\bigcap_{j \in J}A_j)[/mm] =
> > [mm]P(\bigcap_{j=1}^{n}A_j)??[/mm]
>  Das gilt im Allgemeinen nur im Falle [mm]J=\{1,\ldots,n\}[/mm].
>  
>
> Viele Grüße
>  Tobias

Danke und schönen Abend noch
Lisa

Bezug
                        
Bezug
beweis Inklusion/Exklusion: Antwort
Status: (Antwort) fertig Status 
Datum: 21:25 Sa 29.10.2016
Autor: tobit09


>  [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1})[/mm]
>  
>
> [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-P(\bigcup_{i=1}^n(A_i\cap A_{n+1}))[/mm]
>  
>
> [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))[/mm]

Bis hierhin sehr schön! [ok]


> [mm]=\summe_{J \subseteq \{1,..,n+1\} , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) -\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))[/mm]
>  
> im vorletzten Schritt IV. Im letzten schritt [mm]P(A_{n+1})[/mm] mit
> in den ersten Summanden gezogen und dann ist J
> [mm]\subseteq\{1,...,n,n+1\}.[/mm]

Im Allgemeinen hat nicht jedes [mm] $J\subseteq\{1,\ldots,n+1\}$ [/mm] die Gestalt [mm] $J\subseteq\{1,\ldots,n\}$ [/mm] oder [mm] $J=\{n+1\}$. [/mm]
Somit hast du in der unteren Zeile im Allgemeinen mehr Summanden als in der oberen. Daher stimmt diese letzte Gleichheit im Allgemeinen nicht.


Aber die Idee, [mm] $P(A_{n+1})$ [/mm] künstlich als Summanden zu schreiben, ist gut!

Es gilt [mm] $P(A_{n+1})=P(\bigcap_{j\in J}A_j)=(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)$ [/mm] mit [mm] $J=\{n+1\}$ [/mm] und somit als Summe mit nur einem Summanden notiert:

       [mm] $P(A_{n+1})=\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)$. [/mm]


Schauen wir uns nun den letzten Summanden deines großen Terms an:

     [mm] $\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))$ [/mm]

[mm] $=\summe_{J\subseteq I, J\not=\emptyset}(-1)^{|J|-1}*P(\bigcap_{j\in J\cup\{n+1\}}A_j)$ [/mm]

[mm] $=\summe_{K\subseteq\{1,\ldots,n+1\}, n+1\in K,K\setminus\{n+1\}\not=\emptyset}(-1)^{|K|-2}P(\bigcap_{j\in K}A_j)$ [/mm]

[mm] $=(-1)*\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)$. [/mm]


Nun kannst du alles zusammensetzen!
(Beachte, auf welchen Term wir kommen möchten.)

Bezug
                                
Bezug
beweis Inklusion/Exklusion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:28 So 30.10.2016
Autor: lisa2802


> >  [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-P((\bigcup_{i=1}^{n}A_i))\cap A_{n+1})[/mm]

>  
> >  

> >
> > [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-P(\bigcup_{i=1}^n(A_i\cap A_{n+1}))[/mm]
>  
> >  

> >
> > [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))[/mm]
>  
> Bis hierhin sehr schön! [ok]
>  
>
> > [mm]=\summe_{J \subseteq \{1,..,n+1\} , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) -\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))[/mm]
>  
> >  

> > im vorletzten Schritt IV. Im letzten schritt [mm]P(A_{n+1})[/mm] mit
> > in den ersten Summanden gezogen und dann ist J
> > [mm]\subseteq\{1,...,n,n+1\}.[/mm]
>  Im Allgemeinen hat nicht jedes [mm]J\subseteq\{1,\ldots,n+1\}[/mm]
> die Gestalt [mm]J\subseteq\{1,\ldots,n\}[/mm] oder [mm]J=\{n+1\}[/mm].
>  Somit hast du in der unteren Zeile im Allgemeinen mehr
> Summanden als in der oberen. Daher stimmt diese letzte
> Gleichheit im Allgemeinen nicht.
>  
>
> Aber die Idee, [mm]P(A_{n+1})[/mm] künstlich als Summanden zu
> schreiben, ist gut!
>  
> Es gilt [mm]P(A_{n+1})=P(\bigcap_{j\in J}A_j)=(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)[/mm]
> mit [mm]J=\{n+1\}[/mm] und somit als Summe mit nur einem Summanden
> notiert:
>  
> [mm]P(A_{n+1})=\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)[/mm].
>  
>
> Schauen wir uns nun den letzten Summanden deines großen
> Terms an:
>  
> [mm]\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))[/mm]
>  
> [mm]=\summe_{J\subseteq I, J\not=\emptyset}(-1)^{|J|-1}*P(\bigcap_{j\in J\cup\{n+1\}}A_j)[/mm]
>  
> [mm]=\summe_{K\subseteq\{1,\ldots,n+1\}, n+1\in K,K\setminus\{n+1\}\not=\emptyset}(-1)^{|K|-2}P(\bigcap_{j\in K}A_j)[/mm]

[mm] K\subseteq\{1,\ldots,n+1\} [/mm] = [mm] K\subseteq J\cup\{n+1\} [/mm]
und da ich jetzt über eine Teilmenge summiere die ein Element mehr enthalten kann als vorher habe ich jetzt [mm] (-1)^{|K|-2} [/mm] oder?

>  
> [mm]=(-1)*\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)[/mm].

und mit [mm] (-1)^{|K|-2} [/mm] = [mm] (-1)^{|K|-1-1}=(-1)^{|K|-1}*(-1)^{-1} [/mm] = [mm] (-1)*(-1)^{|K|-1} [/mm] folgt dein letzter Schritt.Oder??

>
> Nun kannst du alles zusammensetzen!
>  (Beachte, auf welchen Term wir kommen möchten.)

okay. Ich versuche es weiter. Du hast natürlich vollkommen recht damit, dass ich [mm] P(A_{n+1} [/mm] nicht einfach so mit herein ziehen kann. War mir wohl gestern einfach schon zu spät...

[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1})) [/mm]

[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)-\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1})) [/mm]

[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)-\summe_{J\subseteq I, J\not=\emptyset}(-1)^{|J|-1}*P(\bigcap_{j\in J\cup\{n+1\}}A_j) [/mm]


[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)-(\summe_{K\subseteq\{1,\ldots,n+1\}, n+1\in K,K\setminus\{n+1\}\not=\emptyset}(-1)^{|K|-2}P(\bigcap_{j\in K}A_j)) [/mm]

[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)-((-1)*\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)) [/mm]


[mm] =\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)+\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)) [/mm]

[mm] =\summe_{J \subseteq \{1,...,n\} , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)+\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)) [/mm]



ist nun : [mm] \summe_{J \subseteq \{1,...,n\} , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j) [/mm] = [mm] \summe_{J\subseteq\{1,\ldots,n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)) [/mm] ?


Ziel = [mm] \summe_{J \subseteq \{1,\ldots,n+1\} , J \not= \emptyset} (-1)^{|J|-1}\cdot{}P(\bigcap_{j \in J}A_j) [/mm]




Danke!

Bezug
                                        
Bezug
beweis Inklusion/Exklusion: Antwort
Status: (Antwort) fertig Status 
Datum: 05:26 Mo 31.10.2016
Autor: tobit09


> > Schauen wir uns nun den letzten Summanden deines großen
> > Terms an:
>  >  
> > [mm]\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))[/mm]

Hier habe ich nicht richtig aufgepasst: Es muss hinten [mm] $A_j\cap A_{n+1}$ [/mm] statt [mm] $A_i\cap A_{n+1}$ [/mm] heißen.



> > [mm]=\summe_{J\subseteq I, J\not=\emptyset}(-1)^{|J|-1}*P(\bigcap_{j\in J\cup\{n+1\}}A_j)[/mm]
>  
> >  

> > [mm]=\summe_{K\subseteq\{1,\ldots,n+1\}, n+1\in K,K\setminus\{n+1\}\not=\emptyset}(-1)^{|K|-2}P(\bigcap_{j\in K}A_j)[/mm]
>  
> [mm]K\subseteq\{1,\ldots,n+1\}[/mm] = [mm]K\subseteq J\cup\{n+1\}[/mm]
>  und
> da ich jetzt über eine Teilmenge summiere die ein Element
> mehr enthalten kann als vorher habe ich jetzt [mm](-1)^{|K|-2}[/mm]
> oder?

Gegeben eine nichtleere Teilmenge [mm] $J\subseteq [/mm] I$ sei [mm] $K_J:=J\cup\{n+1\}$. [/mm] Dann ist

      [mm] $(-1)^{|K_J|-2}=(-1)^{|J\cup\{n+1\}|-2}=(-1)^{(|J|+1)-2}=(-1)^{|J|-1}$. [/mm]

Daher gilt

     [mm] $\summe_{J\subseteq I, J\not=\emptyset}(-1)^{|J|-1}*P(\bigcap_{j\in J\cup\{n+1\}}A_j)\quad=\;\summe_{J\subseteq I, J\not=\emptyset}(-1)^{|K_J|-2}*P(\bigcap_{j\in K_J}A_j)$. [/mm]


Wenn J alle nichtleeren Teilmengen [mm] $J\subseteq [/mm] I$ je einmal "durchläuft", dann "durchläuft" [mm] $K_J$ [/mm] gerade alle Teilmengen [mm] $K\subseteq\{1,\ldots,n+1\}$ [/mm] mit [mm] $n+1\in [/mm] K$ und [mm] $K\setminus\{n+1\}\not=\emptyset$ [/mm] genau einmal.

Damit meine ich präzise formuliert Folgendes: Die Abbildung

      [mm] $\{J\subseteq I\;|\;J\not=\emptyset\}\to\{K\subseteq\{1,\ldots,n+1\}\;|\;n+1\in K,K\setminus\{n+1\}\not=\emptyset\},\quad J\mapsto K_J=J\cup\{n+1\}$ [/mm]

ist wohldefiniert und bijektiv.


Daher gilt:

       [mm] $\summe_{J\subseteq I, J\not=\emptyset}(-1)^{|K_J|-2}*P(\bigcap_{j\in K_J}A_j)\quad=\;\summe_{K\subseteq \{1,\ldots,n+1\}, n+1\in K,K\setminus\{n+1\}\not=\emptyset}(-1)^{|K|-2}*P(\bigcap_{j\in K}A_j)$. [/mm]

      

> > [mm]=(-1)*\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)[/mm].
>  
> und mit [mm](-1)^{|K|-2}[/mm] =
> [mm](-1)^{|K|-1-1}=(-1)^{|K|-1}*(-1)^{-1}[/mm] = [mm](-1)*(-1)^{|K|-1}[/mm]
> folgt dein letzter Schritt.Oder??

Genau. [ok]



> [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +P(A_{n+1})-\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))[/mm]

Auch hier muss es am Ende [mm] $A_j\cap A_{n+1}$ [/mm] statt [mm] $A_i\cap A_{n+1}$ [/mm] heißen.


> [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)-\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}(A_i\cap A_{n+1}))[/mm]
>  
> [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)-\summe_{J\subseteq I, J\not=\emptyset}(-1)^{|J|-1}*P(\bigcap_{j\in J\cup\{n+1\}}A_j)[/mm]
>  
>
> [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)-(\summe_{K\subseteq\{1,\ldots,n+1\}, n+1\in K,K\setminus\{n+1\}\not=\emptyset}(-1)^{|K|-2}P(\bigcap_{j\in K}A_j))[/mm]
>  
> [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)-((-1)*\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j))[/mm]
>  
>
> [mm]=\summe_{J \subseteq I , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)+\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j))[/mm]
>  
> [mm]=\summe_{J \subseteq \{1,...,n\} , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)+\summe_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j))[/mm]

Respekt für deine Fleißarbeit! [ok]
Wenn ich nichts übersehen habe, ist alles korrekt! [ok]



> ist nun : [mm]\summe_{J \subseteq \{1,...,n\} , J \not= \emptyset} (-1)^{|J|-1}*P(\bigcap_{j \in J}A_j) +\sum_{J=\{n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)[/mm]
> =
> [mm]\summe_{J\subseteq\{1,\ldots,n+1\}}(-1)^{|J|-1}P(\bigcap_{j\in J}A_j))[/mm]
> ?

Nein, unten hast du im Allgemeinen mehr Summanden als oben.



> Ziel = [mm]\summe_{J \subseteq \{1,\ldots,n+1\} , J \not= \emptyset} (-1)^{|J|-1}\cdot{}P(\bigcap_{j \in J}A_j)[/mm]

Genau.



Um etwas Schreibaufwand zu sparen, schreibe ich ab jetzt abkürzend

        [mm] $a_J:=(-1)^{|J|-1}P(\bigcap_{j\in J}A_j)$ [/mm]

für nichtleere Teilmengen [mm] $J\subseteq\{1,\ldots,n+1\}$. [/mm]
(Auf die Idee hätte ich früher kommen sollen...)

Wir wollen zeigen:

       [mm] $\summe_{J\subseteq I,J\not=\emptyset}a_J+\summe_{J=\{n+1\}}a_J+\summe_{J\subseteq\{n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}a_J\quad=\;\sum_{J\subseteq\{1,\ldots,n+1\},J\not=\emptyset}a_J$. [/mm]

Tatsächlich stehen links und rechts die gleichen Summanden.
Im Einzelnen gilt:

     [mm] $\summe_{J\subseteq I,J\not=\emptyset}a_J+\summe_{J=\{n+1\}}a_J+\summe_{J\subseteq\{n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}a_J$ [/mm]

   [mm] $=\sum_{J\subseteq \{1,\ldots,n+1\},J\not=\emptyset,n+1\notin J}a_J+\left(\sum_{J\subseteq\{1,\ldots,n+1\},n+1\in J,J\setminus\{n+1\}=\emptyset}a_J+\summe_{J\subseteq\{n+1\},n+1\in J,J\setminus\{n+1\}\not=\emptyset}a_J\right)$ [/mm]

   [mm] $=\sum_{J\subseteq \{1,\ldots,n+1\},J\not=\emptyset,n+1\notin J}a_J+\sum_{J\subseteq\{1,\ldots,n+1\},n+1\in J}a_J$ [/mm]

   [mm] $=\sum_{J\subseteq\{1,\ldots,n+1\},J\not=\emptyset}a_J$. [/mm]



Damit sind wir nach aufwändiger Rechnung am Ziel. :-)
Herzlichen Glückwunsch für dein Dranbleiben. [ok]

Bezug
                                                
Bezug
beweis Inklusion/Exklusion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 07:59 Mo 31.10.2016
Autor: lisa2802

Vielen vielen Dank!!! :)


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Stochastik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]