David Madore's WebLog: Amplificateurs de probabilités

Dans la série David fait joujou avec les probas et les maths élémentaires, je me suis fait les réflexions à 15 microzorkmids suivantes :

Voilà un scénario typique : on considère un jeu sportif entre deux joueurs qui se joue, disons, par manches indépendantes les unes des autres (chacune étant gagnée par un des deux joueurs), et on souhaite définir une manière de combiner les manches en un match, c'est-à-dire définir une règle qui détermine en fonction des manches déjà jouées si on en joue une nouvelle ou si on déclare un gagnant et dans ce cas lequel. Des exemples de telles règles pourraient être : le gagnant est le premier joueur qui a emporté deux manches (« deux sets gagnants »), ou trois manches (« trois sets gagnants »), ou encore, le gagnant est celui qui a emporté deux manches de plus que son adversaire (le risque étant alors que la partie dure longtemps). On peut aussi imaginer empiler deux niveaux de telles règles, par exemple avoir un jeu qui se joue sous forme de jeux indépendants, une première règle définissant quel joueur emporte une manche en fonction des jeux qu'il a gagnés, et une seconde définissant quel joueur emporte le match en fonction des manches. Voire trois niveaux (points, jeux, manches, match) ou plus.

Faisons l'hypothèse suivante : le joueur 1 remporte une manche quelconque avec probabilité p, le joueur 2 l'emportant donc avec probabilité 1−p, et chaque manche est indépendante des autres. La probabilité que le joueur 1 emporte le match est une fonction f(p) qui dépend de la règle appliquée. La moindre des choses qu'on souhaite, c'est que la règle soit équitable a priori, favorise le meilleur joueur a posteriori, et d'autant plus qu'il est bon, i.e., f(1−p)=1−f(p) et f strictement croissante (ce qui implique notamment f(p)>½ si p>½), mais même f(p)>p pour ½<p<1. C'est ça que je vais appeler un amplificateur de probabilités.

