Quantifier le caractère non aléatoire d'un générateur aléatoire spécialisé?

Question

Je viens de lire this interesting question à propos d'un générateur de nombres aléatoires qui ne génère jamais la même valeur trois fois consécutives. Cela rend clairement le générateur de nombres aléatoires différent d'un générateur de nombres aléatoires uniformes standard, mais je ne suis pas sûr de savoir comment décrire quantitativement comment ce générateur diffère d'un générateur qui n'a pas cette propriété. Supposons que vous me donniez deux générateurs de nombres aléatoires, R et S, où R est un vrai générateur de nombres aléatoires et S un vrai générateur de nombres aléatoires qui a été modifié pour ne jamais produire la même valeur trois fois consécutives. Si vous ne me disiez pas lequel était R ou S, la seule façon de le détecter serait de faire fonctionner les générateurs jusqu'à ce que l'un d'eux produise la même valeur trois fois de suite.

Ma question est - y a-t-il un meilleur algorithme pour distinguer les deux générateurs? La restriction de ne pas produire trois fois le même nombre affecte-t-elle d'une manière ou d'une autre le comportement observable du générateur d'une manière autre que d'empêcher trois de la même valeur d'apparaître dans une rangée?

Answer 1

En conséquence de Rice's Theorem, il n'y a aucun moyen de dire qui est qui. Preuve: Soit L la sortie du RNG normal.

Soit L 'soit L, mais avec toutes les séquences de longueur> = 3 enlevées. Certaines TM reconnaissent L ', mais d'autres non. Par conséquent, selon le théorème de Rice, déterminer si une MT accepte L 'n'est pas décidable.

Comme d'autres l'ont noté, vous pouvez faire une affirmation comme "Il a couru N étapes sans répéter trois fois", mais vous ne pouvez jamais faire le saut "jamais répéter un chiffre trois fois ."Plus approprié, il existe au moins une machine pour laquelle vous ne pouvez pas déterminer si elle répond ou non à ce critère

Avertissement: si vous aviez un générateur vraiment aléatoire (par exemple la désintégration nucléaire), il est possible que le théorème de Rice ne serait pas applicable Mon intuition est que le théorème est encore pour ces machines, mais je ne l'ai jamais entendu discuté

EDIT:... une preuve secondaire Supposons P(X) détermine avec une forte probabilité ou non X accepte L'. Nous pouvons construire un (infinité de) programmes F comme:

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

P ne peut pas déterminer le comportement de F(P). En outre, disons P prédit correctement le comportement de G. Nous pouvons construire:

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

Donc pour tout bon cas, il doit exister au moins un mauvais cas.

Answer 2

Puisque vous avez défini qu'ils ne diffèrent que par rapport à cette propriété spécifique, il n'y a pas de meilleur algorithme pour les distinguer.

Si vous faites des triples de valeurs de randum bien sûr, le générateur S produira tous les autres triplets un peu plus souvent que R afin de compenser les triplets manquants (X,X,X). Mais pour obtenir un résultat significatif, vous aurez besoin de beaucoup plus de données qu'il n'en coûtera de trouver une valeur trois fois consécutives la première fois.

Answer 3

Si S est défini par le rejet de R, puis une séquence produite par S sera une séquence de la séquence produite par R. Par exemple, en prenant une variable aléatoire simple X avec une probabilité égale d'être 1 ou 0, vous auriez:

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

La seule véritable façon de différencier ces deux est de chercher des stries. Si vous générez des nombres binaires, alors les stries sont incroyablement fréquentes (à tel point qu'on peut presque toujours faire la différence entre une séquence aléatoire de 100 chiffres et une que l'élève écrit en essayant d'être aléatoire). Si les chiffres sont pris de [0,1] uniformément, alors les stries sont beaucoup moins fréquentes.

Il est facile de calculer la probabilité que trois nombres consécutifs soient égaux une fois que vous connaissez la distribution, ou mieux, le nombre attendu de nombres nécessaires jusqu'à ce que la probabilité de trois nombres égaux consécutifs soit supérieure à p pour votre choix préféré de p.

Answer 4

probablement utiliser ENT (http://fourmilab.ch/random/)