Verzwickte Stochastik

volkard

Optimizer schrieb:

Die Wahrscheinlichkeit, dass mindestens ein Gast sein eigenes Geschenk zieht ist:
P(mindestens einer zieht sein Geschenk)
    = 1 - P(niemand zieht sein Geschenk)
    = 1 - (P(ich ziehe mein Geschenk nicht))^n
Ich verrate mal nicht mehr, hoffe das hilft weiter.

für

1 - P(niemand zieht sein Geschenk)
    = 1 - (P(ich ziehe mein Geschenk nicht))^n

ziehst du aber auch

würde mir wünschen, daß das universum ausreicghend symmetrisch ist, daß

zu rate, oder?

damit ist das ergebnis klar. sollte ich mir einen reduzierten baum der tiefe n bauen und alle teilwahrscheinlichkeiten hinschreiben und hoffen, daß sich dein ergebnis ergibt?

Seien die n Teilnehmer, n Element N\0 indiziert mit 1,...,n und p_i : N\0^n -> N\0^n Permutation mit Index i. Die erwartete Zahl der Leute, die ihr eigenes Geschenk ziehen ist
E(#{k|p(k) = k}) = 1/#{p_i} * Summe_i=1^#{p_i} #{k|p_i(k)=k} = ... ausrechnen

Wahrscheinlichkeit, dass keiner sein Geschenk zieht ist
P( Für Alle k: p(k) != k ) = #{p|p Permutation ohne fixpunkte}/#{p|p Permutation} = ... ausrechnen

BAM! fertig

Jester

Die Symmetrie kriegt man doch recht einfach: Die Wahrscheinlichkeit, dass der i-te sein eigenes Geschenk zieht ist das Produkt zweier Wahrscheinlichkeiten:

P(i zieht sein eigenes Geschenk) = P(i zieht sein eigenes | Geschenk i wurde noch nicht gezogen) * P(Geschenk i wurde noch nicht gezogen)

P(i zieht sein eigenes | Geschenk i wurde noch nicht gezogen) = 1/(n-i+1): es gibt noch n-i+1 Geschenke und eines davon ist seines.

P(Geschenk i wurde noch nicht gezogen) geht ähnlich: Für Person j mit j<i gibt es noch (n-j+1) Geschenke und eines davon ist das von i. Die günstigen Fälle für zieht nicht das Geschenk von i sind also (n-j).

Also erhalten wir Produkt k=1...(i-1) über (n-k)/(n-k+1). Brav Kürzen (jeden Bruch mit dem nächsten) und wir behalten nur noch den Nenner vom ersten Bruch: n und den Zähler vom letzten: (n-i+1)

Siehe da, das Produkt der beiden Wahrscheinlichkeiten ist 1/n und die Welt ist symmetrisch.

Bashar

Jester schrieb:

P(i zieht sein eigenes Geschenk) = P(i zieht sein eigenes | Geschenk i wurde noch nicht gezogen) * P(Geschenk i wurde noch nicht gezogen)

Das hab ich mir auch überlegt, aber wieder verworfen, weil die beiden Ereignisse anscheinend nicht unabhängig sind. Oder doch? Vielleicht kannst du das kurz begründen.

Jester

Das ist doch eine bedingte Wahrscheinlichkeit, damit modelliere ich doch gerade die Abhängigkeit:

A: i zieht das Geschenk von i
B: alle j mit j<i ziehen nicht das Geschenk von i

Unabhängigkeit von A und B setze ich gerade nicht voraus, die ist ja hier auch nicht gegeben. Nochmal mein Rechenweg in kürze:

P(A) = P(A und + P(A und nicht

P(A und nicht = 0, da i sein Geschenk nicht mehr ziehen kann, wenn es schon jemand anders hat.

Also P(A) = P(A und = (nach Bayes) P(A | * P(B)

Jester

Man kanns auch so umformulieren: Es gibt bei n Personen, n Lose und genau eines der Lose ist das Gewinnlos. Nun ziehen die Personen nacheinander die Lose aus nem Beutel. Was ist die Gewinnwahrscheinlichkeit von Person i? Glücklicherweise 1/n: Auch wenn der letzte keine Wahl mehr hat, ist seine Gewinnchance dieselbe.

Dass in der Variante mit den Geschenken das Gewinnlos für jeden ein anderes ist, ändert daran überhaupt nichts. Die Zettel (bzw. gezogenen Objekte) sind untereinander ja völlig austauschbar.

volkard schrieb:

Optimizer schrieb:
Die Wahrscheinlichkeit, dass mindestens ein Gast sein eigenes Geschenk zieht ist:
P(mindestens einer zieht sein Geschenk)
    = 1 - P(niemand zieht sein Geschenk)
    = 1 - (P(ich ziehe mein Geschenk nicht))^n
Ich verrate mal nicht mehr, hoffe das hilft weiter.
für
1 - P(niemand zieht sein Geschenk)
    = 1 - (P(ich ziehe mein Geschenk nicht))^n
ziehst du aber auch
würde mir wünschen, daß das universum ausreicghend symmetrisch ist, daß
zu rate, oder?

damit ist das ergebnis klar. sollte ich mir einen reduzierten baum der tiefe n bauen und alle teilwahrscheinlichkeiten hinschreiben und hoffen, daß sich dein ergebnis ergibt?

Ja, ich bin von der Symmetrie ausgegangen. Ich habe nur etwas dazu gesagt, weil du zur letzten Frage keinen Hinweis gegeben hast, das war keine Berichtigung, sondern eine Ergänzung.

Meta Maß

Optimizer schrieb:

volkard schrieb:
Optimizer schrieb:
Die Wahrscheinlichkeit, dass mindestens ein Gast sein eigenes Geschenk zieht ist:
P(mindestens einer zieht sein Geschenk)
    = 1 - P(niemand zieht sein Geschenk)
    = 1 - (P(ich ziehe mein Geschenk nicht))^n
Ich verrate mal nicht mehr, hoffe das hilft weiter.
für
1 - P(niemand zieht sein Geschenk)
    = 1 - (P(ich ziehe mein Geschenk nicht))^n
ziehst du aber auch
würde mir wünschen, daß das universum ausreicghend symmetrisch ist, daß
zu rate, oder?

damit ist das ergebnis klar. sollte ich mir einen reduzierten baum der tiefe n bauen und alle teilwahrscheinlichkeiten hinschreiben und hoffen, daß sich dein ergebnis ergibt?
Ja, ich bin von der Symmetrie ausgegangen. Ich habe nur etwas dazu gesagt, weil du zur letzten Frage keinen Hinweis gegeben hast, das war keine Berichtigung, sondern eine Ergänzung.

Betrachte den Fall n = 3.

P(ich ziehe mein Geschenk nicht)^3 = (2/3)^3

aber es gibt folgende gleichwahrscheinliche ziehungen

von denen nur

231
312

keinem sein eigenes Geschenk geben, was 1/3 aller Fälle entspricht. Die Welt ist hier nicht so symmetrisch.

Jap, so ist es wohl. Schätze, meine Rechnung gilt für den Fall mit Zurücklegen, also 27 Möglichkeiten. Der ist hier offenkundig nicht gegeben. Was zur Zeit von Volkards Post jetzt schon so "klar" war, kapiere ich immer noch nicht ganz, da die Lösung noch nicht da stand. Vielleicht wollte er mir so etwas in der Art sagen.

volkard

Optimizer schrieb:

Was zur Zeit von Volkards Post jetzt schon so "klar" war, kapiere ich immer noch nicht ganz,

ich auch nicht. ich habs dir einfach mal geglaubt. gemeint war nicht klar(offensichtlich), sondern klar(aufgedeckt).

Jester

Also ist derzeit noch offen, wie groß die WK für mindestens einer ist. Dass der Erwartungswert 1 ist, ergibt sich aus meiner Rechnung von oben. Aber da die Ereignisse "i zieht sein eigenes Geschenk" und "j zieht sein eigenes Geschenk" nicht unabhängig sind bringt einen das noch nicht weiter. Das sieht man ja auch ganz deutlich wenn man nur zwei Personen hat: Die Wahrscheinlichkeit für jeden einzeln ist 1/2, die Wahrscheinlichkeit, dass mindestens einer seins zieht ist aber ebenfalls 1/2.

Vielleicht kann man hier tatsächlich den Ansatz machen, dass man die Anzahl der Permutationen ohne Fixpunkte zählt. Dafür dürfte sich eine Rekurrenz aufstellen lassen... vielleicht lässt sich die vernünftig lösen?