असफल न हो सकने वाली Kelly रणनीति

• 52-card deck में रंगों के distribution को लगातार track करने वाले Next Card Bet में, Kelly रणनीति अपने सामान्य high-variance स्वभाव के उलट $1 की शुरुआती पूंजी को हमेशा लगभग $9.08 पर खत्म करती है
• betting rule सरल है: अगर बचे हुए red cards r और black cards b बराबर हों तो रुकें; जिस रंग के कार्ड ज्यादा बचे हों, उस पर मौजूदा पूंजी का |r - b| / (r + b) हिस्सा लगाएं
• Python से shuffle किए गए 10,000 decks चलाने पर भी अंतिम पूंजी 9.081329549427776~9.081329549427803 की range में रही, और सिर्फ आखिरी card पर दांव लगाने वाली 2x strategy से ज्यादा return बिना variation के मिला
• proof में संभावित red/black arrangements (52 choose 26) = 495,918,532,948,104 पर शुरुआती पूंजी बराबर-बराबर बांटी जाती है, और वास्तविक deck से match करने वाली सिर्फ एक sub-strategy 52 बार लगातार double होती है, यानी एक portfolio बनाया जाता है
• इस portfolio की कुल पूंजी में बदलाव Kelly strategy के payoff pattern जैसा ही है, इसलिए Kelly strategy, जो आम तौर पर पैसा गंवा भी सकती है, इस game में zero variance strategy बन जाती है

---

Next Card Bet के नियम और intuition

• Kelly bet allocation strategy gambling situations में information या bias का उपयोग करके betting fraction तय करने का तरीका है
• सामान्य Kelly strategy को aggressive high-variance strategy माना जाता है, और Kelly fraction से ज्यादा bet करने पर ruin risk बढ़ सकता है
• Peter Winkler की Mathematical Puzzles में आने वाले “Next Card Bet” में यह strategy बिना risk के zero variance के साथ काम करती है
• game standard 52-card deck से शुरू होता है
  • इसमें 26 red cards और 26 black cards होते हैं
  • deck shuffle करने के बाद cards एक-एक करके reveal किए जाते हैं, और reveal किए गए cards वापस नहीं डाले जाते
  • player अगले card के red या black होने पर अपनी मौजूदा पूंजी का कोई भी fraction लगा सकता है
  • payout 1:1 है, और शुरुआती पूंजी $1 है
• जो cards पहले आ चुके हैं उन्हें count करने पर unseen deck में बचे रंगों की संख्या पता चलती है
  • अगर आखिरी card तक bet न किया जाए, तो बचे card का रंग पक्का पता चल सकता है
  • यह simple strategy आखिरी card पर पूरी रकम लगाकर पूंजी को सुरक्षित रूप से double कर सकती है

Kelly betting fraction

• Kelly strategy अंतिम पूंजी के log value की expected value को maximize करने वाला bet चुनती है
• बचे red cards की संख्या r और black cards की संख्या b मानें, और अगर r > b हो, तो red card आने की probability r / (r + b) है
• expected log wealth को नीचे दिए गए expression के आधार पर maximize किया जाता है
  • P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction)
• इस expression की derivative 0 होने वाले point पर betting fraction (r - b) / (r + b) होता है
• पूरी strategy बचे दो रंगों के अंतर के बराबर ही risk लेती है
  • अगर r = b हो, तो bet नहीं करती
  • अगर r > b हो, तो मौजूदा पूंजी का |r - b| / (r + b) fraction “red” पर bet करती है
  • अगर b > r हो, तो मौजूदा पूंजी का |r - b| / (r + b) fraction “black” पर bet करती है

Python simulation के नतीजे

• Python example run_bets(is_red) function से Kelly strategy चलाता है
  • stake को 1.0 से शुरू करता है
  • हर card पर बचे red cards और black cards की संख्या update करता है
  • जिस रंग के cards ज्यादा बचे हों, उस पर abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining) fraction bet करता है
  • card सही निकले तो वह bet amount 2x होकर लौटता है, गलत हो तो खो जाता है
