info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: Optimierung
31 views
Skip to first unread message
Diedrich Ehlerding
Jan 27, 2023, 6:30:34 AM1/27/23
to
Stefan Ram meinte:
> In einem Restaurant werden hintereinander fünf Gerichte gezeigt.
> Wenn einem ein Gericht gezeigt wird, weiß man noch nicht,
> welche Gerichte danach gezeigt werden werden. Man kann es sagen,
> wenn man das gezeigte Gericht essen will, aber kann eine
> Entscheidung später nicht mehr ändern. Man darf genau eines
> von den fünf Gerichen essen. Würde man die ersten vier Gerichte
> ablehnen, müßte man dann unweigerlich das fünfte essen.
>
> Wie kann man vorgehen, um die Wahrscheinlichkeit zu maximieren,
> ein Gericht zu erhalten, das einem möglichst gut gefällt?
Ich schlage folgende Strategie vor:
Man schaut sich zwei Gerichte an und wählt dann das erste, das besser
aussieht als die beiden zuerst gesehenen - oder aber eben das letzte.
Ich gehe davon aus, dass es eine eindeutige Rangfolge gibt, also keine
zwei Gerichte gleich gut sind. Und ich gehe davon aus, dass die
Reihenfolge, in der die Gerichte gezeigt werden, zufällig ist.
Ich schreibe im folgenden die "Güte" der Gerichte mit Ziffern 1,2,3,4,5
(größer ist besser) und bezeichne mit x eine der Ziffern 1,2,3, mit y
eine der Ziffern 1 und 2 und mit z eine der Zahlen 1,2,3,4. Es gibt
5!=120 Permutationen von 1,2,3,4,5. Die Strategie erwischt das optimale
Gericht in folgenden Fällen (Reihenfolge, in denen die Gerichte gezeigt
werden):
x45xx, x4x5x, x4xx5, 4xxx5, 4xx5x, 4x5xx (also immer dann wenn das
zweitbeste Gericht unter den ersten beiden auftaucht und das beste unter
den letzten). Ferner gewinnt man auch in den Fällen xx54x und xx5x4,
sowie in den Fällen 3yy54 und y3y54. Von xxx gibt es jeweils 6
Permutationen, von yy jeweils 2, also sind das insgesamt 6*8+2*2=52
Fälle, in denen man das beste Gericht erwischt. Demgegenüber verliert
man in folgenden Fällen: 5zzzz, z5zzz, xxx45, xx45x, xx4x5 und yy354. Es
gibt 24 Permutationen von zzzz, insgesamt sind das also 2*24+3*6+2=68 -
wir haben also alle 120 Fälle betrachtet.
Die "Erfolgsquote", in der man das beste Gericht erwischt ist dabei also
52/120 oder ca. 43,3%
Betrachten wir noch alternative Straegien: Wenn wir die ersten drei
Gerichte vorbeiziehen lassen, dann ist die Wahrscheinlichkeit, dass das
beste schon unter den ersten drei ist, bereits 60%, damit können wir
also keinesfalls ein besseres Ergebnis als 40% erzielen, und das ist
bereits schlechter als die obige 43%-Strategie.
Lassen wir nur ein Gericht vorbeiziehen und wählen dann das nächste, das
besser ist, gewinnen wir nur in den Fällen 15xxx, 25xxx, 35xxx 45xxx,
4x5xx, 4xx5x, 4xxx5 (insgesamt 42 Fälle), ferner 21534, 21543, 31524,
31542, 32514, 32541, 32154, 31254; insgesamt also 50 Gewinne von 120,
also nur ca 41,7 % - etwas schlechter als die obige strategie.
Bleibt noch die Zufallsauswahl - die erwischt nur in 20% der Fälle das
Optimum
--
gpg-Key (DSA 1024) D36AD663E6DB91A4
fingerprint = 2983 4D54 E00B 8483 B5B8 C7D1 D36A D663 E6DB 91A4
HTML-Mail wird ungeleſen entſorgt.
> In einem Restaurant werden hintereinander fünf Gerichte gezeigt.
> Wenn einem ein Gericht gezeigt wird, weiß man noch nicht,
> welche Gerichte danach gezeigt werden werden. Man kann es sagen,
> wenn man das gezeigte Gericht essen will, aber kann eine
> Entscheidung später nicht mehr ändern. Man darf genau eines
> von den fünf Gerichen essen. Würde man die ersten vier Gerichte
> ablehnen, müßte man dann unweigerlich das fünfte essen.
>
> Wie kann man vorgehen, um die Wahrscheinlichkeit zu maximieren,
> ein Gericht zu erhalten, das einem möglichst gut gefällt?
Ich schlage folgende Strategie vor:
Man schaut sich zwei Gerichte an und wählt dann das erste, das besser
aussieht als die beiden zuerst gesehenen - oder aber eben das letzte.
Ich gehe davon aus, dass es eine eindeutige Rangfolge gibt, also keine
zwei Gerichte gleich gut sind. Und ich gehe davon aus, dass die
Reihenfolge, in der die Gerichte gezeigt werden, zufällig ist.
Ich schreibe im folgenden die "Güte" der Gerichte mit Ziffern 1,2,3,4,5
(größer ist besser) und bezeichne mit x eine der Ziffern 1,2,3, mit y
eine der Ziffern 1 und 2 und mit z eine der Zahlen 1,2,3,4. Es gibt
5!=120 Permutationen von 1,2,3,4,5. Die Strategie erwischt das optimale
Gericht in folgenden Fällen (Reihenfolge, in denen die Gerichte gezeigt
werden):
x45xx, x4x5x, x4xx5, 4xxx5, 4xx5x, 4x5xx (also immer dann wenn das
zweitbeste Gericht unter den ersten beiden auftaucht und das beste unter
den letzten). Ferner gewinnt man auch in den Fällen xx54x und xx5x4,
sowie in den Fällen 3yy54 und y3y54. Von xxx gibt es jeweils 6
Permutationen, von yy jeweils 2, also sind das insgesamt 6*8+2*2=52
Fälle, in denen man das beste Gericht erwischt. Demgegenüber verliert
man in folgenden Fällen: 5zzzz, z5zzz, xxx45, xx45x, xx4x5 und yy354. Es
gibt 24 Permutationen von zzzz, insgesamt sind das also 2*24+3*6+2=68 -
wir haben also alle 120 Fälle betrachtet.
Die "Erfolgsquote", in der man das beste Gericht erwischt ist dabei also
52/120 oder ca. 43,3%
Betrachten wir noch alternative Straegien: Wenn wir die ersten drei
Gerichte vorbeiziehen lassen, dann ist die Wahrscheinlichkeit, dass das
beste schon unter den ersten drei ist, bereits 60%, damit können wir
also keinesfalls ein besseres Ergebnis als 40% erzielen, und das ist
bereits schlechter als die obige 43%-Strategie.
Lassen wir nur ein Gericht vorbeiziehen und wählen dann das nächste, das
besser ist, gewinnen wir nur in den Fällen 15xxx, 25xxx, 35xxx 45xxx,
4x5xx, 4xx5x, 4xxx5 (insgesamt 42 Fälle), ferner 21534, 21543, 31524,
31542, 32514, 32541, 32154, 31254; insgesamt also 50 Gewinne von 120,
also nur ca 41,7 % - etwas schlechter als die obige strategie.
Bleibt noch die Zufallsauswahl - die erwischt nur in 20% der Fälle das
Optimum
--
gpg-Key (DSA 1024) D36AD663E6DB91A4
fingerprint = 2983 4D54 E00B 8483 B5B8 C7D1 D36A D663 E6DB 91A4
HTML-Mail wird ungeleſen entſorgt.
Message has been deleted
Rainer ausdemSpring
Jan 27, 2023, 9:36:52 AM1/27/23
to
Diedrich Ehlerding schrieb am Freitag, 27. Januar 2023 um 12:30:34 UTC+1:
> Stefan Ram meinte:
>
> > In einem Restaurant werden hintereinander fünf Gerichte gezeigt.
> > Wenn einem ein Gericht gezeigt wird, weiß man noch nicht,
> > welche Gerichte danach gezeigt werden werden. Man kann es sagen,
> > wenn man das gezeigte Gericht essen will, aber kann eine
> > Entscheidung später nicht mehr ändern. Man darf genau eines
> > von den fünf Gerichen essen. Würde man die ersten vier Gerichte
> > ablehnen, müßte man dann unweigerlich das fünfte essen.
> >
> > Wie kann man vorgehen, um die Wahrscheinlichkeit zu maximieren,
> > ein Gericht zu erhalten, das einem möglichst gut gefällt?
Das ist sehr bekannt. Wenn ich mich recht erinnere wird das als Übungsaufgabe in Wahrscheinlichkeits-/Maßtheorie I als Übungsaufgabe gestellt.
> Stefan Ram meinte:
>
> > In einem Restaurant werden hintereinander fünf Gerichte gezeigt.
> > Wenn einem ein Gericht gezeigt wird, weiß man noch nicht,
> > welche Gerichte danach gezeigt werden werden. Man kann es sagen,
> > wenn man das gezeigte Gericht essen will, aber kann eine
> > Entscheidung später nicht mehr ändern. Man darf genau eines
> > von den fünf Gerichen essen. Würde man die ersten vier Gerichte
> > ablehnen, müßte man dann unweigerlich das fünfte essen.
> >
> > Wie kann man vorgehen, um die Wahrscheinlichkeit zu maximieren,
> > ein Gericht zu erhalten, das einem möglichst gut gefällt?
n Angebote für ein gebrauchtes Auto oder ähnlich. Was ist die beste Strategie?
Außerdem soll das Verhalten bei n gegen unendlich betrachtet werden.
Rainer
neu...@tuhh.de
Jan 27, 2023, 10:06:25 AM1/27/23
to
Diedrich Ehlerding schrieb am Freitag, 27. Januar 2023 um 12:30:34 UTC+1:
https://www.spektrum.de/kolumne/das-sekretaerinnenproblem-wie-findet-man-die-passendste-bewerberin/2036923
Die Lösung ist 1/e-tel., also hier Ganzzahl(5/e)= 2.
Ich kannte das Problem als Rhein-Burgen-tour:
Man macht eine Rheinfahrt entlang N Burgen und möchte "die Schönste" fotografieren, hat aber nur noch ein Bild.
Die Lösung ist, man läßt N/e Burgen an sich vorbei ziehen und Fotografiert die nächst Schönste (oder die Letzte)!
Die damalige Herleitung erinnere ich nicht mehr, sie ähnelte aber der aus dem Spektrum Artikel
VG SiggiN.
Thomas Dorner
Jan 30, 2023, 12:08:03 PM1/30/23
to
r...@zedat.fu-berlin.de (Stefan Ram) writes:
> r...@zedat.fu-berlin.de (Stefan Ram) writes:
>>In einem Restaurant werden hintereinander fünf Gerichte gezeigt.
>>Wenn einem ein Gericht gezeigt wird, weiß man noch nicht,
>>welche Gerichte danach gezeigt werden werden. Man kann es sagen,
>>wenn man das gezeigte Gericht essen will, aber kann eine
>>Entscheidung später nicht mehr ändern. Man darf genau eines
>>von den fünf Gerichen essen. Würde man die ersten vier Gerichte
>>ablehnen, müßte man dann unweigerlich das fünfte essen.
>
> Das letzte Gericht könnte alles Mögliche sein,
> so daß der Erwartungswert der Bewertungsfunktion
> auf der Skala von 0 bis 1 gleich 0,5 ist.
Hmm, ich lese in der Aufgabenstellung nicht, daß die Qualitäten
normalverteilt sind (oder zumindest das gesamte Spektrum abbilden).
Wenn die 5 Gerichte aber alle eher mau sind (Mensa? ;-), nehme ich immer
das letzte, z.B.:
0.2 0.4 0.5 0.3 0.1
Dietrichs Ansatz ist davon unabhängig (und hätte im speziellen Beispiel
das beste Gericht erwischt :-).
Nur so als Gedanke.
Viele Grüße, Thomas
--
Adresse gilt nur kurzzeitig!
> r...@zedat.fu-berlin.de (Stefan Ram) writes:
>>In einem Restaurant werden hintereinander fünf Gerichte gezeigt.
>>Wenn einem ein Gericht gezeigt wird, weiß man noch nicht,
>>welche Gerichte danach gezeigt werden werden. Man kann es sagen,
>>wenn man das gezeigte Gericht essen will, aber kann eine
>>Entscheidung später nicht mehr ändern. Man darf genau eines
>>von den fünf Gerichen essen. Würde man die ersten vier Gerichte
>>ablehnen, müßte man dann unweigerlich das fünfte essen.
>
> so daß der Erwartungswert der Bewertungsfunktion
> auf der Skala von 0 bis 1 gleich 0,5 ist.
Hmm, ich lese in der Aufgabenstellung nicht, daß die Qualitäten
normalverteilt sind (oder zumindest das gesamte Spektrum abbilden).
Wenn die 5 Gerichte aber alle eher mau sind (Mensa? ;-), nehme ich immer
das letzte, z.B.:
0.2 0.4 0.5 0.3 0.1
Dietrichs Ansatz ist davon unabhängig (und hätte im speziellen Beispiel
das beste Gericht erwischt :-).
Nur so als Gedanke.
Viele Grüße, Thomas
--
Adresse gilt nur kurzzeitig!
Thomas Dorner
Jan 31, 2023, 8:08:02 AM1/31/23
to
r...@zedat.fu-berlin.de (Stefan Ram) writes:
> Jetzt ist natürlich die Frage: Welcher Zufallszahlengenerator
> ist denn nun "der richtige" für den Vergleich? Und mit welcher
> Begründung?
>
> Das Prinzip der maximalen Entropie sagt, daß bei vollkommener
> Unkenntnis, Gleichverteilung die Annahme mit dem kleinsten
> Vorurteil ist. Das wäre ZA.
Gleichverteilung sagt aber noch nichts darüber aus, wie der
zugrundeliegende Bereich zustande kommt, hier also, wie wurde der Koch
ausgewählt.
Das erinnert mich ein bischen an eine schöne Aufgabe in einem Buch von
Martin Gardner, die ein Problem von Joseph Bertrand beschrieb:
https://de.wikipedia.org/wiki/Bertrand-Paradoxon_(Wahrscheinlichkeitstheorie)
Es gibt mehrere richtige Lösungen, und ohne weitere Einschränkungen ist
keine "richtiger" als die andere.
> Hierzu ein Beispiel: Es trifft eine Nachricht von Außerirdischen
> ein, die per Funk schon Deutsch gelernt haben. Sie sagen, daß sie
> eine Zahl aus der Menge {0, 1} bestimmt haben, und wir raten sollen
> welche. Da wir mit diesen Außerirdischen noch keine Erfahrungen
> haben, haben wir noch keine Statistik der Zahlenwerte, die sie in
> der Vergangenheit schon bestimmt haben. Ein Anbieter von Wetten
> bittet nun seinen Hausmathematiker die Wahrscheinlichkeit für "0"
> zu bestimmen. Nach dem Prinzip der maximalen Entropie wäre sie 0,5.
Hier ist alles eindeutig vorgegeben, also ist auch das Ergebnis eindeutig.
> Jetzt ist natürlich die Frage: Welcher Zufallszahlengenerator
> ist denn nun "der richtige" für den Vergleich? Und mit welcher
> Begründung?
>
> Das Prinzip der maximalen Entropie sagt, daß bei vollkommener
> Unkenntnis, Gleichverteilung die Annahme mit dem kleinsten
> Vorurteil ist. Das wäre ZA.
Gleichverteilung sagt aber noch nichts darüber aus, wie der
zugrundeliegende Bereich zustande kommt, hier also, wie wurde der Koch
ausgewählt.
Das erinnert mich ein bischen an eine schöne Aufgabe in einem Buch von
Martin Gardner, die ein Problem von Joseph Bertrand beschrieb:
https://de.wikipedia.org/wiki/Bertrand-Paradoxon_(Wahrscheinlichkeitstheorie)
Es gibt mehrere richtige Lösungen, und ohne weitere Einschränkungen ist
keine "richtiger" als die andere.
> Hierzu ein Beispiel: Es trifft eine Nachricht von Außerirdischen
> ein, die per Funk schon Deutsch gelernt haben. Sie sagen, daß sie
> eine Zahl aus der Menge {0, 1} bestimmt haben, und wir raten sollen
> welche. Da wir mit diesen Außerirdischen noch keine Erfahrungen
> haben, haben wir noch keine Statistik der Zahlenwerte, die sie in
> der Vergangenheit schon bestimmt haben. Ein Anbieter von Wetten
> bittet nun seinen Hausmathematiker die Wahrscheinlichkeit für "0"
> zu bestimmen. Nach dem Prinzip der maximalen Entropie wäre sie 0,5.
Hier ist alles eindeutig vorgegeben, also ist auch das Ergebnis eindeutig.
Thomas Dorner
Jan 31, 2023, 12:07:45 PM1/31/23
to
r...@zedat.fu-berlin.de (Stefan Ram) writes:
> Aber nach der Aufgabenstellung ist der Koch ein System, das
> Gerichte liefert, und wir wissen aus der Aufgabenstellung
> nur, daß die Qualität der Gerichte zwischen 0 und 1 liegt.
[Korinthen]
Das steht nicht in der Aufgabenstellung, sondern in dem vorgestellten
Lösungsansatz.
[/Korinthen]
;-)
vgt
> Aber nach der Aufgabenstellung ist der Koch ein System, das
> Gerichte liefert, und wir wissen aus der Aufgabenstellung
> nur, daß die Qualität der Gerichte zwischen 0 und 1 liegt.
[Korinthen]
Das steht nicht in der Aufgabenstellung, sondern in dem vorgestellten
Lösungsansatz.
[/Korinthen]
;-)
vgt
0 new messages