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