• random number generator np.random.default_rng(2024) का उपयोग करता है
• 52 cards में 26 red cards वाले deck को 10,000 बार generate करने पर results लगभग एक ही value पर converge हुए
  • minimum: 9.081329549427776
  • maximum: 9.081329549427803
• result का difference 1e-8 से कम था, और हर run में शुरुआती पूंजी का लगभग 9.08x return मिला
• 9.08x return, सिर्फ आखिरी card पर bet करके सुरक्षित 2x पाने वाली strategy से काफी बड़ा है

zero variance बनाने वाला portfolio proof

• red और black cards के संभावित arrangements की संख्या (52 choose 26) = 495,918,532,948,104 है
• ठीक से shuffled deck में इन red/black arrangements के समान probability से आने वाले standard result का उपयोग किया जाता है
• portfolio strategy में हर संभावित red/black arrangement को एक sub-strategy माना जाता है
  • हर arrangement sub-strategy को शुरुआती पूंजी का 1 / (52 choose 26) हिस्सा दिया जाता है
  • sub-strategies सिर्फ अपना पैसा manage करती हैं, और आपस में reallocate नहीं करतीं
  • हर sub-strategy मानती है कि उसे assigned arrangement ही वास्तविक deck है, और हर card पर पूरी रकम उस रंग पर bet करती है
• वास्तविक deck से अलग सभी sub-strategies कभी न कभी गलत card पर पूरी रकम लगाकर bankrupt हो जाती हैं
• केवल एक sub-strategy, जो वास्तविक deck से बिल्कुल match करती है, सभी 52 cards सही predict करती है और 2^52x हो जाती है
• इसलिए पूरे portfolio का final return card order से independent होकर हमेशा एक ही value होता है
  • $1 / (52 choose 26) * 2^52
  • लगभग $9.08

portfolio और Kelly strategy की समानता

• portfolio में जो sub-strategies अभी bankrupt नहीं हुई हैं, वे अगले card को red या black predict करती हैं
• जब बचे cards में red r और black b हों, तो sub-strategies के predictions का अनुपात बचे रंगों के अनुपात को follow करता है
• अगला card reveal होने पर गलत prediction वाले groups bankrupt हो जाते हैं, और सही prediction वाले groups की पूंजी double हो जाती है
• इस समय portfolio की कुल पूंजी में बदलाव, ज्यादा बचे रंग पर |r - b| / (r + b) लगाने वाली Kelly strategy के payoff pattern से बिल्कुल match करता है
• Kelly strategy zero variance इसलिए है क्योंकि वह अपने-आप में zero variance वाली portfolio strategy की तरह ही move करती है

सामान्य Kelly strategy से फर्क

• Kelly strategy आम तौर पर bankruptcy से बचते हुए wealth के log value की expected growth rate को maximize करती है
• लेकिन सामान्य Kelly strategy इसके अलावा बहुत कुछ guarantee नहीं करती; वास्तव में पैसा खो भी सकती है और आम तौर पर high variance वाली होती है
• इस card game में loss होने पर भी deck का color distribution और imbalance हो जाता है, जिससे बाद की conditions ज्यादा favorable बनती हैं
• अगर bet sufficiently छोटा रखा जाए, तो गलत bet में खोई capital को बाद में बढ़ी हुई edge offset कर देती है
• यह structure A/B test जैसी problems में exploration और exploitation phases की याद दिलाता है

references

• proof Winkler Mathematical Puzzles के solution पर आधारित है
• यह proof Thomas Cover की style से जुड़ा है, और Cover ने बाद में universal portfolio investment strategy बनाई
• demo और source materials
  • Kelly_cant_fail.ipynb: article example की notebook
  • card_count_fns.py: card count और betting execution functions
  • dyn_prog.ipynb: indivisible money units वाले case के लिए dynamic programming notes
  • Demonstrating Kelly Betting with Chips: chips का उपयोग करके demonstration explanation

[GN⁺]

Hacker News की रायें

