A estratégia de Kelly que não pode falhar

• No Next Card Bet, em que se acompanha continuamente a distribuição de cores de um baralho de 52 cartas, a estratégia de Kelly, ao contrário de sua natureza normalmente de alta variância, sempre termina o capital inicial de $1 em cerca de $9,08
• A regra de aposta é simples: se as cartas vermelhas restantes r e as pretas restantes b forem iguais, não aposte; caso contrário, aposte na cor que tiver mais cartas restantes uma fração do capital atual igual a |r - b| / (r + b)
• Mesmo executando 10.000 baralhos embaralhados em Python, o capital final permanece no intervalo de 9.081329549427776 a 9.081329549427803, gerando um retorno maior do que a estratégia de dobrar que aposta só na última carta, sem variação
• A prova distribui igualmente o capital inicial entre (52 choose 26) = 495,918,532,948,104 arranjos possíveis de vermelho/preto e constrói um portfólio em que apenas uma subestratégia compatível com o baralho real dobra 52 vezes seguidas
• Como a variação total do capital desse portfólio coincide com o padrão conservador da estratégia de Kelly, uma estratégia de Kelly que normalmente pode perder dinheiro se torna, neste jogo, uma estratégia de variância zero

---

Regras e intuição do Next Card Bet

• A estratégia de alocação de apostas de Kelly é uma forma de definir a fração da aposta em situações de jogo usando informação ou viés a seu favor
• A estratégia de Kelly em geral é conhecida como uma estratégia agressiva de alta variância, e apostar acima da fração de Kelly pode aumentar o risco de ruína
• No “Next Card Bet” apresentado em Mathematical Puzzles, de Peter Winkler, essa estratégia funciona sem risco e com variância zero
• O jogo começa com um baralho padrão de 52 cartas
  • Há 26 cartas vermelhas e 26 cartas pretas
  • O baralho é embaralhado, as cartas são reveladas uma a uma e as cartas reveladas não voltam ao baralho
  • O jogador pode apostar qualquer fração do capital atual em a próxima carta ser vermelha ou preta
  • O pagamento é de 1:1, e o capital inicial é $1
• Ao contar as cartas que já saíram, é possível saber quantas de cada cor restam no baralho invisível
  • Se você não apostar até a última carta, poderá saber com certeza a cor da carta restante
  • Essa estratégia simples permite dobrar o capital com segurança, apostando tudo na última carta para chegar a 2x

Fração de aposta de Kelly

• A estratégia de Kelly escolhe a aposta que maximiza o valor esperado do logaritmo do capital final
• Se o número de cartas vermelhas restantes for r e o de pretas restantes for b, e r > b, então a probabilidade de sair vermelha é r / (r + b)
• O log esperado do capital é maximizado pela expressão
  • P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction)
• No ponto em que a derivada dessa expressão é zero, a fração de aposta se torna (r - b) / (r + b)
• A estratégia inteira assume risco apenas na medida da diferença entre as duas cores restantes
  • Se r = b, não se aposta
  • Se r > b, aposta-se uma fração do capital atual igual a |r - b| / (r + b) em “red”
  • Se b > r, aposta-se uma fração do capital atual igual a |r - b| / (r + b) em “black”

Resultados da simulação em Python

• O exemplo em Python executa a estratégia de Kelly com a função run_bets(is_red)
  • stake começa em 1.0
  • A cada carta, o número de cartas vermelhas e pretas restantes é atualizado
  • Aposta-se na cor mais numerosa uma fração igual a abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining)
  • Se a previsão estiver certa, o valor apostado volta em dobro; se estiver errada, ele é perdido
• O gerador de números aleatórios usado é np.random.default_rng(2024)
• Ao gerar 10.000 baralhos com 26 cartas vermelhas entre 52, os resultados convergem praticamente para o mesmo valor
  • Mínimo: 9.081329549427776
  • Máximo: 9.081329549427803
• A diferença entre os resultados foi menor que 1e-8, e em todas as execuções o retorno foi de cerca de 9,08x o capital inicial
• Um retorno de 9,08x é muito maior que o da estratégia segura de 2x obtida apostando apenas na última carta

