Re: [obm-l] O sapo, a escada e a moeda (probabilidade)

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Mon, Jul 02, 2007 at 03:53:32PM -0300, Rogerio Ponce wrote:
> Durante o mes de julho, um super-sapo, infinitamente rapido, desceu,
> sequencialmente, todos os degraus de uma escadaria infinita. Somente ao
> final da viagem ele se deu conta que, ao atender o celular no dia 15, ele
> deixou cair sua moeda da sorte em algum degrau.
> 
> Entao, pediu a um primo extremamente minucioso, que faria o mesmo percurso
> durante o mes de agosto, que ele tentasse encontrar a moeda.
> 
> Sabe-se que o primo, ainda mais veloz, desce escadas empregando
> aleatoriamente 2 tipos de pulos: - saltos longos para a frente, (quando
> avanca diretamente do degrau N para o degrau N+2), - e saltos curtos
> para tras (quando retrocede do degrau N para o degrau N-1).
> 
> Como os 2 tipos sao equiprovaveis, o primo realmente desce a escadaria, com
> taxa media de 1 degrau a cada 2 saltos. 
> 
> Sabendo-se tambem que seu primo somente examina os degraus em que pisa, qual
> e' a probabilidade de que a moeda seja encontrada?

Gostei muito deste problema. A probabilidade de que a moeda seja encontrada
é 1 - phi^(-4) = (-5 + 3 sqrt(5))/2 ~= 0.854101966 onde phi = (1+sqrt(5))/2.

Acho que é melhor começar considerando um problema relacionado.
Suponha que no tempo 0 o primo encontra-se no degrau k > 0.
Seja a_k a probabilidade de que o primo *não* volte a pisar no degrau 0.
Vamos calcular a_k.

Podemos considerar que a_0 = 0. Por teoremas de probabilidade
(lei dos grandes números, teorema central do limite ou algo do gênero)
sabemos que lim_(k -> + infinito) a_k = 1.
Considerando o primeiro pulo, temos ainda
a_k = (a_(k-1) + a_(k+2))/2 para k > 0.
Para resolver esta equação de diferenças considere a equação
l^3 - 2 l + 1 = 0, que tem raízes 1, phi^(-1) ~= 0.6 e -phi ~= -1.6.
Assim a_k = C_1 + C_2 phi^(-k) + C_3 (-phi)^k.
Pelas condições acima temos C_3 = 0 donde a_k = 1 - phi^(-k).
Em particular a_1 = 1 - phi^(-1) = phi^(-2) ~= 0.4.

Outro problema preliminar relacionado:
no tempo t = 0 o primo está na posição k < 0.
Seja b_k a probabilidade de que o primeiro degrau >= 0 a ser pisado
seja o degrau 0. Note que ele atingirá degraus >= 0 com probabilidade 1
e que o primeiro a ser pisado pode ser o degrau 0 ou o degrau 1.
Vamos calcular b_k.

Podemos considerar que b_0 = 1, b_1 = 0.
Temos ainda 0 <= b_k <= 1 para todo k < 0.
Novamente considerando o primeiro pulo temos
b_k = (b_(k-1) + b_(k+2))/2 para k < 0.
Novamente temos b_k = C_4 + C_5 phi^(-k) + C_6 (-phi)^k.
Pelas condições acima temos C_5 = 0 donde b_k = phi^(-1) + (-phi)^(k-2).
Em particular lim_(k -> - infinito) b_k = phi^(-1) ~= 0.6.

Vamos agora considerar o problema original.
Suponha sem perda de generalidade que a moeda caiu no degrau 0.
É melhor calcular a probabilidade de que o primo *não* encontre
a moeda, ou seja, de que ele nunca pise no degrau 0.

Vamos observar o primeiro instante em que o primo pisa em degraus >= 0.
Pelo que vimos sobre b_k (lim_(k -> - infinito) b_k = phi^(-1)),
com probabilidade phi^(-1) ele pisa no 0 e acha a moeda;
com probabilidade phi^(-2) ele pisa no 1 e não acha a moeda ainda.
Para que ele de fato nunca encontre a moeda deve ocorrer o segundo
caso e o primo a partir do degrau 1 não deve voltar a pisar no degrau 0.
Pelo que vimos sobre a_k (a_1 = phi^(-2)), isto ocorre com probabilidade
phi^(-2) e portanto a probabilidade de que a moeda não seja encontrada
é phi^(-4).

[]s, N.
=========================================================================
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
=========================================================================