Paradoxe de Cover
On vous présente deux papiers pliés où sont écrits deux nombres choisis aléatoirement $a$ et $b$.
Vous choisissez un des deux papiers et l’ouvrez pour découvrir le nombre $X$ (soit $a$, soit $b$). Puis on vous demande lequel des deux papiers contient le plus grand nombre.
Cela semble du 50-50, et pourtant… Si vous tirez un nombre aléatoire $Z$ selon une distribution continue sur $\mathbb{R}$, vous pouvez augmenter vos chances ! Il suffit de comparer $Z$ à $X$ : si $Z>X$ vous choisissez $Y$ comme plus grand nombre (l’autre papier) et si $Z<X$, vous choisissez $X$.
Dans le code ci-dessous, on tire deux nombres aléatoires $a$ et $b$ selon une distribution normale centrée sur 0 et d’écart-type 100, puis on tire au sort le nombre $X$. Petite différence par rapport à ce qui précède, on se sert d’une fonction logistique pour “envoyer” $X$ entre 0 et 1 puis on le compare à un $Z$ tiré uniformément entre 0 et 1.
On voit qu’on obtient alors un taux de succès autour de 75% !
Par quel miracle ?
Déjà, comme $Z$ est issue d’une loi continues, on n’aura jamais $Z=a$ ou $Z=b$ et pour que la méthode permette de deviner correctement, il faut que :
- $X=\max(a,b)$ (une chance sur deux) et $ Z < X $
- $X=\min(a,b)$ (une chance sur deux) et $ Z>X $
La probabilité de succès est donc :
$$ \begin{aligned} P_\text { succ } &= \frac{1}{2}P(Z<\max (a, b))+\frac{1}{2}[1-P(Z<\min (a, b))]\\ &=\frac{1}{2}+\frac{1}{2}[P(Z<\max (a, b))-P(Z < \min (a, b))]\\ &=\frac{1}{2}+\frac12\color{#970E53}P\left(\min(a,b) < Z<\max(a,b)\right) \end{aligned} $$
Puisque $Z$ suit une loi continue ${\color{#970E53}P\left(\min(a,b) < Z<\max(a,b)\right)}>0$. On se retrouve donc bien avec une probabilité supérieure à $\tfrac12$.
Dans une démonstration similaire (qu’on retrouve dans cet article de John Baez retraçant l’origine du paradoxe), Greg Egan utilise une fonction $f:\mathbb{R}\rightarrow ]0,1[$ strictement croissante (si $x<y$, $f(x)<f(y)$) pour ramener $X$ dans $]0,1[$. C’est en suivant cette méthode qu’on a utilisé dans le code la fonction logistique $f(x)=\frac{\mathrm{e}^x}{\mathrm{e}^x +1}$.
Le nombre aléatoire $Z$ est alors choisi uniformément entre $0$ et $1$ et on compare $Z$ à $f(X)$ plutôt qu’à $X$.
Supposons $a>b$.
La probabilité de deviner correctement devient :
$$P_\text { succ }=\frac{1}{2}+\frac{1}{2}(f(a)-f(b))>\frac{1}{2}$$
En effet, $f(a)>f(b)$ par croissance stricte de $f$.
Les deux démonstrations sont équivalentes. Suffit de poser $f(x)=P(Z<x)$ (bien strictement croissante) pour s’en convaincre. $P_\text { succ }$ devient alors $\frac{1}{2}+\frac{1}{2}(P(Z<\max(a,b))-P(Z<\min(a,b))$.
Dans le code ci-dessus, les nombres $a$ et $b$ sont volontairement très éloignés de 0 ($\sigma=100$). La fonction logistique donne alors soit $\approx 0$ (nombre $\ll 0$), soit $\approx 1$ (nombre $\gg 0$). Donc $f(a)-f(b)$ va donner $1$ lorsque $a$ et $b$ sont de signes différents (50% des cas) et $0$ dans les autres cas. Ça nous donne une espérance de succès de $\tfrac12+\tfrac12\tfrac12=\tfrac34$.
En diminuant $\sigma$, on diminue le pourcentage de succès (on retrouve que l’efficacité de la méthode est d’autant plus grande que $Z$ a de chances d’être entre $a$ et $b$).
Si $a$, $b$ et $Z$ sont tirés uniformément dans $[0,1]$, on obtient une espérance de succès de $\tfrac23$. En effet, on a alors $P_\text { succ }(a,b)=\tfrac12 + \tfrac12|a-b|$. Or comme on l’a vu plus haut, $\mathbb{E}[|a-b|]=\tfrac13$, donc $\mathbb{E}[P_\text{succ}(a,b)]=\tfrac12+\tfrac12\tfrac13=\tfrac23$.
Cela finit par sérieusement perdre de sa magie… Si la loi d’où est tiré $Z$ est adaptée aux valeurs de $a$ et $b$, tout va pour le mieux, mais dès que ce n’est plus le cas, on se retrouve bêtement autour de 50%… Il suffit par exemple d’un $\mu\gg\sigma$ dans la loi normale du code. La fonction logistique va envoyer tout le monde sur $\approx 1$ et on n’aura quasi jamais $Z>f(a)$.
Certes, le hasard permet d’augmenter ses chances, mais tant que la distribution des nombres sur les papiers et celle du nombre aléatoire tiré ne se correspondent pas, l’avantage obtenu sera infinitésimal… Le tirage n’apporte donc finalement aucune information importante. Celle-ci viendrait plutôt du choix adéquat de la distribution de $Z$ puisqu’il impliquerait de connaître celle de $a$ et $b$ !