Strategi Kelly yang Tidak Bisa Gagal

• Dalam Next Card Bet, yang terus melacak distribusi warna dalam dek 52 kartu, strategi Kelly—berbeda dari sifatnya yang umumnya ber-varians tinggi—selalu mengakhiri modal awal $1 pada sekitar $9,08
• Aturan bertaruhnya sederhana: jika sisa kartu merah r dan kartu hitam b sama, tidak bertaruh; jika salah satu warna tersisa lebih banyak, pertaruhkan |r - b| / (r + b) dari modal saat ini pada warna tersebut
• Bahkan saat menjalankan 10.000 dek yang diacak dengan Python, modal akhir tetap berada di rentang 9.081329549427776 hingga 9.081329549427803, menghasilkan keuntungan yang lebih besar daripada strategi 2x yang hanya bertaruh pada kartu terakhir, tanpa fluktuasi
• Pembuktiannya dibangun sebagai portofolio yang membagi modal awal secara merata ke (52 choose 26) = 495,918,532,948,104 susunan merah/hitam yang mungkin, dan hanya satu substrategi yang cocok dengan dek sebenarnya yang menjadi dua kali lipat selama 52 kali berturut-turut
• Karena perubahan total modal portofolio ini sama dengan pola payoff strategi Kelly, strategi Kelly yang biasanya bisa saja kehilangan uang menjadi strategi dengan varians 0 dalam game ini

---

Aturan dan intuisi Next Card Bet

• Strategi alokasi taruhan Kelly adalah metode untuk menentukan proporsi taruhan dengan memanfaatkan informasi atau bias dalam situasi perjudian
• Strategi Kelly pada umumnya dikenal sebagai strategi agresif ber-varians tinggi, dan jika bertaruh lebih besar dari rasio Kelly, risiko bangkrut bisa meningkat
• Dalam “Next Card Bet” dari Mathematical Puzzles karya Peter Winkler, strategi ini bekerja tanpa risiko dengan varians 0
• Permainan dimulai dari dek standar 52 kartu
  • Berisi 26 kartu merah dan 26 kartu hitam
  • Setelah dek dikocok, kartu dibuka satu per satu, dan kartu yang sudah dibuka tidak dimasukkan kembali
  • Pemain dapat mempertaruhkan proporsi berapa pun dari modal saat ini pada apakah kartu berikutnya berwarna merah atau hitam
  • Payout-nya 1:1, dan modal awalnya $1
• Dengan menghitung kartu yang sudah keluar, kita bisa mengetahui jumlah warna yang tersisa di dek yang belum terlihat
  • Jika tidak bertaruh sampai kartu terakhir, warna kartu yang tersisa bisa diketahui dengan pasti
  • Strategi sederhana ini dapat menggandakan modal secara aman dengan mempertaruhkan seluruh modal pada kartu terakhir

Rasio taruhan Kelly

• Strategi Kelly memilih taruhan yang memaksimalkan nilai harapan dari log modal akhir
• Jika jumlah kartu merah tersisa adalah r dan kartu hitam adalah b, dan r > b, maka probabilitas kartu merah keluar adalah r / (r + b)
• Log modal harapan dimaksimalkan berdasarkan persamaan berikut
  • P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction)
• Pada titik ketika turunan persamaan ini menjadi 0, rasio taruhan menjadi (r - b) / (r + b)
• Strategi keseluruhan hanya mengambil risiko sebesar selisih antara dua warna yang tersisa
  • Jika r = b, tidak bertaruh
  • Jika r > b, bertaruh pada “red” sebesar proporsi |r - b| / (r + b) dari modal saat ini
  • Jika b > r, bertaruh pada “black” sebesar proporsi |r - b| / (r + b) dari modal saat ini

Hasil simulasi Python

• Contoh Python menjalankan strategi Kelly dengan fungsi run_bets(is_red)
  • stake dimulai dari 1.0
  • Pada setiap kartu, jumlah kartu merah dan hitam yang tersisa diperbarui
  • Bertaruh pada warna yang tersisa lebih banyak dengan proporsi abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining)
  • Jika kartunya cocok, jumlah taruhan kembali menjadi dua kali lipat; jika salah, taruhan hilang