Prova do portfólio de variância zero

• O número de arranjos possíveis de cartas vermelhas e pretas é (52 choose 26) = 495,918,532,948,104
• Usa-se o resultado padrão de que, em um baralho bem embaralhado, todos esses arranjos de vermelho/preto surgem com a mesma probabilidade
• A estratégia de portfólio trata cada arranjo possível de vermelho/preto como uma subestratégia separada
  • A cada subestratégia é alocada uma fração de 1 / (52 choose 26) do capital inicial
  • As subestratégias administram apenas o próprio dinheiro, sem redistribuição entre si
  • Cada subestratégia assume que o arranjo a ela atribuído é o baralho real e aposta todo o capital, a cada carta, na cor correspondente
• Todas as subestratégias diferentes do baralho real acabam apostando tudo em uma carta errada em algum momento e quebram
• Apenas a única subestratégia que coincide exatamente com o baralho real acerta as 52 cartas e multiplica o capital por 2^52
• Por isso, o retorno final do portfólio inteiro é sempre o mesmo, independentemente da ordem das cartas
  • $1 / (52 choose 26) * 2^52
  • Cerca de $9,08

Equivalência entre o portfólio e a estratégia de Kelly

• No portfólio, as subestratégias que ainda não quebraram fazem previsões sobre a próxima carta: vermelha ou preta
• Quando restam r cartas vermelhas e b pretas, a proporção de previsões das subestratégias segue a proporção das cores restantes
• Quando a próxima carta é revelada, o grupo que errou quebra, e o grupo que acertou dobra o capital
• Nesse momento, a variação total do capital do portfólio coincide exatamente com o padrão conservador da estratégia de Kelly de apostar |r - b| / (r + b) na cor que resta em maior quantidade
• A razão de a estratégia de Kelly ter variância zero aqui é que ela se move exatamente como essa estratégia de portfólio, que já tem variância zero por construção

O que muda em relação à estratégia de Kelly usual

• A estratégia de Kelly normalmente busca maximizar a taxa esperada de crescimento do logaritmo do capital, evitando a ruína
• Mas, fora isso, a estratégia de Kelly usual não garante muita coisa: na prática, ela pode perder dinheiro e geralmente tem alta variância
• Neste jogo de cartas, mesmo que haja perda em uma aposta, a distribuição de cores do baralho fica mais desequilibrada, tornando as condições futuras mais favoráveis
• Se as apostas forem pequenas o suficiente, o capital perdido em apostas erradas é compensado pela vantagem maior que surge depois
• Essa estrutura lembra as fases de exploração e aproveitamento em problemas como testes A/B

Referências

• A prova se baseia na solução apresentada em Winkler Mathematical Puzzles
• Essa prova tem relação com o estilo de Thomas Cover, que depois criou a estratégia de investimento universal portfolio
• Demo e materiais-fonte
  • Kelly_cant_fail.ipynb: notebook do exemplo do texto
  • card_count_fns.py: funções de contagem de cartas e execução das apostas
  • dyn_prog.ipynb: notebook de programação dinâmica para o caso de unidades de capital indivisíveis
  • Demonstrating Kelly Betting with Chips: explicação da demonstração com fichas

[GN⁺]

Comentários do Hacker News

