Vlw cara!! Muito boa a solucao!! Em 22 de dezembro de 2014 04:06, charles <[email protected]> escreveu:
> Cara, o ítem a) eu fiz assim: > Seja E(a, b) o valor esperado do número de movimentos necessários para > alcançar a ou b. Daí a recursão para E(a, b) é: > > E(a, b) = 1/2 * (E(a+1, b-1) + E(a-1, b+1)) + 1. > > Daí vc percebe que nessa equação a soma x+y dos termos E(x, y) é constante > e chama f(k) = E(k, a+b-k), então : > f(k) = 1/2*f(k+1) + 1/2*f(k-1) + 1 -> > f(k+1) - 2*f(k) + f(k-1) = -1 > > Daí como padrão pra esse tipo de recorrência que sobra uma constante vc > repete a equação pra k+2 e elimina a constante: > > f(k+1) - 2*f(k) + f(k-1) = -1 > f(k+2) - 2*f(k+1) + f(k) = -1 , subtraindo uma da outra fica: > > f(k+2) - 3*f(k+1) + 3*f(k) - f(k-1) = 0, cuja equação característica é > (x-1)^3 com solução f(n) = a_0 + a_1*n + a_2*n^2. > > Substituindo f(0) = 0 e f(a+b) = 0 (pois E(x, y) = 0 quando x ou y são > zero), temos que f(n) = a_1*n*(1 - n/(a+b)) (***). Talvez tenha um modo > mais fácil de fazer o resto, mas eu tentei achar outro f, no caso f(1). > > Primeiro vamos calcular um p(x) que é a probabilidade de que dado que eu > estou no inteiro x (x>=0 e x<=S) eu chegue em 0 antes de chegar em S > inteiro (dado que se anda do mesmo modo que no enunciado, i.e., com 1/2 de > probabilidade de ir para cada lado). A recursão para p(x) é p(x) = > 1/2*p(x-1) + 1/2*p(x+1) e a equação característica é x^2 -2*x +1 = (x-1)^2, > logo a solução é p(x) = b_0 + b_1*x. Substituindo p(0) = 1 e p(S) = 0, > chegamos a p(x) = (S-x)/S, i.e., a probabilidade é diretamente proporcional > à distância que falta pra chegar em S. > > Agora vamos calcular f(1). f(1) = E(1, a+b-1). Vamos usar recursão em a+b. > Assim defina g(x) = E(1, x). Seja E1 o valor esperado do número de > movimentos necessários para alcançar -1 dado que não se chegou até x e E2 o > valor esperado do número de movimentos para se alcançar x dado que não se > tocou no -1, tudo isso partindo do zero. Assim, g(x) = prob*E1 + > (1-prob)*E2 (*) (o valor esperado total E(1, x) pode ser dividido na > parcela que atinge -1 e na que atinge x) em que prob é a probabilidade de > se atingir o -1 antes do x (note que prob vale p(1) para S = x+1, i.e., > prob = x/(x+1)). Além disso, g(x+1) = prob*E1 + (1-prob)*(E2 + g(x+1) ) > (**) (esse é mais difícil que o g(x). Ou o cara atinge -1 antes do x (termo > E1), ou chega a atingir o x (termo E2) e aí pode voltar para o -1 ou ir > para o x+1 ( termo g(x+1) ), que está logo ao lado. Veja que esse último > termo vale g(x+1) por simetria). Usando essas duas últimas equações > chegamos a prob*g(x+1) = g(x), mas prob vale x/x+1 -> g(x+1) = g(x) * > (x+1)/x. Note que g(1) = 1. Assim, por indução, g(x) = x. Logo E(1, x) = x > -> f(1) = E(1, a+b-1) = a+b-1. Substituindo em (***), temos que a_1 = a+b > -> f(n) = n*(a+b-n), em particular, f(A) = E(A, B) = A*B. > > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