• Generator angka acak menggunakan np.random.default_rng(2024)
• Dari 10.000 dek yang dibuat dengan 26 kartu merah di antara 52 kartu, hasilnya berkumpul pada nilai yang secara praktis sama
  • Nilai minimum: 9.081329549427776
  • Nilai maksimum: 9.081329549427803
• Selisih hasilnya lebih kecil dari 1e-8, dan pada semua eksekusi menghasilkan keuntungan sekitar 9,08 kali modal awal
• Keuntungan 9,08 kali jauh lebih besar daripada strategi yang bertaruh hanya pada kartu terakhir untuk mendapatkan 2 kali lipat secara aman

Pembuktian portofolio yang membuat varians 0

• Jumlah kemungkinan susunan kartu merah dan hitam adalah (52 choose 26) = 495,918,532,948,104
• Digunakan hasil standar bahwa dalam dek yang dikocok dengan benar, semua susunan merah/hitam ini muncul dengan probabilitas yang sama
• Strategi portofolio menetapkan setiap susunan merah/hitam yang mungkin sebagai satu substrategi
  • Mengalokasikan 1 / (52 choose 26) dari modal awal ke setiap substrategi susunan
  • Setiap substrategi hanya mengelola uangnya sendiri dan tidak mendistribusikannya kembali satu sama lain
  • Setiap substrategi mengasumsikan susunan yang dialokasikan kepadanya adalah dek sebenarnya, dan pada setiap kartu mempertaruhkan seluruh modal pada warna tersebut
• Semua substrategi yang berbeda dari dek sebenarnya pada akhirnya mempertaruhkan seluruh modal pada kartu yang salah dan bangkrut
• Hanya satu substrategi yang persis cocok dengan dek sebenarnya yang menebak benar semua 52 kartu dan menjadi 2^52 kali
• Karena itu, hasil akhir seluruh portofolio selalu sama, terlepas dari urutan kartu
  • $1 / (52 choose 26) * 2^52
  • Sekitar $9,08

Kesetaraan portofolio dan strategi Kelly

• Substrategi dalam portofolio yang belum bangkrut memprediksi kartu berikutnya sebagai merah atau hitam
• Ketika tersisa r kartu merah dan b kartu hitam, proporsi prediksi substrategi mengikuti proporsi warna yang tersisa
• Ketika kartu berikutnya dibuka, kelompok yang prediksinya salah bangkrut, sedangkan kelompok yang benar modalnya menjadi dua kali lipat
• Pada saat itu, perubahan total modal portofolio persis sama dengan pola payoff strategi Kelly yang bertaruh |r - b| / (r + b) pada warna yang tersisa lebih banyak
• Alasan strategi Kelly memiliki varians 0 adalah karena ia bergerak sama dengan strategi portofolio yang dengan sendirinya memiliki varians 0

Perbedaan dari strategi Kelly biasa

• Strategi Kelly biasanya memaksimalkan tingkat pertumbuhan harapan dari log modal sambil menjaga agar tidak bangkrut
• Namun di luar itu, strategi Kelly biasa tidak menjamin banyak hal; dalam praktiknya bisa saja kehilangan uang dan biasanya ber-varians tinggi
• Dalam game kartu ini, meskipun terjadi kerugian, distribusi warna dek menjadi lebih tidak seimbang sehingga kondisi berikutnya menjadi lebih menguntungkan
• Jika ukuran taruhan cukup kecil, keunggulan yang kemudian menjadi lebih besar akan mengimbangi modal yang hilang dari taruhan yang salah
• Struktur ini mengingatkan pada tahap eksplorasi dan eksploitasi dalam masalah seperti A/B testing

Referensi