• यह रणनीति हमेशा सही रहे, इसके लिए दांव की राशि को अनंत रूप से छोटे हिस्सों में बाँटा जा सकना चाहिए
  उदाहरण के लिए, अगर deck के ऊपर लाल 26 कार्ड इकट्ठे हों, तो शुरुआती $1.00 दांव घटकर 0.000000134 तक जाता है और फिर वापस 9.08 तक चढ़ता है

  • अगर शुरुआती दांव $1e12 हो, तो सबसे खराब स्थिति में भी घातक rounding error से बचा जा सकता है। शायद इसमें जीवन का कोई सबक हो
  • अच्छा point है। प्रयोग करके देखा तो यह system betting amount की quantization या rounding के प्रति बहुत संवेदनशील निकला
    expected value लगभग सही जगह पर आती है, लेकिन variance तेजी से बढ़ता है। इसलिए इस महत्वपूर्ण मामले के अलावा भी कुल मिलाकर यह काफी अस्थिर है
  • discrete stakes वाले मामले पर follow-up note यहाँ जोड़ा है: https://win-vector.com/2024/12/21/kelly-betting-with-discret...
    $1 betting से $8.08 profit की guarantee देने वाली dynamic programming strategy ज्ञात है। Kelly strategy को बस round करने से यह result नहीं मिलता
  • अधिकतर लोग इसी बिंदु पर पहुँचते हैं। coin toss को बहुत लंबे समय के सभी tosses की तरह treat करना होगा, और strategy ठीक से काम करे तो एक भी toss skip नहीं करना होगा
    एक बार छूट गया तो profitable continuous segment या किसी एक बड़े profit वाले मौके को miss कर देंगे। price बनाम time chart को Renko chart की तरह खींचकर देखें तो यह किसी भी commodity chart जैसा दिखता है
    वास्तविक stock/crypto/forex trading में इसका मतलब है कि लगभग सभी trades करने होंगे, वरना strategy की performance घटेगी। जैसे experiment के दौरान coin नहीं बदलते, वैसे ही trading में भी instrument बदलना या trade miss करना नहीं चाहिए, और इसे बहुत लंबे समय तक जारी रखना होगा
    कहने की जरूरत नहीं कि इसके लिए जबरदस्त consistency चाहिए, और जब पैसा दांव पर हो तो stress भी बढ़ता है। रोज दोहराने पर मानसिक और शारीरिक थकान इतनी बढ़ती है कि लंबे समय तक करना मुश्किल है
  • इसका उल्टा जोड़ा वैसा ही है जैसे कहना कि अनंत पैसा हो तो Martingale कभी fail नहीं हो सकता

• Kelly से जुड़ी एक दिलचस्प शाखा Proebsting का paradox है
  probability theory में Proebsting का paradox एक ऐसा तर्क है जो दिखाता हुआ लगता है कि Kelly criterion bankruptcy तक ले जा सकता है। गणितीय रूप से इसे हल किया जा सकता है, लेकिन खासकर investment में Kelly को वास्तविक तौर पर लागू करते समय यह दिलचस्प सवाल उठाता है। Edward O. Thorp ने 2008 में पहली बार इसकी चर्चा की थी, और इसका नाम इसके originator Todd Proebsting पर रखा गया
  https://en.wikipedia.org/wiki/Proebsting%27s_paradox

  • उसी page को quote करें तो, इस paradox को आसानी से हराने का तरीका यह देखना है कि Kelly मानता है कि probabilities बदलती नहीं हैं
    यानी Kelly तब अच्छा है जब आप probabilities जानते हों और वे probabilities बदलती न हों
    अगर probabilities पता नहीं हैं या बदल सकती हैं, तो सही approach शायद Kelly से ज्यादा जटिल होनी चाहिए

