[9.8.01: Zwei Strategien ergänzt und einige falsche Zahlen berichtigt.]

Einige Annahmen

1. Der Standard des Hotels spielt bei der Suche keine Rolle.
2. Die Lage eines Hotels (am Ortseingang, in der Ortmitte, am Ortsende) hat keinen voraussehbaren Einfluß auf den Preis.
3. Die Hotels weisen keine bewertbaren Unterschiede auf. Der Reisende hat keine Präferenzen für irgendwelche Ausstattungsdetails oder die Zuvorkommenheit eines Portiers.
4. Der Reisende hat keinerlei Vorstellung von einem angemessenen Preis für 1 Übernachtung.
5. Es gibt keine theoretische Obergrenze für den Übernachtungspreis. Der Preis ist immer positiv und ganzzahlig. Die Preise sind nicht notwendig verschieden.
6. Der Reisende hat das Ziel ein Hotel zu finden, das möglichst preiswert ist, d.h. er sucht ein Hotel, das nach aufsteigend sortierten Preisen, möglichst nah am Minimalpreis ist. Es wird allein die Rangordnung der Hotels nach Preisen berücksichtigt. Die absoluten Unterschiede (in DM) werden nicht weiter bewertet.
7. Jedes Hotel legt seinen Preis völlig unabhängig von den anderen fest. Alle Preise sind gleichwahrscheinlich.

Gleichwertiges Urnenproblem

Strategien zur Auswahl

1. Ziehe eine Kugel und behalte sie (d.h. wähle das erste Hotel).
2. Ziehe k (>0) Kugeln zur Information. Nimm davon das Minimum. Ziehe nun weitere Kugeln. Entscheide Dich für die erste Kugel, die einen Wert kleiner dem Minimum hat. Wenn keine Kugel einen Wert kleiner dem Minimum haben sollte, dann behalte die letzte Kugel.
3. Wie 2. aber mit "kleiner gleich" statt "kleiner".
4. Ziehe k Kugeln zur Information. Bilde daraus den Mittelwert. Ziehe nun weitere Kugeln. Entscheide Dich für die erste Kugel, die einen Wert kleiner dem Mittelwert hat. Wenn keine Kugel einen Wert kleiner dem Mittelwert haben sollte, dann behalte die letzte Kugel.
5. Wie 4. aber mit "kleiner gleich" statt "kleiner".

• Gehe zunächst gemäß einer der o.g. Strategien vor. Ziehe die nächste Kugel.
  Wenn Sie kleiner als das Minimum oder dem Mittelwert der Stichprobe ist (abhg. von der Ausgangsstrategie), dann behalte die Kugel.
  Ansonsten erhöhe den Vergleichswert - und zwar das Minimum um 2/n bzw. bilde den Mittelwert mit dem neuen Wert und und suche weiter. (Variante 1)
• Gehe zunächst gemäß einer der o.g. Strategien vor. Ziehe die nächste Kugel. Ziehe die nächste Kugel.
  Wenn Sie kleiner als das Minimum oder der Mittelwert der Stichprobe ist, dann behalte die Kugel.
  Ansonsten setze den zuletzt gefundenen Wert als Vergleichswert (statt Minimum oder Maximum). (Variante 2)

Welches ist die beste Strategie für die Versuchsperson?

Weil 100 sehr viel ist, diskutiere ich diese Aufgabe mit kleinen Anzahlen von Kugeln.

Sei n die Anzahl der Kugeln.

2 Kugeln (n=2)

Mögliche angetroffene Rangordnungen, wie die Versuchperson sie ziehen könnte:

1 2
2 1
1 1

d.h. entweder wird die Kugel mit dem niedrigeren Wert zuerst oder zuletzt gezogen.
Es können auch beide Kugeln den gleichen Wert tragen.
Bei dieser Anzahl Kugeln ist es gleich, welche Strategie die Versuchsperson hat. Sie wird mit Wahrscheinlichkeit 2/3 bei der niedrigsten Zahl stoppen.

