Duas cabeças são melhores que uma?

Você está jogando com seus amigos mentirosos Alice e Bob.

Bob joga uma moeda e mostra para Alice. Alice conta o que viu – mas ela mente 20% das vezes. Então você adivinha se a moeda é cara ou coroa.

Sua melhor estratégia é confiar em tudo o que Alice diz. Você está certo 80% das vezes.

Agora Bob se junta a nós. Ele toma uma decisão independente de Alice e também mente 20% das vezes 1.

Seus amigos são todos mentirosos!

Você estava certo 80% das vezes ao confiar em Alice.

Quanto melhor você pode fazer com a ajuda de Bob?

Aqui está um espaço vazio para você pensar

Vou te dar a resposta abaixo. Então aqui está um espaço vazio para você pensar caso queira fazer as contas sozinho.

Tudo bem, vamos fazer algumas contas

A resposta é 0% – você não faz nada melhor! Você ainda está exatamente 80% para obter a resposta certa.

Para estabelecer isso, vamos escrever uma simulação simples. Jogaremos uma moeda um milhão de vezes, perguntaremos aos nossos amigos o que eles viram e observaremos os resultados.

Para nossa estratégia, examinaremos um padrão de fato (como “Alice diz cara”), descobriremos o que é mais provável (“a moeda dá cara”) e diremos “adivinhamos o lançamento da moeda corretamente sempre que o resultado mais provável ocorrer para esse padrão de fato” 2.

Dado que Bob e Alice decidem de forma independente e não estão jogando de forma adversária, “adivinhe o resultado mais provável” é o ideal aqui. Pode não ser o ideal se o jogo for contraditório, embora eu ache que essa é uma questão mais complicada do que pode parecer à primeira vista.

Aqui está o código para essa simulação. Começaremos com o caso fácil (apenas Alice):

O código de simulação



from random import random
from collections import defaultdict

table = defaultdict(lambda: (0, 0))
LYING_PROB = 0.2
LYING_FRIENDS = ("Alice")
ITERATIONS = 1_000_000

for _ in range(ITERATIONS):
    is_heads = random() > 0.5
    keys = ()
    for lying_friend in LYING_FRIENDS:
        lied = random()  LYING_PROB
        answer = None
        if is_heads: answer = "T" if lied else "H"
        else: answer = "H" if lied else "T"
        keys.append(f"{lying_friend(0)}:{answer}")

    key = ", ".join(keys)

    table_idx = 0 if is_heads else 1
    table(key)(table_idx) += 1

total_times_we_are_right = 0
for key, (times_heads, times_tails) in table.items():
    total = times_heads + times_tails
    heads_chance = 100 * round(times_heads / total, 2)
    tails_chance = 100 * round(times_tails / total, 2)
    pattern_chance = 100 * round(total / ITERATIONS, 2)

    print(f"{key} - chances -  H {heads_chance:4}% | T {tails_chance:4}% | occurs {pattern_chance}% of the time")

    
    
    total_times_we_are_right += max(times_heads, times_tails)

accuracy = round(total_times_we_are_right / ITERATIONS, 2)
print(f"\nOur accuracy: {100*accuracy}%")

Isso nos dá:

% python heads.py
A:T - chances -  H 20.0% | T 80.0% | occurs 50.0% of the time
A:H - chances -  H 80.0% | T 20.0% | occurs 50.0% of the time

Our accuracy: 80.0%

Agora vamos adicionar Bob à simulação. Vemos algo assim:

% python heads.py
A:T, B:T - chances -  H  6.0% | T 94.0% | occurs 34.0% of the time
A:H, B:T - chances -  H 50.0% | T 50.0% | occurs 16.0% of the time
A:H, B:H - chances -  H 94.0% | T  6.0% | occurs 34.0% of the time
A:T, B:H - chances -  H 50.0% | T 50.0% | occurs 16.0% of the time

