imported>SchlurcherBot: Bot: http → https

2025-12-22T10:12:52Z

Bot: http → https

Neue Seite

Die '''Odds-Strategie''' (abgeleitet von [[Odds]]) bzw. der Bruss-Algorithmus oder die Bruss-[[Strategie (Spieltheorie)|Strategie]] (nach dem Entwickler des Verfahrens [[F. Thomas Bruss]]) ist ein mathematisches [[Algorithmus|Verfahren]] aus der [[Entscheidungstheorie]], mit dem man mit großer Wahrscheinlichkeit eine optimale „[[Gelegenheit]]“ aus einer [[Folge (Mathematik)|Folge]] von [[Ereignis (Wahrscheinlichkeitstheorie)|Ereignissen]] auswählen kann. Der Algorithmus zur Berechnung der Strategie ist außerdem selbst optimal.<ref>Bruss, Louchard: ''The Odds-algorithm based on sequential updating and its performance''. AAP, Nr. 41, 2009, S. 131–153. [https://www.ulb.ac.be/di/mcs/louchard/louchard.papers/genodds.ps (ps)]</ref>

Die Strategie kann angewendet werden, wenn eine zeitliche Abfolge von unabhängigen Ereignissen vorliegt, von denen einige als „Gelegenheiten“ gelten, und bei Eintreten einer Gelegenheit nicht bekannt ist, ob später noch eine andere oder bessere Gelegenheit folgt. Ein Beispiel ist die Situation eines Gebrauchtwagenhändlers oder Immobilienmaklers, der bei Vorliegen eines Kaufangebots nicht weiß, ob später ein weiterer Kaufinteressent ein besseres Angebot macht. Jedes bessere Angebot ist dann ein interessantes Ereignis (Gelegenheit), und das letzte interessante Ereignis, das man im Voraus nicht kennt, stellt das beste Angebot dar. Ein ''spezieller Fall'' für die Anwendung der Odds-Strategie ist das [[Sekretärinnenproblem]], in dem der bzw. die beste Kandidat/Kandidatin ausgewählt werden soll.

Die Odds-Strategie ist in mehreren Bereichen anwendbar, da sie beliebige Definitionen für „Gelegenheit“ bzw. „interessante Ereignisse“ zulässt und damit die Optimierung recht allgemeiner Zielfunktionen ermöglicht. So zum Beispiel ist es bei klinischen Versuchen aus ethischen Gründen optimal zu „stoppen“, wenn in einer Versuchsreihe einer festen Anzahl sequentiell zu behandelnder Patienten mit maximaler Wahrscheinlichkeit der letzte Behandlungserfolg verzeichnet wurde. Hier ist jede erfolgreiche Behandlung eine Gelegenheit. Gelegenheiten werden nicht qualitativ verglichen, doch mit der letzten Gelegenheit sind alle Erfolge erreicht, so dass allen weiteren Patienten die Behandlung erspart werden kann (siehe z. B. „Compassionate use“ und (Bruss, 2005).)

== Definitionen ==
Um die Odds-Strategie anwenden zu können, muss die Realität [[Mathematisches Modell|mathematisch modelliert]] werden. Dazu wird eine Folge von <math>n</math> Ereignissen angenommen, zum Beispiel könnte jedes Ereignis ein Kaufangebot sein. Die Ereignisse werden mit dem [[Index (Mathematik)|Index]] <math>k</math> von <math>1</math> bis <math>n</math> durchnummeriert: <math>E_1, E_2, \dots, E_k, \dots, E_n</math>. Jedes Ereignis <math>E_k</math> ist mit einer bestimmten [[Wahrscheinlichkeit]] <math>p_k</math> eine „Gelegenheit“.

Wenn <math>p_k</math> die Wahrscheinlichkeit dafür ist, dass <math>E_k</math> die gesuchte Gelegenheit ist, dann ist
:<math>q_k = 1-p_k</math>
die Wahrscheinlichkeit dafür, dass sie es nicht ist. Ihren Namen hat die Strategie vom [[Quotient]]en
:<math>r_k = \frac{p_k}{q_k},</math>
der englisch [[Odds]] genannt wird.

== Algorithmus ==
Die Strategie besteht darin, ab einem bestimmten Index <math>s</math>, dem sogenannten „Stoppindex“, die erste Gelegenheit wahrzunehmen, die besser ist als alle bisherigen Gelegenheiten.

Der Stoppindex <math>s</math> wird bestimmt, indem die Odds rückwärts aufgeschrieben werden: <math>r_n</math>, <math>r_{n-1}</math>, <math>r_{n-2}</math> usw. Dabei werden sie aufsummiert, und zwar solange, bis die [[Summe]] 1 erreicht oder übertroffen wird. Man definiert dazu die Summe
:<math>R_k = \sum_{i=k}^n r_i</math>
und dasjenige <math>k</math>, bei dem der Wert dieser Summe erstmals den Wert 1 erreicht oder übertrifft, bildet den Stoppindex <math>s</math>.

== Erfolgswahrscheinlichkeit ==
Die Odds-Strategie ist optimal unter der Vorgabe, von allen Gelegenheiten mit der höchsten Wahrscheinlichkeit die letzte Gelegenheit zu wählen. In der Anwendung wird dabei unter Gelegenheit oft ein Ereignis verstanden, das nach einem Kriterium besser als alle vorherigen Ereignisse ist, zum Beispiel ein besseres Angebot als alle vorgehenden Angebote. In diesem Kontext wählt die Odds-Strategie im Vergleich zu anderen Strategien das beste Angebot mit höchster Wahrscheinlichkeit.

Die Erfolgswahrscheinlichkeit für die Odds-Strategie, also die Wahrscheinlichkeit dafür, dass die letzte beziehungsweise beste Gelegenheit genutzt wird, ist: <math>W = R_s \cdot Q_s</math>. Hierbei ist
:<math>R_s = \sum_{i=s}^n r_i</math>
die Summe der Odds und
:<math>Q_s = \prod_{i=s}^n q_i</math>
die Wahrscheinlichkeit, dass unter den in Frage kommenden Ereignissen keine Gelegenheit ist.

== Beispiele ==
=== Sekretärinnenproblem ===
{| class="wikitable float-right"
! <math>k</math> || <math>p_k</math> || <math>q_k</math> || <math>r_k</math> || <math>R_k</math>
|-
| align="right"|16||align="right"|0,0625||align="right"|0,9375||align="right"|0,0667||align="right"|0,0667
|-
| align="right"|15||align="right"|0,0667||align="right"|0,9333||align="right"|0,0714||align="right"|0,1381
|-
| align="right"|14||align="right"|0,0714||align="right"|0,9286||align="right"|0,0769||align="right"|0,2150
|-
| align="right"|13||align="right"|0,0769||align="right"|0,9231||align="right"|0,0833||align="right"|0,2984
|-
| align="right"|12||align="right"|0,0833||align="right"|0,9167||align="right"|0,0909||align="right"|0,3893
|-
| align="right"|11||align="right"|0,0909||align="right"|0,9091||align="right"|0,1000||align="right"|0,4893
|-
| align="right"|10||align="right"|0,1000||align="right"|0,9000||align="right"|0,1111||align="right"|0,6004
|-
| align="right"| 9||align="right"|0,1111||align="right"|0,8889||align="right"|0,1250||align="right"|0,7254
|-
| align="right"| 8||align="right"|0,1250||align="right"|0,8750||align="right"|0,1429||align="right"|0,8682
|-
| align="right"| 7||align="right"|0,1429||align="right"|0,8571||align="right"|0,1667||align="right"|1,0349
|}

{{Hauptartikel|Sekretärinnenproblem}}
Angenommen, der Gebrauchtwagenverkäufer weiß, dass sich in einem Monat durchschnittlich 16 Kunden für ein Auto interessieren, und er möchte natürlich demjenigen Kunden verkaufen, der den höchsten Preis bietet. Ein Ereignis ist für den Gebrauchtwagenhändler also dann eine „Gelegenheit“, wenn es besser ist als alle vorherigen.

Für das erste Angebot gilt das mit [[Sicherheit]], also ist <math>p_1 = 1</math>. Für das zweite Angebot ist <math>p_2 = \tfrac{1}{2}</math>, wenn jede Ankunftsreihenfolge als gleich wahrscheinlich vorausgesetzt wird, allgemein gilt dann <math>p_k = \tfrac{1}{k}</math>. Daraus folgt <math>q_k = \tfrac{k-1}{k}</math> und <math>r_k = \tfrac{p_k}{q_k} = \tfrac{1}{k-1}</math>.

Da der Gebrauchtwagenhändler durchschnittlich 16 Kunden pro Monat hat, ist <math>n = 16</math>. Die nebenstehende Tabelle zeigt, dass der Stoppindex <math>s=7</math> ist, weil bei <math>k=7</math> die Summe <math>\textstyle R_k = \sum_{i=k}^n r_i</math> der rückwärts aufsummierten Odds den Wert 1 erstmals erreicht bzw. überschreitet. Der Gebrauchtwagenhändler muss also bis zum siebten Angebot warten, und dann das erste annehmen, das besser ist als alle vorherigen.

Die Erfolgswahrscheinlichkeit ist <math>W = R_s \cdot Q_s = 1{,}0349 \cdot 0{,}3750 = 0{,}3881</math>, also zirka 39 %. Mit anderen Worten: Der Gebrauchtwagenhändler verkauft das Auto in 39 % aller Fälle zum besten Preis.

=== Verallgemeinerungen ===
Das vorherige Beispiel ist das „Sekretärinnenproblem“. Die Lösung ist weniger interessant, sobald der Gebrauchtwagenhändler Zusatzinformationen besitzt. Hier zeigt sich der Vorteil der allgemeinen Definition der <math>r_k = \tfrac{p_k}{q_k}</math> in der Odds-Strategie. Nehmen wir als einfaches Beispiel an, der Gebrauchtwagenhändler kenne drei der letzten potentiellen Kunden und glaube aus Erfahrung zu wissen, dass jeder dieser drei den bisherigen Höchstpreis unabhängig voneinander mit der Wahrscheinlichkeit <math>p</math> überbietet. Wenn <math>p</math> mindestens den Wert <math>\tfrac{1}{4}</math> besitzt (bzw. die entsprechenden <math>r_k</math> mindestens den Wert <math>\tfrac{1}{3}</math>), so zeigt nun die Odds-Strategie, dass es optimal ist, zumindest auf eine weitere Angebotserhöhung zu setzen. Verallgemeinerungen für eine unbekannte Anzahl von potentiellen Kunden sind ebenfalls möglich mittels einer Integralversion (Bruss, 2000) der Odds-Strategie.

== Siehe auch ==
Verwandte Themen, bei denen man aus Teilinformation die optimale [[Entscheidung unter Unsicherheit|Entscheidung]] des Restproblems treffen kann:
* [[Gefangenenparadoxon]]
* [[Umtauschparadoxon]]
* [[Ziegenproblem]]
* [[Zwei-Zettel-Spiel]]

== Literatur ==
* [[F. Thomas Bruss]]: ''[http://www.wissenschaft-online.de/artikel/833993 Die Kunst der richtigen Entscheidung].'' In: ''[[Spektrum der Wissenschaft]].'' Juni 2005. Spektrum der Wissenschaft Verlagsgesellschaft mbH, Seiten 78–84, {{ISSN|0170-2971}}.
* F. Thomas Bruss: ''[https://www.jstor.org/stable/2652993 Sum the odds to one and stop]'', In: [[Annals of Probability]], Band 28, Seiten 1384–1391, 2000.

== Weblinks ==
* Bruss-Algorithmus http://www.p-roesler.de/odds.html

== Einzelnachweise ==
<references />

[[Kategorie:Wahrscheinlichkeitsrechnung]]
[[Kategorie:Stochastik]]
[[Kategorie:Spieltheorie]]
[[Kategorie:Entscheidungstheorie]]
[[Kategorie:Sportstatistik]]

Odds-Strategie - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https