Optimale Fragestrategien / Informationsentropie [ehemals "Erwartungswert"]

Neue Frage »

Franzi1986 Auf diesen Beitrag antworten »
Optimale Fragestrategien / Informationsentropie [ehemals "Erwartungswert"]
HI!
Habe da mal eine Aufgabe...

Eine Urne enthält die Nummern 1, 2, 3, 4, 5, 6 mit den Häufigkeiten 1, 2, 3, 4, 5, 6. Wieviel Fragen braucht man im Mittel (bei optimaler Fragestellung), um eine zufällig gezogene Zahl zu erraten?

OK, habe auch schon zwei Lösungen, aber es gibt noch eine bessere und auf die komme ich nicht.

Meine Lösung:

Zunächst:

6 ==> 29% (6/21)
5 ==> 24% (5/21)
4 ==> 19% (4/21)
3 ==> 14% (3/21)
2 ==> 9% (2/21)
1 ==> 4% (1/21)

und dann:

1. Weg:

Simpellösung

1. Ist es die 6?
2. Ist es die 5?
3. Ist es die 4?
4. Ist es die 3?
5. Ist es die 2?

1 erledigt sich ja mit der letzten Frage.

Hier ergibt sich:
E(X) = 1*6/21 + 2*5/21 + 3*4/21 + 4*3/21 + 5*2/21 + 5*1/21
= 55/21

Also im Mittel 2,62 Fragen.


2. Weg:

die Fragen:

1. Ist die Zahl kleiner als 5?
2. Iist die Zahl ungerade/gerade?
3. Ist die Zahl kleiner als 3?

Hier ergibt sich:

E(X) = 2*6/21 + 2*5/21 + 3*4/21 + 3*3/21 + 3*2/21 + 3*1/21
= 52/21

Also im Mittel 2,48 Fragen.

Es soll aber eine Lösung mit im Mittel 47/21 Fragen geben.

Hat jemand eine Idee, probiere schon voll lange. Komme aber nicht auf diese Ergebnis.
AD Auf diesen Beitrag antworten »

Ich nehme an, die Häufigkeiten 1..6 stehen für

Die Informationsentropie dieser Verteilung ist

.

Es kann keine Fragestrategie geben, die im Mittel mit weniger Fragen auskommt, also auch keine mit Fragen.

Da hat man dir einen Bären aufgebunden. smile
 
 
Franzi1986 Auf diesen Beitrag antworten »

Mein Mathelehrer meinte er wäre auf die Lösung gekommen und eine Schülerin hätte die Lösung auch schon mal herausbekommen...also eigentlich müsste es gehen...
Welche Fragen verbergen sich eigentlich hinter der Formel oder wie wird die Formel hergeleitet? Kann sie nicht ganz nachvollziehen verwirrt
AD Auf diesen Beitrag antworten »

Das würde jetzt zu weit führen. Wenn du es wirklich ernst meinst, dann empfehle ich

http://de.wikipedia.org/wiki/Informationsentropie .


EDIT: Titel geändert. "Erwartungswert" trifft nicht den Kern der Sache.
Franzi1986 Auf diesen Beitrag antworten »

Frage mich, wie man auf diese Lösung kommt...aber naja vielleicht würd uns unser Lehrer seine Lösung nochmal erläutern...Dann schreibe ich nochmal ins Forum...Danke trotzdem

CIAOI Wink
AD Auf diesen Beitrag antworten »
RE: Optimale Fragestrategien / Informationsentropie [ehemals "Erwartungswert"]
Dann pass gut auf die angebliche "Lösung" des Lehrers auf, bei 47/21 hat er nämlich irgendwo einen Bock geschossen.

Zitat:
Original von Franzi1986
2. Weg:

die Fragen:

1. Ist die Zahl kleiner als 5?
2. Iist die Zahl ungerade/gerade?
3. Ist die Zahl kleiner als 3?

Hier ergibt sich:

E(X) = 2*6/21 + 2*5/21 + 3*4/21 + 3*3/21 + 3*2/21 + 3*1/21
= 52/21

Nicht schlecht, hier kommt aber eine etwas bessere Variante:

1. Ist die Zahl kleiner als 5?

Falls nein:

2. Ist es die 5?

Falls ja:

2. Ist es die 4?
3. Ist es die 3?
4. Ist es die 2?

Macht insgesamt Erwartungswert

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