• बात सुंदर है, लेकिन portfolio argument एक अनावश्यक चक्कर जैसा लगता है। induction से दो line का proof संभव है

  1. base case (0,1) या (1,0) का payoff 2 है
  2. (r,b), r >= b state में $X लेकर red पर (r-b)/(r+b) लगाएँ, तो red निकलने पर जीत की स्थिति में payoff X * (1+(r-b)/(r+b)) * 2^(r+b-1) / (r+b-1 choose r-1) = X * 2^(r+b) * r / ((r+b) * (r+b-1 choose r-1)) = X * 2^(r+b) / (r+b choose r) है
     इसी तरह black निकलने पर हार की स्थिति में payoff 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
  • वह induction proof अनावश्यक चक्कर क्यों नहीं है?

• Timothy Falcon की quantitative finance interview book के problem #14 में जैसे है, deck से cards पलटते हुए कब रुकना है यह तय करने वाला बहुत मिलता-जुलता card game है। red को $1 और black को −$1 माना जाता है
  Gwern ने इसे समझाया है और optimal stopping strategy verify करने वाला code भी लिखा है: https://gwern.net/problem-14

  • standard finance convention का पालन करना हो तो black +$1 और red -$1 होना चाहिए। यानी “black ink” और “red ink” वाली convention के मुताबिक होना चाहिए

• किशोरावस्था में कार्ड counting करते हुए मैंने पाया था कि deck में जिस रंग के कार्ड ज्यादा बचे हों, उसका अनुमान लगाऊँ तो हमेशा आधे से ज्यादा बार सही हो सकता हूँ
  https://en.wikipedia.org/wiki/TRS-80_Model_100
  पर simulation लिखा था और वह एक बार भी fail नहीं हुआ। हाल में फिर याद आया तो Python script से 3 करोड़ बार चलाया, और तब भी fail नहीं हुआ
  इसे किस काम में लाया जाए सोचते हुए (i) शर्त, (ii) जादू, ये दो बातें सूझीं, लेकिन दोनों ही खास promising नहीं लगीं
  शर्त के रूप में आप सामने वाले के $10 के मुकाबले $1000 लगा सकते हैं, लेकिन यह बड़ी कमाई का रास्ता नहीं है, और गलती हो जाए या धोखा खा जाएँ तो बहुत पैसा खो सकते हैं। फिर सोचा तो शायद इसे parlay यानी लगातार betting के रूप में फिर से गढ़ना बेहतर हो सकता है
  जादू के तौर पर यह बहुत धीमा है। “Parapsychologists शानदार Zener cards से पूर्वज्ञान की क्षमता को भरोसेमंद ढंग से साबित नहीं कर पाए, लेकिन मैंने ऐसा protocol बनाया है जो हर बार साबित कर सकता है!” जैसी लाइन बनाई थी, लेकिन लगा कि यह पर्याप्त मजेदार नहीं है। पूरा deck पलटने में समय लगता है, यह चमत्कार जैसा भी नहीं दिखता, और p=0.01 पर null hypothesis को खारिज करने के लिए इसे लगातार 7 बार करना होगा। बेहतर stage presence वाला कोई व्यक्ति शायद कर पाए, लेकिन मैंने छोड़ दिया

  • यह मुझे मेरे पसंदीदा algorithms में से एक की याद दिलाता है। कितनी भी अलग-अलग items वाली list में, अगर majority element मौजूद हो, तो उसे O(N) time और O(1) space में पाया जा सकता है
    कभी-कभी मैं puzzle के रूप में यह algorithm derive करने को कहता हूँ, लेकिन कोई भी हल नहीं कर पाया। मैं भी नहीं कर पाया था
    https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
  • संभावित card orders इतने ज्यादा हैं कि शायद यह चिंता करनी पड़े कि pseudorandom source पूरे space को ठीक से explore नहीं कर रहा। ऐसे मामलों में simulation बहुत misleading हो सकता है
    entropy पर्याप्त हो तब भी 3 करोड़ बार निश्चित रूप से पर्याप्त नहीं है