Nun 3 Kugeln (n=3)

Mögliche angetroffene Rangordnungen, wie die Versuchperson sie ziehen könnte:

1 1 1
1 1 2
1 2 1
1 2 2
2 1 2
2 2 1
2 1 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

13 mögliche Anordnungen der Ränge.

Rang der Kugel, die die Versuchsperson auswählt für verschiedene Strategie:


	Strategie	Verteilung der Ereignisse ingesamt	Durchschnittlicher Rang
1	Rang 1 = 6 mal Rang 2 = 5 mal Rang 3 = 2 mal	1.69
2 mit k=1	Rang 1 = 8 mal Rang 2 = 4 mal Rang 3 = 1 mal	1.46
2 mit k=2	Rang 1 = 6 mal Rang 2 = 5 mal Rang 3 = 2 mal	1.69
3 mit k=1	Rang 1 = 8 mal Rang 2 = 4 mal Rang 3 = 1 mal	1.46
4 mit k=1	Rang 1 = 8 mal Rang 2 = 4 mal Rang 3 = 1 mal	1.46
5 mit k=1	Rang 1 = 8 mal Rang 2 = 4 mal Rang 3 = 1 mal	1.46

Wenn die Versuchsperson immer die erste Kugel wählt, dann hat sie mit 6/13 Wahrscheinlichkeit die kleinste Zahl. Es gibt mehrere gleich gute Strategien, etwa wird die Versuchsperson in 8/13 der Fälle den kleinsten Wert wählen, wenn sie gemäß Strategie 2 zuerst eine Kugel zieht, dann fortfährt und sich danach für die erste Kugel mit kleinerem Wert entscheidet (oder die letzte akzeptieren muß).
Die Stichprobe kann zur Verbesserung des Ergebnisses nicht beliebig vergrößert werden. Wenn nämlich eine Stichprobe von k=2 Kugeln gezogen wird und dann die Entscheidung unter den letzten 3 - 2 = 1 Kugeln zu treffen ist, dann ist das Ergebnis das gleiche wie bei Strategie 1 - da hätte man auch das erst beste Hotel nehmen können.
Die Anwendung der Varianten liefert bei dieser kleinen Anzahl Kugeln keine Verbesserung.

4 Kugeln (n=4)

	Strategie	Verteilung der Ereignisse ingesamt	Durchschnittlicher Rang
