- Dans Next Card Bet, où l’on suit en continu la répartition des couleurs d’un paquet de 52 cartes, la stratégie de Kelly, contrairement à sa nature habituelle à forte variance, termine toujours avec un capital initial de 1 $ à environ 9,08 $
- La règle de mise est simple : si les cartes rouges restantes
ret les cartes noires restantesbsont en nombre égal, on passe ; sinon, on mise sur la couleur la plus nombreuse une fraction du capital courant égale à|r - b| / (r + b) - Même en exécutant en Python 10 000 paquets mélangés, le capital final reste dans la plage
9.081329549427776à9.081329549427803, produisant un gain supérieur à la stratégie du doublement qui ne mise que sur la dernière carte, sans fluctuation - La preuve consiste à répartir uniformément le capital initial entre les
(52 choose 26) = 495,918,532,948,104séquences rouge/noir possibles, puis à construire un portefeuille où une seule sous-stratégie, celle qui correspond au paquet réel, double 52 fois de suite - L’évolution totale du capital de ce portefeuille correspond au profil de rendement de la stratégie de Kelly : ainsi, dans ce jeu, une stratégie de Kelly qui peut normalement perdre de l’argent devient une stratégie à variance nulle
Règles et intuition de Next Card Bet
- La stratégie d’allocation de mise de Kelly est une méthode qui détermine la fraction à miser en exploitant une information ou un biais dans une situation de jeu
- La stratégie de Kelly classique est connue comme une stratégie agressive à forte variance, et miser davantage que la fraction de Kelly peut accroître le risque de ruine
- Dans « Next Card Bet », présenté dans Mathematical Puzzles de Peter Winkler, cette stratégie fonctionne sans risque, avec une variance nulle
- Le jeu commence avec un paquet standard de 52 cartes
- Il contient 26 cartes rouges et 26 cartes noires
- Après mélange, les cartes sont révélées une par une, sans être remises dans le paquet
- Le joueur peut miser une fraction arbitraire de son capital courant sur le fait que la prochaine carte sera rouge ou noire
- Le paiement est de 1:1, et le capital initial est de 1 $
- En comptant les cartes déjà sorties, on connaît le nombre de cartes de chaque couleur qui restent dans le paquet invisible
- Si l’on ne mise pas avant la dernière carte, on connaît avec certitude la couleur de la carte restante
- Cette stratégie simple permet de miser tout son capital sur la dernière carte et de le faire passer en toute sécurité à 2 fois sa valeur
Fraction de mise de Kelly
- La stratégie de Kelly choisit la mise qui maximise l’espérance du logarithme du capital final
- Si l’on note
rle nombre de cartes rouges restantes etble nombre de cartes noires restantes, avecr > b, la probabilité que la prochaine carte soit rouge estr / (r + b) - L’espérance du logarithme du capital est maximisée à partir de l’expression suivante
P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction)
- Au point où la dérivée de cette expression est nulle, la fraction à miser devient
(r - b) / (r + b) - La stratégie complète ne prend un risque qu’à hauteur de l’écart entre les deux couleurs restantes
- Si
r = b, on ne mise pas - Si
r > b, on mise sur « red » une fraction|r - b| / (r + b)du capital courant - Si
b > r, on mise sur « black » une fraction|r - b| / (r + b)du capital courant
- Si
Résultats de simulation Python
- L’exemple Python exécute la stratégie de Kelly avec la fonction
run_bets(is_red)stakecommence à 1.0- À chaque carte, le nombre de cartes rouges et noires restantes est mis à jour
- On mise sur la couleur la plus nombreuse une fraction
abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining) - Si la carte correspond, le montant misé revient doublé ; sinon, il est perdu
- Le générateur de nombres aléatoires utilise
np.random.default_rng(2024) - Après avoir généré 10 000 paquets contenant 26 cartes rouges parmi 52, les résultats convergent en pratique vers la même valeur
- Valeur minimale :
9.081329549427776 - Valeur maximale :
9.081329549427803
- Valeur minimale :
- L’écart entre les résultats était inférieur à
1e-8, et chaque exécution a produit un gain d’environ 9,08 fois le capital initial - Un gain de 9,08 fois est nettement supérieur à la stratégie qui consiste à ne miser que sur la dernière carte pour obtenir sans risque un doublement
Preuve par portefeuille à variance nulle
- Le nombre de séquences possibles de cartes rouges et noires est
(52 choose 26) = 495,918,532,948,104 - On utilise le résultat standard selon lequel, dans un paquet correctement mélangé, toutes ces séquences rouge/noir apparaissent avec la même probabilité
- La stratégie de portefeuille prend chaque séquence rouge/noir possible comme une sous-stratégie distincte
- Elle alloue à chaque sous-stratégie une fraction
1 / (52 choose 26)du capital initial - Les sous-stratégies ne gèrent que leur propre argent et ne le redistribuent pas entre elles
- Chaque sous-stratégie suppose que la séquence qui lui est assignée est le paquet réel, et mise à chaque carte l’intégralité de son capital sur la couleur correspondante
- Elle alloue à chaque sous-stratégie une fraction
- Toutes les sous-stratégies différentes du paquet réel finissent par miser tout leur capital sur une mauvaise carte et font faillite
- Une seule sous-stratégie, celle qui correspond exactement au paquet réel, prédit correctement les 52 cartes et voit son capital multiplié par
2^52 - Le rendement final du portefeuille total est donc toujours le même, quel que soit l’ordre des cartes
1 $ / (52 choose 26) * 2^52- Environ 9,08 $
Équivalence entre le portefeuille et la stratégie de Kelly
- Les sous-stratégies du portefeuille qui ne sont pas encore ruinées prédisent que la prochaine carte sera rouge ou noire
- Lorsqu’il reste
rcartes rouges etbcartes noires, la proportion des prédictions des sous-stratégies suit la proportion des couleurs restantes - Quand la prochaine carte est révélée, le groupe qui a fait la mauvaise prédiction fait faillite, tandis que le groupe qui a correctement prédit voit son capital doubler
- À ce moment-là, l’évolution du capital total du portefeuille correspond exactement au profil de rendement de la stratégie de Kelly qui mise
|r - b| / (r + b)sur la couleur la plus nombreuse - La raison pour laquelle la stratégie de Kelly a une variance nulle est qu’elle évolue exactement comme cette stratégie de portefeuille, elle-même à variance nulle
Différences avec la stratégie de Kelly classique
- La stratégie de Kelly maximise généralement le taux de croissance attendu du logarithme du capital tout en évitant la ruine
- Mais, en dehors de cela, la stratégie de Kelly classique ne garantit pas grand-chose : elle peut réellement perdre de l’argent et elle est généralement à forte variance
- Dans ce jeu de cartes, même lorsqu’une perte survient, la répartition des couleurs dans le paquet devient plus déséquilibrée, ce qui rend les conditions suivantes plus favorables
- Si les mises sont suffisamment petites, l’avantage accru par la suite compense le capital perdu lors d’une mauvaise mise
- Cette structure rappelle les phases d’exploration et d’exploitation dans des problèmes comme les tests A/B
Références
- La preuve est fondée sur la solution de Winkler Mathematical Puzzles
- Cette preuve est liée au style de Thomas Cover, qui a ensuite créé la stratégie d’investissement de portefeuille universel
- Démonstrations et sources
- Kelly_cant_fail.ipynb : notebook de l’exemple présenté dans l’article
- card_count_fns.py : fonctions de comptage des cartes et d’exécution des mises
- dyn_prog.ipynb : notes de programmation dynamique pour le cas où le capital est constitué d’unités indivisibles
- Demonstrating Kelly Betting with Chips : explication d’une démonstration avec des jetons
1 commentaires
Commentaires sur Hacker News
Cette stratégie ne tient toujours que si l’on peut fractionner la mise à l’infini
Par exemple, si les 26 cartes rouges sont regroupées en haut du paquet, la mise initiale de $1.00 descend jusqu’à 0.000000134 avant de remonter à 9.08
L’espérance reste à peu près au bon niveau, mais la variance augmente rapidement. Donc, même au-delà de ce cas important, l’ensemble est assez instable
Une stratégie de programmation dynamique garantissant un gain de $8.08 à partir d’une mise de $1 est connue. On n’obtient pas ce résultat en arrondissant simplement la stratégie de Kelly
Si vous en manquez un, vous pouvez rater une séquence rentable ou un coup unique très rémunérateur. Si l’on trace le graphique prix/temps comme un graphique Renko, il ressemble à peu près à n’importe quel graphique d’actif
Dans le trading réel d’actions/crypto/devises, cela signifie qu’il faut exécuter presque toutes les transactions, sinon la performance de la stratégie se dégrade. Comme on ne change pas de pièce pendant l’expérience, en trading il ne faut pas changer d’actif ni manquer des transactions, et il faut tenir cela très longtemps
Inutile de dire qu’il faut une constance énorme, et le stress augmente quand de l’argent est en jeu. À force de répéter cela chaque jour, l’usure mentale et physique devient importante, ce qui rend difficile de tenir sur la durée
Un aparté intéressant sur Kelly est le paradoxe de Proebsting
En théorie des probabilités, le paradoxe de Proebsting est un argument qui semble montrer que le critère de Kelly peut mener à la ruine. On peut le résoudre mathématiquement, mais il soulève des questions intéressantes sur l’application pratique de Kelly, surtout en investissement. Edward O. Thorp l’a évoqué pour la première fois en 2008, et le nom vient de son créateur, Todd Proebsting
https://en.wikipedia.org/wiki/Proebsting%27s_paradox
Autrement dit, Kelly est utile si l’on connaît les probabilités et qu’elles restent fixes
Si l’on ne connaît pas les probabilités, ou si elles peuvent changer, la bonne approche doit sans doute être plus complexe que Kelly
C’est élégant, mais l’argument de portefeuille semble être un détour inutile. Une preuve par récurrence en deux lignes suffit
De même, en cas de défaite après avoir tiré une carte noire, le paiement est 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). CQFD
Il existe un jeu de cartes très proche, où l’on retourne les cartes du paquet en décidant quand s’arrêter, comme dans le problème n°14 du livre d’entretiens en finance quantitative de Timothy Falcon. Le rouge vaut $1, le noir vaut −$1
Gwern l’explique et a aussi écrit du code pour vérifier la stratégie d’arrêt optimale : https://gwern.net/problem-14
Adolescent, il a découvert qu’en faisant du card counting pour deviner la couleur la plus présente dans le paquet, on pouvait toujours obtenir un taux de réussite supérieur à la moitié.
Il a écrit une simulation sur
https://en.wikipedia.org/wiki/TRS-80_Model_100
et elle n’a jamais échoué. Cela lui est revenu récemment, il l’a donc relancée 30 millions de fois avec un script Python, et là encore, aucun échec.
En réfléchissant à un usage possible, il a pensé à (i) des paris, (ii) de la magie, mais aucune des deux pistes ne semblait très prometteuse.
Pour les paris, il pourrait miser 1000 $ contre les 10 $ de l’adversaire, mais ce n’est pas une voie vers de gros profits, et une erreur ou une triche pourrait lui faire perdre beaucoup d’argent. En y repensant, il vaudrait peut-être mieux reformuler cela sous forme de paris en chaîne (parlay).
Pour la magie, c’est trop lent. Il avait imaginé une accroche du genre : « Les parapsychologues n’ont pas réussi à démontrer de façon fiable leurs pouvoirs de précognition avec de superbes cartes de Zener, mais moi, j’ai construit un protocole qui le prouve à chaque fois ! », mais il a jugé que ce n’était pas assez amusant. Parcourir tout un paquet prend du temps, cela n’a pas vraiment l’air miraculeux, et pour rejeter l’hypothèse nulle à p=0.01, il faut réussir 7 fois de suite. Quelqu’un avec une meilleure présence scénique y arriverait peut-être, mais il a laissé tomber.
Il le propose parfois comme énigme en demandant de le dériver, mais personne n’y est jamais arrivé. Lui non plus.
https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
Même avec assez d’entropie, 30 millions d’essais ne suffisent certainement pas.
Le critère de Kelly est l’un de ses concepts préférés en théorie des jeux, et il est souvent utilisé pour la gestion de bankroll des joueurs professionnels, notamment les joueurs de poker.
C’est une bonne manière de comprendre comment gérer ses finances et ses mises pour avancer régulièrement sans prendre trop de risques ni faire faillite, mais il est souvent mal appliqué dans ce domaine. Kelly traite des résultats binaires ; si on l’applique à des situations dont les résultats ne sont pas binaires, on peut obtenir quelque chose qui paraît presque juste selon l’angle mathématique adopté, mais qui reste légèrement faux.
Comme on joue contre d’autres joueurs, l’utilité d’une certaine distribution de jetons semble devoir être plus complexe que le simple nombre de jetons possédés.
Il n’est pas joueur de poker.
Le critère de Kelly se généralise bien aux allocations continues, simultanées et complexes.
Il suffit d’avoir une liste d’actions possibles et la distribution de probabilité conjointe des résultats en termes de richesse après chaque action. Une action peut aussi être une action composite avec des résultats continus.
Au poker, l’issue n’est pas binaire : les montants gagnés ou perdus varient, donc on utilise la valeur attendue. Après avoir calculé une valeur attendue approximative, on utilise aussi un calculateur de variance, par exemple https://www.primedope.com/poker-variance-calculator/, pour estimer à long terme à quelle fréquence et dans quelle mesure on peut gagner sur un certain nombre de mains.
On a l’impression qu’on passerait beaucoup de temps à ne ni gagner ni perdre.
Cela aurait été une meilleure démonstration en réduisant à des nombres plus maniables, par exemple un paquet de 2 cartes noires et 2 cartes rouges.
Au 1er tour, r = b, donc on ne mise pas.
Au 2e tour, on mise 1/3 sur la couleur qui n’est pas sortie au 1er tour.
Au 3e tour, si on s’est trompé au 2e tour, il ne reste que 2/3 de la mise initiale, mais comme on connaît la couleur des deux cartes suivantes, on double à chaque fois et, après le 3e tour, on atteint 4/3 de la mise initiale. Si on a eu raison, on est aussi à 4/3, mais comme il reste alors une rouge et une noire, on ne mise pas à ce tour-ci.
Au 4e tour, comme on connaît la couleur de la dernière carte, on double l’argent et on arrive à 8/3 de la mise initiale.
Et l’exercice laissé au lecteur consiste à prouver l’optimalité ; c’est assez straightforward, mais il ne pense pas qu’il existe une preuve courte.
Donc commencer par l’exemple à 4 cartes, puis montrer les diagrammes en arbre pour les cas à 5 et 6 cartes, permet de garder des chiffres encore gérables tout en construisant l’intuition nécessaire pour une induction vers le cas général.
En pratique, bien des facteurs rendent l’usage de Kelly plus difficile que dans l’exemple-jouet.
Qu’est-ce que la bankroll ? Le cash disponible ? Le patrimoine net total ? Le patrimoine net liquide ? Les revenus du travail futurs ?
Selon la taille de la bankroll, de nombreux facteurs entrent en jeu. Par exemple, avec une bankroll de 100 $, tout perdre n’est généralement pas dramatique. Mais avec une bankroll de 1 million de dollars, on hésite bien davantage à l’exposer au risque.
Qu’est-ce que la valeur attendue ? Est-elle connue ? Stable ? Le jeu est-il honnête ?
Selon les propriétés statistiques de la valeur attendue, il faut fortement ajuster l’approche de dimensionnement des mises. Si l’on ne peut qu’estimer la valeur attendue et que le secteur est plein d’escrocs, comme au poker, il faut déterminer la taille des mises sous forte incertitude.
Quels montants de mise peut-on utiliser ?
En pratique, il n’existe pas de plage continue de montants de mise. On n’a généralement accès qu’à des montants discrets, par exemple de 5 $ à 500 $ par incréments de 5 $ ou 25 $. Si la bankroll tombe trop bas, on est exclu du jeu ; si elle monte trop haut, on ne peut plus maximiser les profits.
Au final, les joueurs professionnels misent souvent demi-Kelly ou quart-Kelly à cause de cette complexité.
En trading, il y a les spreads et les commissions ; aux tables de casino, il y a le rake.
Le fait qu’il n’y ait aucune variance dans le résultat est vraiment remarquable. Mais à cause de cela, on a l’impression que, dans la structure particulière de ce problème, il devrait exister une stratégie avec un rendement espéré plus élevé
Sait-on ici si la stratégie de Kelly est optimale ?
Au début, je pensais que ces stratégies étaient très différentes, mais ce n’est pas tout à fait le cas. La stratégie de Kelly fait la même chose quand il ne reste plus qu’une seule couleur. La différence, c’est que cette stratégie ne fait rien avant cela
Malgré tout, les deux ressemblent à des cas limites. Miser tout quand il ne reste plus qu’une seule couleur est le seul choix manifestement correct ; la vraie question est donc ce qu’on fait avant. Ne rien faire et Kelly sont les seules stratégies qui paraissent plausibles
Cela dit, l’argument ne s’enchaîne pas aussi naturellement que la démonstration montrant une variance nulle, donc il ne l’a pas inclus. Le texte original semblait aussi suggérer une preuve de type théorie des jeux en qualifiant les sous-stratégies du portefeuille de « stratégies pures »
Ce problème et sa solution semblent venir de Thomas Cover
Je ne me souviens pas de cet exemple précis, mais j’ai appris le critère de Kelly dans un cours donné par Thomas Cover. C’était l’un de mes professeurs préférés, et chaque discussion avec lui était intéressante et enrichissante. RIP