Verzwickte Stochastik

[Michamab]

Hallo, ich komme bei folgender Aufgabe einfach nicht voran. Vielleicht hat ja jemand von euch Spaß an ein bisschen Knobeln und kann mir mit einem Ansatz helfen. Vielen Dank schonmal im Voraus.

*Auf einer Weihnachtsfeier gibt es einen Julklapp. Dazu bringt jeder Teilnehmer ein Geschenk mit, und alle Geschenke werden in einen großen Sack verfrachtet. Danach zieht jeder der Partygäaste zufällig ein Geschenk aus dem Sack.

Was ist die erwartete Anzahl der Leute, die ihr eigenes Geschenk ziehen?

Was ist die Wahrscheinlichkeit dafür, dass mindestens ein Partygast sein eigenes
Geschenk zieht?*

[volkard]

Michamab schrieb:

Was ist die erwartete Anzahl der Leute, die ihr eigenes Geschenk ziehen?

nur ein blitzgedanke, ohne nachweis.
sei n die anzahl der leute.
also daß der erste sein eigenes geschenk zieht ist 1/n.
ich würde mir wünschen, daß das universum ausreicghend symmetrisch ist, daß das für alle anderen auch gilt.
dann würde die anzahl n*1/n=1 sein, unabhängig von n.

[Thracian]

Tafelwerk
Stochastik und Kombinatorik ab Seite 48, sollte eigentlich genug Handwerkszeug sein.
lg,
Thracian

[long long double]

Anzahl der gesamten Möglichkeiten: N = n! -> Der erste hat n Mgl., der 2. n - 1, etc.

Jetzt würde ich diejenigen herausnehmen, die ich nicht brauche -> ich will den Fall:

ABCDEFGH ...
12345678 ...

Also Person A erhält ihr eigenes Geschenk 1, usw. Dieser Fall entspricht genau einer Mgl. von N, also ist die Wahrscheinlichkeit 1/N, dass jeder sein eigenes zieht.

Nach der Aufgabenstellung soll mindestens einer sein eigenes ziehen, d.h. das Gegenereignis ist, dass höchstens n - 1 Personen ein anderes ziehen.

Jetzt wirds mir zu kompliziert für die Uhrzeit. ^^

[Gast]

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.

[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?

[Mak Sim]

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.

[Gast]

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

123
132
213
231
312 
321

von denen nur

231
312

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

[Gast]

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?