• Pembuktian ini didasarkan pada solusi dari Winkler Mathematical Puzzles
• Pembuktian ini terkait dengan gaya Thomas Cover, dan Cover kemudian membuat strategi investasi universal portfolio
• Demo dan materi sumber
  • Kelly_cant_fail.ipynb: notebook contoh dalam artikel
  • card_count_fns.py: fungsi untuk menghitung kartu dan menjalankan taruhan
  • dyn_prog.ipynb: catatan dynamic programming untuk kasus unit modal yang tidak dapat dibagi
  • Demonstrating Kelly Betting with Chips: penjelasan demonstrasi menggunakan chip

[GN⁺]

Opini Hacker News

• Agar strategi ini selalu berlaku, taruhan harus bisa dipecah menjadi bagian-bagian yang tak terhingga kecilnya
  Misalnya, jika 26 kartu merah terkumpul di bagian atas dek, taruhan awal $1.00 akan menyusut hingga 0.000000134 lalu naik kembali menjadi 9.08

  • Jika taruhan awalnya $1e12, bahkan dalam skenario terburuk pun kesalahan pembulatan yang fatal bisa dihindari. Mungkin ada pelajaran hidup di sini
  • Poin yang bagus. Setelah dicoba, sistem ini sangat sensitif terhadap kuantisasi atau pembulatan jumlah taruhan
    Nilai harapan memang kira-kira berada di posisi yang tepat, tetapi variansnya cepat membesar. Jadi selain kasus penting ini, secara umum sistem ini cukup tidak stabil
  • Saya menambahkan catatan lanjutan tentang kasus taruhan diskret di sini: https://win-vector.com/2024/12/21/kelly-betting-with-discret...
    Ada strategi dynamic programming yang diketahui dapat menjamin keuntungan $8.08 dari taruhan $1. Membulatkan strategi Kelly secara sederhana tidak menghasilkan hasil ini
  • Kebanyakan orang sampai pada titik ini. Lemparan koin harus diperlakukan seperti semua lemparan dalam jangka waktu yang sangat panjang, dan agar strateginya bekerja apa adanya, tidak boleh ada satu pun yang dilewatkan
    Jika satu kali terlewat, Anda bisa kehilangan rangkaian yang menguntungkan atau satu kejadian tertentu yang memberi keuntungan besar. Jika grafik harga terhadap waktu digambar seperti grafik Renko, tampilannya akan mirip dengan grafik instrumen apa pun
    Dalam perdagangan saham/kripto/valas di dunia nyata, artinya Anda harus melakukan hampir semua transaksi; jika tidak, kinerja strategi akan turun. Sama seperti tidak mengganti koin saat eksperimen, dalam trading Anda juga tidak boleh mengganti instrumen atau melewatkan transaksi, dan harus melakukannya untuk waktu yang sangat lama
    Tak perlu dikatakan lagi, ini membutuhkan konsistensi yang luar biasa, dan ketika uang dipertaruhkan, stresnya juga besar. Jika diulang setiap hari, beban mental dan fisiknya besar sehingga sulit bertahan lama
  • Pasangan kebalikannya sama seperti mengatakan Martingale tidak bisa gagal jika punya uang tak terbatas

• Cabang menarik terkait Kelly adalah paradoks Proebsting
  Dalam teori probabilitas, paradoks Proebsting adalah argumen yang tampaknya menunjukkan bahwa kriteria Kelly dapat berujung pada kebangkrutan. Secara matematis ini bisa diselesaikan, tetapi terutama dalam penerapan nyata Kelly pada investasi, ia mengajukan persoalan yang menarik. Edward O. Thorp pertama kali membahasnya pada 2008, dan namanya diambil dari pencetusnya, Todd Proebsting
  https://en.wikipedia.org/wiki/Proebsting%27s_paradox

  • Mengutip halaman yang sama, cara mudah untuk mematahkan paradoks ini adalah melihat bahwa Kelly mengasumsikan probabilitas tidak berubah
    Dengan kata lain, Kelly bagus ketika probabilitasnya diketahui dan probabilitas itu tidak berubah
    Jika probabilitasnya tidak diketahui atau bisa berubah, pendekatan yang benar tampaknya harus lebih kompleks daripada Kelly