• Para essa estratégia valer sempre, a aposta precisa poder ser dividida em partes infinitamente pequenas.
  Por exemplo, se 26 cartas vermelhas estiverem concentradas no topo do baralho, a aposta inicial de $1.00 cai até 0.000000134 e depois volta a subir para 9.08.

  • Se a aposta inicial fosse de $1e12, seria possível evitar erros de arredondamento fatais mesmo no pior caso. Talvez haja uma lição de vida aqui.
  • Boa observação. Fiz alguns experimentos e esse sistema se mostrou muito sensível à quantização ou ao arredondamento do valor apostado.
    O valor esperado fica aproximadamente no lugar certo, mas a variância cresce rapidamente. Então, além desse caso importante, ele é bem instável no geral.
  • Acrescentei aqui uma nota de acompanhamento sobre o caso de apostas discretas: https://win-vector.com/2024/12/21/kelly-betting-with-discret...
    Há uma estratégia de programação dinâmica conhecida que garante lucro de $8.08 em uma aposta de $1. Simplesmente arredondar a estratégia de Kelly não produz esse resultado.
  • A maioria chega a esse ponto. É preciso tratar os lançamentos de moeda como todos os lançamentos ao longo de um período muito longo, e para a estratégia funcionar como está, não se pode pular nem uma vez.
    Se você perder uma única vez, pode deixar passar uma sequência lucrativa ou uma jogada específica de grande lucro. Se desenhar um gráfico de preço versus tempo como um gráfico Renko, ele se parece com o gráfico de qualquer ativo.
    Na negociação real de ações/cripto/forex, isso significa que você precisa fazer praticamente todas as operações; caso contrário, o desempenho da estratégia cai. Assim como, no experimento, você não troca a moeda, no trading você não pode trocar de ativo nem perder operações, e precisa manter isso por muito tempo.
    Nem é preciso dizer que isso exige uma consistência enorme e, quando há dinheiro envolvido, o estresse também aumenta. Repetir isso todos os dias gera um desgaste mental e físico grande, então é difícil sustentar por muito tempo.
  • O par oposto disso é como dizer que, com dinheiro infinito, o Martingale não pode falhar.

• Uma ramificação interessante sobre Kelly é o paradoxo de Proebsting.
  Na teoria das probabilidades, o paradoxo de Proebsting é um argumento que parece mostrar que o critério de Kelly pode levar à ruína. Matematicamente, ele pode ser resolvido, mas levanta questões interessantes na aplicação prática de Kelly, especialmente em investimentos. Foi discutido pela primeira vez por Edward O. Thorp em 2008 e recebeu o nome de seu criador, Todd Proebsting.
  https://en.wikipedia.org/wiki/Proebsting%27s_paradox

  • Citando a mesma página, uma forma fácil de derrotar esse paradoxo é notar que Kelly pressupõe que as probabilidades não mudam.
    Ou seja, Kelly funciona bem quando você conhece as probabilidades e elas não mudam.
    Se você não conhece as probabilidades, ou se elas podem mudar, imagino que a abordagem correta precise ser mais complexa do que Kelly.

• É um conteúdo bonito, mas o argumento de portfólio parece um desvio desnecessário. Dá para fazer uma prova de duas linhas por indução.

  1. O caso-base, (0,1) ou (1,0), tem payoff 2.
  2. No estado (r,b), r >= b, com $X, se você apostar (r-b)/(r+b) no vermelho, então, ao tirar vermelho e ganhar, o 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).
     Da mesma forma, ao tirar preto e perder, o 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
  • Por que essa prova por indução não é um desvio desnecessário?

• Como no problema nº 14 do livro de entrevistas de finanças quantitativas de Timothy Falcon, há um jogo de cartas muito parecido em que você vira cartas do baralho e decide quando parar. Vermelho conta como $1, preto como −$1.
  Gwern explicou isso e também escreveu código para verificar a estratégia ótima de parada: https://gwern.net/problem-14

  • Para seguir a convenção financeira padrão, preto deveria ser +$1 e vermelho deveria ser -$1. Ou seja, deveria estar de acordo com a convenção de “no azul” e “no vermelho”.

