Wahrscheinlichkeit 3 Permutationen Fixpunkt

23.10.2011, 13:22

math_mrg

Wahrscheinlichkeit 3 Permutationen Fixpunkt

Meine Frage:
Gegeben seien drei identische Kartenspiele mit jeweils n unterschiedlichen Karten. Zunächst mischen Sie jedes KArtenspiel. Danach decken Sie in n Durchgängen die jeweils oberste Karte auf.

Mit welcher Wahrscheinlichkeit stimmen in mindestens einem Durchgang die drei gezogenen Karten überein?

Wie verändert sich diese Wahrscheinlichkeit für $\begin{eqnarray*} n\to \infty \end{eqnarray*}$ ?

Meine Ideen:
Ich habe mir gedacht, das sind drei Permutationen und ich soll die Wahrscheinlichkeit finden, dass diese drei an mindestens einer Stelle den selben Fixpunkt haben, d.h.

$\begin{eqnarray*} A=\lbrace (\sigma, \pi ,\tau )\in \mathfrak{S}^n \mid \sigma (i) = \tau (i) = \pi (i) \text{ für mind. ein }i\in \lbrace 1, \hdots ,n \rbrace \end{eqnarray*}$

Das müsste ja mit Einschluss-Ausschluss-Formel gehen...dann habe ich für den Schnitt von $\begin{eqnarray*} A_{j_1}\cap \hdots A_{j_k} \end{eqnarray*}$ eine Kardinalität von $\begin{eqnarray*} ((n-k)!)^3 \end{eqnarray*}$ und komme im Endeffekt auf folgende Wahrscheinlichkeit:

$\begin{eqnarray*} \mathbb{P}(A)=\left( \frac{1}{n!}\right)^2 - \sum_{k=0}^n \frac{(-1)^k}{k!}\left( \frac{(n-k)!}{n!}\right)^2 \end{eqnarray*}$

Kann das stimmen? Gegen unendlich würde diese ja dann gegen 0 konvergieren...

Wäre super, wenn ihr mir helfen könntet!

edit: latex korrigiert

31.10.2016, 04:18

djtrump

Auf diesen Beitrag antworten »

5 Jahre später - die gleiche Aufgabe ... Augenzwinkern

Ich komme auch auf das gleiche Ergebnis mit Konvergenz gegen Null für $\begin{eqnarray*} n \longto \infty \end{eqnarray*}$ ...

Stimmt denn die Argumentation/Rechnung von math_mrg?

31.10.2016, 04:55

djtrump

Auf diesen Beitrag antworten »

Nachtrag
"! Undefinied control sequence." soll $\begin{eqnarray*} n \to \infty \end{eqnarray*}$ heißen.

01.11.2016, 09:19

HAL 9000

Auf diesen Beitrag antworten »

RE: Nachtrag

Zitat:

Original von math_mrg
Das müsste ja mit Einschluss-Ausschluss-Formel gehen...dann habe ich für den Schnitt von $\begin{eqnarray*} A_{j_1}\cap \hdots A_{j_k} \end{eqnarray*}$ eine Kardinalität von $\begin{eqnarray*} ((n-k)!)^3 \end{eqnarray*}$

Na wohl eher $\begin{align*} (n-k)!^2\cdot n! \end{align*}$ .

Zitat:

Original von math_mrg
und komme im Endeffekt auf folgende Wahrscheinlichkeit:

$\begin{eqnarray*} \mathbb{P}(A)=\left( \frac{1}{n!}\right)^2 - \sum_{k=0}^n \frac{(-1)^k}{k!}\left( \frac{(n-k)!}{n!}\right)^2 \end{eqnarray*}$

Ich komme da auf

$\begin{align*} \mathbb{P}(A) = \sum_{k=1}^n (-1)^{k-1}\binom{n}{k} \left( \frac{(n-k)!}{n!}\right)^2 = \sum_{k=1}^n (-1)^{k-1} \frac{(n-k)!}{n!k!} \end{align*}$ .

Die Konvergenz gegen Null ist richtig und auch nachvollziehbar: Bereits für die Übereinstimmung an mindestens einer Stelle bei nur zwei statt drei Kartenspielen ergibt sich im Grenzwert $\begin{align*} 1-\frac{1}{e} \end{align*}$ als Wahrscheinlichkeit, und hier kommt nun eine weitere Übereinstimmungsforderung obendrauf...

EDIT: Der bloße Nachweis der Nullkonvergenz geht ziemlich einfach. Mit der oben ja auch schon verwendeten Bezeichnung

$\begin{align*} A_j \end{align*}$ ... an der Stelle $\begin{align*} i \end{align*}$ stimmen die drei Permutationen überein

gilt $\begin{align*} \mathbb{P}(A) = \mathbb{P}\left( \bigcup_{j=1}^n A_j\right) \leq \sum_{j=1}^n \mathbb{P}(A_j) = n\cdot \frac{1}{n^2} = \frac{1}{n} \end{align*}$

Tatsächlich ist diese Abschätzung sogar ziemlich gut, vor allem für größere $\begin{align*} n \end{align*}$ : Denn dort schwindet der Einfluß der Schnittwahrscheinlichkeiten von zwei oder noch mehr der $\begin{align*} A_j \end{align*}$ rapide, so dass man für große n tatsächlich sogar $\begin{align*} \mathbb{P}(A) \approx \frac{1}{n} \end{align*}$ sagen kann.

Neue Frage »

Antworten »

Wahrscheinlichkeit 3 Permutationen Fixpunkt

Verwandte Themen