Suponha que você tenha uma moeda torta. Ela cai cara com uma probabilidade $p$ que você não conhece, talvez $0{,}7$, talvez $0{,}55$. Dá para usá-la num sorteio perfeitamente justo, meio a meio?

No mesmo artigo de 1951 em que falou do “estado de pecado” de quem fabrica números ao acaso, von Neumann deu uma resposta curta e surpreendente.

O truque

Jogue a moeda duas vezes:

  • se sair cara, coroa, diga “cara”;
  • se sair coroa, cara, diga “coroa”;
  • se sair cara, cara ou coroa, coroa, esqueça e jogue mais duas vezes.

Por que é justo? Os dois lançamentos são independentes, então

$$P(\text{cara, coroa}) = p\,(1-p), \qquad P(\text{coroa, cara}) = (1-p)\,p.$$

São o mesmo número, qualquer que seja $p$. Os empates são jogados fora, e entre os resultados que sobram, cara e coroa têm exatamente a mesma chance. Não é preciso saber quanto a moeda é viciada, só que os lançamentos não influenciam uns aos outros.

Quanto custa

O preço é jogar fora pares. A chance de um par servir é $2p(1-p)$. Com uma moeda honesta, $p = \frac12$, um par serve com probabilidade $\frac12$: em média são $2$ pares, ou $4$ lançamentos, para cada resultado. Com uma moeda bem torta, o custo sobe muito: se $p = 0{,}9$, um par serve só com probabilidade $2 \times 0{,}9 \times 0{,}1 = 0{,}18$, e são necessários, em média, cerca de $11$ lançamentos por resultado.

Custo do extrator de von Neumann: no eixo horizontal está a probabilidade p de cara; no vertical, o número esperado de lançamentos por resultado, 1/[p(1−p)]. O mínimo é 4 em p = 1/2, e o custo cresce quando p se aproxima de 0 ou de 1.
Custo do extrator de von Neumann: no eixo horizontal está a probabilidade p de cara; no vertical, o número esperado de lançamentos por resultado, 1/[p(1−p)]. O mínimo é 4 em p = 1/2, e o custo cresce quando p se aproxima de 0 ou de 1.Dabed · Wikimedia Commons · CC BY-SA 4.0

O método de von Neumann é o avô dos extratores de aleatoriedade, que transformam fontes de acaso imperfeitas, como o ruído elétrico de um circuito ou os movimentos do mouse, nos bits uniformes que a criptografia exige.

Exercício: uma moeda de 70%

Com $p = 0{,}7$, calcule a probabilidade de cada tipo de par e o número médio de lançamentos por resultado.

$P(\text{cara, cara}) = 0{,}49$, $P(\text{coroa, coroa}) = 0{,}09$, $P(\text{cara, coroa}) = P(\text{coroa, cara}) = 0{,}21$. Um par serve com probabilidade $0{,}42$. O número de pares até o primeiro útil tem média $\frac{1}{0{,}42} \approx 2{,}4$, ou cerca de $4{,}8$ lançamentos por resultado.

Exercício: por que não um lançamento só?

Alguém propõe: “jogue uma vez; se der cara, jogue de novo e use o segundo resultado”. Isso é justo?

Não. O segundo lançamento continua viciado: dá cara com probabilidade $p$, seja qual for o primeiro. Nenhuma regra que olhe um lançamento de cada vez consegue corrigir o vício sem saber $p$. O truque de von Neumann funciona porque compara dois lançamentos e usa a simetria entre as ordens “cara, coroa” e “coroa, cara”.

Fontes: John von Neumann, “Various techniques used in connection with random digits”, National Bureau of Standards Applied Mathematics Series 12 (1951) · Persi Diaconis, Susan Holmes e Richard Montgomery, “Dynamical bias in the coin toss”, SIAM Review (2007).

Todos os tópicos de John von Neumann · ← O método de Monte Carlo: calcular jogando dados · Autômatos que se reproduzem →

Créditos das imagens.