Algorithme de cotes — Wikipédia

Cet article présente des problèmes à corriger.

Vous pouvez aider à l'améliorer ou bien discuter des problèmes sur sa page de discussion.

• Il ne cite pas suffisamment ses sources. Vous pouvez indiquer les passages à sourcer avec {{référence nécessaire}} ou {{Référence souhaitée}}, et inclure les références utiles en les liant aux notes de bas de page. (Marqué depuis mars 2024)
• Certaines informations devraient être mieux reliées aux sources mentionnées dans la bibliographie ou les liens externes. Améliorez sa vérifiabilité en les associant par des références. (Marqué depuis mars 2024)
• Son texte doit être wikifié : il ne correspond pas à la mise en forme Wikipédia (style, typographie, liens internes, liens entre les wikis, etc.). (Marqué depuis mars 2024)
• Il doit être recyclé. La réorganisation et la clarification du contenu sont nécessaires. (Marqué depuis mars 2024)
• Il est orphelin : moins de trois articles lui sont liés. Aidez à ajouter des liens en plaçant le code [[Algorithme de cotes]] dans les articles relatifs au sujet. (Marqué depuis mars 2024)
• Le résumé introductif est trop long. En l'état, il ne respecte pas les recommandations. Vous pouvez l'améliorer en le raccourcissant et/ou en déplaçant son contenu. (Marqué depuis mars 2024)

Trouver des sources sur « Algorithme de cotes » :

• Archive Wikiwix
• Bing
• Cairn
• DuckDuckGo
• E. Universalis
• Gallica
• Google
• G. Books
• G. News
• G. Scholar
• Persée
• Qwant
• (zh) Baidu
• (ru) Yandex
• (wd) trouver des œuvres sur Wikidata

En théorie de la décision, l'algorithme de cotes (ou algorithme de Bruss) est une méthode de recherche mathématique des stratégies optimales dans le domaine des problèmes d'arrêt optimal. Les solutions découlent de la stratégie des cotes, et son importance réside dans son caractère optimal.

L'algorithme des probabilités est appliqué à une catégorie de problèmes appelés problèmes du dernier succès. Formellement, ces problèmes visent à maximiser la probabilité d'identifier, dans une séquence d'événements indépendants observés séquentiellement, le dernier événement satisfaisant un critère spécifique (un "événement spécifique"). Cette identification doit se faire au moment de l'observation, sans possibilité de révision des observations précédentes. Généralement, un événement spécifique est défini par le décideur comme un événement présentant un véritable intérêt dans la perspective de "s'arrêter" pour entreprendre une action bien définie. Ces types de problèmes se rencontrent dans diverses situations.

Exemples[modifier | modifier le code]

Cette section a besoin d'être recyclée (novembre 2023).
Motif : Pas encyclopédique. Améliorez-le ou discutez des points à améliorer.

Deux situations distinctes mettent en lumière l'importance de maximiser la probabilité de s'arrêter sur un dernier événement spécifique.

1. Supposons qu'une voiture soit mise en vente au plus offrant (meilleure « offre »). Laissons n acheteurs potentiels répondre et demander à voir la voiture. Chacun insiste pour que le vendeur décide immédiatement d'accepter ou non l'offre. Définissons une offre comme intéressante, et codée 1 si elle est meilleure que toutes les offres précédentes, et codée 0 sinon. Les enchères forment une séquence aléatoire de 0 et de 1. Seuls les 1 intéressent le vendeur, qui peut craindre que chaque 1 successif ne soit le dernier. Il résulte de la définition que le tout dernier 1 est l'offre la plus élevée. Maximiser la probabilité de vendre sur le dernier signifie donc maximiser la probabilité de vendre au mieux.
2. Un médecin, utilisant un traitement particulier, peut attribuer le code 1 à un traitement réussi, 0 sinon. Le médecin traite une séquence de n patients de la même manière, cherchant à minimiser toute souffrance et à traiter chaque patient réactif dans la séquence. S'arrêter sur le dernier 1 dans une séquence aussi aléatoire de 0 et de 1 permettrait d'atteindre cet objectif. Puisque le médecin n'est pas un prophète, l'objectif est de maximiser la probabilité d'arrêter sur le dernier (voir utilisation compassionnelle)

Définitions[modifier | modifier le code]

Considérons une séquence de n événements indépendants. Associons une autre séquence d'événements indépendants ${\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}$avec les valeurs 1 ou 0. Ici, ${\displaystyle \,I_{k}=1}$succès, représente l'événement où la k-ième observation est intéressante (selon le décideur), et${\displaystyle \,I_{k}=0}$pour non intéressant. Ces variables ${\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}$ sont observées séquentiellement, le but étant de sélectionner correctement le dernier succès lorsqu'il se produit.