1	Rang 1 = 26 mal Rang 2 = 25 mal Rang 3 = 18 mal Rang 4 = 6	2.05
2 mit k=1	Rang 1 = 42 mal Rang 2 = 22 mal Rang 3 = 9 mal Rang 4 = 2	1.61
2 mit k=1 Variante 1	Rang 1 = 44 mal Rang 2 = 21 mal Rang 3 = 8 mal Rang 4 = 2	1.57
2 mit k=1 Variante 2	Rang 1 = 42 mal Rang 2 = 24 mal Rang 3 = 8 mal Rang 4 = 1	1.57
2 mit k=2	Rang 1 = 36 mal Rang 2 = 22 mal Rang 3 = 13 mal Rang 4 = 4	1.80
2 mit k=2 Variante 1	Rang 1 = 36 mal Rang 2 = 22 mal Rang 3 = 13 mal Rang 4 = 4	1.80
2 mit k=2 Variante 2	Rang 1 = 36 mal Rang 2 = 22 mal Rang 3 = 13 mal Rang 4 = 4	1.80
3 mit k=1	Rang 1 = 42 mal Rang 2 = 22 mal Rang 3 = 9 mal Rang 4 = 1	1.61
3 mit k=1 Variante 1	Rang 1 = 44 mal Rang 2 = 22 mal Rang 3 = 7 mal Rang 4 = 2	1.56
3 mit k=1 Variante 2	Rang 1 = 42 mal Rang 2 = 24 mal Rang 3 = 8 mal Rang 4 = 1	1.57
3 mit k=2	Rang 1 = 40 mal Rang 2 = 22 mal Rang 3 = 9 mal Rang 4 = 4	1.69
3 mit k=2 Variante 1	Rang 1 = 40 mal Rang 2 = 22 mal Rang 3 = 9 mal Rang 4 = 4	1.69
3 mit k=2 Variante 2	Rang 1 = 40 mal Rang 2 = 20 mal Rang 3 = 11 mal Rang 4 = 4	1.72
2 mit k=1	Rang 1 = 42 mal Rang 2 = 22 mal Rang 3 = 9 mal Rang 4 = 2	1.61
2 mit k=1 Variante 1	Rang 1 = 44 mal Rang 2 = 21 mal Rang 3 = 8 mal Rang 4 = 2	1.57
2 mit k=1 Variante 2	Rang 1 = 42 mal Rang 2 = 24 mal Rang 3 = 8 mal Rang 4 = 1	1.57
2 mit k=2 Variante 1	Rang 1 = 36 mal Rang 2 = 22 mal Rang 3 = 13 mal Rang 4 = 4	1.8
2 mit k=2 Variante 2	Rang 1 = 36 mal Rang 2 = 22 mal Rang 3 = 13 mal Rang 4 = 4	1.8
4 mit k=1	Rang 1 = 42 mal Rang 2 = 22 mal Rang 3 = 9 mal Rang 4 = 2	1.61
4 mit k=1 Variante 1	Rang 1 = 44 mal Rang 2 = 22 mal Rang 3 = 7 mal Rang 4 = 2	1.56
4 mit k=1 Variante 2	Rang 1 = 42 mal Rang 2 = 24 mal Rang 3 = 8 mal Rang 4 = 1	1.57
4 mit k=2 Variante 1	Rang 1 = 40 mal Rang 2 = 22 mal Rang 3 = 9 mal Rang 4 = 4	1.69
4 mit k=2 Variante 2	Rang 1 = 40 mal Rang 2 = 22 mal Rang 3 = 9 mal Rang 4 = 4	1.69

Die beste Strategie ist eine Stichprobe von 1 Kugel zu ziehen und sich dann für die nächste Kugel mit niedrigerem Wert zu entscheiden, ansonsten aus der Stichprobe incl. des neuen Wertes einen neuen Mittelwert zu berechnen usw. Damit erreicht man in 44 von 75 Fällen (58.6%) den Rang 1.
Stichprobenumfang größer n/2 habe ich schon nicht mehr in Betracht gezogen. Ein Stichprobenumfang gleich n/2 ergibt hier nicht die besten Ergebnisse. Eine Stichprobe kann also auch zu groß sein.

Nun 5 Kugeln (n=5)

	Strategie	Verteilung der Ereignisse ingesamt	Durchschnittlicher Rang
