Irrfahrt, Spiegelung, WS < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:59 Mo 01.04.2013 | | Autor: | sissile |
| Aufgabe | Bei einem Wahlgang mit total n STimmen erhält der SIeger von zwei Kandidaten k STimmen mehr als sein gegner. Wie groß ist die Wahrscheinlichkeit, dass der Sieger während der ganzen AUszählung in Führung liegt, wenn die STimmen in zufälliger Reihenfolge aufgezählt werden?
Hinweis: Betrachte dazu die Irrfahrt [mm] (S_l)_{0 \le l \le n} [/mm] und zeige, dass es gleich viele Pfade von (1,1) nach (n,k) gibt, welche die l-achse schneiden oder berühren, wie Pfae von (1,1) nach (n,-k) (k>0) |
Hallo
Funktion l-> [mm] S_l
[/mm]
Die jeden Punkt der Stimmenauszählung(0 bis n) die Differenz der Summen zuordnet.
Den Grundraum hab ich mir schon überlegt
(wie ich genau darauf komme, formuliere ich gerne - wenn ihr denkt, dass es falsch ist)
[mm] \Omega [/mm] = [mm] \{ \omega = (\omega_1 , ..., \omega_n) : \omega_i \in \{1,-1}\} [/mm] : | [mm] \{\omega_i =1 \}|= [/mm] (n+k)/2, | [mm] \{\omega_i =-1 \}|= [/mm] (n-k)/2
Sowie das Ereignis:
A= [mm] \{ \omega \in \Omega : S_l (\omega) > 0 \forall 1 \le l \le n \}
[/mm]
[mm] A^c [/mm] = [mm] \{ \omega \in \Omega : \exists l \in \{1,..,n\} : S_l (\omega) \le 0 \}
[/mm]
Die Kardinalität des Grundraums ist auch klar. [mm] |\Omega|=\vektor{n \\ \frac{n+k}{2}} [/mm]
Überlegung war noch: Pfade in [mm] A^c [/mm] muss ein erstes Mal die Gerade l treffen z.B in Punkt Q. Ich spiegle den Endabschnitt von Q bis (n,k) an der Geraden l . Ich erhalte so einen Gitterweg der in (n,-k) endet.
Warum wird im Hinweis immer von Anfangspunkt (1,1) gesprochen?
Ich komme nicht weiter,..
|
|
| |
|
Hiho,
> Den Grundraum hab ich mir schon überlegt
> (wie ich genau darauf komme, formuliere ich gerne - wenn ihr denkt, dass es falsch ist)
Dann mach mal.
Ich denke zum Glück nicht nur, dass der Raum falsch ist, ich weiß es sogar 
Der Raum ist viel viel einfacher zu wählen. Auf welchem Raum bewegst du dich denn?
> Die Kardinalität des Grundraums ist auch klar.
> [mm]|\Omega|=\vektor{n \\ \frac{n+k}{2}}[/mm]
Achso? Was machst du denn, wenn n+k ungerade ist?
Aber wenn du deinen Raum korrigierst, kannst du das hier gleich mitmachen.
> Überlegung war noch: Pfade in [mm]A^c[/mm] muss ein erstes Mal die Gerade l treffen
Was immer die Gerade l sein soll.
Beschreibe das genauer: Welche Gerade muss getroffen werden? Schau dir dein [mm] A^c [/mm] nochmal an. Die Menge kannst du auch genauer beschreiben, dann wird dir auch klar, welche Gerade das sein muss. Muss da wirklich [mm] \le [/mm] in der Menge stehen?
> z.B in Punkt Q. Ich spiegle den Endabschnitt von Q bis (n,k) an der Geraden l . Ich erhalte so einen Gitterweg der in (n,-k) endet.
Ja, die Idee ist korrekt.
> Warum wird im Hinweis immer von Anfangspunkt (1,1) gesprochen?
Welche Menge an Pfaden möchtest du denn heraus bekommen?
Wie fangen die auf jeden Fall alle an?
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:16 Di 02.04.2013 | | Autor: | tobit09 |
Hallo Gonozal_IX,
> > Den Grundraum hab ich mir schon überlegt
> > (wie ich genau darauf komme, formuliere ich gerne - wenn
> ihr denkt, dass es falsch ist)
>
> Dann mach mal.
> Ich denke zum Glück nicht nur, dass der Raum falsch ist,
> ich weiß es sogar
[mm] $\omega_i$ [/mm] gibt jeweils an, welcher Kandidat die i-te ausgezählte Stimme erhält: -1 steht für den Verlierer der Wahl, +1 für den Gewinner der Wahl.
Sei $x$ die Anzahl der Stimmen des Verlierers. Dann ist $x+k$ die Anzahl der Stimmen des Gewinners. Die Gesamtzahl der Stimmen wird beschrieben sowohl durch $n$ als auch durch $x+(x+k)$. Also ergibt sich $n=x+(x+k)$ und somit [mm] $x=\bruch{n-k}{2}$ [/mm] und [mm] $x+k=\bruch{x+k}{2}$. [/mm] Der Verlierer erhält also genau [mm] $\bruch{n-k}{2}$ [/mm] Stimmen, der Gewinner [mm] $\bruch{x+k}{2}$.
[/mm]
Ich kann somit nicht erkennen, was an sissiles Wahl von [mm] $\Omega$ [/mm] falsch sein soll.
> Der Raum ist viel viel einfacher zu wählen. Auf welchem
> Raum bewegst du dich denn?
>
> > Die Kardinalität des Grundraums ist auch klar.
> > [mm]|\Omega|=\vektor{n \\ \frac{n+k}{2}}[/mm]
>
> Achso? Was machst du denn, wenn n+k ungerade ist?
> Aber wenn du deinen Raum korrigierst, kannst du das hier
> gleich mitmachen.
[mm] $\bruch{n+k}{2}$ [/mm] ist die Anzahl der Stimmen des Verlierers und somit nach Sachsituation eine ganze Zahl. Somit ist n+k in jedem Fall gerade.
Auch bei der Bestimmung von [mm] $|\Omega|$ [/mm] vermag ich keinen Fehler zu finden.
> > Überlegung war noch: Pfade in [mm]A^c[/mm] muss ein erstes Mal die
> Gerade l treffen
> Was immer die Gerade l sein soll.
> Beschreibe das genauer: Welche Gerade muss getroffen
> werden? Schau dir dein [mm]A^c[/mm] nochmal an. Die Menge kannst du
> auch genauer beschreiben, dann wird dir auch klar, welche
> Gerade das sein muss.
Was meinst du damit, [mm] $A^c$ [/mm] genauer zu beschreiben, als sissile es getan hat?
> Muss da wirklich [mm]\le[/mm] in der Menge
> stehen?
Man könnte auch $=$ schreiben, das würde nichts an der richtigen Beschreibung der Menge ändern.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:55 Di 02.04.2013 | | Autor: | tobit09 |
Hallo sissile,
> Funktion l-> [mm]S_l[/mm]
> Die jeden Punkt der Stimmenauszählung(0 bis n) die
> Differenz der Summen zuordnet.
Das würde ich hier weglassen.
> Den Grundraum hab ich mir schon überlegt
> (wie ich genau darauf komme, formuliere ich gerne - wenn
> ihr denkt, dass es falsch ist)
> [mm]\Omega[/mm] = [mm]\{ \omega = (\omega_1 , ..., \omega_n) : \omega_i \in \{1,-1}\}[/mm]
> : | [mm]\{\omega_i =1 \}|=[/mm] (n+k)/2, | [mm]\{\omega_i =-1 \}|=[/mm]
> (n-k)/2
![[ok]](/images/smileys/ok.gif "[ok]")
Ich würde noch die Erklärung ergänzen, die ich Gonozal in meiner Mitteilung gegeben habe.
Welche Verteilung nimmst du auf [mm] $\Omega$ [/mm] an?
Dann solltest du für [mm] $S_l\colon\Omega\to\IR$ [/mm] für [mm] $l=0,\ldots,n$ [/mm] definieren und erklären, dass [mm] $S_l$ [/mm] die Differenz von Sieger-Stimmenzahl und Verlierer-Stimmenzahl nach l ausgewählten Stimmen angibt.
> Sowie das Ereignis:
> A= [mm]\{ \omega \in \Omega : S_l (\omega) > 0 \forall 1 \le l \le n \}[/mm]
>
> [mm]A^c[/mm] = [mm]\{ \omega \in \Omega : \exists l \in \{1,..,n\} : S_l (\omega) \le 0 \}[/mm]
> Die Kardinalität des Grundraums ist auch klar.
> [mm]|\Omega|=\vektor{n \\ \frac{n+k}{2}}[/mm]
Jedem [mm] $\omega\in\Omega$ [/mm] können wir den zugehörigen Pfad [mm] $f_\omega:=(S_l(\omega))_{l=0,\ldots,n}$ [/mm] zuordnen. Wenn wir als Pfade nur solche Abbildungen [mm] $P\colon\{1,\ldots,n\}\to\IZ$ [/mm] zulassen, die $|P(i)-P(i+1)|=1$ für alle [mm] $i=0,\ldots,n-1$ [/mm] erfüllen (nur solche Pfade sind im Hinweis gemeint), existiert umgekehrt zu jedem Pfad $f$ von $(0,0)$ nach $(n,k)$ ein [mm] $\omega\in\Omega$ [/mm] mit [mm] $f_\omega=f$.
[/mm]
Einen Pfad möchte ich "gut" nennen, wenn er die l-Achse an einer Stelle [mm] $i\in\{1,\ldots,n\}$ [/mm] trifft.
Für alle [mm] $\omega\in\Omega$ [/mm] gilt die Äquivalenz: [mm] $\omega\in A^c\gdw f_\omega$ [/mm] gut. Somit ist [mm] $|A^c|$ [/mm] die Anzahl $a$ der guten Pfade von $(0,0)$ nach $(n,k)$.
> Überlegung war noch: Pfade in [mm]A^c[/mm] muss ein erstes Mal die
> Gerade l treffen z.B in Punkt Q.
Genau, und zwar in einem Punkt $Q(l,k)$ mit [mm] $l\ge1$. [/mm] (Alle durch [mm] $\omega\in\Omega$ [/mm] gegebene Pfade treffen die l-Achse im Punkt (0,0).)
> Ich spiegle den
> Endabschnitt von Q bis (n,k) an der Geraden l . Ich erhalte
> so einen Gitterweg der in (n,-k) endet.
Damit dir das Reflexionsprinzip beim Abzählen hilft, musst du dich für eine bestimmte Regel entscheiden, von welchem Punkt Q aus du den Endabschnitt spiegeln möchtest (z.B. den ersten Punkt Q, in dem die $l$-Achse getroffen wird).
Leider ist die Anzahl der guten Pfade von $(0,0)$ nach $(n,-k)$ nicht leichter zu bestimmen als die Anzahl $a$ der guten Pfade von $(0,0)$ nach $(n,k)$.
> Warum wird im Hinweis immer von Anfangspunkt (1,1)
> gesprochen?
> Ich komme nicht weiter,..
Wir benötigen ein Trick: Jeder Pfad von $(0,0)$ nach $(n,k)$ verläuft entweder durch den Punkt $(1,1)$ oder durch den Punkt $(1,-1)$. Sei nun $b$ die Anzahl der guten Pfade von $(0,0)$ über den Punkt $(1,1)$ nach $(n,k)$. Ebenso sei $c$ die Anzahl der guten Pfade von $(0,0)$ über den Punkt $(1,-1)$ nach $(n,k)$. Dann gilt $a=b+c$.
Um $b$ zu ermitteln, können wir genauso gut die Anzahl der guten Pfade von $(1,1)$ nach $(n,k)$ zählen. Da hilft das Reflexionsprinzip. Um $c$ zu ermitteln, können wir ebenso gut die Anzahl der guten Pfade von $(1,-1)$ nach $(n,k)$ ermitteln.
Viel Erfolg!
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:13 Di 02.04.2013 | | Autor: | sissile |
Danke.
> Genau, und zwar in einem Punkt Q(l,k) mit $ [mm] l\ge1 [/mm] $. (Alle durch $ [mm] \omega\in\Omega [/mm] $ gegebene Pfade treffen die l-Achse im Punkt (0,0).)
Du meinst sicher: im Punkt Q= (l,0)
Ich glaub ich habs (fast).
Sei b die Anzahl der guten Pfade von (0,0) über (1,1) nach (n,k)
B= [mm] \{ \omega \in \Omega: \omega \in A^c \wedge \omega_1=+1 \}
[/mm]
Sei c die Anzahl der (guten ) Pfase von (0,0) über (1,-1) nach (n,k)
Wobei hier die Bedingung in [mm] A^c [/mm] zu sein eine leere ist.
C= [mm] \{ \omega \in \Omega: \omega_1=-1 \}
[/mm]
a=b+c
Für b:
->Spiegelunsprinzip
Pfade in $ [mm] A^c [/mm] $ muss ein erstes Mal die Gerade l treffen im Punkt Q=(l,0) mit l [mm] \ge [/mm] 1.
Spiegle den Endabschnitt von Q bis (n,k) an der Geraden l . Ich erhalte so einen Pfad von (1,1) nach (n,-k).. (k>0) [dass es gute Pfade sind wird wieder eine leere Bedingung)
Für c:
c= [mm] \vektor{n-1 \\ \frac{n+k}{2}}
[/mm]
b=Anzahl aller Pfade von (1,1) nach (n,-k) = Anzahl der Pfade von (1,-1) nach (n,k)=c
P(A) =1- 2* [mm] \frac{|C|}{|\Omega|}= [/mm] 1 -2 * [mm] \frac{ \vektor{n-1 \\ \frac{n+k}{2}}}{\vektor{n \\ \frac{n+k}{2}} }
[/mm]
2Fragen bleiben:
1) Da bin ich mir nicht sicher am Schluß.. Ist das überhaupt ein Laplacemodell? Die Wahrscheinlichkeit der pfade sind ja nicht constant oder doch?
2) Jetzt bin ich mir nicht ganz sicher, wie ich mathematisch korrekt erkläre(Intuitiv war es mir sofort klar):
Anzahl aller Pfade von (1,1) nach (n,-k) = Anzahl der Pfade von (1,-1) nach (n,k)
Da die anzahl der Pfade von (1,1) nach (n,-k) ja gar nicht in [mm] \Omega [/mm] sind.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:30 Mi 03.04.2013 | | Autor: | tobit09 |
> > Genau, und zwar in einem Punkt Q(l,k) mit [mm]l\ge1 [/mm]. (Alle
> durch [mm]\omega\in\Omega[/mm] gegebene Pfade treffen die l-Achse im
> Punkt (0,0).)
> Du meinst sicher: im Punkt Q= (l,0)
Ja. Da war ich wohl geistig umnachtet...
> Sei b die Anzahl der guten Pfade von (0,0) über (1,1) nach
> (n,k)
> B= [mm]\{ \omega \in \Omega: \omega \in A^c \wedge \omega_1=+1 \}[/mm]
>
> Sei c die Anzahl der (guten ) Pfase von (0,0) über (1,-1)
> nach (n,k)
> Wobei hier die Bedingung in [mm]A^c[/mm] zu sein eine leere ist.
> C= [mm]\{ \omega \in \Omega: \omega_1=-1 \}[/mm]
>
> a=b+c
>
> Für b:
> ->Spiegelunsprinzip
> Pfade in [mm]A^c[/mm] muss ein erstes Mal die Gerade l treffen im
> Punkt Q=(l,0) mit l [mm]\ge[/mm] 1.
> Spiegle den Endabschnitt von Q bis (n,k) an der Geraden l
> . Ich erhalte so einen Pfad von (1,1) nach (n,-k).. (k>0)
> [dass es gute Pfade sind wird wieder eine leere Bedingung)
>
> Für c:
> c= [mm]\vektor{n-1 \\ \frac{n+k}{2}}[/mm]
>
> b=Anzahl aller Pfade von (1,1) nach (n,-k) = Anzahl der
> Pfade von (1,-1) nach (n,k)=c
> P(A) =1- 2* [mm]\frac{|C|}{|\Omega|}=[/mm] 1 -2 * [mm]\frac{ \vektor{n-1 \\ \frac{n+k}{2}}}{\vektor{n \\ \frac{n+k}{2}} }[/mm]
Das sieht gut aus!
Wenn ich mich nicht verrechnet habe, lässt sich der Ausdruck für $P(A)$ noch deutlich vereinfachen. Starte damit, die Definition der auftretenden Binomialkoeffizienten anzuwenden.
Man könnte noch Kleinigkeiten ausführlicher darstellen, aber das ist Geschmackssache. Falls ich näher darauf eingehen soll, frag einfach nochmal nach.
> 1) Da bin ich mir nicht sicher am Schluß.. Ist das
> überhaupt ein Laplacemodell? Die Wahrscheinlichkeit der
> pfade sind ja nicht constant oder doch?
Tatsächlich liegt ein Laplace-Modell vor und tatsächlich war ich zunächst genauso unsicher darüber wie du.
Daher könnten wir das Modell mit Grundmenge
[mm] $\Omega':=\{(\omega_1',\ldots,\omega_n')\in\{1,\ldots,n\}^n\;|\;\omega_i'\not=\omega_j'\text{ für alle }i\not=j\}$
[/mm]
betrachten, wobei wir uns die Stimmzettel von 1 bis n durchnummeriert denken und annehme, dass die Zettel mit den Nummern 1 bis [mm] $\bruch{n+k}{2}$ [/mm] Stimmen für den Sieger beinhalten und die Zettel mit den Nummern [mm] $\bruch{n+k}{2}+1$ [/mm] bis $n$ Stimmen für den Verlierer. [mm] $\omega_i'$ [/mm] gebe die Nummer des als i-tes ausgezählten Zettels an.
Dass auf [mm] $\Omega'$ [/mm] eine Laplace-Annahme gerechtfertigt ist, ist deutlich klarer als auf [mm] $\Omega$. [/mm] Sei P' die Laplace-Verteilung auf [mm] $\Omega'$.
[/mm]
Jedes Ergebnis [mm] $\omega=(\omega_1,\ldots,\omega_n)\in\Omega$ [/mm] in deinem Modell entspricht dem Ereignis
[mm] $A_\omega:=\{(\omega_1',\ldots,\omega_n')\in\Omega'\;|\;(\omega_i'\in\{1,\ldots,\bruch{n+k}{2}\}\gdw\omega_i=1)\text{ für alle }i=1,\ldots,n\}$.
[/mm]
im neuen Modell.
Somit sollte [mm] $P(\{\omega\}):=P'(A_\omega)$ [/mm] für alle [mm] $\omega\in\Omega$ [/mm] gesetzt werden.
Nun kann man nachprüfen, dass damit [mm] $P(\{\omega\})=P(\{\overline{\omega}\})$ [/mm] für alle [mm] $\omega,\overline{\omega}\in\Omega$ [/mm] gilt und P somit die Laplace-Verteilung auf [mm] $\Omega$ [/mm] ist.
> 2) Jetzt bin ich mir nicht ganz sicher, wie ich
> mathematisch korrekt erkläre(Intuitiv war es mir sofort
> klar):
> Anzahl aller Pfade von (1,1) nach (n,-k) = Anzahl der
> Pfade von (1,-1) nach (n,k)
> Da die anzahl der Pfade von (1,1) nach (n,-k) ja gar nicht
> in [mm]\Omega[/mm] sind.
Es geht hier um eine rein kombinatorische Frage. Dabei spielt es für die Argumentation keine Rolle, ob die hilfsweise betrachteten Pfade von (1,1) nach (n,-k) Elementen von [mm] $\Omega$ [/mm] entsprechen.
Will man diese Gleichheit exakt begründen (die wenigsten Mathematiker machen sich die Mühe, solche kombinatorischen Tatsachen exakt zu begründen...  ), so gibt man eine Bijektion zwischen der Menge der Pfade von (1,1) nach (n,-k) und der Menge der Pfade von (1,-1) nach (n,k) an: Die Zuordnung [mm] $(s_1,\ldots,s_n)\mapsto(-s_1,\ldots,-s_n)$ [/mm] leistet das Gewünschte.
|
|
|
|
