Başarısız Olamayan Kelly Stratejisi

• 52 kartlık destedeki renk dağılımını sürekli takip eden Next Card Bet oyununda Kelly stratejisi, alışılmış yüksek varyanslı yapısının aksine başlangıç sermayesi olan $1’i her zaman yaklaşık $9.08 ile bitirir
• Bahis kuralı basittir: Kalan kırmızı kart sayısı r ile siyah kart sayısı b eşitse pas geçilir; biri daha fazlaysa mevcut sermayenin |r - b| / (r + b) kadarı fazla kalan renge yatırılır
• Python ile karıştırılmış 10.000 deste çalıştırıldığında bile nihai sermaye 9.081329549427776~9.081329549427803 aralığında kalır; yalnızca son karta oynayan iki kat stratejisinden daha yüksek getiriyi dalgalanma olmadan üretir
• İspat, mümkün olan tüm kırmızı/siyah dizilimlere, yani (52 choose 26) = 495,918,532,948,104 olasılığa, başlangıç sermayesini eşit dağıtır ve gerçek deste ile eşleşen tek alt stratejinin 52 kez üst üste ikiye katlandığı bir portföy kurar
• Bu portföyün toplam sermaye değişimi Kelly stratejisinin temkinli desenine eşit olduğundan, normalde para kaybettirebilen Kelly stratejisi bu oyunda sıfır varyanslı bir stratejiye dönüşür

---

Next Card Bet kuralları ve sezgi

• Kelly bet allocation strategy, kumar durumlarında bilgi veya yanlılığı kullanarak bahis oranını belirleme yöntemidir
• Genel Kelly stratejisi agresif ve yüksek varyanslı bir strateji olarak bilinir; Kelly oranından daha fazla bahis yapmak iflas riskini artırabilir
• Peter Winkler’ın Mathematical Puzzles kitabındaki “Next Card Bet” probleminde bu strateji risksiz ve sıfır varyanslı biçimde çalışır
• Oyun standart 52 kartlık bir deste ile başlar
  • Destedeki 26 kart kırmızı, 26 kart siyahtır
  • Deste karıştırılır, ardından kartlar birer birer açılır ve açılan kartlar tekrar desteye konmaz
  • Oyuncu, sıradaki kartın kırmızı mı siyah mı olacağına mevcut sermayesinin istediği kadarını yatırabilir
  • Ödeme oranı 1:1’dir ve başlangıç sermayesi $1’dir
• Daha önce açılan kartlar sayılırsa görünmeyen destede her renkten kaç kart kaldığı bilinebilir
  • Son karta kadar bahis yapılmazsa kalan son kartın rengi kesin olarak bilinir
  • Bu basit strateji, tüm sermayeyi son karta yatırarak parayı güvenli biçimde iki katına çıkarabilir

Kelly bahis oranı

• Kelly stratejisi, nihai sermayenin logaritmasının beklenen değerini maksimize eden bahsi seçer
• Kalan kırmızı kart sayısı r, siyah kart sayısı b olsun; r > b ise sıradaki kartın kırmızı gelme olasılığı r / (r + b) olur
• Beklenen log sermaye şu ifadeye göre maksimize edilir
  • P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction)
• Bu ifadenin türevinin 0 olduğu noktada bahis oranı (r - b) / (r + b) olur
• Genel strateji, yalnızca kalan iki renk arasındaki fark kadar risk alır
  • r = b ise bahis yapılmaz
  • r > b ise mevcut sermayenin |r - b| / (r + b) oranı “red” üzerine yatırılır
  • b > r ise mevcut sermayenin |r - b| / (r + b) oranı “black” üzerine yatırılır

Python simülasyonu sonuçları

• Python örneği, Kelly stratejisini run_bets(is_red) fonksiyonu ile çalıştırır
  • stake değeri 1.0’dan başlar
  • Her kartta kalan kırmızı ve siyah kart sayıları güncellenir
  • Daha fazla kalan renge abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining) oranında bahis yapılır
  • Tahmin doğruysa ilgili bahis tutarı iki kat olarak geri gelir, yanlışsa kaybedilir
