Geschenkverteilung < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 11:35 Mo 04.07.2005 | | Autor: | Thorinson |
Erstmal möchte ich anmerken, dass dies eine Frage nur an Interessierte ohne wirklich dringenden hintergrund ist.
Ich habe schon ein paar Jahre mit der Stochastik nichts mehr zu tun und bin kürzlich über folgende Aufgabe gestolpert. Da ich mich gerne an solchen Übungen Versuche hab ich auch diese probiert, bin aber kläglichst gescheitert. Vielleicht kann mir ja hier einer weiterhelfen:
Auf einer Geburtstagsfeier befinden sich n Gäste. Jeder Gast bringt ein mit seinem Namen markiertes Geschenk mit, das auf einen Tisch gestellt wird. Anschließend nimmt nacheinander jeder Gast zufällig ein Geschenk vom Tisch, wobei jeder darauf achtet, daß er nicht sein eigenes Geschenk nimmt.
Wie hoch ist die Wahrscheinlichkeit p(n), dass das ganze so verläuft, dass diese Art der Verteilung nicht möglich ist?
Beispiele:
p(1) = 1
p(2) = 0
p(3) = 1/3
p(4) = 2/11
Ich scheitere schon bei einer Beschreibung der ersten drei Fälle in einer Formel, mit n seh ich da nur noch schwarz. Kann hier vielleicht einer diese Aufgabe lösen. Vielleicht hat auch jemand diese Aufgabe schon einmal mit einer Lösung irgendwo gesehen, dann würde mir auch ein Link schon reichen.
Vielen Dank im Vorraus,
MfG Stefan
P.S. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 12:48 Mo 04.07.2005 | | Autor: | Julius |
Hallo!
Du findest hier die Wahrscheinlichkeit für eine fixpunktfreie Permutation. Was du hier berechnen sollst, ist ja die Wahrscheinlichkeit für das Eintreffen einer Permutation mit mindestens einem Fixpunkt, also genau die Gegenwahrscheinlichkeit.
Wenn du mehr darüber wissen willst:
Das Stichwort heißt: Rencontre-Problem.
Edit: Muss es nicht $p(2)= [mm] \frac{1}{2}$ [/mm] heißen, oder habe ich die Aufgabe etwa falsch verstanden?
Viele Grüße
Julius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:27 Mo 04.07.2005 | | Autor: | Thorinson |
Nein, p2 = 0, da der erste der Auswählt ja da Geschenk des anderen nehmen MUSS, wenn er nicht seins nehmen will. Und der zweite bekommt dann das Geschenk von Person eins. Daher funktioniert die Verteilung hier immer, und die Wahrscheinlichkeit dass es nicht klappt ist 0.
Das ist ja gerade die Schwierigkeit an dieser Aufgabe. Währe es eine rein zufällige Verteilung wäre sie schnell gelöst, aber da jeder darauf achtet, dass er nicht sein geschenk nimmt sondern ein zufälliges anderes wird das ganze recht kompliziert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:32 Mo 04.07.2005 | | Autor: | Julius |
Hallo!
Sorry, dann habe ich die Aufgabe falsch verstanden. ![[sorry]](/images/smileys/sorry.gif "[sorry]") Kannst du (oder jemand anderes) die Frage bitte wieder auf "teilweise beantwortet" stellen? Danke!
Viele Grüße
Julius
|
|
|
| |
|
Bei 3 Gästen a,b,c sehen die Möglichkeiten folgendermassen aus:
[mm]a \to b \to a \ \ \ \ \ \ \ \Rightarrow [/mm] c geht leer aus
[mm]a \to b \to c \to a \Rightarrow [/mm] alles paletti
[mm]a \to c \to a \ \ \ \ \ \ \ \Rightarrow [/mm] b geht leer aus
[mm]a \to c \to b \to a \Rightarrow [/mm] alles paletti
wenn b anfängt, sieht es ähnlich aus:
[mm]b \to c \to b \ \ \ \ \ \ \ \Rightarrow [/mm] a geht leer aus
[mm]b \to c \to a \to b \Rightarrow [/mm] alles paletti
[mm]b \to a \to b \ \ \ \ \ \ \ \Rightarrow [/mm] c geht leer aus
[mm]b \to a \to c \to b \Rightarrow [/mm] alles paletti
analog wenn c beginnt, also 12 Möglichkeiten, von denen 6 OK sind.
[mm]p \ = \ \bruch{6}{12} \ = \ \bruch{1}{2} [/mm]
Ich schlage vor, für vier oder fünf Gäste ebenfalls eine solches Diagramm (Baumdiagram) zu erstellen und erst dann zu versuchen, die Formel zu entwickeln.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:54 Mi 13.07.2005 | | Autor: | Thorinson |
Hallo,
Ne, das ist nicht korrekt, jeder Gast bekommt nur EIN Geschenk, somit kann keiner leer ausgehen. Die Frage ist, wie Wahrscheinlich es ist, dass am ende noch das Geschenk da liegt, das derjenige mitgebracht hat, der zuletzt dran ist.
MfG Stefan
|
|
|
| |
|
Hallo Stefan,
Ich habe in letzter Zeit immer wieder über das Problem nachgedacht, und jetzt habe ich es endlich gelöst. Hinterher betrachtet recht simpel.
Erste Frage: Wie sieht der Wahrscheinlichkeitsraum aus?
Es geht hier offensichtlich um Permutationen. In den W-Raum kommen einerseits die fixpunktfreien Permutationen, (Das sind die guten.) und andererseits die Permutationen, die n und nur n als Fixpunkt haben. (Das sind die schlechten.)
Begründung: Man kann das Spiel so verstehen. Keiner darf sein Geschenk nehmen (-> fixpunktfreie). Ausgenommen ist Gast n (-> Fixpunkt n), der allerdings verliert, wenn er seines nimmt.
Zweite Frage: Wie rechnet man das?
Um die Anzahl der fixpunktfreien Permutationen zu zählen, ist es leichter, alle Permutaionen mit Fixpunkt zu zählen, und von ver Gesamtmenge zu subtrahieren. Sei A(n) die Anzahl der Permutationen von n Elementen, die einen Fixpunkt haben. Nach der Siebformel von Poincaré gilt:
A(n) = [mm] $\summe_{k=1}^n (-1)^{k+1} [/mm] * [mm] \vektor{n \\ k} [/mm] * (n-k)!$
Dabei steht [mm] $\vektor{n \\ k}$ [/mm] für die Zahl der Permutationen mit k (oder mehr Fixpunkten).
Somit gilt für die Mächtigkeit des W-Raumes:
W(n)=(n! - A(n)) + ((n-1)! - A(n-1))
In der ersten Klammer steht die Anzahl der fixpunktfreien Permutationen, inder zweiten die Anzahl der Permutationen, die genau das letzte Element fix lassen.
Die Wahrscheinlichkeit, dass die Sache schief läuft errechnet sich nun ganz einfach. Es gilt:
[mm] $p_n [/mm] = [mm] \bruch{(n-1)! - A(n-1)}{W(n)}$
[/mm]
Ich habe das für die ersten 100 n durchgerechnet, und habe für n=1, ... , 4 genau Deine Werte ermittelt. Dann kommt
[mm] $p_5$ [/mm] = 9/53 = 0,170
[mm] $p_6$ [/mm] = 44/309 = 0,142
[mm] $p_7$ [/mm] = 265/2119 = 0.125
[mm] $p_8$ [/mm] = 1854/16687 = 0,111
[mm] $p_9$ [/mm] = 14833/148329 = 0,100
[mm] $p_{10}$ [/mm] = 133496/1468457 = 0,090
Und das ist doch irgendwie sehr interessant. Es sieht so aus, als wäre jeweils 1/(n+1) eine brauchbare Näherung an [mm] $p_n$. [/mm] Tatsächlich scheint diese Näherung sogar asymptotisch exakt zu sein.
So, damit lasse ich es bewenden.
Liebe Grüße,
Holy Diver
|
|
|
|
