Re: [obm-l] Probabilidade de parar

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 24.11.03 14:02, Nicolau C. Saldanha at nicolau@mat.puc-rio.br wrote:

> On Mon, Nov 24, 2003 at 12:56:01PM +0000, Rogerio Ponce wrote:
>> Olá pessoal,
>> 
>> Joga-se uma moeda honesta até que a quantidade obtida de "caras" seja maior
>> que a de "coroas" , quando então interrompe-se a sequência de jogadas.
>> Qual a probabilidade dessa sequência não terminar nunca ?
> 
> ZERO
> 
> Este problema é um clássico.
> 
>> Variação:
>> E se a moeda apresenta uma probabilidade de 60% de dar "coroa" ?
> 
> Vou generalizar ainda mais.
> 
> Suponha que a moeda tem probabilidade p >= 1/2 de dar coroa.
> Se em um dado momento as coroas tem uma vantagem de k > 0
> qual a probabilidade de que as caras nunca consigam nem empatar o jogo?
> 
> Seja f(k) a resposta, f: Z -> [0,1].
> Por definição temos f(k) = 0 para k <= 0.
> Para k > 0 jogamos a moeda uma vez: se cair cara, o que tem probabilidade
> (1-p) de acontecer, a probabilidade passa a ser f(k-1); por outro lado,
> se cair coroa, o que tem prob p de acontecer, a prob passa a ser f(k+1).
> Assim:
> 
> f(k) = (1-p) f(k-1) + p f(k+1) para k > 0.
> 
> Uma solução para esta equação é dada por
> 
> f(k) = 0 para k <= 0 e f(k) = 1 - a^k para k >= 0 onde a = (1-p)/p.
> 
> De fato esta é a solução correta: ela é a única que tende para 1
> quando k tende para infinito.
> 
> Mas escrevendo isso estou com uma sensação de déja vu: acho que este
> problema já foi discutido nesta lista.
> 
> []s, N.

Nao sei se foi discutido ou nao, mas me parece que esse problema estah
relacionado aos numeros de Catalan.

Eh facil ver que o jogo soh pode parar apos um numero impar de lancamentos.
Se o jogo para no (2m+1)-esimo lancamento, entao terao sido obtidas m+1
caras e m coroas. Alem disso, ateh o 2m-esimo lancamento (que tem que ter
dado cara), as caras nunca estiveram na frente.
O numero de maneiras disso acontecer eh Binom(2m,m)/(m+1) = m-esimo numero
de Catalan. Logo, a probabilidade do jogo acabar no (2m+1)-esimo lancamento
eh igual a P(2m+1) = Binom(2m,m)/(m+1) * p^m * (1-p)^(m+1).

A probabilidade do jogo nao terminar nunca serah igual a:
1 - (P(1) + P(3) + P(5) + ... )

Eh interessante observar que, para p >= 1/2:
P(1) + P(3) + P(5) + ... = (1-p)/p

Ou seja, que:
(1-p) * SOMA(m>=0) Binom(2m,m)/(m+1) * (p*(1-p))^m  =  (1-p)/p ==>

Quando p varia de 1/2 a 1, p*(1-p) varia de 1/4 a 0.
Fazendo b = p*(1-p) obtemos um resultado que talvez seja interessante por si
soh (o que voce acha, Luis Lopes?):

Para 0 <= b <= 1/4:
SOMA(m>=0) Binom(2m,m)/(m+1) * b^m  =  (1 - raiz(1 - 4b))/2

Para b > 1/4, o termo geral nao tende a zero (teste da razao ou Stirling) e
a serie diverge.

Uma outra consequencia eh que se expandirmos (1 - raiz(1 - 4x))/2 em serie,
obteremos justamente a serie formal cujos coeficientes sao os numeros de
Catalan.

Um abraco,
Claudio.


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================