• Rastgele sayı üreteci olarak np.random.default_rng(2024) kullanılır
• 52 kartın 26’sı kırmızı olacak şekilde 10.000 deste üretildiğinde sonuçlar fiilen aynı değerde toplanır
  • Minimum: 9.081329549427776
  • Maksimum: 9.081329549427803
• Sonuç farkı 1e-8’den küçüktür ve tüm çalıştırmalarda başlangıç sermayesinin yaklaşık 9.08 katı elde edilir
• 9.08 kat getiri, yalnızca son karta oynayıp güvenli biçimde iki kat kazandıran stratejiden çok daha yüksektir

Sıfır varyans üreten portföy ispatı

• Kırmızı ve siyah kartların olası dizilim sayısı (52 choose 26) = 495,918,532,948,104 adettir
• Düzgün karıştırılmış bir destede bu kırmızı/siyah dizilimlerinin hepsinin eşit olasılıkla ortaya çıktığı standart sonuç kullanılır
• Portföy stratejisi, mümkün olan her kırmızı/siyah dizilimini bir alt strateji olarak ele alır
  • Başlangıç sermayesinin 1 / (52 choose 26) kadarı her dizi alt stratejisine ayrılır
  • Alt stratejiler yalnızca kendi paralarını yönetir; aralarında yeniden dağıtım yapılmaz
  • Her alt strateji, kendisine atanmış dizilimin gerçek deste olduğunu varsayar ve her kartta tüm sermayesini ilgili renge yatırır
• Gerçek deste ile uyuşmayan tüm alt stratejiler, bir noktada yanlış karta tüm sermayeyi yatırıp iflas eder
• Yalnızca gerçek deste ile tam eşleşen tek alt strateji, 52 kartın tamamını doğru tahmin ederek 2^52 katına ulaşır
• Bu yüzden tüm portföyün nihai getirisi kart sırasından bağımsız olarak her zaman aynıdır
  • $1 / (52 choose 26) * 2^52
  • yaklaşık $9.08

Portföy ile Kelly stratejisinin aynı olması

• Portföyde henüz iflas etmemiş alt stratejiler, sıradaki kartı kırmızı veya siyah olarak tahmin eder
• Kalan kartlar r kırmızı ve b siyah olduğunda, alt stratejilerin tahmin oranları kalan renklerin oranını izler
• Sıradaki kart açıldığında yanlış tahmin eden grup iflas eder, doğru tahmin eden grubun sermayesi ikiye katlanır
• Bu anda portföyün toplam sermaye değişimi, fazla kalan renge |r - b| / (r + b) yatıran Kelly stratejisinin temkinli deseniyle tam olarak aynıdır
• Kelly stratejisinin sıfır varyanslı olmasının nedeni, kendi başına sıfır varyanslı olan bu portföy stratejisiyle aynı şekilde hareket etmesidir

Genel Kelly stratejisinden farkı

• Kelly stratejisi normalde iflası önlerken sermayenin logaritmasının beklenen büyüme oranını maksimize eder
• Ancak genel Kelly stratejisi bunun dışında pek az şey garanti eder; gerçekten para kaybettirebilir ve genellikle yüksek varyanslıdır
• Bu kart oyununda zarar oluşsa bile destedeki renk dağılımı daha dengesiz hale gelir ve sonraki koşullar daha avantajlı olur
• Bahis yeterince küçük tutulursa, yanlış bahislerde kaybedilen sermaye daha sonra büyüyen avantaj tarafından telafi edilir
• Bu yapı, A/B testleri gibi problemlerdeki keşif ve kullanım aşamalarını hatırlatır

Referanslar