• Quando eu era adolescente, descobri, contando cartas, que se tentasse adivinhar a cor que havia em maior quantidade restante no baralho, eu sempre acertaria mais da metade das vezes
  https://en.wikipedia.org/wiki/TRS-80_Model_100
  Escrevi uma simulação nele e ela nunca falhou. Recentemente lembrei disso de novo e rodei 30 milhões de vezes com um script em Python, e também não falhou
  Ao pensar no que poderia fazer com isso, imaginei (i) apostas e (ii) mágica, mas nenhum dos dois pareceu muito promissor
  Como aposta, eu poderia apostar US$ 1000 contra US$ 10 da outra pessoa, mas não é um caminho para ganhar muito dinheiro, e se eu errar ou for enganado posso perder uma boa quantia. Pensando melhor, talvez fosse melhor reformular isso como uma aposta acumulada (parlay)
  Como mágica, é lento demais. Cheguei a criar uma fala do tipo: “Parapsicólogos não conseguiram demonstrar poderes de premonição de forma confiável com aquelas elegantes cartas de Zener, mas eu criei um protocolo que consegue provar isso todas as vezes!”, mas concluí que não era divertido o bastante. Leva tempo para passar por um baralho inteiro, não parece um milagre, e para rejeitar a hipótese nula com p=0,01 seria preciso fazer isso 7 vezes seguidas. Talvez alguém com melhor presença de palco conseguisse, mas eu desisti

  • Isso me lembra um algoritmo de que gosto. Em uma lista com qualquer número de itens diferentes, se existir um elemento majoritário, é possível encontrá-lo em tempo O(N) e espaço O(1)
    Às vezes proponho como quebra-cabeça derivar esse algoritmo, mas ninguém conseguiu resolver. Eu também não consegui
    https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
  • Há tantas ordens possíveis de cartas que talvez seja preciso se preocupar com o problema de uma fonte pseudoaleatória não percorrer adequadamente todo o espaço. Nesses casos, simulações podem ser muito enganadoras
    Mesmo com entropia suficiente, 30 milhões certamente não é o bastante

• O critério de Kelly é um dos meus conceitos favoritos de teoria dos jogos, e é muito usado na gestão de banca de jogadores profissionais, especialmente jogadores de pôquer
  É uma boa forma de entender como administrar finanças e tamanhos de aposta para seguir avançando de maneira consistente sem assumir risco grande demais nem quebrar, mas é frequentemente aplicado de forma errada nessa área. Kelly lida com resultados binários; quando aplicado a situações em que o resultado não é binário, dependendo de como se olha a matemática, o resultado pode parecer quase correto, mas ficar ligeiramente deslocado

  • O critério de Kelly parece excelente para várias formas de jogo, mas pôquer pode ser uma exceção
    Como no pôquer se joga contra outros jogadores, a utilidade de uma determinada distribuição de fichas parece ter de ser mais complexa do que simplesmente a quantidade de fichas possuídas
    Não sou jogador de pôquer
  • A afirmação de que “Kelly lida com resultados binários” está errada. https://entropicthoughts.com/the-misunderstood-kelly-criteri...
    O critério de Kelly se generaliza bem para alocações contínuas, simultâneas e complexas
    O que é necessário é apenas uma lista de ações possíveis e a distribuição de probabilidade conjunta dos resultados de riqueza após cada ação. A ação pode ser uma ação composta com resultados contínuos
  • Está certo dizer que o critério de Kelly lida com resultados binários, e por isso não se aplica ao pôquer
    No pôquer, ganhar ou perder não é binário, pois o valor ganho ou perdido varia; por isso se usa o valor esperado. Depois de calcular um valor esperado aproximado, usa-se também uma calculadora de variância, por exemplo https://www.primedope.com/poker-variance-calculator/, para ver, no longo prazo, com que frequência e quanto é provável ganhar ao longo de um determinado número de mãos
  • Será que isso funcionaria também apostando em cores na roleta?
    Parece que se gastaria muito tempo sem ganhar nem perder

• Teria sido uma demonstração melhor se tivesse reduzido para números mais fáceis de tratar, por exemplo um baralho com 2 cartas pretas e 2 cartas vermelhas
  No turno 1, r = b, então não se aposta
  No turno 2, aposta-se 1/3 na cor que não saiu no turno 1
  No turno 3, se você errou no turno 2, restam apenas 2/3 da banca, mas como sabe as cores das próximas duas cartas, dobra a cada vez e termina o turno 3 com 4/3 da banca original. Se acertou, a banca está em 4/3, mas restam uma vermelha e uma preta, então não se aposta neste turno
  No turno 4, como você sabe a cor da última carta, dobra o dinheiro e fica com 8/3 da banca original
  E o exercício deixado ao leitor é provar a otimalidade; é bem straightforward, mas não acredito que haja uma prova curta

  • Certo. Mas no caso de 4 cartas só há uma ramificação não trivial no turno 3
    Por isso, começar com o exemplo de 4 cartas e depois mostrar diagramas de árvore para os casos de 5 e 6 cartas, ainda com números fáceis de lidar, ajuda a construir a intuição para induzir ao caso geral
  • Consegui acompanhar o argumento geral, mas não o suficiente para me convencer de por que o resultado fica exatamente igual independentemente da ordem das cartas

