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

[Rogerio Ponce <rogerioponce-obm@xxxxxxxxxxxx>]

Ola' Nicolau,
tambem gostei do problema!
Segue a solucao que encotrei.
(me desculpem os colegas da lista, mas a explicacao detalhada tornou o texto muito longo)

------ Solucao ------

Queremos a probabilidade de que o sapo ache a moeda, ou seja, a probabilidade de um degrau ser pisado.
Vamos, primeiramente, calcular a probabilidade de que um degrau nao seja pisado jamais.

Ao contar o numero de pulos do sapo, podemos dizer que:
(usando "#" para designar  "o numero de")

#total_de_pulos =
 [1 * #degraus visitados exatamente uma vez] +
 [2 * #degraus visitados exatamente duas vezes] +
 [3 * #degraus visitados exatamente tres vezes] + ...

Como o sapo gasta, na media, 2 pulos para avancar 1 degrau, entao, dividindo os dois lados da equacao pelo total de degraus percorridos, temos (no limite):
2 =
 [1 * probabilidade de um degrau ser visitado exatamente uma vez] +
 [2 * probabilidade
 de um degrau ser visitado exatamente duas vezes] +
 [3 * probabilidade de um degrau ser visitado exatamente tres vezes] +
 ...

Bem, para que um degrau seja visitado mais de uma vez, alguns "loops" serao necessarios.
Vamos numerar os degraus, de forma que o degrau de referencia para um loop seja 0, e os degraus 'a frente sejam positivos.
Sabemos que o sapo executa pulos com extensao +2 (para frente) e -1 (para tras) , ambos com probabilidade 1/2 .
Entao, qual e' a probabilidade do sapo retornar a um dado ponto? (ou seja, qual a probabilidade de um "loop" ?)


Vamos analisar os 3 tipos possiveis de "loops" :

1) Existe um tipo de "loop" em que o sapo utiliza apenas os degraus 'a frente (ou degraus positivos)  do degrau de referencia (ou degrau zero).
Chamemos esse loop de "loop positivo".
Entao, qual a probabilidade de, partindo do degrau 0, o sapo retornar ao mesmo, tendo pisado apenas em degraus positivos?
Vamos
 chama'-la de Pp (Probabilidade de "loop com degraus positivos" ):
Basicamente o sapo pula do degrau "0" para o degrau "2", e depois volta ao degrau "1" , e finalmente volta ao degrau "0".
Neste percurso ele pode executar loops positivos a partir do degrau 2 e a partir do degrau 1.
Assim, partindo do degrau "0" (sem perda de generalidade) , existe uma probabilidade de 1/2 de pular para o degrau "2" .
Entao, o sapo pode novamente executar um numero qualquer de "loops positivos" a partir deste degrau (antes de voltar ao degrau 1).
Entao ha' uma probabilidade de 1/2 de pular para o degrau 1.
E, novamente, o sapo pode executar uma quantidade qualquer de "loops positivos" , e, finalmente, ha' uma probabilidade de 1/2 de atingir o degrau 0.
Repare que todos os movimentos que o sapo pode fazer num "loop positivo" se encaixam no esquema descrito.

Assim,
Pp = 1/2 * (1+Pp+Pp**2+Pp**3+... ) * 1/2 * (1+Pp+Pp**2+Pp**3+...) * 1/2
Pp = 1/8 * 
 1/(1-Pp)**2
Pp * (1-Pp)**2 = 1/8

Por inspecao , 0.5 e' raiz. Assim, apos decompor a expressao, obtemos
(Pp-0.5) * (Pp - (3+sqrt(5))/4 ) * (Pp - (3-sqrt(5))/4 ) = 0

Sabemos que a probabilidade do primeiro pulo (de "0" a "2") e'  0.5 , de forma que a probabilidade para completar o loop tem que ser menor que 0.5 .

Assim, Pp = (3-sqrt(5))/4


2) Outra especie de loop e' o "loop negativo", em que o sapo pisa apenas em degraus negativos.
Vamos chamar de Pn a probabilidade deste loop  (Probabilidade de loop com os degraus negativos):
Basicamente o sapo pula do degrau "0" para o degrau "-1", passando depois ao degrau "-2" , e finalmente volta ao degrau "0".
Neste percurso ele pode executar loops negativos a partir do degrau -1 e a partir do degrau -2.
Assim, comecando do degrau "0" (sem perda de generalidade), ha' uma probabilidade de 1/2 de pular para o degrau "-1" .
Entao o sapo pode executar uma quantidade qualquer de
 "loops negativos" a partir deste degrau (antes de passar para o degrau "-2").
Entao ha' uma probabilidade de 1/2 de pular para o degrau "-2".
E, novamente, o sapo pode executar uma quantidade qualquer de "loops negativos" , e, finalmente , ha' uma probabilidade de 1/2 de atingir o degrau 0.
Repare que todos os movimentos que o sapo pode fazer num "loop negativo" se encaixam no esquema descrito.

Assim,
Pn = 1/2 * (1+Pn+Pn**2+Pn**3+... ) * 1/2 * (1+Pn+Pn**2+Pn**3+...) * 1/2

Observe que a equacao para Pn e' similar 'a equacao para Pp. Assim,  Pn = (3-sqrt(5))/4


3) O ultimo tipo de loop e' o "loop misto", em que o sapo passeia inicialmente por degraus negativos, e ( apos pular "por cima" do degrau zero) depois passeia por degraus positivos, antes de voltar ao degrau zero.
Calculemos a probabilidade "Pm" de um loop misto:
Basicamente o sapo pula do degrau "0" para o degrau "-1", passando depois ao degrau "+1" , e finalmente volta
 ao degrau "0".