• İspat, Winkler Mathematical Puzzles içindeki çözüme dayanır
• Bu ispat Thomas Cover’ın tarzıyla ilişkilidir; Cover daha sonra universal portfolio yatırım stratejisini geliştirmiştir
• Demo ve kaynak materyaller
  • Kelly_cant_fail.ipynb: metindeki örneğin not defteri
  • card_count_fns.py: kart sayımı ve bahis yürütme fonksiyonları
  • dyn_prog.ipynb: bölünemez sermaye birimleri için dinamik programlama not defteri
  • Demonstrating Kelly Betting with Chips: fişlerle yapılan gösterimin açıklaması

[GN⁺]

Hacker News yorumları

• Bu stratejinin her zaman geçerli olabilmesi için bahis miktarının sonsuz derecede küçük parçalara bölünebilir olması gerekir.
  Örneğin destenin üst tarafında 26 kırmızı kart toplanmışsa, başlangıçtaki $1.00 bahis miktarı 0.000000134'e kadar düşüp sonra tekrar 9.08'e kadar çıkar.

  • Başlangıçtaki bahis miktarı $1e12 olsaydı, en kötü durumda bile ölümcül yuvarlama hatalarından kaçınılabilirdi. Burada hayata dair bir ders olabilir.
  • İyi nokta. Deneyince bu sistemin bahis miktarındaki kuantizasyon veya yuvarlamaya karşı çok hassas olduğunu gördüm.
    Beklenen değer kabaca doğru konuma geliyor, ancak varyans hızla büyüyor. Bu yüzden bu önemli durumun dışında da genel olarak oldukça kararsız.
  • Ayrık bahis miktarları durumuna ilişkin takip notunu buraya ekledim: https://win-vector.com/2024/12/21/kelly-betting-with-discret...
    $1'lik bahisten $8.08 kazancı garanti eden bir dinamik programlama stratejisi biliniyor. Kelly stratejisini basitçe yuvarlamak bu sonucu vermiyor.
  • Çoğu kişi bu noktaya varıyor. Yazı turayı çok uzun bir dönem boyunca yapılan tüm atışlar gibi ele almak gerekir ve stratejinin aynen çalışması için tek bir atışı bile atlamamak gerekir.
    Bir kez kaçırırsanız kârlı bir ardışık aralığı ya da büyük kazanç getiren belirli tek bir işlemi kaçırmış olursunuz. Fiyat-zaman grafiğini Renko grafiği gibi çizerseniz herhangi bir emtia grafiğine benzer görünür.
    Gerçek hayattaki hisse/kripto/forex işlemlerinde bu, neredeyse tüm işlemleri yapmanız gerektiği anlamına gelir; aksi halde stratejinin performansı düşer. Deney sırasında parayı değiştirmemek gibi, işlemlerde de enstrüman değiştirmemeli veya işlem kaçırmamalı ve bunu çok uzun süre sürdürmelisiniz.
    Söylemeye gerek yok, muazzam bir tutarlılık gerekir ve işin içine para girince stres de artar. Her gün tekrarlanınca zihinsel ve fiziksel yıpranma büyük olur; uzun süre yapmak zordur.
  • Bunun karşıt ikilisi, sonsuz paranız varsa Martingale'in başarısız olamayacağını söylemek gibidir.

• Kelly ile ilgili ilginç bir yan konu Proebsting paradoksudur.
  Olasılık teorisinde Proebsting paradoksu, Kelly kriterinin iflasa yol açabileceğini gösteriyor gibi görünen bir argümandır. Matematiksel olarak çözülebilir, ancak özellikle yatırımda Kelly'nin pratik uygulanışı açısından ilginç sorunlar ortaya koyar. İlk kez 2008'de Edward O. Thorp tarafından tartışılmış ve adını yaratıcısı Todd Proebsting'den almıştır.
  https://en.wikipedia.org/wiki/Proebsting%27s_paradox

  • Aynı sayfadan alıntılayacak olursak, bu paradoksu kolayca bertaraf etmenin yolu Kelly'nin olasılıkların değişmediğini varsaydığını görmektir.
    Yani Kelly, olasılıkları bildiğinizde ve bu olasılıklar değişmediğinde iyidir.
    Olasılıkları bilmiyorsanız ya da değişebiliyorlarsa, doğru yaklaşımın Kelly'den daha karmaşık olması gerektiğini düşünüyorum.