Soit ${\displaystyle \,p_{k}=P(\,I_{k}\,=1)}$ la probabilité que le k-ième événement soit intéressant. Définissons également${\displaystyle \,q_{k}=\,1-p_{k}}$ et ${\displaystyle \,r_{k}=p_{k}/q_{k}}$.${\displaystyle \,r_{k}}$ représente les chances que le k-ième événement soit intéressant, expliquant ainsi le nom de l'algorithme des cotes.

Procédure algorithmique[modifier | modifier le code]

L'algorithme des cotes résume les cotes dans l'ordre inverse

${\displaystyle r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,}$

jusqu'à ce que la somme dépasse 1 pour la première fois, enregistrant l'indice s et la somme correspondante.

${\displaystyle R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}.\,}$

Si la somme des cotes n'atteint pas 1, il définit s=1. En même temps, il calcule

${\displaystyle Q_{s}=q_{n}q_{n-1}\cdots q_{s}.\,}$

La sortie est

1. ${\displaystyle \,s}$, le seuil d'arrêt
2. ${\displaystyle \,w=Q_{s}R_{s}}$, la probabilité de gagner.

Stratégie de cotes[modifier | modifier le code]

La stratégie des cotes consiste à observer les événements successivement et à s'arrêter au premier événement intéressant à partir de l'indice s, le cas échéant, où s est le seuil d'arrêt de la sortie.

L'importance de la stratégie des cotes et de son algorithme associé réside dans le théorème des cotes suivant.

Théorème des probabilités[modifier | modifier le code]

Le théorème des probabilités stipule que

1. La stratégie des cotes est optimale, c'est-à-dire qu'elle maximise la probabilité de s'arrêter sur le dernier 1.
2. La probabilité de gain de la stratégie des cotes est égale à ${\displaystyle w=Q_{s}R_{s}}$
3. Si ${\displaystyle R_{s}\geq 1}$, la probabilité de gagner ${\displaystyle w}$ est toujours au moins 1/e = 0.367879... , et cette limite inférieure est la meilleure possible.

Caractéristiques[modifier | modifier le code]

L'algorithme des cotes calcule simultanément la stratégie optimale et la probabilité de gain optimale, avec un nombre d'opérations (sous)linéaire en n. Cela en fait un choix optimal comme algorithme, car aucun algorithme plus rapide ne peut exister pour toutes les séquences.

Sources[modifier | modifier le code]

Bruss 2000 a créé et nommé l'algorithme des cotes, également connu sous le nom d'algorithme de Bruss. Des implémentations gratuites sont disponibles en ligne.

Applications[modifier | modifier le code]

Les applications incluent les essais cliniques médicaux, les problèmes de secrétaire, de vente, de sélection de portefeuille, de recherche unidirectionnelle, de trajectoire et de stationnement, de maintenance en ligne, et d'autres encore.

Le théorème des cotes s'applique aux processus d'arrivée en temps continu à incréments indépendants tels que le processus de Poisson ( Bruss 2000 ). En l'absence de cotes préalables, l'application directe de l'algorithme des cotes peut être impossible. Dans de tels cas, des estimations séquentielles des probabilités peuvent être utilisées, notamment lorsque le nombre de paramètres inconnus n'est pas important par rapport au nombre d'observations n. La question de l'optimalité devient plus complexe et nécessite des études supplémentaires. Les généralisations de l'algorithme des cotes autorisent différentes récompenses en cas d'échec ou d'arrêt incorrect, et peuvent remplacer les hypothèses d'indépendance par des hypothèses plus faibles (Ferguson 2008).

Variantes[modifier | modifier le code]

Bruss et Paindaveine 2000 ont traité du problème de sélection des derniers k succès.

Tamaki 2010 a démontré un théorème des cotes multiplicatives pour un problème d'arrêt aux derniers \(\ell\) succès, et Matsui et Ano 2014. ont obtenu une borne inférieure serrée de la probabilité de gain.

Matsui et Ano 2017 ont traité du problème de sélection de ${\displaystyle k}$ parmi les derniers ${\displaystyle \ell }$ succès, obtenant une borne inférieure serrée de la probabilité de gain. Lorsque ${\displaystyle \ell =k=1,}$le problème est équivalent au problème des cotes de Bruss. Si le problème est similaire à celui discuté dans Bruss et Paindaveine 2000. Un problème traité par Tamaki 2010 est également obtenu.

Problème à choix multiples[modifier | modifier le code]

Un joueur a ${\displaystyle r}$ choix et gagne si l'un d'entre eux est le dernier succès. Gilbert et Mosteller 1966 ont discuté des cas ${\displaystyle r=2,3,4}$ pour le problème classique du secrétaire. Le problème des chances avec ${\displaystyle r=2,3}$ est discuté par Ano, Kakinuma et Miyoshi 2010. Pour d'autres cas de problèmes de cotes, voir Matsui et Ano 2016.