Our accuracy: 80.0%

Isso é estranho! Mas talvez isso lhe dê uma intuição do que está acontecendo. Ao apresentar um segundo jogador, introduzimos a possibilidade de empate.

Na maior parte do tempo, Alice e Bob concordam. Maioria (~94%) das vezes que isso acontece, eles estão dizendo a verdade. Ocasionalmente, ambos mentem, mas isso é bastante improvável.

Mas em uma parte significativa do tempo (32%) Alice diz cara e Bob diz coroa, ou vice-versa. E nesse caso não sabemos de nada! Alice e Bob são igualmente confiáveis e discordaram – estaríamos melhor se tivéssemos perguntado a Alice 3!

Estou profundamente curioso para saber se alguém leu o livro “Vá perguntar a Alice” pelo professor de ciências do ensino médio para assustá-lo ou se isso foi específico da minha experiência no ensino médio.

Vamos provar isso

Agora que simulamos esse resultado, vamos examinar cada caso, assumindo que a moeda deu cara.

- both tell the truth
Alice: Heads (80%), Bob: Heads (80%)
happens 80% * 80% = 64% of the time
we always guess correctly in this case

- both lie
Alice: Tails (20%), Bob: Tails (20%)
happens 20% * 20% = 4% of the time
we never guess correctly in this case

- alice tells the truth, bob lies
Alice: Heads (80%), Bob: Tails (20%)
happens 80% * 20% = 16% of the time
we guess at random in this case; we're right 50% of the time

- alice lies, bob tells the truth
Alice: Tails (20%), Bob: Heads (80%)
happens 20% * 80% = 16% of the time
we guess at random in this case; we're right 50% of the time

Our total chance to guess correctly is:
64% + 16% / 2 + 16% / 2 = 64% + 8% + 8% = 80%

Há algo lindo aqui. Nossa chance total de adivinhar permanece em 80% porque nossa chance adicional de adivinhar corretamente quando Alice e Bob concordam é perfeitamente compensada pela chance de Alice e Bob discordarem!

Conheça Charlie (e David)

Se o nosso amigo Charlie – que também mente 20% das vezes – se juntar à diversão, as nossas probabilidades aumentam substancialmente. Se Bob e Alice discordarem, Charlie pode servir de desempate.

% python heads.py
A:H, B:H, C:H - chances -  H 98.0% | T  2.0% | occurs 26.0% of the time
A:T, B:T, C:T - chances -  H  2.0% | T 98.0% | occurs 26.0% of the time
A:T, B:H, C:H - chances -  H 80.0% | T 20.0% | occurs 8.0% of the time
A:H, B:T, C:T - chances -  H 20.0% | T 80.0% | occurs 8.0% of the time
A:H, B:H, C:T - chances -  H 80.0% | T 20.0% | occurs 8.0% of the time
A:H, B:T, C:H - chances -  H 80.0% | T 20.0% | occurs 8.0% of the time
A:T, B:T, C:H - chances -  H 20.0% | T 80.0% | occurs 8.0% of the time
A:T, B:H, C:T - chances -  H 20.0% | T 80.0% | occurs 8.0% of the time

Our accuracy: 90.0%

Mas se David aderir, o padrão se repete. David introduz a possibilidade de uma divisão de 2-2 e as nossas probabilidades não melhoram em nada!

