Caro Nicolau,
Obrigado pela sua resposta. A sua segunda interpretacao do problema eh a correta. Por favor, veja a mesmae tambemo 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 acasotera 5*B digitos;
Por exemplo, para tres blocos (B=3)a sequencia inicial teria 15 digitos e poderia ser: (1 00 11 0 0 1 1 0 1 0 1 0 1). Vou utilizar colchetes para facilitar a visualizacao dos blocos ([1 00 11][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 inversaoo valor da sequencia eh avaliado. Se o valor dasequencia apos a inversao for igual ou maior que o valor anterior,a inversao e aceita. Caso contrario a sequencia permanece inalterada.
Exemplo, suponha queuma sequencia com tres blocos B=3 esteja no seguinte estado: ([1 0100][1][0 00 0 1]).
Pode observar-se que o primeiro bloco vale 0 masosegundo e o terceiro bloco valem 1 cada. Portantoo valor da sequencia toda eh 0+1+1=2.
Suponha que o sexto digito da sequencia acima seja escohlido para troca; entao teriamos: ([1 0100][0][0 00 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, aconfiguracao anterior ([1 0100][1][0 00 0 1]) eh mantida. No entanto a troca feitano sexto digitoconta 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 0100][1][0 00 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" [EMAIL PROTECTED] 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 nopró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 escolhermosum 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.Assimx2 = (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 probabilidadede irmos parar em uma seq com 1 bit e neste caso o processo acaba em tempo 1e 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 emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=
Yahoo! Messenger - Communicate instantly..."Ping" your friends
today! Download Messenger Now
