Après plusieurs échecs, est-il raisonnable de continuer ? Les deux paradoxes du lampadaire.


Un homme ayant perdu ses clés dans la nuit, les cherche de réverbère en réverbère. Il arrive au dernier… Il ne sait pas si c’est l’endroit où il les a perdues mais c’est le seul lieu éclairé de la rue qu’il n’a pas encore visité…

Image provenant d’une IA.

En persévérant, l’individu progresse dans sa recherche. A-t-il pour autant plus de chances de trouver ses clés lors de cette ultime tentative qu’il n’en avait à la première ? Nous avons tendance à chercher des solutions là où il est facile de chercher et de persévérer, mais cela est-il vraiment pertinent ?

Ce n’est pas évident.

Plus il y a de tentatives infructueuses, plus les chances de trouver les clés sous un lampadaire sont faibles : il y a en effet plus de chances de les trouver sous un des lampadaires { (k+1),(k+2),...,(n) } que parmi les lampadaires { (k+2),(k+3),..., (n) }. En même temps, il y a plus de chances de ne pas les trouver sous les k premiers lampadaires que sous les (k+1) premiers.

Alors, lequel des deux effets va l’emporter ?

C’est le premier paradoxe du lampadaire. À chaque étape la probabilité \alpha(k) que les clés soient sous un autre lampadaire, sachant qu’elles n’étaient pas sous les premiers, diminue avec le nombre de tentatives k. Cependant la probabilité \beta(k), de les trouver à chaque nouveau lampadaire, sachant qu’elles n’étaient pas sous les précédents, est toujours plus grande qu’au départ…

Comment raisonner ? Globalement, les n lampadaires éclairent une certaine proportion p de la rue. Pour nous, p est donc un nombre connu strictement compris entre 0 et 1 exprimant tout simplement la probabilité que les clés soient éclairées.

Tous les lampadaires ne sont pas équivalents, il y a plus de chances de trouver les clés à certains endroits plutôt qu’à d’autres. On note p_k la part qui revient au réverbère (k). Autrement dit, la probabilité que les clés soient au pied du lampadaire (k) vaut : p \cdot p_k. On suppose aussi que l’individu commence sa recherche par les endroits qui sont les plus probables, on suppose donc :

    \[p_1 \geq p_2 \geq \ldots \geq p_n, \quad p_i \in ]0,1[, \]

    \[\text{et } p_1 + p_2 + \ldots + p_n = 1.\]

On désigne enfin par F la fonction de répartition associée à la distribution des (p_i) de la façon suivante :

    \[F(0)=0,F(i)=p_1 + p_2  \ldots + p_i ,\]

    \[F(n)= 1.\]


Dès lors, la probabilité \alpha(k) que les clés soient sous un des (n-k) lampadaires restants sachant qu’elles n’étaient pas sous les k premiers est donnée par :

    \[\alpha(k) = \frac{p (p_{k+1} + \ldots + p_n)}{(1-p) + p (p_{k+1} + \ldots + p_n)} .\]

    \[\alpha(k) = 1 + \frac{1-p}{p F(k) - 1}.\]

On remarque effectivement que \alpha(k) est une fonction décroissante de k. À chaque étape k, la probabilité \alpha(k) que les clés soient sous un des lampadaires restants, sachant qu’elles n’étaient pas sous les k premiers, diminue bien avec k.

Par ailleurs, savoir qu’il y a eu k échecs avant la (k+1)-ième tentative donne à la probabilité \beta(k) de la présence des clés sous ce (k+1)-ième lampadaire une valeur plus grande que celle qu’elle avait a priori au départ :

    \[\beta(k) = \frac{p \cdot p_{k+1}}{(1-p) + p \cdot (p_{k+1} + \ldots + p_n)} = \frac{p \cdot p_{k+1}}{1 - p F(k)} \geq p p_{k+1} }.\]

Ce calcul montre en particulier que :

    \[\beta(k) = 1 - \frac{u_{k+1}}{u_k}, \quad \text{avec } u_k = 1 - p \cdot F(k),\]


et donc cette probabilité est maximale lorsque le quotient \frac{u_{k+1}}{u_k} est minimal, et réciproquement.

Ceci conduit au second paradoxe du lampadaire : la probabilité de trouver ses clés après une succession d’échecs peut être plus grande sous un lampadaire autre que le premier, même si ce dernier était a priori le plus probable… Par exemple :

L’histoire est intéressante, car elle permet de décrire la ténacité de quelqu’un qui s’accroche échec après échec en poursuivant son effort. Dans cette description, la forme de la distribution de la probabilité (p_k) est importante. Si, par exemple, l’individu n’a aucune idée de l’endroit où il a perdu ses clés, il peut supposer les lampadaires équiprobables : pour tout lampadaire k dans {1,2,…,n} : p_k = \frac{1}{n}.

Dans ce cas, la persévérance de l’individu repose beaucoup sur l’espoir de trouver la clé sous un des lampadaires non encore explorés. Après k échecs, cette probabilité s’écrit avec l’hypothèse d’équiprobabilité des lampadaires :

    \[\alpha_e(k) = p \cdot \frac{n-k}{n-pk}.\]

Question : Parmi toutes les distributions (p_k) possibles, la distribution équiprobable (p_k=1/n) est-elle optimale au sens où pour tout k dans { 1,2,\ldots,n } :

    \[\alpha(k) \geq \alpha_e(k)  \quad =>\alpha(k) =\alpha_e(k)?\]

Réponse.

Laisser un commentaire

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