• Isinya indah, tetapi argumen portofolio terasa seperti jalan memutar yang tidak perlu. Ada pembuktian dua baris dengan induksi

  1. Pada kasus dasar (0,1) atau (1,0), payoff-nya adalah 2
  2. Pada keadaan (r,b), r >= b, jika memiliki $X dan memasang (r-b)/(r+b) pada merah, maka saat menang karena menarik merah, payoff-nya adalah 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)
     Demikian pula, saat kalah karena menarik hitam, payoff-nya adalah 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
  • Mengapa pembuktian induksi itu bukan jalan memutar yang tidak perlu?

• Seperti yang muncul sebagai soal #14 dalam buku wawancara quantitative finance Timothy Falcon, ada permainan kartu yang sangat mirip: Anda membalik kartu dari dek dan menentukan kapan harus berhenti. Merah dihitung $1, hitam dihitung −$1
  Gwern menjelaskan ini dan juga menulis kode untuk memverifikasi strategi berhenti optimal: https://gwern.net/problem-14

  • Jika mengikuti konvensi keuangan standar, hitam seharusnya +$1 dan merah -$1. Artinya harus sesuai dengan konvensi “black” untuk laba dan “red” untuk rugi

• Saat remaja, saya menemukan lewat card counting bahwa jika menebak warna yang tersisa lebih banyak di deck, hasilnya selalu bisa benar lebih dari separuh waktu
  https://en.wikipedia.org/wiki/TRS-80_Model_100
  Saya menulis simulasi di situ dan tidak pernah gagal. Baru-baru ini teringat lagi, lalu menjalankannya 30 juta kali dengan skrip Python, dan tetap tidak gagal
  Saat memikirkan untuk apa ini bisa dipakai, saya terpikir (i) taruhan, (ii) sulap, tetapi keduanya tidak terlalu menjanjikan
  Untuk taruhan, mungkin bisa memasang $1000 melawan $10 milik lawan, tetapi itu bukan jalan menuju keuntungan besar, dan kalau salah atau ditipu bisa kehilangan banyak uang. Setelah dipikir lagi, mungkin lebih baik direkonstruksi dalam bentuk taruhan berantai (parlay)
  Untuk sulap, terlalu lambat. Saya sempat membuat kalimat seperti, “Para parapsikolog gagal membuktikan kemampuan prekognisi secara andal dengan kartu Zener yang keren, tetapi saya membuat protokol yang bisa membuktikannya setiap kali!” namun menilai itu tidak cukup menarik. Membalik satu deck penuh memakan waktu, tidak terlihat seperti keajaiban, dan untuk menolak hipotesis nol pada p=0,01 harus dilakukan 7 kali berturut-turut. Mungkin bisa dilakukan oleh orang dengan penguasaan panggung yang lebih baik, tetapi saya menyerah

  • Ini mengingatkan saya pada algoritma yang saya suka. Dalam sebuah daftar berisi berapa pun banyaknya item berbeda, jika ada elemen mayoritas, elemen itu bisa ditemukan dalam waktu O(N) dan ruang O(1)
    Kadang saya jadikan teka-teki dengan meminta orang menurunkan algoritma ini, tetapi tidak ada yang berhasil memecahkannya. Saya juga tidak bisa
    https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
  • Urutan kartu yang mungkin cukup banyak, sehingga mungkin perlu mengkhawatirkan masalah sumber pseudorandom yang tidak menjelajahi seluruh ruang dengan baik. Dalam kasus seperti itu, simulasi bisa sangat menyesatkan
    Bahkan dengan entropi yang cukup, 30 juta kali jelas belum cukup