• Güzel bir içerik, ancak portföy argümanı gereksiz bir dolambaç gibi görünüyor. Tümevarımla iki satırlık bir kanıt mümkün.

  1. Taban durum olan (0,1) veya (1,0)'ın getirisi 2'dir.
  2. (r,b), r >= b durumunda elinizde $X varken kırmızıya (r-b)/(r+b) yatırırsanız, kırmızı çekip kazandığınızda getiri 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) olur.
     Benzer şekilde siyah çekip kaybettiğinizde getiri 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) olur. QED
  • Peki bu tümevarım kanıtı neden gereksiz bir dolambaç değil?

• Timothy Falcon'ın kantitatif finans mülakat kitabındaki problem #14'te olduğu gibi, desteden kart açarken ne zaman duracağınıza karar verdiğiniz çok benzer bir kart oyunu var. Kırmızı $1, siyah −$1 olarak sayılıyor.
  Gwern bunu açıklamış ve optimal durma stratejisini doğrulayan kod da yazmış: https://gwern.net/problem-14

  • Standart finans geleneğine uymak için siyah +$1, kırmızı ise -$1 olmalı. Yani “kara geçmek” ve “zarara geçmek” geleneğine uygun olmalı.

• Gençken kart sayarak destede hangi rengin daha çok kaldığını tahmin edersem her zaman yarıdan fazlasını doğru bilebileceğimi keşfetmiştim.
  https://en.wikipedia.org/wiki/TRS-80_Model_100
  üzerinde bir simülasyon yazdım ve bir kez bile başarısız olmadı. Geçenlerde tekrar aklıma geldi; bir Python betiğiyle 30 milyon kez çalıştırdım, yine başarısız olmadı.
  Bunu ne için kullanabileceğimi düşünürken (i) bahis, (ii) sihirbazlık aklıma geldi ama ikisi de pek umut verici değildi.
  Bahiste karşı tarafın $10'ına karşı $1000 koyabilirdim; ama bu büyük kazanç elde etmenin yolu değil, ayrıca hata yaparsam ya da kandırılırsam büyük para kaybedebilirim. Tekrar düşününce bunu parlay, yani ardışık bahis biçiminde yeniden kurgulamak daha iyi olabilir.
  Sihirbazlık içinse fazla yavaş. “Parapsikologlar şık Zener kartlarıyla önsezi yeteneğini güvenilir biçimde kanıtlayamadılar, ama ben bunu her seferinde kanıtlayabilen bir protokol yaptım!” gibi bir replik hazırlamıştım; fakat yeterince eğlenceli olmadığına karar verdim. Bir desteyi baştan sona çevirmek zaman alıyor, mucize gibi de görünmüyor; p=0,01 düzeyinde sıfır hipotezini reddetmek için bunu arka arkaya 7 kez yapmak gerekiyor. Sahne hâkimiyeti daha iyi biri belki başarabilir, ama ben vazgeçtim.

  • Bu bana sevdiğim bir algoritmayı hatırlatıyor. Kaç farklı öğe olursa olsun bir listede çoğunluk elemanı varsa, O(N) zamanda ve O(1) bellekle bulunabilir.
    Bazen bu algoritmayı türetmelerini istediğim bir bulmaca olarak soruyorum ama kimse çözemedi. Ben de çözememiştim.
    https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
  • Olası kart sıraları yeterince fazla olduğundan, sözde rastgele sayı kaynağının tüm uzayı doğru dürüst tarayamaması sorunundan endişe etmek gerekebilir. Böyle durumlarda simülasyon çok yanıltıcı olabilir.
    Entropi yeterli olsa bile 30 milyon kez kesinlikle yeterli değil.

