On Fri, Jan 23, 2004 at 12:44:16PM +0000, Elon Correa wrote: > Caros colegas, > > Uma sequencia (bloco) de 5 digitos binarios, por > exemplo, (1 0 1 0 1), e gerada aleatoriamente com > iqual probabilidade (50%) de se gerar 1 ou 0. ... (cortando fora um longo enunciado) > sequencia maior com 5*N digitos. Ou seja qual o numero > esperado de movimentos (trocas) para se obter o valor > N para a sequencia maior?
Se eu bem entendi o problema é o seguinte: começamos com uma seqüência de 5 bits, dos quais k = k0 são iguais a 1. Sorteamos um dos 5 bits e invertemos, assim alterando o valor de k para k1. Repetimos o processo. Seja n o menor inteiro para o qual kn = 1 ou 5: encontre f(k0), o valor esperado de n em função de k0. Trivialmente f(1) = f(5) = 0. Também é fácil ver que f(0) = 1 pois qualquer que seja o bit sorteado no próximo passo teremos uma seqüência com 1 bit igual a 1. Falta calcular x2 = f(2), x3 = f(3) e x4 = f(4). A cada passo sorteamos um bit e temos probabilidade k/5 de escolhermos um 1 e portanto diminuirmos em 1 o valor de k e probabilidade 1-(k/5) de escolhermos um 0 e portanto aumentarmos em 1 o valor de k. Assim x2 = (2/5) + (3/5)*(1 + x3) x3 = (3/5)*(1 + x2) + (2/5)*(1 + x4) x4 = (4/5)*(1 + x3) + (1/5) A primeira equação tem a seguinte justificativa: a partir de uma seq com 2 bits iguais a 1, temos 2/5 de probabilidade de irmos parar em uma seq com 1 bit e neste caso o processo acaba em tempo 1 e temos 3/5 de probabilidade de irmos parar em uma seq com 3 bits iguais a 1, neste caso o processo acaba, em média, em tempo (1 + x3). Assim x2 = (2/5) + (3/5)*(1 + x3), como queríamos. As outras duas equações são análogas. Resolvendo o sistema temos f(2) = 19/4, f(3) = 25/4, f(4) = 6. Mas talvez eu não tenha interpretado corretamente. Talvez a pergunta seja: começando com uma seqüência tomada ao acaso, qual o valor esperado de n? Neste caso a resposta seria (1/32)*f(0) + (5/32)*f(1) + (10/32)*f(2) + + (10/32)*f(3) + (5/32)*f(4) + (1/32)*f(5) = 141/32 ~= 4.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 =========================================================================