• Na prática, há muitos fatores que tornam o uso de Kelly mais difícil do que no exemplo de brinquedo
  Qual é o tamanho da banca? É o dinheiro em caixa? O patrimônio líquido total? O patrimônio líquido líquido? A renda futura do trabalho?
  Dependendo do tamanho da banca, vários fatores entram em jogo. Por exemplo, se a banca é de US$ 100, perder tudo normalmente não é um grande problema. Mas se a banca é de US$ 1 million, a pessoa fica muito mais relutante em expô-la ao risco
  Qual é o valor esperado? Ele é conhecido? É estacionário? O jogo é honesto?
  Dependendo das propriedades estatísticas do valor esperado, é preciso ajustar bastante a abordagem de dimensionamento das apostas. Em áreas onde o valor esperado só pode ser estimado e há muitos golpistas, como no pôquer, é preciso definir o tamanho das apostas sob grande incerteza
  Quais valores de aposta estão disponíveis?
  Na prática, não existe uma faixa contínua de valores de aposta. Em geral, só há valores discretos, como de US$ 5 a US$ 500 em incrementos de US$ 5 ou US$ 25. Se a banca cair demais, você é expulso do jogo; se subir demais, já não consegue maximizar o lucro
  No fim, por causa dessas complexidades, jogadores profissionais muitas vezes apostam meio Kelly ou um quarto de Kelly

  • Na prática, além de não ser possível criar valores de aposta contínuos, também pode ser necessário pagar pelo próprio direito de fazer a aposta
    Em negociações há spread e comissões; nas mesas de cassino, há rake

• O fato de o resultado não ter variância é muito interessante. Mas, por causa disso, pela estrutura especial deste problema, dá a impressão de que deveria existir uma estratégia com retorno esperado maior
  Alguém sabe se a estratégia de Kelly é ótima aqui?

  • Tenho a sensação de que deve ser a de maior valor esperado. Tentei uma estratégia de virar todas as cartas até restar apenas uma cor e então apostar tudo a cada vez; depois de rodar um milhão de vezes, deu 9,08
    No começo achei que essas estratégias fossem muito diferentes, mas não é exatamente assim. A estratégia de Kelly também faz a mesma coisa quando resta apenas uma cor. A diferença é que essa estratégia não faz nada antes disso
    Mesmo assim, as duas parecem casos extremos. Apostar tudo quando resta apenas uma cor é a única jogada correta, e no fim a questão é o que fazer antes disso. Não fazer nada e Kelly parecem ser as únicas estratégias boas
  • O que significa ser ótima? Quer dizer que você pode aceitar risco de falência em troca de um valor esperado maior?
  • O livro afirma que ela é ótima para um conjunto de estratégias que chama de “racionais”
    Só que esse argumento não flui tão naturalmente quanto a prova que mostra variância 0, então não o incluí. O texto original também chamava as subestratégias dentro do portfólio de “estratégias puras”, sugerindo uma prova de teoria dos jogos
  • Neste jogo, se você apenas seguir a regra de que, quando o baralho restante for todo da mesma cor, deve apostar tudo o que tem nessa cor, todas as estratégias têm o mesmo valor esperado
  • O critério de Kelly é justamente a estratégia que gera retornos melhores por causa da estrutura peculiar deste problema

• Este problema e a solução parecem ter vindo de Thomas Cover
  Não me lembro deste exemplo específico, mas aprendi o critério de Kelly em uma aula dada por Thomas Cover. Ele foi um dos meus professores favoritos, e qualquer discussão com ele era interessante e valiosa. Descanse em paz

  • Ele também deixou muitos artigos interessantes nessa área, e alguns deles ocupam uma parte considerável do livro sobre o critério de Kelly