Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Hutproblem

Hutproblem

Schüler

Tags: permutation

Randolph Esser aktiv_icon

19:50 Uhr, 14.05.2025

Hallo,

Aufgabe:

n

Gäste geben an der Garderobe jeweils ihren Hut ab.
Später werden ihnen die Hüte jedoch völlig zufällig wieder zurückgegeben.
Bestimmen Sie den Erwartungswert für die Anzahl der Gäste,
die ihren Hut wiederbekommen.

Zunächst ist klar, dass das der Erwartungswert für die Anzahl
der Fixpunkte einer (beliebigen) Permutation von

n

Elementen ist.
Wir definieren also die Zufallsvariable

X,

die Permutationen von

n

Elementen auf die Anzahl ihrer Fixpunkte abbildet.
Dann ist

E [X]

der gesuchte Wert.

Nun zu meiner Rechnung:

Seien die Gäste laufend nummeriert und
sei

X_{k}

für alle

1 \leq k \leq n

die Indikator-Zufallsvariable für Gast

k,

also mit

X_{k} = 1,

falls Gast

k

seinen Hut zurückbekommt
und

X_{k} = 0

sonst.

Dann gilt

E [X_{k}] = P r [X_{k} = 1] = \frac{1}{n - k + 1} \prod_{m = 1}^{k - 1} \frac{n - m}{n - m + 1} = \frac{1}{n - k + 1} \frac{n - k + 1}{n} = \frac{1}{n}

.

Gedankengang zu dieser Formel:
Ich gehe ich davon aus, dass die Gäste sich oBdA
nacheinander wie nummeriert ihre Hüte abholen.
Dass Gast

k

seinen Hut bekommt, bedeutet dann also,
dass er ihn und somit alle vor ihm ihn nicht bekommen, also

\frac{1}{n - k + 1} \prod_{m = 1}^{k - 1} \frac{n - m}{n - m + 1}

(Für

k = 2

und

n = 4 z . B

\frac{3}{4} \cdot \frac{1}{3} = \frac{1}{4})

.

Nun rechne ich damit

E [X] = E [\sum_{k = 1}^{n} X_{k}] = \sum_{k = 1}^{n} E [X_{k}] = \sum_{k = 1}^{n} \frac{1}{n} = 1

.

Ich habe also das unglaubliche Ergebnis,
dass man unabhängig von

n

damit im Mittel damit rechnen darf,
dass genau ein Gast seinen Hut zurückbekommt.

Stimmt das ?

Roman-22

20:21 Uhr, 14.05.2025

Überraschend, aber richtig.
Sowohl der Erwartungswert als auch die Varianz der Fixpunktanzahl einer beliebigen Permutation ist 1.
Die Herleitung für den Erwartungswert 1 findet sich zB in
shorturl.at/gU05l
= people.eecs.berkeley.edu/%7Ejfc/cs174/lecs/lec2/lec2.pdf
auf Seite 3.

Randolph Esser aktiv_icon

20:29 Uhr, 14.05.2025

Tatsächlich habe ich gerade folgende Werte rechnen lassen:

A d P =

Anzahl der Permutationen,

S d F =

Summe der Fixpunkte über alle Permutationen

(\begin{matrix} n & A d P & S d F \\ 1 & 1 & 1 \\ 2 & 2 & 2 \\ 3 & 6 & 6 \\ 4 & 24 & 24 \\ 5 & 120 & 120 \\ 6 & 720 & 720 \\ 7 & 5040 & 5040 \end{matrix})

.

Also tatsächlich

E [X] = 1

Fixpunkt zumindest für alle

1 \leq n \leq 7

.

Ich finde das verblüffend !

Randolph Esser aktiv_icon

20:35 Uhr, 14.05.2025

Danke für die Bestätigung meiner abenteuerlichen Rechnung, Roman-22.

Wir lernen in der Informatik gerade so eine Art

Handkantenstochastik, heißt, wir verwenden