• Kriteria Kelly adalah salah satu konsep teori permainan favorit saya, dan banyak digunakan khususnya dalam manajemen bankroll penjudi profesional seperti pemain poker
  Ini cara yang bagus untuk memahami bagaimana mengelola keuangan dan besaran taruhan agar bisa terus maju secara konsisten sambil menghindari risiko yang terlalu besar atau kebangkrutan, tetapi sering disalahterapkan di bidang itu. Kelly menangani hasil biner; jika diterapkan pada situasi yang hasilnya tidak biner, tergantung bagaimana melihat matematikanya, hasilnya bisa tampak hampir benar tetapi sedikit meleset

  • Kriteria Kelly terlihat sangat bagus untuk berbagai bentuk perjudian, tetapi poker mungkin pengecualian
    Karena poker dimainkan melawan pemain lain, utilitas dari distribusi chip tertentu tampaknya harus lebih kompleks daripada sekadar jumlah chip yang dimiliki
    Saya bukan pemain poker
  • Pernyataan “Kelly menangani hasil biner” itu salah. https://entropicthoughts.com/the-misunderstood-kelly-criteri...
    Kriteria Kelly tergeneralisasi dengan baik ke alokasi yang kontinu, simultan, dan kompleks
    Yang dibutuhkan hanyalah daftar tindakan yang bisa dipilih, serta distribusi probabilitas gabungan atas hasil kekayaan setelah tiap tindakan. Tindakannya boleh berupa tindakan majemuk dengan hasil kontinu
  • Benar bahwa kriteria Kelly menangani hasil biner, dan karena itu tidak cocok untuk poker
    Dalam poker, menang-kalah bukan biner karena jumlah yang dimenangkan atau hilang berbeda-beda, sehingga digunakan nilai ekspektasi. Setelah menghitung nilai ekspektasi kasar, biasanya juga memakai kalkulator varians, misalnya https://www.primedope.com/poker-variance-calculator/, untuk melihat dalam jangka panjang seberapa sering dan seberapa besar kemungkinan menang selama jumlah hand tertentu
  • Apakah ini juga bisa bekerja untuk cara bertaruh pada warna di roulette?
    Rasanya akan menghabiskan banyak waktu tanpa menang maupun kalah

• Akan menjadi demo yang lebih baik jika diperkecil ke angka yang lebih mudah ditangani, misalnya deck berisi 2 kartu hitam dan 2 kartu merah
  Pada giliran 1, r = b, jadi tidak bertaruh
  Pada giliran 2, bertaruh 1/3 pada warna yang tidak muncul di giliran 1
  Pada giliran 3, jika salah di giliran 2, hanya tersisa 2/3 dari modal taruhan, tetapi karena warna dua kartu berikutnya diketahui, setiap kali modal bisa digandakan sehingga setelah giliran 3 menjadi 4/3 dari modal awal. Jika benar, modal menjadi 4/3, tetapi karena masih tersisa satu merah dan satu hitam, pada giliran ini tidak bertaruh
  Pada giliran 4, karena warna kartu terakhir diketahui, uang digandakan sehingga menjadi 8/3 dari modal awal
  Dan latihan untuk pembaca adalah membuktikan optimalitasnya; ini cukup straightforward, tetapi saya tidak percaya ada bukti yang singkat

  • Benar. Namun pada contoh 4 kartu, hanya ada satu percabangan nontrivial di giliran 3
    Jadi jika dimulai dengan contoh 4 kartu lalu menunjukkan diagram pohon untuk kasus 5 dan 6 kartu, angkanya masih mudah ditangani sehingga bagus untuk membangun intuisi induksi ke kasus umum
  • Saya bisa mengikuti argumen umumnya, tetapi belum cukup untuk menerima mengapa hasilnya persis sama terlepas dari urutan kartu