• Kelly criterion game theory के मेरे पसंदीदा concepts में से एक है, और खासकर poker players जैसे professional gamblers के bankroll management में बहुत इस्तेमाल होता है
  यह समझाने का अच्छा तरीका है कि finances और stakes कैसे manage किए जाएँ ताकि बहुत बड़ा risk या bankruptcy टालते हुए लगातार आगे बढ़ा जा सके, लेकिन उस क्षेत्र में इसे अक्सर गलत apply किया जाता है। Kelly binary outcomes को handle करता है, और जब इसे non-binary outcomes वाली स्थितियों पर apply किया जाता है, तो आप math को कैसे देखते हैं इस पर निर्भर करते हुए नतीजा लगभग सही दिख सकता है, लेकिन थोड़ा off हो सकता है

  • Kelly criterion कई तरह के gambling के लिए शानदार लगता है, लेकिन poker अपवाद हो सकता है
    poker दूसरे players के खिलाफ होता है, इसलिए किसी खास chip distribution की utility केवल हाथ में मौजूद chips की संख्या से ज्यादा जटिल होनी चाहिए
    मैं poker player नहीं हूँ
  • “Kelly binary outcomes को handle करता है” यह बात गलत है। https://entropicthoughts.com/the-misunderstood-kelly-criteri...
    Kelly criterion continuous, simultaneous और complex allocations पर भी अच्छी तरह generalize होता है
    जरूरत बस selectable actions की list और हर action के बाद wealth outcomes के लिए joint probability distribution की होती है। action continuous outcomes वाला compound action भी हो सकता है
  • Kelly criterion binary outcomes को handle करता है, यह बात सही है, और इसी वजह से यह poker के लिए fit नहीं बैठता
    poker में जीत-हार binary नहीं होती, बल्कि जीतने या हारने की रकम अलग-अलग होती है, इसलिए expected value इस्तेमाल किया जाता है। मोटे तौर पर expected value calculate करने के बाद variance calculator, जैसे https://www.primedope.com/poker-variance-calculator/ भी साथ में इस्तेमाल करते हैं ताकि लंबे समय में किसी निश्चित hand count के दौरान कितनी बार और कितना कमाने की संभावना है, यह देखा जा सके
  • roulette में रंग पर दांव लगाने के तरीके में भी क्या यह काम करेगा?
    लगता है कि जीतेंगे भी नहीं, हारेंगे भी नहीं, बस बहुत समय लगेगा

• अगर इसे ज्यादा manageable numbers, जैसे 2 काले और 2 लाल cards वाले deck तक घटाया जाता, तो बेहतर demo होता
  turn 1 पर r = b है, इसलिए betting नहीं करते
  turn 2 पर turn 1 में जो रंग नहीं आया, उस पर 1/3 लगाते हैं
  turn 3 पर अगर turn 2 में गलत हुए, तो stake का सिर्फ 2/3 बचेगा, लेकिन अगले दो cards के रंग पता हैं, इसलिए हर बार दोगुना करके turn 3 के बाद original stake का 4/3 हो जाता है। अगर सही हुए, तो stake 4/3 है, लेकिन एक लाल और एक काला बचा है, इसलिए इस turn पर betting नहीं करते
  turn 4 पर आखिरी card का रंग पता है, इसलिए पैसा दोगुना करके original stake का 8/3 हो जाता है
  और पाठक के लिए छोड़ा गया exercise optimality prove करना है; यह काफी straightforward तो है, लेकिन मुझे नहीं लगता कि इसका छोटा proof होगा

  • सही। हालांकि 4-card वाले मामले में turn 3 पर सिर्फ एक non-trivial branch है
    इसलिए 4-card example से शुरू करके 5-card और 6-card cases के tree diagram दिखाए जाएँ, तो numbers अब भी manageable रहते हैं और general case पर induction की intuition बनाना आसान होता है
  • general argument follow कर सका, लेकिन card order से स्वतंत्र होकर result बिल्कुल एक जैसा क्यों आता है, यह मानने लायक समझ नहीं आया