% python heads.py
A:T, B:T, C:T, D:T - chances -  H  0.0% | T 100.0% | occurs 21.0% of the time
A:T, B:H, C:H, D:H - chances -  H 94.0% | T  6.0% | occurs 5.0% of the time
A:T, B:H, C:T, D:T - chances -  H  6.0% | T 94.0% | occurs 5.0% of the time
A:H, B:H, C:H, D:H - chances -  H 100.0% | T  0.0% | occurs 21.0% of the time
A:H, B:T, C:H, D:T - chances -  H 50.0% | T 50.0% | occurs 3.0% of the time
A:T, B:T, C:H, D:H - chances -  H 50.0% | T 50.0% | occurs 3.0% of the time
A:H, B:T, C:H, D:H - chances -  H 94.0% | T  6.0% | occurs 5.0% of the time
A:T, B:T, C:T, D:H - chances -  H  6.0% | T 94.0% | occurs 5.0% of the time
A:H, B:T, C:T, D:T - chances -  H  6.0% | T 94.0% | occurs 5.0% of the time
A:H, B:H, C:H, D:T - chances -  H 94.0% | T  6.0% | occurs 5.0% of the time
A:H, B:H, C:T, D:T - chances -  H 50.0% | T 50.0% | occurs 3.0% of the time
A:T, B:T, C:H, D:T - chances -  H  6.0% | T 94.0% | occurs 5.0% of the time
A:H, B:H, C:T, D:H - chances -  H 94.0% | T  6.0% | occurs 5.0% of the time
A:T, B:H, C:T, D:H - chances -  H 50.0% | T 50.0% | occurs 3.0% of the time
A:H, B:T, C:T, D:H - chances -  H 50.0% | T 50.0% | occurs 3.0% of the time
A:T, B:H, C:H, D:T - chances -  H 50.0% | T 50.0% | occurs 3.0% of the time

Our accuracy: 90.0%

E isso continua, indefinidamente, para sempre (enquanto tivermos amigos suficientes). Se o nosso número N de amigos é estranho, nossas chances de acertar não melhoram quando mudamos para N+1 amigos.

Existe um nome para isso?

Pelo que sei, não há nome para esse pequeno fenômeno estranho. Mas isso faz aparecem, implicitamente, na literatura eleitoral.

O teorema do júri de Condorcet é um teorema famoso na ciência política. Afirma:

Se você tiver um grupo de eleitores de tamanho N
…e todos votam, de forma independente, numa questão com resposta correta
…e cada eleitor vota da maneira “certa” com probabilidade P
…e tomamos qualquer decisão que a maioria dos eleitores vote
…então se P > 50%a chance de tomarmos a decisão certa se aproxima de 100% à medida que adicionamos mais eleitores

Parece um pouco com o nosso problema de lançamento de moeda. Aqui está uma suposição simplificadora que a Wikipedia faz ao provar o teorema:

Uma captura de tela do artigo da Wikipedia sobre o Teorema do Júri de Condorcet. Texto completo: Prova 1: Calculando a probabilidade de dois eleitores adicionais alterarem o resultado Para evitar a necessidade de uma regra de desempate, assumimos que n é ímpar. Essencialmente, o mesmo argumento funciona mesmo para n se os empates forem desfeitos pela adição de um único eleitor.

Hah! A prova reconhece explicitamente (e evita) o caso do eleitor par precisamente porque esse eleitor não acrescenta qualquer informação.

Por que escrevi isso?

Me deparei com esse resultado enquanto escrevia uma simulação para um problema mais complexo. Eu era então surpreso com os resultados da simulação, presumi que havia um bug em meu código. E quando fiz as contas manualmente, fiquei absolutamente encantado.

Suspeito que parte da surpresa para mim foi porque normalmente encontro problemas como esses no contexto de apostas, não de votação. Se estivermos apostas no lançamento da moeda, certamente ficaremos entusiasmados em apostar mais se Alice e Bob concordarem do que se estivermos apenas ouvindo Alice.

Mas votar é uma fera diferente; nosso resultado é binário. Não há como colher o EV adicional do aumento de confiança que Bob às vezes nos dá.

A propósito – encontrei esse problema enquanto trabalhava com um amigo no The Recurse Center (um retiro de escritores para programadores). É um ótimo lugar para ser nerd atacado por problemas bobos de matemática; Se você gostou deste blog, considere se inscrever!

De qualquer forma. Espero que isso te encante como me encantou.

Source link