• Kelly kriteri sevdiğim oyun teorisi kavramlarından biri; özellikle poker oyuncuları gibi profesyonel kumarbazların bankroll yönetiminde çok kullanılır.
  Çok büyük risklerden ya da iflastan kaçınırken istikrarlı biçimde ilerlemek için sermayeyi ve bahis miktarlarını nasıl yönetmek gerektiğini anlatmanın iyi bir yolu; ancak o alanda sık sık yanlış uygulanıyor. Kelly ikili sonuçlarla ilgilenir; sonuçların ikili olmadığı durumlara uygulandığında, matematiğe nasıl baktığınıza bağlı olarak neredeyse doğru görünen ama biraz sapmış sonuçlar verebilir.

  • Kelly kriteri birçok kumar türü için harika görünüyor, ama poker istisna olabilir.
    Poker diğer oyunculara karşı oynandığından, belirli bir fiş dağılımının faydasının yalnızca eldeki fiş sayısından daha karmaşık olması gerekir gibi geliyor.
    Poker oyuncusu değilim.
  • “Kelly ikili sonuçlarla ilgilenir” sözü yanlış. https://entropicthoughts.com/the-misunderstood-kelly-criteri...
    Kelly kriteri sürekli, eşzamanlı ve karmaşık tahsislere de iyi biçimde genellenir.
    Gerekli olan tek şey seçilebilir eylemlerin listesi ve her eylemden sonraki servet sonuçlarına ilişkin birleşik olasılık dağılımıdır. Eylemler, sürekli sonuçları olan bileşik eylemler de olabilir.
  • Kelly kriterinin ikili sonuçlarla ilgilendiği doğru; bu yüzden pokere uymaz.
    Pokerde kazanç/kayıp ikili değildir; kazanılan ya da kaybedilen tutar değiştiği için beklenen değer kullanılır. Yaklaşık beklenen değeri hesapladıktan sonra, örneğin https://www.primedope.com/poker-variance-calculator/ gibi bir varyans hesaplayıcısı da kullanılarak uzun vadede belirli sayıda elde ne kadar sıklıkla ve ne kadar kazanma olasılığı olduğu görülür.
  • Rulette renge bahis oynama biçiminde bu işe yarar mı?
    Sanırım kazanıp kaybetmeden çok zaman harcanır.

• Daha yönetilebilir sayılara, örneğin 2 siyah ve 2 kırmızı kartlık bir desteye indirgeseydi daha iyi bir demo olurdu.

  1. turda r = b olduğu için bahis yapmazsın.
  2. turda 1. turda gelmeyen renge sermayenin 1/3'ünü koyarsın.
  3. turda 2. turda yanıldıysan bahis paranının yalnızca 2/3'ü kalır; ama sıradaki iki kartın rengini bildiğin için her seferinde ikiye katlayıp 3. turdan sonra başlangıç sermayenin 4/3'üne ulaşırsın. Doğru bildiysen sermayen 4/3 olur, fakat bir kırmızı bir siyah kaldığından bu tur bahis yapmazsın.
  4. turda son kartın rengini bildiğin için paranı ikiye katlar ve başlangıç sermayenin 8/3'üne ulaşırsın.
     Okura bırakılan alıştırma ise optimal olduğunu kanıtlamak; epey straightforward olsa da kısa bir kanıtı olduğuna inanmıyorum.
  • Doğru. Yalnız 4 kartlık örnekte 3. turda yalnızca bir trivial olmayan dallanma var.
    Bu yüzden 4 kartlık örnekle başlayıp ardından 5 ve 6 kartlık durumların ağaç diyagramını göstermek, sayılar hâlâ yönetilebilir olduğu için genel duruma tümevarım sezgisi kazandırmak açısından iyi olur.
  • Genel argümanı takip edebildim ama sonucun kart sırasından bağımsız olarak neden tam olarak aynı çıktığına ikna olacak kadar değil.

