Prouvez qu'un nombre généré au hasard est uniformément distribué

Question

On m'a posé cette question lors d'un entretien.

Étant donné un générateur de nombres aléatoires pour générer un nombre entre [0,N], comment prouver que ce nombre est uniformément distribué.

Je ne sais pas comment aborder ce problème, une suggestion ?

Answer 1

A prouver Pour cela, il faut connaître l'algorithme utilisé et montrer en termes de graphique que l'ensemble de tous les états constitue un cycle, qu'il n'y a pas de sous-cycles et que la cardinalité de l'espace d'état modulo N est nulle, de sorte qu'il n'y a pas d'ensemble d'états qui se produisent plus/moins fréquemment que d'autres. C'est ainsi que nous savons que le Mersenne Twister, par exemple, est uniformément distribué, même si la version 64 bits a une longueur de cycle de 2. 19937 -1 et ne pourront jamais être énumérés au cours de la vie de l'univers.

Sinon, vous utilisez des tests statistiques pour vérifier l'hypothèse d'uniformité. Les statistiques ne peuvent pas prouver un résultat, elles échouent à réfuter l'hypothèse. Plus la taille de votre échantillon est grande, plus l'échec à réfuter une hypothèse est convaincant, mais ce n'est jamais une preuve. (Cette perspective cause plus de problèmes de communication avec les non-statisticiens/non-scientifiques que toute autre chose que je connais). Il existe de nombreux tests d'uniformité, notamment les tests du chi carré, Anderson-Darling et Kolmogorov-Smirnov, pour n'en citer que quelques-uns.

Tous les tests d'uniformité laisseront passer des séquences de valeurs telles que 0,1,2,...,N-1,0,1,... l'uniformité n'est donc pas suffisante pour dire que vous avez un bon générateur. Vous devez également tester la corrélation sérielle à l'aide de tests tels que les tests d'espacement, les runs-up/runs-down, les runs au-dessus/en dessous de la moyenne, les tests d'"anniversaire", etc.

Une suite assez complète de tests d'uniformité et de corrélation sérielle a été créée par George Marsaglia au cours de sa carrière, et publiée en 1995 dans ce qu'il appelait en plaisantant le " test d'uniformité ". Tests de résistance " (car il s'agit d'une batterie de tests lourds).

Answer 2

Pour les tests en boîte noire (vous n'avez pas accès au code source), vous ne pouvez pas prouver qu'il est uniformément distribué (UD). Vous pouvez cependant effectuer des tests statistiques pour déterminer la probabilité qu'il soit UD. Exécutez le générateur de nombreuses fois (disons N*X fois) et chaque nombre entre 0 et N devrait être apparu environ X fois.

Cela ne tient absolument pas compte du fait qu'il s'agit de nombres aléatoires ou non, mais uniquement de l'uniformité. Cependant, cela ne prouverait que le générateur est uniformément distribué que si vous effectuez des tests infinis. Au mieux, vous avez une probabilité que le générateur soit uniforme pendant les N*X premières itérations, mais c'est simple et facile à mettre en œuvre.

Answer 3

Il n'y a aucun moyen de le prouver, car le générateur peut d'abord générer une distribution uniforme, puis dévier vers une distribution non uniforme.

Answer 4

Juste un numéro du générateur, ou autant que vous le souhaitez ? Si un seul, on ne peut rien dire sur l'uniformité. Tant que 0 ≤ nombre < N, c'est bon.

En supposant que l'enquêteur ait voulu dire "[l'uniformité d'] un grand nombre de résultats", vous devez examiner à la fois la distribution résultante et les tendances dans les résultats. La première étape consiste à trier et à classer les résultats et à examiner l'histogramme qui en résulte. Il devrait être raisonnablement "plat" (par exemple, pas une courbe gaussienne) pour un grand nombre de valeurs.

Le deuxième test est un peu plus difficile, car vous pouvez obtenir des modèles de 2, 3, voire 4 chiffres ou plus. Un test que j'ai vu, pour les triplets, consiste à tracer les résultats par groupes de trois, en coordonnées sphériques (le premier est l'azimut, le second l'altitude et le troisième le rayon). Je ne me souviens pas des détails, mais je crois que vous devriez voir une sphère uniformément remplie, ou quelque chose comme ça. Il existe probablement un terme formel pour ce test, mais l'essentiel est qu'il existe un certain nombre de tests pour voir ce que fait un RNG, de sorte que le prochain numéro sorti soit difficile à prédire à partir du dernier numéro sorti (sans modèle apparent).

Answer 5

Je commencerais par leur demander dans quel délai ils veulent une réponse, et quelle est la qualité de la réponse qu'ils veulent obtenir une fois que vous avez le générateur.

Oui, l'exécution d'un ensemble complet de tests statistiques est utile si vous voulez être minutieux. Mais cela peut prendre des jours ou des semaines. Dans certaines situations, la question peut être posée lors d'une réunion avec un groupe de personnes qui veulent une réponse immédiate, et la meilleure réponse peut consister à utiliser Google pendant la réunion pour voir si le générateur est "suffisamment bon" selon les autres utilisateurs. Il existe tout un éventail de réponses entre "google rapide" et "tests complets".

Points bonus pour avoir mentionné qu'en REALISTIQUE, vous ne pouvez pas prouver que le générateur est 100% uniforme dans toutes les situations. Les cas sont :

1) Vous ne pouvez pas consulter le code source. Ainsi, même si vous générez N nombres aléatoires qui semblent uniformes, il n'y a aucun moyen de savoir que chaque nombre à partir de N+1 est 10 (par exemple) sans générer d'autres nombres. Quel que soit l'endroit où vous vous arrêtez, vous ne pouvez rien affirmer au sujet des nombres que vous n'avez pas encore générés.

2) Vous pouvez regarder le code source. Il est probablement trop laid pour être compris, à moins qu'il ne s'agisse d'un générateur linéaire congruentiel très simple. Si c'est trop laid, je dirais qu'à part admirer le code, vous ne pourrez probablement pas tirer de conclusions solides.

Bien que cela soit risqué, il peut être intéressant de mentionner que si l'application a un nombre prévisible d'appels au générateur de nombres aléatoires, alors vous pourriez tester ce générateur pour ce nombre d'appels. Cependant, j'ai vu certains intervieweurs qui interpréteraient mal cette information et supposeraient que vous ne savez pas comment créer des algorithmes qui sont robustes et qui évoluent bien.