Nasihat, konsultasi, dan pelatihan ilmu data
Oleh
pada •Perkenalan
Anda mungkin pernah mendengar tentang Strategi alokasi taruhan Kelly. Ini adalah sistem untuk mengeksploitasi informasi atau bias dengan benar dalam situasi perjudian. Ini juga dikenal sebagai strategi yang sangat agresif atau varian tinggi, karena bertaruh lebih dari pilihan Kelly bisa sangat merusak.
Baru-baru ini saya mengalami permainan kartu aneh yang menggunakan strategi Kelly tanpa risiko varian nol. Peter Winkler menyebut permainan ini “Taruhan Kartu Berikutnya” dalam bukunya yang luar biasa Teka-teki Matematika. Masalah dan solusinya tampaknya datang dari Thomas Cover. Saya menemukan permainan taruhan ini dan analisisnya luar biasa, dan ingin membaginya dengan Anda di sini.
Permainan
Permainan ini dimainkan sebagai berikut. Setumpuk 52 kartu standar yang terdiri dari 26 kartu merah dan 26 kartu hitam dikocok dan pemain memulai dengan taruhan $1. Setiap kartu dibuka satu per satu, tanpa diganti di dek. Pemain diperbolehkan untuk bertaruh berapa pun pecahan dari taruhannya saat ini jika kartu berikutnya berwarna hitam atau merah dengan hasil satu lawan satu.
Pemain jelas memiliki strategi menguntungkan yang melibatkan penghitungan jumlah kartu hitam dan merah yang terlihat. Menghitung kartu yang terlihat memungkinkan mereka mengetahui berapa banyak kartu dari setiap warna yang tersisa di bagian tumpukan kartu yang tidak terlihat. Misalnya, mereka dapat dengan aman menggandakan taruhannya dengan tidak bertaruh pada kartu apa pun selain kartu terakhir. Hal ini memungkinkan mereka untuk dengan aman mempertaruhkan seluruh taruhan mereka pada warna kartu terakhir yang tidak terlihat.
Strategi Kelly
Strategi Kelly adalah memilih taruhan yang memaksimalkan logaritma taruhan yang diharapkan. Kita dapat memperolehnya sebagai berikut.
Membiarkan r
menjadi nomor kartu merah yang tersisa di dek dan b
kartu hitam tersisa. Tanpa kehilangan asumsi umum r > b
. Kami kemudian ingin memaksimalkan P(draw red) * log(1 + bet_fraction) + P(draw black) * log(1 - bet_fraction)
sebagai fungsi dari bet_fraction
. Ekspresi ini dimaksimalkan jika turunannya nol. Peluang terambilnya warna merah selanjutnya adalah r/(r + b)
. Jadi kita perlu menyelesaikannya (r/(r + b)) / (1 + bet_fraction) - (b/(r + b)) / (1 - bet_fraction) = 0
. Beberapa aljabar memberitahu kita bet_fraction = (r - b) / (r + b)
.
Keseluruhan strategi taruhan Kelly adalah:
- Jika
r = b
maka tidak ada taruhan - Jika
r > b
bertaruh a|r - b| / (r + b)
faksi taruhan Anda pada “merah” - Jika
b > r
bertaruh a|r - b| / (r + b)
faksi taruhan Anda pada “hitam.”
Dalam (1):
# import tools
import numpy as np
Dalam (2):
# set up our pseudo-random number generator to produce shuffled decks
rng = np.random.default_rng(2024)
Dalam (3):
# define our deck shuffling tool
def k_array_with_t_true(k: int, t: int):
"""Create a length-k boolean array with t-True values"""
is_true = np.array((False) * k, dtype=bool)
is_true(rng.choice(k, size=t, replace=False)) = True
return is_true
Dalam (4):
# implement our betting strategy
def run_bets(is_red) -> float:
"""Run the Kelly betting strategy"""
stake = 1.0
n_red_remaining = int(np.sum(is_red))
n_black_remaining = len(is_red) - n_red_remaining
for i in range(len(is_red)):
# form bet
bet_red = 0
bet_black = 0
fraction = np.abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining)
if n_red_remaining > n_black_remaining:
bet_red = stake * fraction
elif n_black_remaining > n_red_remaining:
bet_black = stake * fraction
# derive outcome
stake = stake - (bet_red + bet_black)
if is_red(i):
stake = stake + 2 * bet_red
n_red_remaining = n_red_remaining - 1
else:
stake = stake + 2 * bet_black
n_black_remaining = n_black_remaining - 1
return stake
Dalam (5):
# play the game 10000 times
payoffs = (
run_bets(k_array_with_t_true(52, 26)) for _ in range(10000)
)
assert np.max(payoffs) - 1e-8 < np.min(payoffs)
(np.min(payoffs), np.max(payoffs))
Keluar (5):
(9.081329549427776, 9.081329549427803)
Untuk setiap putaran kami menghasilkan pengembalian 9.08
kali lipat taruhan awal kami. Sungguh luar biasa bahwa tidak ada variasi atau perbedaan dalam hasil. Perhatikan ini 9.08
kali pengembalian jauh lebih besar daripada 2
kali kembalinya strategi sederhana “tunggu sampai akhir”.
Hasil ini sangat tidak biasa untuk strategi Kelly. Strategi Kelly menjamin untuk tidak “bust” (kehilangan semua uang) dan memaksimalkan tingkat pertumbuhan yang diharapkan dari logaritma taruhan. Namun mereka biasanya tidak menjamin hal lain, bahkan bisa merugi, dan biasanya memiliki variansi yang tinggi. Bagaimana bisa dalam hal ini Kelly tidak bisa gagal?
Penjelasan
Ada bukti luar biasa bahwa strategi ini adalah zero variance.
Ada (52 choose 26) = 495,918,532,948,104
kemungkinan susunan kartu merah versus hitam. Ini adalah hasil standar (tidak dibuktikan di sini) bahwa masing-masing pengaturan ini sebenarnya memiliki kemungkinan yang sama dalam tumpukan yang dikocok dengan benar.
Kami mendefinisikan strategi “portofolio” baru sebagai berikut.
- Masing-masing
(52 choose 26)
kemungkinan pengaturan merah/hitam ditetapkan sebagai sub-strategi dalam portofolio kami. - Kami mengalokasikan a
1/(52 choose 26)
sebagian kecil dari taruhan awal kami untuk setiap sub-strategi. Kami mengizinkan setiap sub-strategi untuk menyimpan uangnya sendiri dan tidak mengalokasikan kembali uang antar sub-strategi. - Setiap sub-strategi mengasumsikan pengaturan merah/hitam yang ditetapkan adalah apa yang akan terjadi di dek sebenarnya. Sub-strategi mempertaruhkan seluruh taruhannya pada setiap kartu, bertaruh bahwa kartu yang terbuka akan cocok dengan kartu yang sesuai dengan pengaturannya sendiri.
Semua kecuali satu sub-strategi portofolio akan kehilangan seluruh uangnya karena pada akhirnya mereka mempertaruhkan seluruh taruhannya pada tebakan yang salah. Strategi tunggal yang menebak dengan benar seluruh pengalaman akhir dek 52
dua kali lipat dan tidak ada kerugian. Dengan demikian, strategi ini melipatgandakan taruhan awalnya sebesar 2^(52)
. Jadi strategi portofolio kami sendiri selalu mengalami pengembalian agregat total sebesar $1/(52 choose 26) * 2^(52) ~ $9.08
pada inisial $1
mempertaruhkan. Pengembalian portofolio akhir ini tidak bergantung pada urutan kartunya.
Klaim untuk mengakhiri argumen ini adalah: strategi portofolio baru sebenarnya identik dengan strategi Kelly sebelumnya.
Bayangkan apa yang terjadi pada portofolio ketika kita mendapat kartu merah. Dalam strategi portofolio kami a r / (r + b)
sebagian kecil dari sub-strategi tidak bangkrut mengharapkan kartu berikutnya berwarna “merah”, dan a b / (r + b)
sebagian kecil dari sub-strategi non-bangkrut mengharapkan kartu berikutnya menjadi “hitam”. Pengundian berikutnya membuat salah satu keluarga ini bangkrut, dan menggandakan keluarga lainnya (tergantung pada warna yang digambar). Beberapa menunjukkan bahwa strategi portofolio mengembangkan saham gabungannya sebagai berikut:
- Agregat
stake
pergi kestake * 2 * b / (r + b)
pada menggambar “merah” - Agregat
stake
pergi kestake * 2 * r / (r + b)
tentang menggambar “hitam.”
Ini adalah masalah aljabar untuk memastikan bahwa hasil portofolio ini benar tepat pola pembayaran untuk strategi puting Kelly kami sebelumnya |r - b| / (r + b)
pada sisa warna yang paling umum. Strategi Kelly memiliki keuntungan yang sama persis dengan strategi portofolio, dan kami mendapatkan hasil bahwa kedua strategi tersebut adalah satu dan sama.
Strategi Kelly adalah zero variance karena identik dengan strategi portofolio yang merupakan zero variance.
Ide yang ingin saya ambil adalah sebagai berikut. Saat kita bertaruh pada warna mayoritas, setiap kali kita kalah taruhan, dek menjadi lebih tidak seimbang dan lebih menguntungkan bagi kita. Jika kita membuat taruhan cukup kecil maka keuntungan dari taruhan yang salah mengimbangi hilangnya modal. Dalam hal ini strategi Kelly adalah menentukan harga informasi atau menentukan harga ketidakpastian dengan tepat. Hal ini mirip dengan pertimbangan “fase eksplorasi versus eksploitasi” dalam masalah seperti pengujian A/B.
Bukti yang diberikan berasal dari Winkler Teka-teki Matematika. SAYA dengan kuat merekomendasikan untuk mengambil buku tersebut untuk melihat tulisannya tentang hal ini dan banyak masalah lainnya. Buktinya sendiri sangat banyak pada gaya Covernya. Inilah Sampul yang kemudian menciptakan portofolio universal strategi investasi.
Kategori: Tutorial Keuangan Kuantitatif Matematika