Discussion:
Erwartungswert Hausmeisterschlüssel
Add Reply
Christian Steins
2018-09-18 18:42:39 UTC
Antworten
Permalink
Hi,
habe gerade einen Disput mit meinem Freund.

Rätsel:

Ein Hausmeister hat 6 Schlüssel. Um eine bestimmte Tür zu öffnen nimmt
er immer einen per Zufall und wenn der nicht passt dann den nächsten
wieder per Zufall. Probierte Schlüssel werden nicht nochmal probiert.

Was ist der Erwartungswert EW (wieviele Versuche benötigt der
Hausmeister im Durchschnitt)?

Per Simulation habe ich EW=3,3333 ermittelt, mein Freund durch
Berechnung EW=3,5.

Wer hat Recht?

Christian
Robin Koch
2018-09-18 22:14:24 UTC
Antworten
Permalink
Post by Christian Steins
Ein Hausmeister hat 6 Schlüssel. Um eine bestimmte Tür zu öffnen nimmt
er immer einen per Zufall und wenn der nicht passt dann den nächsten
wieder per Zufall. Probierte Schlüssel werden nicht nochmal probiert.
Was ist der Erwartungswert EW (wieviele Versuche benötigt der
Hausmeister im Durchschnitt)?
3,5
Post by Christian Steins
Per Simulation habe ich EW=3,3333 ermittelt, mein Freund durch
Berechnung EW=3,5.
Dann ist Deine Simulation möglicherweise fehlerhaft.

Bei Mir führen Simulation und Berechnung zum gleichen Ergebnis.

Sei X die Anzahl der getesteten Schlüssel.
Dann ist E(X) =
1/6 * 1
+ 5/6 * 1/5 * 2
+ 5/6 * 4/5 * 1/4 * 3
+ 5/6 * 4/5 * 3/4 * 1/3 * 4
+ 5/6 * 4/5 * 3/4 * 2/3 * 1/2 * 5
+ 5/6 * 4/5 * 3/4 * 2/3 * 1/2 * 1/1 * 6

= 1/6 * (1+2+3+4+5+6) = 21/6 = 7

Man beachte, dass die sich Brüche in jeder Zeile teleskopartig zu 1/6
kürzen lassen.

Das ganz erinnert mich an meinen WiPo-Lehrer, der uns früher dazu
anhalten wollte aktuelle Nachrichten zu verfolgen:

Der schrieb verdeckt eine Zahl an die Rückseite der Tafel, die kleiner
oder gleich der Anzahl der anwesenden Schüler war. Also eine Ganzzahl in
[1,n].

- Der Reihe nach sollte nun jeder Schüler eine Zahl aus dem selben
Zahlenbereich nennen.

- Genannte Zahlen wurden angeschrieben und durften kein zweites Mal
genannt werden.

- Wer die zuvor notierte Zahl "erriet", "durfte" über ein tagesaktuelles
Ereignis berichten, das der in den Nachrichten gesehen und gelesen hatte.


Ich fragte mich damals bereits, ob das Verfahren eigentlich fair sei.
Und tatsächlich hatte jeder Schüler die Wahrscheinlichkeit von 1/n dran
zu kommen:

- Der erste Schüler, klar, hat freie Auswahl und die Wsk. 1/n die
korrekte Zahl zu nennen.

- Für jeden weiteren Schüler steigt zwar die Wahrscheinlichkeit die
richtige Zahl zu nennen, wenn er dran kommt, dafür ist seine Wsk.
geringer, *dass* er drankommt.

Die Wahrscheinlichkeiten kürzen sich genauso weg wie oben. Und
tatsächlich ist es das selbe Experiment. (Ziehen ohne Zurücklegen bis zu
einem Treffer)
--
Robin Koch
Christian Steins
2018-09-19 06:16:15 UTC
Antworten
Permalink
Post by Robin Koch
3,5
Post by Christian Steins
Per Simulation habe ich EW=3,3333 ermittelt, mein Freund durch
Berechnung EW=3,5.
Dann ist Deine Simulation möglicherweise fehlerhaft.
Danke, dann werde ich mal gucken, wo mein Bug liegt.


Grüße
Christian
Christian Gollwitzer
2018-09-19 07:35:44 UTC
Antworten
Permalink
Post by Christian Steins
Post by Robin Koch
3,5
Post by Christian Steins
Per Simulation habe ich EW=3,3333 ermittelt, mein Freund durch
Berechnung EW=3,5.
Dann ist Deine Simulation möglicherweise fehlerhaft.
Danke, dann werde ich mal gucken, wo mein Bug liegt.
Dein Ergebnis ist 20/6 statt 21/6. Womöglich hast Du einfach anders
gezählt: Wenn Du beim ersten Treffer den Schlüssel findest, dann ist das
"1".