• असल में toy example की तुलना में Kelly का इस्तेमाल कठिन बनाने वाले factors बहुत हैं
  bankroll का आकार क्या है? हाथ में cash? कुल net worth? liquid net worth? future labor income?
  bankroll के आकार के अनुसार कई factors आते हैं। उदाहरण के लिए अगर bankroll $100 है और वह पूरा खो जाए, तो आम तौर पर कोई बड़ी बात नहीं। लेकिन अगर bankroll $1 million है, तो उसे risk में डालने में बहुत ज्यादा हिचक होगी
  expected value क्या है? क्या वह known है? क्या वह stable है? game honest है?
  expected value की statistical properties के आधार पर betting size approach को काफी adjust करना पड़ता है। जहाँ expected value सिर्फ estimate की जा सकती है और scammers बहुत हैं, जैसे poker में, वहाँ बड़ी uncertainty के तहत bet size तय करनी पड़ती है
  किस betting amount का इस्तेमाल किया जा सकता है?
  असल में continuous betting amount range नहीं होती। आम तौर पर $5 से $500 तक $5 या $25 increments जैसे discrete amounts ही उपलब्ध होते हैं। bankroll बहुत कम हो जाए तो game से बाहर हो जाते हैं, और बहुत ज्यादा हो जाए तो फिर profit maximize नहीं कर सकते
  आखिरकार professional gamblers इन complexities की वजह से अक्सर half Kelly या quarter Kelly लगाते हैं

  • असल में केवल continuous betting amount बना पाना ही नहीं, बल्कि bet लगाने के अधिकार की भी cost देनी पड़ सकती है
    trading में spread और commission, casino table पर rake होता है

• नतीजों में variance नहीं है—यह बात बहुत शानदार है। लेकिन इसी वजह से, इस समस्या की खास संरचना को देखते हुए लगता है कि कोई ऐसी रणनीति होनी चाहिए जो अधिक expected return दे सके
  क्या यहां Kelly strategy वाकई optimal है?

  • लगता है इसका expected value सबसे ज्यादा होगा। मैंने एक रणनीति आजमाई जिसमें एक ही रंग बचने तक सारे कार्ड पलट दिए, फिर हर बार सब कुछ दांव पर लगाया; दस लाख बार चलाने पर 9.08 आया
    शुरुआत में मुझे लगा था कि ये strategies बहुत अलग हैं, लेकिन बिल्कुल ऐसा नहीं है। Kelly strategy भी जब सिर्फ एक रंग बचता है तो वही करती है। फर्क यह है कि यह strategy उससे पहले कुछ नहीं करती
    फिर भी दोनों extreme cases जैसी लगती हैं। जब एक ही रंग बचा हो तो सब कुछ दांव पर लगाना ही अकेला सही move है, और आखिरकार सवाल यह है कि उससे पहले क्या किया जाए। कुछ न करना और Kelly ही सिर्फ अच्छी दिखने वाली strategies हैं
  • optimal से आपका मतलब क्या है? क्या मतलब है कि अधिक expected value के लिए bankruptcy risk उठाया जा सकता है?
  • किताब में इसे “rational” कहे गए strategies के set के लिए optimal बताया गया है
    हालांकि वह argument variance 0 दिखाने वाले proof जितना स्वाभाविक रूप से नहीं बहता, इसलिए मैंने उसे शामिल नहीं किया। लगता है original text ने भी portfolio के भीतर sub-strategy को “pure strategy” कहा था और game-theoretic proof की ओर संकेत किया था
  • इस game में, अगर बस यह नियम माना जाए कि बचा हुआ deck पूरा एक ही रंग का हो तो उस रंग पर अपनी सारी पूंजी लगानी है, तो सभी strategies का expected value समान होता है
  • Kelly criterion इसी समस्या की अनोखी संरचना के कारण बेहतर return देने वाली strategy है

• लगता है यह समस्या और इसका समाधान Thomas Cover से आया है
  यह specific example याद नहीं है, लेकिन Thomas Cover द्वारा पढ़ाए गए class में मैंने Kelly criterion सीखा था। वे मेरे पसंदीदा teachers में से एक थे, और उनके साथ कोई भी चर्चा दिलचस्प और मूल्यवान होती थी। RIP

  • उन्होंने इस क्षेत्र में भी कई रोचक papers छोड़े, जिनमें से कुछ Kelly criterion पर बनी किताब का बड़ा हिस्सा बनते हैं