Mehr ist mit deterministischen Strategien bezogen auf eine Einzelauswahl auch nicht drin, da 50/21 bereits kleiner als die oben berechnete Entropie ist.
Franzi1986 Auf diesen Beitrag antworten »

Ok, Danke schon mal Tanzen . Auf jeden Fall schon mal besser wie meine Strategie. Habe mich nochmal mit meinem Lehrer verständigt.
Die Formel (welche ich gestern bei Wikipedia nachvollzogen habe) deutet auf das Idealergebnis der Intervallhalbierungsstrategie hin (kann nicht
genau passen, da es für 6 kein 2^n mit ganzzahligem n gibt) und deswegen kann man die 47/21 nicht mit einer allgemeingültigen Formel errechnen, da eine solche Formel die Fragenzahl für eine Strategie ermittelt, die durchgängig angewandt wird. Die 47/21 erhält man nur, wenn man eine "Mischstrategie" benutzt, d.h. 2 verschiedene Strategien nacheinander anwendet.

Vielleicht hat ja jetzt jemand eine Idee, probiere auf jeden Fall weitersmile

Ciaoi
AD Auf diesen Beitrag antworten »

Zitat:
Original von Franzi1986
Die 47/21 erhält man nur, wenn man eine "Mischstrategie" benutzt, d.h. 2 verschiedene Strategien nacheinander anwendet.

Vielleicht hast du mich nicht verstanden: Wer denkt, sich über die Gesetze der Informationsentropie hinwegsetzen zu können (ob mit direkter oder mit Mischstrategie), glaubt sicher auch an die Existenz von Perpetuum mobile, also die Nichtgültigkeit des Energieerhaltungssatzes.

Oder nochmal deutlich:

Ansage Es gibt keine Strategie, die im Mittel mit 47/21 Fragen auskommt!!! Auch Lehrer können Unsinn erzählen.

Wenn du immer noch drauf beharrst, wirst du einen Hernn Shannon in seinem Grab mächtig in Rotation versetzen.
Franzi1986 Auf diesen Beitrag antworten »

OK, ok... Prost
AD Auf diesen Beitrag antworten »

Ich will dich ja nur vor unsinniger Probiererei bewahren. Und wenn dein Lehrer glaubt, was mit 47/21 gefunden zu haben, dann hat er sich schlicht verrechnet.

Oder er denkt an eine andere Interpretations-Möglichkeit: Es werden nach und nach alle 21 Kugeln aus der Urne entnommen. Dann verbessert sich natürlich nach und nach die Informationslage (wenn man natürlich die Ziehungen aufmerksam verfolgt), und man braucht von Kugel zu Kugel im Mittel weniger Fragen.

Betrachtet man alle vollständigen 21-er-Ziehungen aus der Grundmenge

122333444455555666666

dann ist die Informationsentropie der Gesamziehung gleich

,

d.h., es genügen 41 Fragen, um die 21-er-Ziehung als Ganzes in der Ziehungsreihenfolge richtig zu tippen.

Das ist aber ein völlig anderes Problem, als von dir beschrieben.
Franzi1986 Auf diesen Beitrag antworten »

Ich beschreibe nochmal, damit es keine Missverständnisse gibt...also ich habe 21 Kugeln mit der Häufigkeit:

6*Nummer 6
5*Nummer 5
4*Nummer 4
3*Nummer 3
2*Nummer 2
1*Nummer 1

und jemand zieht eine Kugel aus der Urne und diese soll erraten werden.

Dann ist die Anzahl der Fragen gefragt, die man im Mittel braucht, um sie Zahl
zu erraten...weiß auch nicht, kam auch noch nicht auf dieses Ergebnis...naja was solls...ich werde es sehen...Danke auf jeden Fall Wink
AD Auf diesen Beitrag antworten »

Dann bleibt's dabei:

ist die durch die Theorie bestimmte Untergrenze, die nicht unterboten werden kann, und wenn man sonstwas anstellt. Praktische Verfahren erreichen diese Grenze oftmals sogar nicht einmal, zumindest nicht bei "Einzelraten" wie hier.
Franzi1986 Auf diesen Beitrag antworten »

Hat sich heute herausgestellt, dass mein Lehrer die Zahlen vertauscht hatte. Kann ja mal passieren. Habe noch lange ausprobiert, bin aber auch nur auf 51/21 gekommen und dies ist auch das bestmöglichste Ergebnis.
Also hat es sich jetzt erledigt. Danke nochma Wink

Ciaoi Big Laugh
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »