sexta-feira, 14 de setembro de 2012

Probabilidade - Problemas clássicos em probabilidade



Um dos problemas clássicos em probabilidade foi proposto por Pacioli em sua famosa Summa. Este problema ficou conhecido como o problema da divisão dos pontos:

Dois jogadores disputavam um prêmio de 64 moedas que seria dado a quem primeiro fizesse 3 pontos no jogo. Quando o primeiro jogador tinha 2 pontos e o segundo tinha 1 pontos, foi preciso interromper o jogo. Como dividir o prêmio ?

A solução deste problema exigia o desenvolvimento de ferramenta matemática capaz de analisar todas as possibilidades futuras do jogo para calcular corretamente a probabilidade de vitória de cada jogador. Essa ferramenta ficou conhecida como esperança matemática.

A solução dada por Pascal é o produto do ganho eventual pela probabilidade desse ganho. Se o primeiro jogador ganhar a próxima partida, então ele venceria o jogo. Logo, podemos dizer que ele tem direito a metade das moedas (neste caso, 32 moedas) se isso acontecer. Se o primeiro jogador não ganhar a próxima partida, então cada jogador ficará com 2 pontos. O que pode acontecer agora? Se o primeiro jogador vence então ele tem o direito a metade da metade das moedas (neste caso, 16 moedas);caso contrário, o segundo jogador recebe 16 moedas. A divisão baseada na probabilidade de vitória de cada jogador seria:
·        O jogador 1 recebe 48 moedas.
·        O jogador 2 recebe 16 moedas.

Podemos perceber que este problema tem a seguinte estrutura recursiva:
P[i,j] = probabilidade do jogador 1 vencer sabendo que o jogador 1 tem i pontos e o jogador 2 tem j pontos e o primeiro jogador que chegar em n pontos vence a partida.
P[n,j] = 1.0 , j=0..2
P[i,n] =0.0 ,  i=0..2
P[i,j] = 0.5*P[i+1,j] +0.5*P[i,j+1] , i!=n e j!=n



double prob(int j1, int j2){
 if( j1 == n ) return 1.0;
 if( j2 == n ) return 0.0;
 return 0.5*prob(j1+1,j2) + 0.5*prob(j1,j2+1);
}

numero de vitorias do jogador 1:2
numero de vitorias do jogador 2:1
numero de jogos:3
0.750000

numero de vitorias do jogador 1:5
numero de vitorias do jogador 2:3
numero de jogos:7
0.812500

Podemos utilizar a memorização para evitar cálculos desnecessários.
double prob2(int i, int j){
 if( i == n ) return 1.0;
 if( j == n ) return 0.0;
 if( P[i][j] > 0 ) return P[i][j];
 P[i][j] = 0.5*prob2(i+1,j) + 0.5*prob2(i,j+1);
 return P[i][j];
}

Colocando um contador em prob1 e prob2 podemos comparar o numero de chamadas :
numero de vitorias do jogador 1:2
numero de vitorias do jogador 2:3
numero de jogos:11
prob1: 0.401810
prob2: 0.401810
chamadas de prob1 48619
chamadas de prob2 145


2 comentários:

Anônimo disse...

Buuu

Anônimo disse...

Tem alguém ai?