[obm-l] Numero esperado de movimentos?

[Elon Correa <elonsc2@xxxxxxxxxxx>]

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.
Sequencias que contem um unico digito igual a 1 ou
exatamente cinco digitos iguais a 1 sao dominantes e
tem valor 1. Todos os outros casos valem 0. 

Isto e, os 6 casos de valor 1 sao: (1 0 0 0 0) = 1, (0
1 0 0 0) = 1, (0 0 1 0 0) = 1, (0 0 0 1 0) = 1, (0 0 0
0 1) = 1 e (1 1 1 1 1) = 1.

Todos os outros casos valem ZERO.

Depois de gerada a sequencia, um dos cinco digitos e
escolhido ao acaso e seu valor trocado (se for 1 passa
a ser 0 ou vice-versa). Todos os 5 digitos ou
"posicoes" tem a mesma probabilidade de serem
escolhidos para troca. O processo e repetido ate que
uma sequencia de valor 1 seja encontrada (um dos 6
casos acima seja gerado). Se a primeira sequencia
gerada tiver valor 1 nenhuma troca e feita e o
processo acaba, pois, uma sequencia de valor 1 foi
gerada.

Suponha agora que tenhamos um numero inteiro positivo
de N sequencias iguais a esta compondo uma sequencia
maior com 5*N digitos binarios gerada aleatoriamente.

Cada um dos 5*N digitos sera escolhido com igual
probabilidade e seu valor trocado como no processo
anterior. O valor desta sequencia completa e baseada
no valor de cada um dos blocos de 5 digitos contidos
nela. Os blocos sao considerados da esquerda para a
direita (de 5 em 5 digitos). Desta forma o maior valor
possivel para a sequencia completa com 5*N digitos
sera N quando todos os N blocos contidos nela valerem
1. Quando um bloco dentro da sequencia 5*N vale 1 ou
passa a valer 1 depois de uma troca, mudancas neste
bloco nao sao mais aceitas, mas, posicoes dentro
deste(s) bloco(s) continua(m) podendo ser selecionadas
mas sao "trocas perdidos".

A pergunta e: Qual e o numero esperado de trocas para
se obter todos os blocos iguais a 1 dentro da
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?

ESC

________________________________________________________________________
Yahoo! Messenger - Communicate instantly..."Ping" 
your friends today! Download Messenger Now 
http://uk.messenger.yahoo.com/download/index.html
=========================================================================
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
=========================================================================