Bit aleatório com probabilidade 1/2

Programação
#1

Bom dia, estava estudando algoritmo e estrutura de dados em um livro, e apareceu essa questão:

image
image.png903×172 23.2 KB

  1. Criei uma função que soma esse biased-random 100 vezes. Dessa forma, o retorno dessa função é um número aleatório (mas com a tendencia em p) de 0 a 100.
  2. Criei uma função que chama a função criada no item 1 1000 vezes, calculando a media aritmética desses resultados.
  3. Por fim, com essa média em mãos, eu chamava a primeira função 100 vezes e somava os resultados, se o somatório for maior (ou igual a 1) que a média retornava 1 e se não, retornava 0.

Para testar, criei a função biased-random usando o random do java para gerar 30% em 1 e 70% em 0. A segunda função retorna o valor satisfatório (28~29), enquanto a terceira função varia muito, em 5 testes de 100 chamadas cada, retornaram esses resultados:

Número de 0: 58
Número de 1: 42

Número de 0: 47
Número de 1: 53

Número de 0: 52
Número de 1: 48

Número de 0: 52
Número de 1: 48

Número de 0: 45
Número de 1: 55

A minha pergunta é, existe um algoritmo que funcione 50%-50%? Procurei pela internet sobre e não encontrei nada.

#2

Esse é um problema conhecido (como produzir resultados “justos” em uma moeda viciada) e também se aplica aqui, pois gerar 0 ou 1 e dar cara ou coroa é basicamente o mesmo problema.

A ideia básica é: a chance de sair 1 é p e de sair 0 é 1 - p, então se eu fizer dois lançamentos seguidos, a chance de sair 1 seguido de 0 é p(1 - p), e a chance de sair 0 seguido de 1 é (1 - p)p. Ou seja, são eventos equiprováveis, então basta usar o BIASED-RANDOM duas vezes, e se os resultados forem iguais, você descarta. Faça isso até que eles sejam diferentes e retorne o primeiro.

Ficaria assim (código descaradamente copiado inspirado neste aqui):

int biasedRandom() {
    // retorna 0 ou 1, com probabilidades diferentes
}

int unbiasedRandom() { // retorna 0 ou 1, com probabilidade de 50%
    int x, y;
    do {
        x = biasedRandom();
        y = biasedRandom();
    } while(x == y);
    return x;
}

Vale lembrar que ter um gerador com 50% de chance de gerar 0 ou 1 não garante que se rodá-lo N vezes você sempre terá N / 2 de cada um. Jogue uma moeda 10 vezes, mesmo que a chance de sair cara seja 50%, isso garante que sempre vai sair cara exatamente 5 vezes?

#3

entendi, faz realmente muito sentido