Quantificando a não-aleatoriedade de um gerador aleatório especializado?

9

Acabei de ler esta questão interessante sobre um gerador de números aleatórios que nunca gera o mesmo valor três vezes consecutivas. Isso claramente torna o gerador de números aleatórios diferente de um gerador de números aleatórios uniforme padrão, mas não tenho certeza de como descrever quantitativamente como esse gerador difere de um gerador que não possui essa propriedade.

Suponha que você me forneceu dois geradores de números aleatórios, R e S, onde R é um verdadeiro gerador de números aleatórios e S é um verdadeiro gerador de números aleatórios que foi modificado para nunca produzir o mesmo valor três vezes consecutivas. Se você não me disse qual deles era R ou S, a única maneira que eu posso pensar em detectar isso seria executar os geradores até que um deles produzisse o mesmo valor três vezes consecutivas.

Minha pergunta é - existe um algoritmo melhor para separar os dois geradores? A restrição de não produzir o mesmo número três vezes de alguma forma afeta o comportamento observável do gerador de uma maneira diferente de impedir que três do mesmo valor subam em seqüência?

    
por templatetypedef 01.07.2011 в 19:43
fonte

4 respostas

2

Como conseqüência do Teorema de Rice , não há nenhuma maneira para dizer qual é qual.

Prova: Seja L a saída do RNG normal. Seja L ', mas com todas as seqüências de comprimento > = 3 removidas. Algumas TMs reconhecem L ', mas outras não. Portanto, pelo teorema de Rice, determinar se uma TM aceita L 'não é decidível.

Como outros observaram, você pode fazer uma afirmação como "Ele executou N passos sem repetir três vezes", mas você nunca pode dar o salto para "ele nunca repetirá" um dígito três vezes. " Mais apropriadamente, existe pelo menos uma máquina para a qual você não pode determinar se cumpre ou não este critério.

Advertência: se você tivesse um gerador verdadeiramente aleatório (por exemplo, decaimento nuclear), é possível que o teorema de Rice não se aplicasse. Minha intuição é que o teorema ainda vale para essas máquinas, mas nunca o ouvi falar.

EDITAR : uma prova secundária. Suponha que P(X) determine com alta probabilidade se X aceita L' . Podemos construir um (número infinito de) programas como:

F(x): if x(F), then don't accept L'
      else, accept L'

P não pode determinar o comportamento de F(P) . Além disso, digamos P previu corretamente o comportamento de G . Nós podemos construir:

F'(x): if x(F'), then don't accept L'
       else, run G(x)

Portanto, para todo bom caso, deve existir pelo menos um caso ruim.

    
por Xodarap 01.07.2011 / 22:02
fonte
2

Se S for definido rejeitando de R , então uma sequência produzida por S será uma subsequência da sequência produzida por R . Por exemplo, considerando uma variável aleatória simples X com a mesma probabilidade de ser 1 ou 0 , você teria:

R = 0 1 1 0 0 0 1 0 1
S = 0 1 1 0 0 1 0 1

A única maneira real de diferenciar esses dois é procurar por estrias. Se você está gerando números binários, então as estrias são incrivelmente comuns (tanto que quase sempre é possível diferenciar entre uma sequência aleatória de 100 dígitos e uma que um aluno anota tentando ser aleatória). Se os números forem tirados de [0,1] uniformemente, então as estrias serão muito menos comuns.

É um exercício fácil de probabilidade calcular a chance de três números consecutivos serem iguais quando você souber a distribuição, ou melhor, o número esperado de números necessários até que a probabilidade de três números iguais consecutivos seja maior que p sua escolha favorita de p .

    
por PengOne 01.07.2011 / 19:59
fonte
1

Como você definiu que eles diferem apenas em relação a essa propriedade específica, não há algoritmo melhor para diferenciá-los.

Se você fizer triplos de valores de randum, é claro que o gerador S produzirá todos os outros triplos com uma frequência ligeiramente maior que R para compensar os triplos em falta (X,X,X) . Mas, para obter um resultado significativo, você precisaria de muito mais dados do que o custo de encontrar qualquer valor três vezes consecutivas na primeira vez.

    
por Howard 01.07.2011 / 19:50
fonte
0

Provavelmente use ENT ( link )

    
por Nthalk 01.07.2011 / 20:40
fonte