Christian
Christian Steins
2018-09-20 08:24:13 UTC
Antworten
Permalink
Post by Christian Gollwitzer
Post by Christian Steins
Post by Robin Koch
Post by Christian Steins
Per Simulation habe ich EW=3,3333 ermittelt, mein Freund durch
Berechnung EW=3,5.
Dann ist Deine Simulation möglicherweise fehlerhaft.
Danke, dann werde ich mal gucken, wo mein Bug liegt.
Dein Ergebnis ist 20/6 statt 21/6. Womöglich hast Du einfach anders
gezählt: Wenn Du beim ersten Treffer den Schlüssel findest, dann ist das
"1".
Der Bug lag am anderen Ende. Wenn im fünften Versuch nur noch ein
Schlüssel übrig ist, muss es der ja sein, habe ich mir gedacht
und die Anzahl Versuche auf max. 5 begrenzt.

Ohne diese Begrenzung liefert die Simulation 3,5.

Christian
Andreas Leitgeb
2018-09-19 10:22:58 UTC
Antworten
Permalink
Post by Robin Koch
Das ganz erinnert mich an meinen WiPo-Lehrer, der uns früher dazu
Der schrieb verdeckt eine Zahl an die Rückseite der Tafel, die kleiner
oder gleich der Anzahl der anwesenden Schüler war. Also eine Ganzzahl in
[1,n].
- Der Reihe nach sollte nun jeder Schüler eine Zahl aus dem selben
Zahlenbereich nennen.
- Genannte Zahlen wurden angeschrieben und durften kein zweites Mal
genannt werden.
- Wer die zuvor notierte Zahl "erriet", "durfte" über ein tagesaktuelles
Ereignis berichten, das der in den Nachrichten gesehen und gelesen hatte.
Ich fragte mich damals bereits, ob das Verfahren eigentlich fair sei.
Und tatsächlich hatte jeder Schüler die Wahrscheinlichkeit von 1/n dran
- Der erste Schüler, klar, hat freie Auswahl und die Wsk. 1/n die
korrekte Zahl zu nennen.
- Für jeden weiteren Schüler steigt zwar die Wahrscheinlichkeit die
richtige Zahl zu nennen, wenn er dran kommt, dafür ist seine Wsk.
geringer, *dass* er drankommt.
Die Wahrscheinlichkeiten kürzen sich genauso weg wie oben. Und
tatsächlich ist es das selbe Experiment. (Ziehen ohne Zurücklegen bis zu
einem Treffer)
Fair ist es nur solange, wie es keine "side-channels" zur Kenntnis der
versteckten Zahl gibt.

Nach hinreichend vielen solchen Spielchen könnte einer der Schüler
den "Zufallsgenerator" des Lehrers durchschauen, einer mit gutem
Gehör könnte die Schreibgeräusche der Kreide identifizieren, noch einer
könnte eine spy-cam mit Blick auf die Tafelhinterseite verstecken ...

