Re: [obm-l] Numero esperado de movimentos?

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

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
=========================================================================