La règle « deux sets gagnants » est sans doute la plus simple (à part celle qui consiste à dire qu'on ne fait qu'une seule manche) : il revient évidemment au même de faire toujours exactement trois manches et de prendre pour gagnant celui qui en a gagné le plus (c'est-à-dire, au moins deux), étant entendu qu'il n'a pas d'incidence mathématique qu'on décide de ne pas jouer la troisième manche lorsqu'elle ne peut pas influencer l'issue du match. La probabilité que le joueur 1 emporte le match est égale à la somme de la probabilité qu'il emporte les trois manches, soit p³, et de la probabilité qu'il emporte deux des manches et perde la troisième, qui peut être n'importe laquelle des trois, soit 3·p²·(1−p) ; ce qui fait, au total, f(p) = 3·p² − 2·p³.

De façon générale, pour k sets gagnants, f est la somme des C_(2k−1)ⁱ·pⁱ·(1−p)^2k−1−i pour i allant de k à 2k−1 ; ceci définit donc un polynôme de degré 2k−1 en p dont la valuation est k (i.e., tous les termes sont de degré au moins k). Par exemple, pour k=3 (« trois sets gagnants »), f(p) = 10·p³ − 15·p⁴ + 6·p⁵.

Pour « k sets d'avance » (i.e., le gagnant est le premier qui remporte k manches de plus que son adversaire), la fonction f est un petit peu plus compliquée à calculer. Le plus naturel me semble être d'écrire un système linéaire sur les probabilités q_i (avec i allant de −k+1 à k−1, soit 2k−1 variables) pour le joueur 1 de gagner à partir d'une situation où il a déjà i manches d'avance : à savoir, q_k−1 = p + (1−p)·q_k−2 car si on a k−1 manches d'avance, on va, avec probabilité p, gagner le match, et avec probabilité k−1, descendre à k−2 manches d'avance, tandis que q_−k+1 = p·q_−k+2 et pour i strictement compris entre les deux, q_i−1 = p·q_i+1 + (1−p)·q_i−1. La fonction f(p) est alors la valeur q₀.

Pour « deux sets d'avance », on trouve : f(p) = p²/(1 − 2·p + 2·p²). Tandis que pour « trois sets d'avance » : f(p) = 2p³/(2 − 6·p + 6·p²).

Voici un petit graphique illustrant l'amplification des probabilités par ces différentes techniques (je ne trace que l'intervalle ½≤p≤1, i.e., le joueur 1 est meilleur, puisque de toute façon c'est symétrique) :

C'est un peu confus à cause des couleurs multiples, mais la légende décrit les courbes en gros de bas en haut : la courbe simple (f(x)=x), puis deux sets gagnants, trois sets gagnants, deux sets d'avance, quatre sets gagnants, deux sets gagnants itérés une fois (c'est-à-dire la même règle utilisée à deux niveaux : on gagne une supermanche par deux manches gagnantes et le match par deux supermanches gagnantes), cinq sets gagnants et enfin trois sets d'avance. Bien sûr, plus la courbe est haute, plus l'amplificateur est puissant, i.e., plus la règle permet efficacement de détecter le meilleur joueur (après, on paye peut-être ça par le fait qu'on joue un grand nombre de manches, mais je ne m'intéresse pas à cet aspect ici).

Si une courbe est toujours plus haute qu'une autre sur l'intervalle ½<p<1, alors l'amplificateur est sans ambiguïté plus puissant. Mais les courbes peuvent se croiser, c'est-à-dire qu'un amplificateur sera meilleur pour tel intervalle de p (de rapport de force entre les deux joueurs, donc) et un autre le sera pour tel autre. Je suis assez surpris, sur mon petit échantillon de méthodes, de voir qu'il y a si peu de courbes qui se croisent : la courbe « deux sets d'avance » coupe la courbe « trois sets gagnants » (en p=½(1+(√3)/3)≃0.789) ; la courbe « trois sets d'avance » coupe chacune des courbes « cinq sets gagnants » (en ≃0.855), « deux sets gagnants itérés » (en ≃0.955) et « quatre sets gagnants » (en ½(1+(√195)/15)≃0.965), et c'est tout — les autres courbes ne se croisent pas (sauf en ½ et en 1, bien sûr). Je suis surpris que la courbe « deux sets gagnants itérés » se trouve comme ça joliment strictement comprise entre quatre et cinq sets gagnants ; en fait, ce qui me surprend encore plus, c'est que la fonction f(p) correspondante soit un barycentre de ces deux-là (avec coefficients 54/70 et 16/70) : je n'ai aucune idée de si on peut démontrer ça plus intelligemment qu'en menant directement le calcul.

Une façon de comparer les courbes serait de considérer l'aire entre elle et la droite f(p)=p, rapportée à l'aire du triangle. I.e., appeler qualité de f l'intégrale de f(p) entre ½ et 1, moins 3/8, le tout multiplié par 8 (ces constantes étant choisies pour avoir un nombre entre 0 et 1). Avec cette mesure, la qualité de l'amplificateur « k sets gagnants » vaut : 1 − C_(2k−1)^k/4^k−1 (on va dire que je laisse ça comme exercice au lecteur). Pour « deux sets gagnants itérés », c'est 29/64. Pour l'amplificateur « k sets d'avance », les premiers termes sont : pour k=1, évidemment, 0 (c'est f(p)=p), pour k=2 c'est 2·log(2)−1 ≃ 0.386, et pour k=3 c'est (16/9)·log(2)−(2/3) ≃ 0.566. On pourrait chercher la logique, mais pour k=4 l'expression est déjà sacrément moins agréable : (√2)·log(3-2√2) + 6·log(2) − 1 ≃ 0.666.

Une autre façon serait de prendre pour qualité simplement la dérivée en ½ (suivant l'idée qu'on essaie d'amplifier la différence entre deux joueurs de niveau presque égal, donc ce qui importe est combien une toute petite différence de niveau autour de p=½ est multipliée) : avec cette mesure, la qualité de l'amplificateur « k sets gagnants » est (2k−1)!/((k−1)!²·4^k−1) (qui a pour équivalent 2√(k/π)) alors que la qualité de l'amplificateur « k sets d'avance » est exactement k (et cette métrique a ceci de sympa, aussi, qu'en itérant on multiplie les qualités : donc la qualité de « deux sets gagnants itérés » est (3/2)²=9/4).

Voilà, pour rendre ces petits calculs un tout petit peu moins inintéressants, il faudrait calculer l'espérance du nombre de manches jouées sous ces différents amplificateurs, au moins pour p tendant vers ½ (ce qui, de nouveau, est la valeur intéressante). S'agissant des amplificateurs « k sets gagnants » (en étant bien d'accord, maintenant, qu'on s'arrête dès que le match est décidé), cette espérance vaut 2k·(1−C_(2k−1)^k/2^2k−1), tandis que pour les amplificateurs « k sets d'avance », elle vaut k².

Pour signaler au moins quelque chose de concret, l'amplificateur « 2 sets d'avance » semble de tout point de vue préférable à « 3 sets gagnants » : l'espérance du nombre de manches jouées est toujours inférieure pour le premier (pas seulement pour p=½ où c'est 4 contre 33/8, mais pour tout p), et les courbes, comme on l'a vu plus haut, sont extrêmement proches, et les deux mesures de qualité donnent une meilleure qualité à « 2 sets d'avance ».

(Ce que je dis sur la longueur de l'amplificateur « k sets d'avance », qui n'est pas si énorme que ça, peut sembler contre-intuitif pour ceux qui pensent aux matchs de tennis vraiment interminables quand il s'agit de gagner la manche par deux jeux d'avance, ou aux tournois d'échecs : la raison est, je pense, que dans ces deux sports, on a un avantage tournant — au tennis le service et aux échecs les pièces blanches — et que cet avantage est trop fort. Moi j'ai supposé des probabilités égales à chaque manche.)