• Gerçekte Kelly kullanımını zorlaştıran etkenler oyuncak örneklerden çok daha fazla.
  Sermaye büyüklüğü nedir? Elde tutulan nakit mi? Toplam net varlık mı? Likit net varlık mı? Gelecekteki emek geliri mi?
  Sermaye büyüklüğüne göre birçok etken devreye girer. Örneğin sermayeniz $100 ise hepsini kaybetmek genelde büyük mesele değildir. Ama sermayeniz $1 million ise onu riske atma konusunda çok daha isteksiz olursunuz.
  Beklenen değer nedir? Biliniyor mu? Durağan mı? Oyun dürüst mü?
  Beklenen değerin istatistiksel özelliklerine göre bahis büyüklüğü yaklaşımını ciddi biçimde ayarlamak gerekir. Beklenen değerin yalnızca tahmin edilebildiği ve çok sayıda dolandırıcının bulunduğu alanlarda, örneğin pokerde, büyük belirsizlik altında bahis boyutunu belirlemeniz gerekir.
  Hangi bahis tutarları kullanılabilir?
  Gerçekte sürekli bir bahis tutarı aralığı yoktur. Genelde $5 ile $500 arasında $5 ya da $25'lık adımlar gibi yalnızca ayrık tutarlar mümkündür. Sermaye çok düşerse oyundan itilirsiniz; çok yükselirse artık getiriyi maksimize edemezsiniz.
  Sonuçta profesyonel kumarbazlar bu karmaşıklıklar yüzünden çoğu zaman yarım Kelly ya da çeyrek Kelly ile bahis yapar.

  • Gerçekte yalnızca sürekli bahis tutarları oluşturamamakla kalmazsınız; bahis yapma hakkının kendisi için de ücret ödemeniz gerekebilir.
    Alım satımda spread ve komisyonlar, casino masalarında ise rake vardır.

• Sonuçlarda hiç varyans olmaması çok hoş. Ama bu yüzden, bu problemin özel yapısı gereği daha yüksek beklenen getiri sağlayan bir strateji olmalıymış gibi geliyor
  Burada Kelly stratejisinin optimal olup olmadığını biliyor musun?

  • En yüksek beklenen değere sahip gibi hissettiriyor. Kartlar tek bir renk kalana kadar hepsini açıp sonra her seferinde tamamını yatırma stratejisini denedim; bir milyon çalıştırmada 9.08 çıktı
    Başta bu stratejilerin çok farklı olduğunu düşünmüştüm, ama tam olarak öyle değil. Kelly stratejisi de tek bir renk kaldığında aynı şeyi yapıyor. Fark, bu stratejinin ondan önce hiçbir şey yapmaması
    Yine de ikisi uç örnekler gibi geliyor. Tek bir renk kaldığında tamamını yatırmak tek doğru hamle; sonuçta mesele ondan önce ne yapıldığı. Hiçbir şey yapmamak ve Kelly, iyi görünen tek stratejiler
  • “Optimal” derken ne kastediliyor? Daha yüksek beklenen değer için iflas riskini göze alabileceğin anlamına mı geliyor?
  • Kitapta “rasyonel” diye adlandırılan strateji kümesi için optimal olduğu iddia ediliyor
    Ancak bu argüman, varyansın 0 olduğunu gösteren kanıt kadar doğal akmadığı için dahil etmedim. Orijinal metin de portföy içindeki alt stratejileri “saf stratejiler” diye adlandırıp oyun teorik bir kanıta işaret ediyor gibiydi
  • Bu oyunda, kalan deste tamamen aynı renktense o renge elindeki her şeyi yatırma kuralına uyulduğu sürece, tüm stratejilerin beklenen değeri aynıdır
  • Kelly kriteri, tam da bu problemin kendine özgü yapısı nedeniyle daha iyi getiri sağlayan stratejidir

• Bu problem ve çözüm Thomas Cover’dan çıkmış gibi görünüyor
  Bu spesifik örneği hatırlamıyorum, ama Thomas Cover’ın verdiği bir derste Kelly kriterini öğrenmiştim. En sevdiğim hocalardan biriydi; onunla yapılan her tartışma ilginç ve değerliydi. Huzur içinde yatsın

  • Bu alanda da çok sayıda ilginç makale bıraktı; bunların bazıları Kelly kriteri üzerine yazılmış kitabın önemli bir bölümünü oluşturuyor