Formeln, Sätze, Tricks, die vorher nicht

wirklich sauber erarbeitet wurden.

So

z . B

. die Art, wie ich das da oben gerechnet habe.

Und bei dem Ergebnis fragt man dann schon nochmal nach...

(Und ein "damit" im vorletzten Satz meines ersten Beitrags kann weg.)

HAL9000

22:38 Uhr, 14.05.2025

Ja, das bekannte Problem "Anzahl Fixpunkte einer zufälligen Permutation" - in der Weihnachtszeit auch gern in der Verkleidung "Wichtelproblem".

Die genaue Verteilung ist

P (X_{n} = k) = \frac{1}{k!} \sum_{j = 0}^{n - k} \frac{{(- 1)}^{j}}{j!}

für

k = 0, 1, \dots, n

.

Für

n \to \infty

konvergiert das gegen die Poisson-Verteilung mit Parameter 1, d.h.

lim_{n \to \infty} P (X_{n} = k) = \frac{1}{e k!}

für

k = 0, 1, \dots

,

welche natürlich ebenfalls Erwartungswert 1 und Varianz 1 aufweist.

Randolph Esser aktiv_icon

00:58 Uhr, 15.05.2025

Yo, den Berkeley-Beweis habe ich jetzt auch gelesen
und verstanden. Dasselbe wie meine Rechnung,
nur dass

E [X_{k}]

sehr plausibel durch

\frac{(n - 1)!}{n!} = \frac{1}{n}

hergeleitet wird - ohne feierliches Schlange
stehen an der Hutausgabe.

Und Danke, HAL...

Wenn ich es ohne Indikatorvariablen versuche,
habe ich Probleme, es zu Ende zu rechnen:

Also, ich entwickle ganz feierlich mit dem Binomialkoeffizient,
fixpunktfreien Permutationen und somit der Sylvesterschen Siebformel

E [X] = \sum_{k = 0}^{n} k \frac{(\begin{matrix} n \\ k \end{matrix}) (n - k)! \sum_{m = 0}^{n - k} \frac{{(- 1)}^{m}}{m!}}{n!} = \sum_{k = 1}^{n} \frac{1}{(k - 1)!} \sum_{m = 0}^{n - k} \frac{{(- 1)}^{m}}{m!}

Das ist tatsächlich 1 für alle

n \in ℕ,

aber ich weiß nicht, wie ich es zu Ende rechnen soll,
dass es dann da steht...

Mein Ehrgeiz ist allerdings auch nicht besonders groß,
weil ich schon eine Lösung habe.
Die alternierende Summe nervt.
Hat jemand einen kleinen Kung-Fu-Trick ?

HAL9000

07:27 Uhr, 15.05.2025

Die Doppelsumme umfasst in den Indizes alle ganzen Zahlen

k, m

mit

1 \leq k \leq n

und

0 \leq m \leq n - k

, d.h.

1 \leq m + k \leq n

. Ersetzen wir

k

durch

j = m + k

, dann entspricht das einer äußeren Summation von

j = 1, 2, \dots, n

und einer inneren von

m = 0, 1, \dots, j - 1

\sum_{k = 1}^{n} \frac{1}{(k - 1)!} \sum_{m = 0}^{n - k} \frac{{(- 1)}^{m}}{m!} = \sum_{j = 1}^{n} \sum_{m = 0}^{j - 1} \frac{{(- 1)}^{m}}{(j - m - 1)! m!} \overset{!}{=} \sum_{j = 1}^{n} \frac{1}{(j - 1)!} \sum_{m = 0}^{j - 1} {(- 1)}^{m} (\begin{array}{c} j - 1 \\ m \end{array})

\overset{!}{=} \sum_{j = 1}^{n} \frac{1}{(j - 1)!} \cdot {(1 - 1)}^{j - 1} = \frac{1}{0!} = 1

denn es ist

0^{j - 1} = 0

für

j > 1

