Le Détecteur de robots

Êtes-vous sûr et certain que vous n’êtes pas un robot construit dans le but de réaliser dieu sait quel plan maléfique ? Pour le savoir, essayez le détecteur de robots ci-dessous.

Le but est de générer une séquence de 0 et de 1 qui a l’air aléatoire : imaginez par exemple que vous simulez un jeu de pile ou face. Le détecteur doit pouvoir dire si cette séquence a été générée par un ordinateur ou par un humain. Pour que ça marche correctement, il faut que la séquence ait au moins une longueur de 200.

Le détecteur de robots. Entrez une séquence de 0 et de 1 de longueur 200, qui a l’air aléatoire.

Comment ça marche ?

Aucune donnée n’a été utilisée pour créer ce détecteur : il repose entièrement sur des calculs de probabilités.

L’idée principale est que les humains ont du mal a penser de manière parfaitement aléatoire, le « pierre-feuille-ciseaux » du New York Times en donne une excellente illustration. Le détecteur observe certaines caractéristiques de la séquence soumise et les compare aux caractéristiques idéales d’une séquence purement aléatoire. Il calcule ensuite la probabilité que l’écart entre les caractéristiques observées et les caractéristiques idéales soit dû au hasard. Si cette probabilité est inférieure à 1%, il conclut que la séquence a été produite par un humain, sinon qu’elle a été produite par un robot.

Plus précisément, le détecteur de robots s’intéresse à la distribution de la longueur des séquences consécutives de 0 et de 1. Le test qui en résulte n’est pas le plus puissant qu’on puisse imaginer (il s’agit juste d’un prétexte pour faire des maths) et échoue lamentablement dans certaines situations : par exemple, si vous ne rentrez que des 0 ou que des 1, il va conclure que la séquence est aléatoire alors qu’elle ne l’est manifestement pas !

Faisons un peu de maths

Considérons une séquence infinie de 0 et de 1 telle que chaque élément ait une probabilité p d’être égal à 1 et que les éléments soient indépendants les uns des autres. Intéressons-nous à la variable X égale à la longueur d’une séquence consécutive de 0 et de 1. Par exemple dans la séquence suivante, X vaut successivement 2, 6, 1, 3, 2, 1, 2 et 1.

Quelle est la loi de X ? Si une séquence commence par un 1 (resp. 0), alors sa longueur suit une loi géométrique de paramètre p (resp. 1-p) :

Par construction, une suite de 0 est toujours suivie d’une suite de 1 et inversement. Il y a donc autant de séquences de 0 que de séquences de 1. Autrement dit :

On en déduit que la loi de X est :

En particulier, quelque soit p, on a :

Considérons maintenant une suite de 0 et de 1 comprenant N séquences de 0 et de 1. Intéressons nous à la variable qui représente le nombre de séquences de longueur k parmi les N séquences. Il est clair que suit une loi binomiale de paramètres N et .

On a donc :

et :

On peut également montrer que :

Notons :

et :

Si N est assez grand, alors Y suit approximativement une loi normale multivariée d’espérance E(Y) et de variance en vertu du théorème central limite. Par conséquent, la statistique suivante :

suit asymptotiquement une loi du chi-deux à k degrés de libertés à condition que la séquence de 0 et 1 considérée soit parfaitement aléatoire.

C’est sur cette statistique que repose le test utilisé par le détecteur de robots. Lorsque sa valeur est trop grande, on en conclut que la séquence n’est pas aléatoire et qu’elle a donc été produite non par une machine mais par un humain.

Conclusion

Le test en soi n’est pas très intéressant mais la démarche mathématique utilisée pour le construire l’est. De nombreux test statistiques utilisent des principes analogues : on fait apparaître des lois normales, souvent grâce au théorème central limite, puis on calcule l’espérance et la matrice de variance -covariance ; enfin on calcule la statistique ci-dessus qui a la bonne idée de suivre une loi du chi-deux.

La démarche ci-dessus doit en particulier pouvoir être utilisée pour faire des tests d’égalité entre deux distributions, même si d’autres tests seront souvent plus puissants.

Cette entrée a été publiée dans Probabilités. Vous pouvez la mettre en favoris avec ce permalien.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>