1	Rang 1 = 150 mal Rang 2 = 149 mal Rang 3 = 134 mal Rang 4 = 84 Rang 5 = 24	2.05
2 mit k=1	Rang 1 = 276 mal Rang 2 = 152 mal Rang 3 = 77 mal Rang 4 = 30 Rang 5 = 6	1.77
2 mit k=1 Variante 1	Rang 1 = 292 mal Rang 2 = 149 mal Rang 3 = 68 mal Rang 4 = 26 Rang 5 = 6	1.71
2 mit k=1 Variante 2	Rang 1 = 260 mal Rang 2 = 177 mal Rang 3 = 83 mal Rang 4 = 20 Rang 5 = 1	1.75
2 mit k=2	Rang 1 = 262 mal Rang 2 = 136 mal Rang 3 = 85 mal Rang 4 = 46 Rang 5 = 12	1.90
2 mit k=2 Variante 1	Rang 1 = 288 mal Rang 2 = 127 mal Rang 3 = 72 mal Rang 4 = 42 Rang 5 = 12	1.82
2 mit k=2 Variante 2	Rang 1 = 262 mal Rang 2 = 160 mal Rang 3 = 82 mal Rang 4 = 31 Rang 5 = 6	1.81
3 mit k=1	Rang 1 = 276 mal Rang 2 = 152 mal Rang 3 = 77 mal Rang 4 = 30 Rang 5 = 6	1.77
3 mit k=1 Variante 1	Rang 1 = 236 mal Rang 2 = 202 mal Rang 3 = 80 mal Rang 4 = 21 Rang 5 = 2	1.80
3 mit k=1 Variante 2	Rang 1 = 244 mal Rang 2 = 178 mal Rang 3 = 93 mal Rang 4 = 25 Rang 5 = 1	1.81
4 mit k=1	Rang 1 = 276 mal Rang 2 = 152 mal Rang 3 = 77 mal Rang 4 = 30 Rang 5 = 6	1.77
4 mit k=1 Variante 1	Rang 1 = 284 mal Rang 2 = 173 mal Rang 3 = 62 mal Rang 4 = 19 Rang 5 = 3	1.67
4 mit k=1 Variante 2	Rang 1 = 260 mal Rang 2 = 177 mal Rang 3 = 83 mal Rang 4 = 20 Rang 5 = 1	1.75
5 mit k=1	Rang 1 = 276 mal Rang 2 = 152 mal Rang 3 = 77 mal Rang 4 = 30 Rang 5 = 6	1.77
5 mit k=1 Variante 1	Rang 1 = 266 mal Rang 2 = 177 mal Rang 3 = 72 mal Rang 4 = 23 Rang 5 = 3	1.74
5 mit k=1 Variante 2	Rang 1 = 244 mal Rang 2 = 178 mal Rang 3 = 93 mal Rang 4 = 25 Rang 5 = 1	1.81

Nun kommt es auf die Zielfunktion der Optimierung an. Soll die absolute Anzahl für "Rang 1" maximiert, oder der Durchschnitt der Ergebnisse minimiert werden?
Mit der lernenden Mittelwertstrategie mit einer Stichprobe der Größe 1 erreicht man 292 mal Rang 1; der Durchschnitt über alle möglichen Ausgänge ist 1.71.
Den besten Durchschnitt erzielt man mit der lernenden Mittelwertstrategie nach einer Stichprobe des Umfangs 2, nämlich 1.67.

An diesem Beispiel wird auch deutlich, daß die "Gleichheit genügt"-Strategien wohl nie die Gewinner sein werden.

6 Kugeln (n=6)

	Strategie	Verteilung der Ereignisse ingesamt	Durchschnittlicher Rang