Neste percurso ele pode executar loops negativos a partir do degrau -1 e loops positivos a partir do degrau +1.
Comecando do degrau "0" (sem perda de generalidade) , ha' uma probabilidade de 1/2 de pular para o degrau "-1" .
Entao o sapo pode executar uma quantidade qualquer de loops negativos a partir deste degrau (antes de pular para o degrau +1).
Entao ha' uma probabilidade de 1/2 de pular para o degrau "+1"
E, novamente, o sapo pode executar uma quantidade qualquer de "loops positivos" a partir do degrau +1 , e, finalmente , ha' uma probabilidade de 1/2 de pular para o degrau 0.
Repare que todos os movimentos que o sapo pode fazer num "loop misto" se encaixam no esquema descrito.

Pm = 1/2 * (1+Pn+Pn**2+Pn**3+... ) * 1/2 * (1+Pp+Pp**2+Pp**3+...) * 1/2

Assim, Pm = (3-sqrt(5))/4



Entao, a probabilidade "PL" de executar um loop generico e'  PL = Pp+Pn+Pm
 = (9-3*sqrt(5))/4

Chamemos de
 "Probabilidade do degrau virgem", ou simplesmente "Pdv", a probabilidade de que um degrau jamais seja pisado.
Bem, se um degrau e' visitado K vezes, entao apos a primeira visita, havera' (K-1) loops genericos (de forma que haja mais K-1 visitas), e nenhum loop a mais.
Assim, a probabilidade de um degrau ser visitado exatamente K vezes e'
[1-Pdv] * [PL**K-1)] * [1-PL]

Lembrando que
2 =
 [1 * probabilidade de um degrau ser visitado exatamente uma vez] +
 [2 * probabilidade de um degrau ser visitado exatamente duas vezes] +
 [3 * probabilidade de um degrau ser visitado exatamente tres vezes] +
 ...

vemos que podemos reescrever a equacao como:
2 =
 [1 * (1-Pdv) * PL**0 * (1-PL) ] +
 [2 * (1-Pdv) * PL**1 * (1-PL) ] +
 [3 * (1-Pdv) * PL**2 * (1-PL) ] + ...

ou,
2 = (1-Pdv) * (1-PL) * [ 1*PL**0 + 2*PL**1 + 3*PL**2 +... ]
2 = (1-Pdv) * (1-PL) * [ 1/ (1-PL)**2 ]
2 = (1-Pdv) /
 (1-PL)
Pdv = 2*PL - 1 = [7-3*sqrt(5)] / 2 
Pdv = 3.5 - 1.5 * sqrt(5)

Assim, a probabilidade de que o sapo ache a moeda e'
1-Pdv = 1.5 * sqrt(5) - 2.5 = 0.854102

[]'s
Rogerio Ponce


-------------------------------------------

Rogerio Ponce <rogerioponce-obm@yahoo.com.br> escreveu:

Ola' pessoal,
nesse passeio randomico, o sapo pode pisar mais de uma vez em alguns degraus, e jamais pisar em outros. Ainda assim, podemos afirmar que o sapo  pisara' pelo menos 1 vez em todos os grupos de 2 degraus consecutivos, de modo que a probabilidade de que ele pise em um degrau qualquer da escadaria (ou seja, a resposta que estamos procurando) deve ser maior que 0.5 .

[]'s
Rogerio Ponce

PS: dizem que o resultado e' maior que 0.8 ...



Rogerio Ponce <rogerioponce-obm@yahoo.com.br> escreveu:

Ola' pessoal,

 

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?

[]'s
Rogerio Ponce

---

---

Novo Yahoo! Cadê? - Experimente uma nova busca.