Une stratégie optimale pour ce problème utilise un ensemble de nombres seuils ${\displaystyle (a_{1},a_{2},...,a_{r})}$, où${\displaystyle a_{1}>a_{2}>\cdots >a_{r}}$.

Imaginez avoir ${\displaystyle r}$ lettres d'acceptation étiquetées de 1 à ${\displaystyle r}$. Vous avez ${\displaystyle r}$ agents responsables des demandes, chacun détenant une lettre. Vous interviewez les candidats et les classez sur un tableau visible par chaque responsable des candidatures. L'agent ${\displaystyle i}$ enverra sa lettre d'acceptation au premier candidat meilleur que tous les candidats de 1 à ${\displaystyle a_{i}}$. (Les lettres d'acceptation non envoyées vont par défaut aux derniers candidats, comme dans le problème standard du secrétaire.)

Pour ${\displaystyle r=2}$, Ano, Kakinuma et Miyoshi 2010 ont montré que la limite inférieure étroite de la probabilité de victoire est ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}.}$. Pour ${\displaystyle r}$ entier positif général, Matsui et Ano 2016 ont prouvé que la limite inférieure étroite de la probabilité de victoire est celle de la variante du problème de secrétaire où les k meilleurs candidats sont choisis en utilisant seulement k tentatives.

Pour ${\displaystyle r=3,4,5}$, les limites inférieures serrées des probabilités de victoire sont respectivement${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}}$, ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}}$ et ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}}.}$

Pour d'autres valeurs de ${\displaystyle r}$ (de 6 à 10) et un algorithme général, consultez Matsui et Ano 2016.

Références[modifier | modifier le code]

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Bibliographie[modifier | modifier le code]

• Ano, Kakinuma et Miyoshi, « Odds theorem with multiple selection chances », Journal of Applied Probability, vol. 47, n^o 4,‎ 2010, p. 1093–1104 (DOI 10.1239/jap/1294170522, S2CID 17598431)
• Bruss, « Sum the odds to one and stop », The Annals of Probability, Institute of Mathematical Statistics, vol. 28, n^o 3,‎ 2000, p. 1384–1391 (ISSN 0091-1798, DOI 10.1214/aop/1019160340)
• —: "A note on Bounds for the Odds Theorem of Optimal Stopping", Annals of Probability Vol. 31, 1859–1862, (2003).
• —: "The art of a right decision", Newsletter of the European Mathematical Society, Issue 62, 14–20, (2005).
• Bruss et Paindaveine, « Selecting a sequence of last successes in independent trials », Journal of Applied Probability, vol. 37, n^o 2,‎ 2000, p. 389–399 (DOI 10.1239/jap/1014842544, lire en ligne)
• Gilbert et Mosteller, « Recognizing the Maximum of a Sequence », Journal of the American Statistical Association, vol. 61, n^o 313,‎ 1966, p. 35–73 (DOI 10.2307/2283044, JSTOR 2283044)
• Matsui et Ano, « A note on a lower bound for the multiplicative odds theorem of optimal stopping », Journal of Applied Probability, vol. 51, n^o 3,‎ 2014, p. 885–889 (DOI 10.1239/jap/1409932681)
• Matsui et Ano, « Lower bounds for Bruss' odds problem with multiple stoppings », Mathematics of Operations Research, vol. 41, n^o 2,‎ 2016, p. 700–714 (DOI 10.1287/moor.2015.0748, arXiv 1204.5537, S2CID 31778896)
• Matsui et Ano, « Compare the ratio of symmetric polynomials of odds to one and stop », Journal of Applied Probability, vol. 54,‎ 2017, p. 12–22 (DOI 10.1017/jpr.2016.83, S2CID 41639968, lire en ligne)
• Shoo-Ren Hsiao and Jiing-Ru. Yang: "Selecting the Last Success in Markov-Dependent Trials", Journal of Applied Probability, Vol. 93, 271–281, (2002).
• Tamaki, « Sum the multiplicative odds to one and stop », Journal of Applied Probability, vol. 47, n^o 3,‎ 2010, p. 761–777 (DOI 10.1239/jap/1285335408, S2CID 32236265)
• Mitsushi Tamaki: "Optimal Stopping on Trajectories and the Ballot Problem", Journal of Applied Probability Vol. 38, 946–959 (2001).
• E. Thomas, E. Levrat, B. Iung: "L'algorithme de Bruss comme contribution à une maintenance préventive", Sciences et Technologies de l'automation, Vol. 4, 13-18 (2007).

Liens externes[modifier | modifier le code]

• Algorithme de Bruss

Articles connexes[modifier | modifier le code]

• Cote (probabilités)
• Essai clinique
• Problème du secrétaire

• Portail des mathématiques
• Portail des probabilités et de la statistique
• Portail des sciences