Random.nextInt(int) est [légèrement] biaisé.

Question

En d'autres termes, il ne générera jamais plus de 16 nombres pairs à la suite avec un certain nombre de chiffres spécifiques. upperBound paramètres :

Random random = new Random();

int c = 0;
int max = 17;
int upperBound = 18;

while (c <= max) {
    int nextInt = random.nextInt(upperBound);
    boolean even = nextInt % 2 == 0;
    if (even) {
        c++;
    } else {
        c = 0;
    }
}

Dans cet exemple, le code bouclera indéfiniment, alors que lorsque upperBound est, par exemple, de 16, il se termine rapidement.

Quelle peut être la raison de ce comportement ? Il y a quelques notes dans la javadoc de la méthode, mais je n'ai pas réussi à les comprendre.

---

UPD1 : Le code semble se terminer avec des limites supérieures impaires, mais peut rester bloqué avec des limites paires.

---

UPD2 : J'ai modifié le code pour capturer les statistiques de c comme suggéré dans les commentaires :

Random random = new Random();

int c = 0;
long trials = 1 << 58;
int max = 20;
int[] stat = new int[max + 1];

while (trials > 0) {
    while (c <= max && trials > 0) {
        int nextInt = random.nextInt(18);
        boolean even = nextInt % 2 == 0;
        if (even) {
            c++;
        } else {
            stat[c] = stat[c] + 1;
            c = 0;
        }
        trials--;
    }
}

System.out.println(Arrays.toString(stat));

Maintenant, il essaie d'atteindre 20 pairs dans la rangée - pour obtenir de meilleures statistiques, et le upperBound est toujours 18 .

Les résultats se sont révélés plus que surprenants :

[16776448, 8386560, 4195328, 2104576, 1044736, 
 518144, 264704, 132096, 68864, 29952, 15104, 
 12032, 1792, 3072, 256, 512, 0, 256, 0, 0]

Au début, il diminue comme prévu par le facteur 2, mais notez la dernière ligne ! Ici, ça devient fou et les statistiques capturées semblent être complètement bizarres.

Voici un diagramme à barres en échelle logarithmique :

Comment c obtient la valeur 17 256 fois est encore un autre mystère

Answer 1

http://docs.oracle.com/javase/6/docs/api/java/util/Random.html :

Une instance de cette classe est utilisée pour générer un flux de nombres pseudo-aléatoires. La classe utilise une graine de 48 bits, qui est modifiée en utilisant une formule congruentielle linéaire. (Voir Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1).

Si deux instances de Random sont créées avec la même graine, et que l'option même séquence d'appels de méthode pour chacune d'elles, elles génèreront et retourneront et renverront des séquences de nombres identiques. [...]

Il s'agit d'un pseudo -générateur de nombres aléatoires. Cela signifie que vous ne lancez pas réellement un dé mais que vous utilisez une formule pour calculer la prochaine valeur "aléatoire" sur la base de la valeur aléatoire actuelle. Pour créer l'illusion de la randomisation, un seed est utilisé. La graine est la première valeur utilisée avec la formule pour générer la valeur aléatoire.

Apparemment, l'implémentation aléatoire de Java (la "formule") ne génère pas plus de 16 nombres pairs à la suite.

Ce comportement est la raison pour laquelle le seed est généralement initialisé avec l'heure. En fonction du moment où vous démarrez votre programme, vous obtiendrez des résultats différents.

L'avantage de cette approche est que vous pouvez générer des résultats reproductibles. Si vous avez un jeu qui génère des cartes "aléatoires", vous pouvez vous souvenir de la graine pour régénérer la même carte si vous voulez y rejouer, par exemple.

Pour obtenir de véritables nombres aléatoires, certains systèmes d'exploitation fournissent des dispositifs spéciaux qui génèrent un "caractère aléatoire" à partir d'événements externes tels que les mouvements de la souris ou le trafic réseau. Cependant, je ne sais pas comment les exploiter avec Java.

Extrait de la documentation Java pour secureRandom :

De nombreuses implémentations de SecureRandom se présentent sous la forme d'un pseudo-aléatoire (PRNG), ce qui signifie qu'elles utilisent un algorithme déterministe pour produire une séquence déterministe pour produire une séquence pseudo-aléatoire à partir d'une graine aléatoire réelle. D'autres implémentations peuvent produire de véritables nombres aléatoires, et d'autres encore peuvent utiliser une combinaison des deux techniques.

Notez que secureRandom ne PAS garantie vrai des nombres aléatoires non plus.

Pourquoi changer la semence ne sert à rien

Supposons que les nombres aléatoires soient compris entre 0 et 7. Maintenant, nous utilisons la formule suivante pour générer le prochain numéro "aléatoire" :

 next = (current + 3) % 8

la séquence devient 0 3 6 1 4 7 2 5 .

Si vous prenez maintenant la graine 3 il suffit de changer le point de départ.

Dans cette implémentation simple qui n'utilise que la valeur précédente, chaque valeur ne peut apparaître qu'une seule fois avant que la séquence ne s'enroule et ne recommence. Sinon, il y aurait une partie inaccessible.

Par exemple, imaginez la séquence 0 3 6 1 3 4 7 2 5 . Les chiffres 0,4,7,2 and 5 ne seraient jamais générées plus d'une fois (selon la graine, elles pourraient ne jamais être générées), car une fois que la séquence boucle 3,6,1,3,6,1,.... .

Les générateurs de nombres pseudo-aléatoires simplifiés peuvent être considérés comme une permutation de tous les nombres de la plage et vous utilisez la graine comme point de départ. S'ils sont plus avancés, vous devrez remplacer la permutation par une liste dans laquelle les mêmes nombres peuvent apparaître plusieurs fois.

Les générateurs plus complexes peuvent avoir un état interne, ce qui permet au même numéro d'apparaître plusieurs fois dans la séquence, puisque l'état permet au générateur de savoir où continuer.

Answer 2

L'implémentation de Random utilise une simple formule linéaire congruentielle. De telles formules ont une périodicité naturelle et toutes sortes de motifs non aléatoires dans la séquence qu'elles génèrent.

Ce que vous voyez est un artefact de l'un de ces modèles... rien de délibéré. Ce n'est pas un exemple de partialité. C'est plutôt un exemple de auto-corrélation .

Si vous avez besoin de meilleurs nombres (plus "aléatoires"), vous devez alors utiliser SecureRandom plutôt que Random .

Et la réponse à "pourquoi cela a été mis en œuvre de cette façon est" ... performance. Un appel à Random.nextInt peut être réalisée en quelques dizaines ou centaines de cycles d'horloge. Un appel à SecureRandom est susceptible d'être plus lente d'au moins deux ordres de grandeur, voire plus.

Answer 3

Pour la portabilité, Java spécifie que les implémentations doit utiliser la méthode inférieure LCG pour java.util.Random. Cette méthode est totalement inacceptable pour toute utilisation sérieuse des nombres aléatoires, comme les simulations complexes ou les méthodes Monte Carlo. Utilisez une bibliothèque complémentaire avec un meilleur algorithme PRNG, comme le MWC de Marsaglia ou le KISS. Les générateurs Mersenne Twister et Lagged Fibonacci sont souvent acceptables également.

Je suis sûr qu'il existe des bibliothèques Java pour ces algorithmes. J'ai une bibliothèque en C avec des liaisons Java si cela peut vous convenir : ojrandlib .