Simulando um dado de 7 lados de um dado de 5 lados

A.S.: Sim, aparentemente o singular de ‘dado’ é ‘dado’. 😉

Uma complicada tarefa de programação tem flutuado pela Internet que, como você deve ter adivinhado pela minha tentativa de um título pragmático, pode ser formalizada da seguinte forma:

Dado uma função que retorna um número uniformemente aleatório entre 1 e 5 (inclusive), projete uma função que retorna um número uniformemente aleatório entre 1 e 7 (inclusive).

Se a intersecção de algoritmos e estatísticas é o seu tipo de coisa, sinta-se à vontade para tentar! Um desafio extra é fazer com que o seu algoritmo seja limitado no tempo. Achei isto um exercício divertido, apenas para perceber que existem limitações fundamentais em jogo aqui.

O claro, um dado aqui significa um gerador aleatório perfeitamente uniforme que existe apenas em teoria. Os dados do mundo real são governados por leis naturais e imperfeições ambientais de tal forma que são apenas uma aproximação (embora boa) deste modelo abstrato.

Uma solução sem limites

Vejamos uma família de algoritmos sem limites. A fim de criar um gerador aleatório que tenha pelo menos 7 resultados, precisaremos rolar o dado de 5 lados pelo menos duas vezes. Rolá-lo duas vezes cria 5^2=25 resultados possíveis, e embora este não seja um fator de 7, podemos atribuir os primeiros 21 resultados a 7 grupos de igual tamanho 3. No entanto, se acabarmos em um dos 4 resultados restantes, então o procedimento deve ser reiniciado. Não podemos simplesmente atribuir qualquer um destes 4 estados finais azarados a um output, pois isso irá estragar a propriedade de aleatoriedade uniforme.

No gráfico acima, os círculos representam ‘estados’ do nosso programa, e o texto dentro deles é o valor mais recente do dado rolado. As caixas verdes então representam a saída que atribuímos dependendo do estado final (= após laminar o troquel duas vezes). 84% do tempo, nós obtemos uma saída após dois rolos e o algoritmo termina. Como você pode ver, um loop está presente e faz com que o algoritmo não tenha limites. Isto significa que para cada número inteiro, não importa quão grande, há uma probabilidade pequena, mas não nula, de que o número total de rolos ultrapasse essa quantidade, a fim de calcular um valor de saída. Aplicações em tempo real com requisitos de tempo rigorosos estão, portanto, fora de questão, a menos que você esteja disposto a fazer concessões na precisão estatística do algoritmo.

Uma variante desta solução inicialmente rola até três dados antes de reiniciar: isto cria 5^3=125 estados finais, e podemos atribuir no máximo 119 deles a 7 grupos de igual tamanho 17. Agora, há uma probabilidade de 95,2% de terminar após um máximo de três lançamentos. Note que temos que rolar menos vezes em média do que antes (280/119 ≈ 2,35 versus 50/21 ≈ 2,38), porque na maioria das vezes já podemos pegar um atalho após os dois primeiros rolos, e mapear diretamente esses estados entre eles para uma saída. Essa quantidade média de rolos continua caindo conforme continuamos a tendência.

Se você está familiarizado com a teoria da informação, então considere o fato de que um rolo de dado de 5 lados (= rand5) gera log2(5) ≈ 2,32 bits de informação, e um rolo de dado de 7 lados (= rand7) gera log2(7) ≈ 2,81 bits de informação. Acontece que, no caso limite, precisamos apenas de log(7)/log(5) ≈ 1.21 chamadas de rand5 para cada valor de rand7 que desejamos obter. A implementação exata que funciona arbitrariamente perto deste limite é bastante complicada e está fora do escopo deste artigo. Precisaríamos armazenar informações de estado entre várias chamadas de rand7, e o algoritmo que tenho em mente não só ainda está sem limites no tempo, mas também na memória. Convido-vos com prazer a informar-me de um método que resolva este último problema!

A bounded solution

Não existe tal coisa como um algoritmo bounded que calcule um valor aleatório perfeitamente uniforme entre 1 e 7, dado um gerador aleatório entre 1 e 5 apenas. Considere a família de soluções não-limitadas acima. Como tenho sugerido, em cada ponto haverá sempre uma quantidade de estados de ‘sobra’ (variando entre 1 e 6) que fazem com que o algoritmo reinicie. Isto porque 5 e 7 são números primos, e nenhum poder de 5 pode ser um múltiplo de 7. Por mais tentador que seja usar o pequeno teorema de Fermat, tais tentativas resultarão em erros fora de um, uma vez que a teoria básica dos números torna impossível uma solução limitada nesta família.

Você pode corretamente apontar que o número de estados finais nem sempre é um poder de 5, por exemplo, no caso de ‘até três rolos’ onde podemos pegar atalhos depois de dois rolos já. Talvez possamos organizar o gráfico de estados para criar um algoritmo limitado com caminhos de comprimento variável e estados finais 7n? Contudo, considere o seguinte:

1. Estes estados finais não serão igualmente prováveis porque nem todos os caminhos têm o mesmo comprimento (= quantidade de chamadas rand5).
2. Podemos muito facilmente expandir a árvore para tornar cada caminho igualmente longo, chamando inutilmente rand5 uma quantidade apropriada de vezes sempre que estivermos num estado final prematuro. Agora a quantidade de estados finais torna-se novamente um poder de 5, e todos os estados finais são igualmente prováveis.

Obviamente, isto não é uma prova formal, mas espero ter-lhe dado alguma intuição sobre o problema. Como vemos, às vezes um problema pode parecer muito realista, apenas para tropeçar em fatos matemáticos como estes. Após esta análise, você pode descobrir se é possível simular um dado de 8 lados a partir de um dado de 4 lados?