• Dalam praktiknya, ada banyak faktor yang membuat penggunaan Kelly lebih sulit daripada contoh mainan
  Berapa ukuran bankroll-nya? Apakah kas yang dimiliki? Total kekayaan bersih? Kekayaan bersih likuid? Pendapatan kerja masa depan?
  Bergantung pada ukuran bankroll, banyak faktor ikut masuk. Misalnya jika bankroll $100 dan semuanya hilang, biasanya bukan masalah besar. Tetapi jika bankroll $1 million, kita akan jauh lebih enggan menempatkannya dalam risiko
  Berapa nilai ekspektasinya? Apakah diketahui? Apakah stasioner? Apakah permainannya jujur?
  Bergantung pada karakteristik statistik nilai ekspektasi, pendekatan ukuran taruhan harus disesuaikan secara besar. Di area seperti poker, di mana nilai ekspektasi hanya bisa diestimasi dan banyak penipu, ukuran taruhan harus ditentukan di bawah ketidakpastian besar
  Besaran taruhan apa yang tersedia?
  Dalam praktiknya, tidak ada rentang besaran taruhan yang kontinu. Biasanya hanya tersedia nominal diskret, seperti dari $5 sampai $500 dalam kelipatan $5 atau $25. Jika bankroll terlalu rendah, kita tersingkir dari permainan; jika terlalu tinggi, kita tidak lagi bisa memaksimalkan keuntungan
  Pada akhirnya, karena kompleksitas semacam ini, penjudi profesional sering bertaruh dengan half Kelly atau quarter Kelly

  • Dalam praktiknya, bukan hanya tidak bisa membuat besaran taruhan yang kontinu; hak untuk memasang taruhan itu sendiri juga bisa berbiaya
    Dalam trading ada spread dan komisi, sementara di meja kasino ada rake

• Sangat keren bahwa hasilnya tidak memiliki varians. Namun karena itu, mengingat struktur khusus masalah ini, rasanya seperti seharusnya ada strategi yang menghasilkan ekspektasi keuntungan lebih tinggi
  Apakah ada yang tahu apakah strategi Kelly optimal di sini?

  • Rasanya ini kemungkinan memiliki nilai harapan tertinggi. Saya mencoba strategi membalik semua kartu sampai hanya tersisa satu warna, lalu mempertaruhkan semuanya setiap kali; setelah dijalankan sejuta kali, hasilnya 9,08
    Awalnya saya mengira strategi-strategi ini sangat berbeda, tetapi ternyata tidak sepenuhnya begitu. Strategi Kelly juga melakukan hal yang sama ketika hanya tersisa satu warna. Bedanya, strategi ini tidak melakukan apa pun sebelumnya
    Meski begitu, keduanya terasa seperti kasus ekstrem. Ketika hanya satu warna yang tersisa, mempertaruhkan semuanya adalah satu-satunya langkah yang benar, dan pada akhirnya persoalannya adalah apa yang dilakukan sebelum itu. Tidak melakukan apa pun dan Kelly tampaknya menjadi satu-satunya strategi yang terlihat bagus
  • Apa maksudnya optimal? Apakah maksudnya bersedia menanggung risiko bangkrut demi nilai harapan yang lebih tinggi?
  • Di buku, ia mengklaim optimal untuk himpunan strategi yang disebut “rasional”
    Namun argumennya tidak mengalir sealami pembuktian yang menunjukkan varians 0, jadi saya tidak memasukkannya. Teks aslinya juga tampaknya menyebut sub-strategi di dalam portofolio sebagai “strategi murni” dan mengisyaratkan pembuktian teori permainan
  • Dalam permainan ini, selama mengikuti aturan bahwa jika sisa deck semuanya berwarna sama maka harus mempertaruhkan semua yang dimiliki pada warna itu, nilai harapan semua strategi sama
  • Kriteria Kelly justru merupakan strategi yang menghasilkan keuntungan lebih baik karena struktur unik masalah ini

• Masalah dan solusinya tampaknya berasal dari Thomas Cover
  Saya tidak ingat contoh spesifik ini, tetapi saya mempelajari kriteria Kelly di kelas yang diajarkan Thomas Cover. Ia adalah salah satu dosen favorit saya, dan setiap diskusi dengannya selalu menarik dan berharga. RIP

  • Ia juga meninggalkan banyak makalah menarik di bidang ini, dan sebagian di antaranya mengisi porsi yang cukup besar dalam buku tentang kriteria Kelly