Início > Matemática, Programação > Prova Computacional do Problema de Monty Hall

Prova Computacional do Problema de Monty Hall

O Problema de Monty Hall, que outrora apresentei, é um jogo probabilístico em que um apresentar pede que uma dentre três portas seja escolhida. Uma porta contém um prêmio e as outras têm alguma bizarrice. A imagem abaixo resume as possibilidades de escolha depois que uma porta é aberta pelo apresentador:

Figura 1 – Síntese das escolhas

Para sermos mais didáticos, podemos utilizar a árvore de decisão abaixo, que mostra que temos 2/3 de chances de vencer trocando de porta:

Figura 2 – Árvore de decisão

O blog O Desafio: Aprender apresentou o problema de Monty Hall e citou minha explicação da solução. Revisitar o problema me fez pensar em ir um pouco além e desenvolver um pequeno algoritmo em Java para provar a solução já conhecida do problema.

Escrevi rapidamente um código que utilizava listas de strings e mapas de portas para totais de escolhas. Funcionou, mas depois gastei um tempo reescrevendo com orientação a objetos visando criar abstrações mais claras para que pudesse ser didático. Primeiro, criei uma classe que representa uma porta e o total de vezes que ela foi escolhida:


public class Porta {
    private String nome;
    private long totalEscolhas;
 
    public Porta(String nome) {
        this.nome = nome;
    }
 
    public void escolher() {
        totalEscolhas++;
    }
 
    public long getTotalEscolhas() {
        return totalEscolhas;
    }
 
    public String getNome() {
        return nome;
    }
};

Sabemos que o problema começa quando uma porta é escolhida e outra é aberta pelo apresentador. Sabemos também que a porta aberta e aquela que permanece fechada e que você não escolheu formam um grupo.

Figura 3 – Grupos de portas

Para o problema, isso significa que, se a porta aberta for escolhida pelo algoritmo de escolhas aleatórias, a escolha será transferida para a porta do mesmo grupo que permaneceu fechada. Pensando assim, criei uma abstração para a porta aberta que estende a porta comum e recebe uma referência para a porta fechada. Pensei no padrão Decorator:

public class PortaAberta extends Porta {
   private Porta portaDelegada;

   public PortaAberta(String nome, Porta portaDelegada) {
      super(nome);
      this.portaDelegada = portaDelegada;
   }

   public void escolher() {
      portaDelegada.escolher();
   }

};

O algoritmo que escrevi faz três coisas:

  1. Cria as portas fechadas e a porta aberta e as adiciona em uma lista;
  2. Escolhe aleatoriamente uma das portas e incrementa o total de escolhas em cada instância de porta;
  3. Exibe a porcentagem de vezes que cada porta foi escolhida.
public class MontyHall {
   private List<Porta> portas;

   public void executar(long totalEscolhas) {
      configurarPortas();
      escolher(totalEscolhas);
      exibir(totalEscolhas);
   }

   private void configurarPortas() {
      /*
      * Porta 1 do Grupo A (A1)
      */
      Porta portaA1 = new Porta("A1");
      /*
      * Porta 1 do Grupo B (B1)
      */
      Porta portaB1 = new Porta("B1");
      /*
      * Porta 2 do Grupo B (B2)
      * 
      * Essa e a porta que foi aberta pelo apresentador.
      * Se ela for escolhida pelo sistema, a escolha sera 
      * delegada para a outra porta do mesmo grupo, que e a porta B1
      */
      Porta portaB2 = new PortaAberta("B2", portaB1);
      portas = Arrays.asList(portaA1, portaB1, portaB2);
   }

   private void escolher(long totalEscolhas) {
      Random escolhaAleatoria = new Random();
      for (int escolha = 0; escolha < totalEscolhas; escolha++) {
         int indicePortaEscolhida = escolhaAleatoria.nextInt(portas.size());
         Porta porta = portas.get(indicePortaEscolhida);
         porta.escolher();
      }
   }
   private void exibir(long totalEscolhas) {
      System.out.println("\n" + totalEscolhas + " tentativas\n");
      NumberFormat totalEscolhasFormat = NumberFormat.getPercentInstance();
      totalEscolhasFormat.setMinimumFractionDigits(4);
      for (Porta porta : portas) {
        String totalPorta = totalEscolhasFormat.format(
           (double) porta.getTotalEscolhas() / totalEscolhas);
         System.out.println(porta.getNome() + ": " + totalPorta);
      }
   }
}

Agora, vamos testar nosso código para algumas configurações de quantidades de tentativas:

@RunWith(JUnit4.class)
public class TesteMontyHall {
   @Test
   public void teste() {
      MontyHall montyHall = new MontyHall();	
      montyHall.executar(10);
      montyHall.executar(100);
      montyHall.executar(1000);		
      montyHall.executar(1000000);
      montyHall.executar(1000000000);
   }
}

A saída do programa para as configurações anteriores mostra que quanto maior a quantidade de tentativas, mais evidente fica a tendência dos resultados:

10 tentativas
A1: 40,0000%
B1: 60,0000%
B2: 0,0000%

100 tentativas
A1: 38,0000%
B1: 62,0000%
B2: 0,0000%

1000 tentativas
A1: 33,7000%
B1: 66,3000%
B2: 0,0000%

1000000 tentativas
A1: 33,3255%
B1: 66,6745%
B2: 0,0000%

1000000000 tentativas
A1: 33,3360%
B1: 66,6640%
B2: 0,0000%

Esse algoritmo não funcionaria bem para mais de 3 portas. Eu modificaria a abstração da porta aberta: é necessário que ela receba todas as outras portas do grupo das portas não escolhidas e que estão fechadas e, quando a porta aberta for escolhida aleatoriamente, é necessário escolher aleatoriamente uma das portas desses grupo.

Anúncios
  1. Nenhum comentário ainda.
  1. No trackbacks yet.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: