Vous pouvez retrouver cette question au format pdf.

Question du jeudi #58 : Vous devez tirer au sort équitablement entre deux joueurs mais ne disposez pour ce faire que d'une pièce biaisée (dont vous ignorez en plus le biais exact). Comment faire ?

La solution la plus simple est de faire des séries de deux lancers de pile ou face et de s'arrêter quand une de ces séries ne renvoie pas deux fois le même résultat.

En effet, quelle que soit la probabilité $p$ qu'a la pièce de tomber sur pile, les probabilités que deux lancers successifs fassent pile puis face ou face puis pile sont les mêmes, à savoir $p(1-p)$. Géométriquement, il s'agit simplement du fait que les deux rectangles non carrés de la figure suivante ont la même aire.

Cette figure illustre d'ailleurs le fait (relativement intuitif) que plus la pièce est biaisée, plus la probabilité $2 p(1-p)$ de tomber sur deux résultats différents est faible, et donc plus il faudra tirer un grand nombre de séries (en moyenne) pour enfin obtenir deux résultats différents.

Cette question appartient au thème des extracteurs d'aléa. Plus précisément, on vient de définir l'extracteur de Von Neumann.