- Beim Next Card Bet, bei dem die Farbverteilung eines 52-Karten-Decks laufend verfolgt wird, endet die Kelly-Strategie entgegen ihrer üblichen Natur mit hoher Varianz bei einem Startkapital von $1 immer bei etwa $9,08
- Die Wettregel ist einfach: Wenn die verbleibenden roten Karten
rund schwarzen Kartenbgleich sind, wird ausgesetzt; andernfalls wird auf die Farbe mit den meisten verbleibenden Karten|r - b| / (r + b)des aktuellen Kapitals gesetzt - Selbst wenn man 10.000 gemischte Decks in Python durchläuft, bleibt das Endkapital im Bereich
9.081329549427776bis9.081329549427803und liefert ohne Schwankung einen höheren Gewinn als die Verdopplungsstrategie, die nur auf die letzte Karte setzt - Der Beweis verteilt das Anfangskapital gleichmäßig auf alle möglichen Rot/Schwarz-Anordnungen
(52 choose 26) = 495,918,532,948,104und konstruiert ein Portfolio, in dem nur die eine Teilstrategie, die mit dem tatsächlichen Deck übereinstimmt, 52-mal in Folge verdoppelt wird - Da die Veränderung des gesamten Portfoliokapitals genau dem konservativen Muster der Kelly-Strategie entspricht, wird die Kelly-Strategie, die normalerweise auch Geld verlieren kann, in diesem Spiel zu einer Strategie mit Varianz 0
Regeln und Intuition von Next Card Bet
- Die Kelly bet allocation strategy ist eine Methode, in Glücksspielsituationen anhand von Informationen oder Verzerrungen die Einsatzquote zu bestimmen
- Die gewöhnliche Kelly-Strategie gilt als aggressive Strategie mit hoher Varianz, und wer über die Kelly-Quote hinaus setzt, erhöht das Risiko des Ruins
- In Peter Winklers Mathematical Puzzles arbeitet diese Strategie im „Next Card Bet“ jedoch ohne Risiko und mit Varianz 0
- Das Spiel beginnt mit einem Standarddeck aus 52 Karten
- Es enthält 26 rote und 26 schwarze Karten
- Das Deck wird gemischt, dann werden die Karten nacheinander aufgedeckt und nicht wieder zurückgelegt
- Der Spieler kann einen beliebigen Anteil seines aktuellen Kapitals darauf setzen, ob die nächste Karte rot oder schwarz ist
- Die Auszahlung ist 1:1, das Startkapital beträgt $1
- Wenn man die bereits erschienenen Karten mitzählt, kennt man die Anzahl der Farben im unsichtbaren Restdeck
- Wenn man nicht bis zur letzten Karte setzt, kann man die Farbe der verbleibenden letzten Karte sicher wissen
- Mit dieser einfachen Strategie lässt sich das Kapital sicher verdoppeln, indem man auf die letzte Karte alles setzt
Kelly-Einsatzquote
- Die Kelly-Strategie wählt den Einsatz so, dass der Erwartungswert des Logarithmus des Endkapitals maximiert wird
- Bezeichnet man die verbleibenden roten Karten mit
rund die schwarzen mitbund giltr > b, dann ist die Wahrscheinlichkeit für eine rote Karter / (r + b) - Der erwartete Logarithmus des Kapitals wird anhand der folgenden Formel maximiert
P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction)
- An der Stelle, an der die Ableitung dieses Ausdrucks 0 wird, ergibt sich als Einsatzquote
(r - b) / (r + b) - Die Gesamtstrategie geht also nur das Risiko ein, das dem Unterschied zwischen den verbleibenden Kartenfarben entspricht
- Wenn
r = b, wird nicht gesetzt - Wenn
r > b, werden|r - b| / (r + b)des aktuellen Kapitals auf „red“ gesetzt - Wenn
b > r, werden|r - b| / (r + b)des aktuellen Kapitals auf „black“ gesetzt
- Wenn
Ergebnisse der Python-Simulation
- Das Python-Beispiel führt die Kelly-Strategie mit der Funktion
run_bets(is_red)ausstakestartet bei 1.0- Für jede Karte wird die Zahl der verbleibenden roten und schwarzen Karten aktualisiert
- Auf die häufiger verbleibende Farbe wird ein Anteil von
abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining)gesetzt - Ist die Vorhersage richtig, kommt der entsprechende Einsatz doppelt zurück; ist sie falsch, ist er verloren
- Als Zufallszahlengenerator wird
np.random.default_rng(2024)verwendet - Erzeugt man 10.000 Decks mit 26 roten Karten unter 52 Karten, ballen sich die Ergebnisse praktisch auf denselben Wert
- Minimum:
9.081329549427776 - Maximum:
9.081329549427803
- Minimum:
- Der Unterschied zwischen den Ergebnissen lag unter
1e-8, und in allen Durchläufen ergab sich ein Gewinn von etwa dem 9,08-Fachen des Startkapitals - Ein Gewinn um das 9,08-Fache liegt weit über der sicheren Verdopplung durch eine Wette nur auf die letzte Karte
Portfoliobeweis für Varianz 0
- Die Zahl möglicher Rot/Schwarz-Anordnungen der Karten beträgt
(52 choose 26) = 495,918,532,948,104 - Für ein korrekt gemischtes Deck verwendet man das Standardresultat, dass all diese Rot/Schwarz-Anordnungen mit gleicher Wahrscheinlichkeit auftreten
- Die Portfoliostrategie behandelt jede mögliche Rot/Schwarz-Anordnung als eigene Teilstrategie
- Jeder Teilstrategie wird
1 / (52 choose 26)des Anfangskapitals zugewiesen - Die Teilstrategien verwalten jeweils nur ihr eigenes Geld und verteilen nicht untereinander um
- Jede Teilstrategie nimmt an, dass ihr zugewiesenes Muster das tatsächliche Deck ist, und setzt bei jeder Karte den gesamten Betrag auf die entsprechende Farbe
- Jeder Teilstrategie wird
- Alle Teilstrategien, die nicht zum tatsächlichen Deck passen, gehen irgendwann bankrott, weil sie ihre gesamte Summe auf eine falsche Karte setzen
- Nur die eine Teilstrategie, die exakt mit dem tatsächlichen Deck übereinstimmt, trifft alle 52 Karten und wird zum
2^52-Fachen - Daher ist der Endertrag des gesamten Portfolios unabhängig von der Kartenreihenfolge immer derselbe
$1 / (52 choose 26) * 2^52- etwa $9,08
Gleichheit von Portfolio und Kelly-Strategie
- Im Portfolio sagen die noch nicht bankrotten Teilstrategien entweder rot oder schwarz für die nächste Karte voraus
- Wenn noch
rrote undbschwarze Karten übrig sind, folgt der Anteil der Vorhersagen der Teilstrategien dem Verhältnis der verbleibenden Farben - Wird die nächste Karte aufgedeckt, gehen die Gruppen mit falscher Vorhersage bankrott, und die Gruppe mit richtiger Vorhersage verdoppelt ihr Kapital
- Dadurch entspricht die Veränderung des gesamten Portfoliokapitals exakt dem konservativen Muster der Kelly-Strategie, die
|r - b| / (r + b)auf die häufiger verbleibende Farbe setzt - Die Kelly-Strategie hat hier deshalb Varianz 0, weil sie sich identisch zu einer Portfoliostrategie mit Varianz 0 verhält
Was hier anders ist als bei der gewöhnlichen Kelly-Strategie
- Die Kelly-Strategie maximiert normalerweise die erwartete Wachstumsrate des Logarithmus des Kapitals, ohne bankrottzugehen
- Darüber hinaus garantiert die gewöhnliche Kelly-Strategie jedoch nicht viel; man kann tatsächlich Geld verlieren, und in der Regel ist sie hoch volatil
- In diesem Kartenspiel führt selbst ein Verlust dazu, dass die Farbverteilung im Deck unausgeglichener wird und die späteren Bedingungen günstiger werden
- Wenn die Einsätze klein genug bleiben, kann der Verlust aus falschen Wetten später durch den größer gewordenen Vorteil ausgeglichen werden
- Diese Struktur erinnert an die Phasen Exploration und Exploitation in Problemen wie A/B-Tests
Weiterführende Hinweise
- Der Beweis basiert auf der Lösung in Winkler Mathematical Puzzles
- Dieser Beweis steht im Zusammenhang mit dem Stil von Thomas Cover, der später die Anlagestrategie des universal portfolio entwickelte
- Demo und Quellmaterial
- Kelly_cant_fail.ipynb: Notebook mit dem Beispiel aus dem Text
- card_count_fns.py: Funktionen zum Kartenzählen und Ausführen der Wetten
- dyn_prog.ipynb: Notebook zur dynamischen Programmierung für den Fall nicht teilbarer Geldeinheiten
- Demonstrating Kelly Betting with Chips: Erläuterung einer Demonstration mit Chips
1 Kommentare
Meinungen auf Hacker News
Damit diese Strategie immer aufgeht, muss sich der Einsatz unendlich fein aufteilen lassen.
Wenn sich zum Beispiel die 26 roten Karten oben im Deck ballen, sinkt der anfängliche Einsatz von $1.00 bis auf 0.000000134 und steigt dann wieder auf 9.08.
Der Erwartungswert landet ungefähr an der richtigen Stelle, aber die Varianz wächst schnell. Deshalb ist es auch abgesehen von diesem wichtigen Fall insgesamt ziemlich instabil.
Es ist eine dynamische Programmierungsstrategie bekannt, die bei einem Einsatz von $1 einen Gewinn von $8.08 garantiert. Durch einfaches Runden der Kelly-Strategie erhält man dieses Ergebnis nicht.
Wenn man einmal aussetzt, verpasst man eine profitable Serie oder einen bestimmten einzelnen Wurf mit großem Gewinn. Zeichnet man ein Preis-Zeit-Diagramm wie einen Renko-Chart, sieht es ähnlich aus wie jeder beliebige Chart eines handelbaren Instruments.
Im realen Aktien-/Krypto-/Devisenhandel bedeutet das, dass man nahezu jeden Trade machen muss; andernfalls sinkt die Performance der Strategie. So wie man im Experiment die Münze nicht wechselt, darf man auch beim Trading nicht das Instrument wechseln oder Trades verpassen, und man muss sehr lange durchhalten.
Es versteht sich von selbst, dass das enorme Konsistenz erfordert, und wenn Geld auf dem Spiel steht, steigt auch der Stress. Wenn man das täglich wiederholt, ist es geistig und körperlich so zehrend, dass es schwer ist, es lange durchzuhalten.
Eine interessante Nebenlinie zu Kelly ist Proebstings Paradoxon.
In der Wahrscheinlichkeitstheorie ist Proebstings Paradoxon ein Argument, das zu zeigen scheint, dass das Kelly-Kriterium zum Ruin führen kann. Mathematisch lässt es sich auflösen, wirft aber besonders bei der praktischen Anwendung von Kelly im Investment interessante Fragen auf. Edward O. Thorp diskutierte es erstmals 2008; benannt ist es nach seinem Urheber Todd Proebsting.
https://en.wikipedia.org/wiki/Proebsting%27s_paradox
Kelly ist also gut, wenn man die Wahrscheinlichkeiten kennt und sie sich nicht ändern.
Wenn man die Wahrscheinlichkeiten nicht kennt oder sie sich ändern können, dürfte der richtige Ansatz komplexer sein als Kelly.
Schöner Inhalt, aber das Portfolio-Argument wirkt wie ein unnötiger Umweg. Per Induktion ist ein zweizeiliger Beweis möglich.
Entsprechend beträgt die Auszahlung, wenn man Schwarz zieht und verliert, X * (1-(r-b)/(r+b)) * 2^(r+b-1) / (r+b-1 choose r) = X * 2^(r+b) * b / ((r+b) * (r+b-1 choose r)) = X * 2^(r+b) / (r+b choose r). QED
Wie in Problem Nr. 14 aus Timothy Falcons Interview-Buch zur quantitativen Finanzmathematik gibt es ein sehr ähnliches Kartenspiel, bei dem man Karten vom Deck aufdeckt und entscheidet, wann man aufhört. Rot zählt als $1, Schwarz als −$1.
Gwern hat das erklärt und auch Code geschrieben, der die optimale Stoppstrategie verifiziert: https://gwern.net/problem-14
Als Teenager entdeckte ich beim Card Counting, dass man immer in mehr als der Hälfte der Fälle richtigliegen kann, wenn man die Farbe tippt, von der noch mehr Karten im Deck übrig sind.
https://en.wikipedia.org/wiki/TRS-80_Model_100
Darauf schrieb ich eine Simulation, und sie scheiterte kein einziges Mal. Vor Kurzem fiel mir das wieder ein, und ich ließ ein Python-Skript 30 Millionen Mal laufen; auch dabei scheiterte es nicht.
Ich überlegte, wofür man das verwenden könnte, und kam auf (i) Wetten und (ii) Zauberei, aber beides wirkte nicht besonders vielversprechend.
Als Wette könnte man vielleicht $1000 gegen $10 des Gegenübers setzen, aber das ist kein Weg zu großem Gewinn, und wenn man einen Fehler macht oder betrogen wird, kann man viel Geld verlieren. Wenn ich noch einmal darüber nachdenke, wäre es vielleicht besser, das als Parlay, also als fortlaufende Kombiwette, neu zu formulieren.
Für Zauberei ist es zu langsam. Ich hatte mir einen Spruch zurechtgelegt wie: „Parapsychologen konnten mit ihren schicken Zener-Karten keine Präkognition zuverlässig nachweisen, aber ich habe ein Protokoll entwickelt, mit dem ich sie jedes Mal beweisen kann!“ Doch ich entschied, dass das nicht unterhaltsam genug ist. Ein ganzes Deck durchzugehen dauert, es wirkt nicht wie ein Wunder, und um bei p=0,01 die Nullhypothese auszuschließen, müsste man es 7-mal hintereinander machen. Vielleicht könnte das jemand mit besserer Bühnenpräsenz hinbekommen, aber ich habe es aufgegeben.
Manchmal stelle ich die Herleitung dieses Algorithmus als Rätsel, aber niemand konnte es lösen. Ich auch nicht.
https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
Selbst bei ausreichender Entropie sind 30 Millionen definitiv nicht genug.
Das Kelly-Kriterium ist eines meiner liebsten Konzepte aus der Spieltheorie und wird besonders häufig beim Bankroll-Management professioneller Glücksspieler wie Pokerspielern verwendet.
Es ist eine gute Methode, um verständlich zu machen, wie man Finanzen und Einsätze so verwaltet, dass man stetig vorankommt, ohne zu große Risiken oder den Ruin zu riskieren, wird in diesem Bereich aber oft falsch angewendet. Kelly behandelt binäre Ergebnisse; wendet man es auf Situationen an, in denen die Ergebnisse nicht binär sind, kann je nach mathematischer Betrachtung etwas herauskommen, das fast richtig aussieht, aber leicht danebenliegt.
Poker spielt man gegen andere Spieler, daher dürfte der Nutzen einer bestimmten Chipverteilung komplizierter sein als einfach nur die Anzahl der eigenen Chips.
Ich bin kein Pokerspieler.
Das Kelly-Kriterium lässt sich gut auf kontinuierliche, gleichzeitige und komplexe Allokationen verallgemeinern.
Alles, was man braucht, ist eine Liste wählbarer Handlungen und die gemeinsame Wahrscheinlichkeitsverteilung der Vermögensergebnisse nach jeder Handlung. Die Handlung kann auch eine zusammengesetzte Handlung mit kontinuierlichen Ergebnissen sein.
Beim Poker ist Gewinn oder Verlust nicht binär, sondern die gewonnenen oder verlorenen Beträge unterscheiden sich, daher verwendet man den Erwartungswert. Nachdem man einen ungefähren Erwartungswert berechnet hat, nutzt man zusätzlich einen Varianzrechner, zum Beispiel https://www.primedope.com/poker-variance-calculator/, um zu sehen, wie oft und wie viel man langfristig über eine bestimmte Anzahl von Händen wahrscheinlich gewinnt.
Ich vermute, man würde viel Zeit damit verbringen, weder zu gewinnen noch zu verlieren.
Es wäre eine bessere Demo gewesen, wenn man auf handlichere Zahlen reduziert hätte, zum Beispiel auf ein Deck mit 2 schwarzen und 2 roten Karten.
In Runde 1 gilt r = b, also wettet man nicht.
In Runde 2 setzt man 1/3 auf die Farbe, die in Runde 1 nicht erschienen ist.
Wenn man in Runde 3 in Runde 2 falschlag, hat man nur noch 2/3 des Einsatzes, kennt aber die Farben der nächsten beiden Karten und verdoppelt jedes Mal, sodass man nach Runde 3 bei 4/3 des ursprünglichen Einsatzes landet. Lag man richtig, hat man 4/3 des Einsatzes, aber es bleibt je eine rote und eine schwarze Karte, also wettet man in dieser Runde nicht.
In Runde 4 kennt man die Farbe der letzten Karte und verdoppelt das Geld, sodass man bei 8/3 des ursprünglichen Einsatzes landet.
Die Übungsaufgabe für die Leser ist dann, die Optimalität zu beweisen; das ist zwar ziemlich straightforward, aber ich glaube nicht, dass es einen kurzen Beweis gibt.
Wenn man also mit dem 4-Karten-Beispiel beginnt und danach die Baumdiagramme für 5 und 6 Karten zeigt, bleiben die Zahlen gut handhabbar, und man kann eine Intuition für die Induktion auf den allgemeinen Fall aufbauen.
In der Praxis gibt es viele Faktoren, die den Einsatz von Kelly schwieriger machen als im Spielzeugbeispiel.
Wie groß ist die Bankroll? Ist es der Kassenbestand? Das gesamte Nettovermögen? Das liquide Nettovermögen? Zukünftiges Erwerbseinkommen?
Je nach Größe der Bankroll spielen viele Faktoren hinein. Wenn die Bankroll zum Beispiel $100 beträgt und man alles verliert, ist das normalerweise keine große Sache. Beträgt sie aber $1 million, ist man deutlich zurückhaltender, sie diesem Risiko auszusetzen.
Was ist der Erwartungswert? Ist er bekannt? Stationär? Ist das Spiel ehrlich?
Je nach statistischen Eigenschaften des Erwartungswerts muss man den Ansatz für die Einsatzgröße stark anpassen. In Bereichen, in denen man den Erwartungswert nur schätzen kann und es viele Betrüger gibt, etwa beim Poker, muss man die Einsatzgröße unter großer Unsicherheit bestimmen.
Welche Einsatzbeträge sind möglich?
In der Realität gibt es keinen kontinuierlichen Bereich von Einsatzbeträgen. Meist sind nur diskrete Beträge möglich, etwa von $5 bis $500 in Schritten von $5 oder $25. Fällt die Bankroll zu niedrig, wird man aus dem Spiel gedrängt; steigt sie zu hoch, kann man den Gewinn nicht mehr maximieren.
Letztlich setzen professionelle Glücksspieler wegen dieser Komplexität oft nach Half Kelly oder Quarter Kelly.
Beim Trading gibt es Spreads und Gebühren, an Casinotischen den Rake.
Sehr elegant ist, dass das Ergebnis keine Varianz hat. Gerade deshalb fühlt es sich aber so an, als müsste es wegen der speziellen Struktur dieses Problems eine Strategie mit höherer erwarteter Rendite geben.
Weiß jemand, ob die Kelly-Strategie hier optimal ist?
Anfangs dachte ich, diese Strategien seien sehr unterschiedlich, aber ganz so ist es nicht. Auch die Kelly-Strategie verhält sich genauso, sobald nur noch eine Farbe übrig ist. Der Unterschied ist, dass diese Strategie davor gar nichts tut.
Trotzdem wirken die beiden wie Grenzfälle. Wenn nur noch eine Farbe übrig ist, alles darauf zu setzen, ist der einzig richtige Zug; letztlich geht es also darum, was man davor macht. Nichts zu tun und Kelly scheinen die einzigen Strategien zu sein, die gut aussehen.
Die Argumentation dazu verläuft allerdings nicht so natürlich wie der Beweis für Varianz 0, deshalb habe ich sie nicht aufgenommen. Auch der Originaltext schien eine spieltheoretische Beweisführung anzudeuten, indem er Unterstrategien innerhalb des Portfolios als „reine Strategien“ bezeichnete.
Dieses Problem und seine Lösung scheinen von Thomas Cover zu stammen.
An dieses konkrete Beispiel erinnere ich mich nicht, aber ich habe das Kelly-Kriterium in einem Kurs gelernt, den Thomas Cover unterrichtete. Er war einer meiner Lieblingsdozenten, und jede Diskussion mit ihm war interessant und wertvoll. RIP