, demnach verbleibt nur der Summand für

j = 1

. Ob nun die Umindizierung oder vielleicht auch das Einbringen des Binomischen Satzes unter Kung-Fu einzuordnen ist, musst du entscheiden. ;-)

Ganz ähnlich klappt es für

n \geq 2

mit

E (X (X - 1)) = \sum_{k = 2}^{n} \frac{1}{(k - 2)!} \sum_{m = 0}^{n - k} \frac{{(- 1)}^{m}}{m!} = \sum_{j = 2}^{n} \sum_{m = 0}^{j - 2} \frac{{(- 1)}^{m}}{(j - m - 2)! m!} \overset{!}{=} \sum_{j = 2}^{n} \frac{1}{(j - 2)!} \sum_{m = 0}^{j - 2} {(- 1)}^{m} (\begin{array}{c} j - 2 \\ m \end{array})

\overset{!}{=} \sum_{j = 2}^{n} \frac{1}{(j - 2)!} \cdot {(1 - 1)}^{j - 2} = 1

und daraufhin

E (X^{2}) = E (X (X - 1)) + E (X) = 2

und weiter

V (X) = E (X^{2}) - {(E (X))}^{2} = 1

Randolph Esser aktiv_icon

09:46 Uhr, 15.05.2025

Ahhh, verstehe !

Die Umindizierung habe ich auch
mal als haptische Grafik angehängt.
Damit ist es sonnenklar,
man muss es nur tun, aber ich war gestern zu faul dafür.

Vielen Dank, Hal !

HAL9000

10:02 Uhr, 15.05.2025

Die haptische Grafik scheint unsichtbar zu sein (bedenke maximale Filegröße 500 kByte).

Ich vermute, du hast da ein Gitterpunkt-Dreieck gezeichnet, in der (k,m)- bzw. (j,m)-Ebene.

HAL9000

10:02 Uhr, 15.05.2025

(verfluchte Doppelposts)

Randolph Esser aktiv_icon

10:10 Uhr, 15.05.2025

Ja, das ist das Haptische daran.
Sie ist rein virtuell und kann
nur von der experimentellen Google KI
gelesen, verstanden und beschrieben werden.

Ja nö, kleiner Scherz. Hab das Anhängen vergessen.

Randolph Esser aktiv_icon

16:31 Uhr, 15.05.2025

Hier noch eine Compilation zum Thread...

HAL9000

18:53 Uhr, 15.05.2025

Ich kann noch was ergänzen: Varianzberechnung via Summe Indikatorvariablen im Fall

n \geq 2

.

Wie oben gesehen ist

X = \sum_{i = 1}^{n} X_{i}

, und es wurde da ja schon

E (X_{i}) = \frac{1}{n}

berechnet.

Wie bei jeder 0-1-Variablen ist

X_{i}^{2} = X_{i}

und damit auch

E (X_{i}^{2}) = E (X_{i}) = \frac{1}{n}

. Für

i \neq j

bekommen wir hingegen

E (X_{i} X_{j}) = P (X_{i} = 1, X_{j} = 1) = \frac{(n - 2)!}{n!} = \frac{1}{n (n - 1)}

,

weil bei genau

(n - 2)!

von insgesamt

n!

Permutationen an den beiden Stellen

i

und

j

jeweils Fixpunkte sind. Damit folgt

E (X^{2}) = E ({(\sum_{i = 1}^{n} X_{i})}^{2}) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} E (X_{i} X_{j}) = \sum_{i = 1}^{n} E (X_{i}^{2}) + \sum_{i = 1}^{n} \sum_{j = 1, j \neq i}^{n} E (X_{i} X_{j})

= n \cdot \frac{1}{n} + n (n - 1) \cdot \frac{1}{n (n - 1)} = 2

,

und in der Folge

V (X) = 2 - 1^{2} = 1

, wie oben schon mal gesehen.

1591012

1590986

	Status: nicht eingeloggt	Noch nicht registriert?