Angenommen, m (m<n) der Schüler "wissen" die Zahl (was ihnen aber nur
dann was nutzt, wenn sie jeweils nicht als letzte zum zahlenrufen kommen)
dann erhöht sich die "Chance" auf die richtige Zahl abhängig davon,
wieviele (m') der wissenden davor zum "Raten" drankamen (und bewusst
was anderes auswählten) von 1/n auf 1/(n-m').

(just for fun)
Christian Gollwitzer
2018-09-19 19:15:22 UTC
Antworten
Permalink
Post by Andreas Leitgeb
Fair ist es nur solange, wie es keine "side-channels" zur Kenntnis der
versteckten Zahl gibt.
Nach hinreichend vielen solchen Spielchen könnte einer der Schüler
den "Zufallsgenerator" des Lehrers durchschauen, einer mit gutem
Gehör könnte die Schreibgeräusche der Kreide identifizieren, noch einer
könnte eine spy-cam mit Blick auf die Tafelhinterseite verstecken ...
Und es ist nur fair, wenn entweder der Lehrer oder alle(!) Schüler
perfekte Zufallszahlengeneratoren sind. Menschen sind aber in der Regel
sehr schlechte Zufallszahlengeneratoren. Wenn also sowohl der Lehrer als
auch mindestens ein Schüler einen Bias haben, ist das Ergebnis nicht
mehr gleichverteilt.

Als simples Beispiel kann man sich das hier anschauen:

https://www.afiniti.com/corporate/rock-paper-scissors

Bei Stein-Schere-Papier kann es eigentlich keine Gewinnstrategie geben,
man hat immer 1/3 Gewinn/Verlust/Patt, wenn einer der Partner ein
perfekter Zufallsgenerator ist. In dem Beispiel versucht die KI das
Verhalten des Gegners zu lernen und so eine möglichst starken Bias
Richtung Gewinn zu erzielen.

Aber auch wenn ees nicht gewollt wäre, wenn z.B. Schüler 1 eine
Korrelatino mit dem Lehrer aufweist, alle anderen nicht, dann kommen die
Schüler 2..N dementsprechend seltener dran.

Christian
Robin Koch
2018-09-20 07:48:26 UTC
Antworten
Permalink
Post by Christian Gollwitzer
Und es ist nur fair, wenn entweder der Lehrer oder alle(!) Schüler
perfekte Zufallszahlengeneratoren sind. Menschen sind aber in der Regel
sehr schlechte Zufallszahlengeneratoren. Wenn also sowohl der Lehrer als
auch mindestens ein Schüler einen Bias haben, ist das Ergebnis nicht
mehr gleichverteilt.
Vielleicht hätte ich "theoretisch fair" schreiben sollen. :-)
Post by Christian Gollwitzer
https://www.afiniti.com/corporate/rock-paper-scissors
Bei Stein-Schere-Papier kann es eigentlich keine Gewinnstrategie geben,
man hat immer 1/3 Gewinn/Verlust/Patt, wenn einer der Partner ein
perfekter Zufallsgenerator ist.
Funfact: Es gibt eine RPS-Weltmeisterschaft. Die beste (und einzige)
Strategie ist: Zufallsreihen auswendig zu lernen und zu spielen.
Ich weiß nicht, ob es signifikante Unterschiede in der Qualität der
Zufallsreihen gibt, oder ob man sich irgendwie anders einen Vorteil
erspielen kann.
--
Robin Koch
Lothar Frings
2018-09-19 15:39:22 UTC
Antworten
Permalink
Post by Christian Steins
Hi,
habe gerade einen Disput mit meinem Freund.
Ein Hausmeister hat 6 Schlüssel. Um eine bestimmte Tür zu öffnen nimmt
er immer einen per Zufall und wenn der nicht passt dann den nächsten
wieder per Zufall. Probierte Schlüssel werden nicht nochmal probiert.
Was ist der Erwartungswert EW (wieviele Versuche benötigt der
Hausmeister im Durchschnitt)?
Per Simulation habe ich EW=3,3333 ermittelt, mein Freund durch
Berechnung EW=3,5.
Wer hat Recht?
Ich habe meinen guten Bekannten Edward
gefragt, und der sagt 0,36.
Stephan Gerlach
2018-09-21 22:43:13 UTC
Antworten
Permalink
Post by Christian Steins
Hi,
habe gerade einen Disput mit meinem Freund.
Ein Hausmeister hat 6 Schlüssel. Um eine bestimmte Tür zu öffnen nimmt
er immer einen per Zufall und wenn der nicht passt dann den nächsten
wieder per Zufall. Probierte Schlüssel werden nicht nochmal probiert.
Was ist der Erwartungswert EW (wieviele Versuche benötigt der
Hausmeister im Durchschnitt)?
Es ist mutmaßlich der Erwartungswert der Zufallsvariable

X = "Anzahl Versuche, bis die Tür geöffnet ist"

gesucht. Angenommen, man hat n Schlüssel, man wählt in jedem Versuch aus
den verbleibenden Schlüsseln mit gleicher Wahrscheinlichkeit einen aus,
und probiert einen probierten Schlüssel nicht nochmal, dann ergibt sich
(komischerweise!?), daß X diskret gleichverteilt mit Parameter n auf der
Menge {1;...;n} ist.
D.h. für alle k Element {1;...;n} gilt
P(X=k) = 1/n.

Das kann man z.B. anhand eines Baumdiagramms rechnerisch nachvollziehen.
Folglich gilt für den Erwartungswert E(X) nach der bekannten Formel für
Gleichverteilung auf {1;...;n}:

E(X) = (n+1)/2.
Post by Christian Steins
Per Simulation habe ich EW=3,3333 ermittelt, mein Freund durch
Berechnung EW=3,5.
Wer hat Recht?
Für n=6 kommt mit der Formel für die Gleichverteilung
E(X) = (6+1)/2 = 7/2 = 3,5
raus.

Es ist nicht klar, was genau deine Simulation macht bzw. wie die
funktioniert?!
Interessant wäre, was deine Simulation für die einfacheren Fälle n=1 (1
Schlüssel) oder n=2 (2 Schlüssel) liefert.
--
Post by Christian Steins
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Loading...