2 mit k=1	Rang 1 = 2190 mal Rang 2 = 1258 mal Rang 3 = 717 mal Rang 4 = 362 Rang 5 = 132 Rang 6 = 24	1.94
2 mit k=1 Variante 1	Rang 1 = 2284 mal Rang 2 = 1261 mal Rang 3 = 692 mal Rang 4 = 308 Rang 5 = 114 Rang 6 = 24	1.88
2 mit k=1 Variante 2	Rang 1 = 1906 mal Rang 2 = 1459 mal Rang 3 = 888 mal Rang 4 = 359 Rang 5 = 70 Rang 6 = 1	1.98
2 mit k=2	Rang 1 = 2240 mal Rang 2 = 1098 mal Rang 3 = 657 mal Rang 4 = 430 Rang 5 = 210 Rang 6 = 48	2.02
2 mit k=2 Variante 1	Rang 1 = 2512 mal Rang 2 = 1063 mal Rang 3 = 532 mal Rang 4 = 342 Rang 5 = 186 Rang 6 = 48	1.88
2 mit k=2 Variante 2	Rang 1 = 2064 mal Rang 2 = 1407 mal Rang 3 = 795 mal Rang 4 = 328 Rang 5 = 24 Rang 6 = 8	1.92
2 mit k=3	Rang 1 = 1970 mal Rang 2 = 1064 Rang 3 = 749 mal Rang 4 = 551 Rang 5 = 283 Rang 6 = 66	2.21
4 mit k=1	Rang 1 = 2190 mal Rang 2 = 1258 Rang 3 = 717 mal Rang 4 = 362 Rang 5 = 132 Rang 6 = 24	1.94
4 mit k=1 Variante 1	Rang 1 = 2144 mal Rang 2 = 1547 Rang 3 = 700 mal Rang 4 = 229 Rang 5 = 55 Rang 6 = 8	1.83
4 mit k=1 Variante 2	Rang 1 = 1906 mal Rang 2 = 1459 Rang 3 = 888 mal Rang 4 = 359 Rang 5 = 70 Rang 6 = 1	1.98
4 mit k=2	Rang 1 = 2260 mal Rang 2 = 1510 Rang 3 = 545 mal Rang 4 = 242 Rang 5 = 102 Rang 6 = 24	1.82
4 mit k=2 Variante 1	Rang 1 = 2134 mal Rang 2 = 1665 Rang 3 = 637 mal Rang 4 = 173 Rang 5 = 58 Rang 6 = 16	1.80
4 mit k=2 Variante 2	Rang 1 = 1976 mal Rang 2 = 1573 Rang 3 = 785 mal Rang 4 = 286 Rang 5 = 59 Rang 6 = 4	1.90
4 mit k=3	Rang 1 = 1992 mal Rang 2 = 1570 Rang 3 = 648 mal Rang 4 = 293 Rang 5 = 144 Rang 6 = 36	1.96

Die beste Strategie (im Sinne maximale Anzahl von Rang 1) unter den untersuchten ist:

Ziehe 2 Kugeln von 6 Kugeln. Ermittle daraus das Minimum.
Ziehe dann weiter und behalte die Kugel, wenn deren Wert kleiner dem Minimum ist.
Variante 1: Ansonsten erhöhe den Vergleichswert - und zwar das Minimum - um 2/n und suche weiter.

Offene Fragen

Die Entscheidung für eine Strategie hängt vom Optimierungsziel ab. Will der Reisende im Mittel (Durchschnitt) einen günstigen Wert erreichen, oder sucht er möglichst den Rang 1? Es ist aus den bisher berechneten Fällen nicht ersichtlich, aber es scheint möglich, daß eine Verteilung der Ränge, die den besten durchschnittlichen Rang aufweist, nicht zugleich die Verteilung ist, die die absolut größte Chance auf den Rang 1 ergibt.
Die optimale Stichprobe ist nicht n/2. Für n=6 ist k=2 besser als k=3. Welches ist der optimale Stichprobenumfang?
Ist es tatsächlich richtig, die "kleiner gleich" Strategien grundsätzlich zu verwerfen?
Bei der anscheinend besten Strategie wird nach jedem "Fehlversuch" der Vergleichswert um 2/n erhöht. Warum gerade 2/n. Wie sind die Ergebnisse mit anderen Deltas? Mit 1/n und 3/n erhalte ich bei n=6 das gleiche. Mit delta=4/n beginnen die Ergebnisse sich wieder zu verschlechtern.
Gibt es andere Strategien, die ich nicht getestet habe, die aber erfolgversprechend sein könnten?
Von welchem Typ ist die Verteilungsfunktion der Zufallsvariablen für dieses Problem?

Experimentierfeld

Zur Förderung meiner "Anschauung" habe ich ein Programm geschrieben, mit dem ich die oben in Tabellen festgehaltenenen Werte ermittelt habe. Wer selbst experimentieren möchte finde das Programm hier. Sollte sich jemand für den Source-Code interessieren, dann möge er mir schreiben.
Allerdings ist das Experiment maximal mit 6 Kugeln erlaubt, mehr kann der Server nicht.
Viel Spaß beim Grübeln wünscht Matroid.

[Edit]
\(\endgroup\)
[Show outline only]