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

Caro Nicolau,

Obrigado pela sua resposta. A sua segunda interpretacao do problema eh a correta. Por favor, veja a mesma e tambem o email anterior abaixo.

No entanto, o problema completo nao eh composto apenas por um bloco com 5 digitos e sim por varios.

Utilizando a sua notacao, seja f(k0) o problema com um bloco; qual seria o menor numero inteiro N (numero esperado de trocas) para se ter f1(k0)+f2(k0)+...+fn(k0)=n? Ou seja, f1(k0)=1, f2(k0)=1, ..., fn(k0)=1?

Observe que:

1) Neste caso a sequencia tomada ao acaso tera 5*B digitos;

Por exemplo, para tres blocos (B=3) a sequencia inicial teria 15 digitos e poderia ser: (1 0 0 1 1 0 0 1 1 0 1 0 1 0 1). Vou utilizar colchetes para facilitar a visualizacao dos blocos ([1 0 0 1 1] [0 0 1 1 0] [1 0 1 0 1]).

2) A cada passo, cada um dos 5*B digitos da sequencia tem sempre a mesma probabilidade 1/(5*B) de ser sorteado. Isto eh, a posicao a ser invertida eh tomada ao acaso.

3) A cada inversao o valor da sequencia eh avaliado. Se o valor da sequencia apos a inversao for igual ou maior que o valor anterior, a inversao e aceita. Caso contrario a sequencia permanece inalterada.

Exemplo, suponha que uma sequencia com tres blocos B=3 esteja no seguinte estado: ([1 0 1 0 0] [1 1 1 1 1] [0 0 0 0 1]).

Pode observar-se que o primeiro bloco vale 0 mas o segundo e o terceiro bloco valem 1 cada. Portanto o valor da sequencia toda eh 0+1+1=2.

Suponha que o sexto digito da sequencia acima seja escohlido para troca; entao teriamos: ([1 0 1 0 0] [0 1 1 1 1] [0 0 0 0 1]). O valor da sequencia passaria a ser 0+0+1=1. Como este valor eh menor que o valor da configuracao anterior a troca nao e aceita. Portanto, a configuracao anterior ([1 0 1 0 0] [1 1 1 1 1] [0 0 0 0 1]) eh mantida. No entanto a troca feita no sexto digito conta para o numero esperado de trocas - embora a troca nao seja aceita.

4) O processo acaba somente quando todos os blocos valem 1. Ou seja, quando a sequencia toda vale B.

Por exemplo, na sequenci acima poderiamos ter:

([0 0 1 0 0] [1 1 1 1 1] [0 0 0 0 1]), ou o valor da sequencia = 3.

Obrigado,

Elon

-------- Nicolau escreveu: ------------

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

"Nicolau C. Saldanha" <nicolau@mat.puc-rio.br> wrote:

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