algorithme probabiliste

Imaginez un programme qui doit comparer deux expressions très longues. Au lieu d'examiner tous les cas, il choisit quelques valeurs au hasard et compare les résultats obtenus. Une différence suffit à conclure que les expressions ne sont pas identiques. Des résultats égaux donnent seulement une réponse assortie d'un risque d'erreur.

L'aléatoire n'est donc pas un défaut du calcul : il est introduit pour gagner du temps. En répétant des essais indépendants, on peut rendre le risque aussi petit que l'exige l'usage.

Un algorithme probabiliste, ou algorithme aléatoire, utilise des valeurs tirées au hasard pendant son exécution. À données d'entrée identiques, deux exécutions peuvent donc suivre des chemins différents, prendre des durées différentes ou produire des réponses différentes. Sa qualité ne se décrit pas seulement par son temps de calcul : elle inclut aussi la probabilité d'obtenir une réponse correcte.

Dans un algorithme de type Monte-Carlo, le temps de calcul est borné comme prévu, mais la réponse peut être fausse avec une probabilité contrôlée. Dans un algorithme de type Las Vegas, la réponse produite est correcte ; c'est le temps d'exécution qui varie. Ces garanties supposent que le tirage suit bien la loi annoncée et, lorsqu'on multiplie les essais, que leur indépendance est assurée.

Pour l'observabilité algébrique locale et l'identifiabilité d'un système dynamique, cette approche aide à décider si des états ou des paramètres peuvent être retrouvés à partir des entrées et sorties observées. Elle devient particulièrement utile quand le nombre de paramètres rend une méthode déterministe trop coûteuse. Le résultat reste alors une décision probabiliste, accompagnée d'une borne d'erreur, et non une certitude obtenue par simple échantillonnage.

On choisit d'abord une loi de tirage et un test dont on connaît une borne d'erreur. On effectue ensuite le test avec une valeur aléatoire. Si le test fournit un certificat décisif, l'algorithme s'arrête ; sinon, il recommence avec un tirage indépendant jusqu'au nombre d'essais fixé.

Si un essai se trompe avec une probabilité au plus égale à p, alors k essais indépendants, tous trompeurs, ont une probabilité au plus égale à $p^{k}p^k$. Le point d'arrêt est choisi pour que cette borne soit inférieure au risque accepté.

La méthode s'applique lorsqu'un tirage aléatoire remplace avantageusement une exploration exhaustive et qu'une garantie probabiliste peut être établie. Il faut connaître l'ensemble ou la loi de tirage, disposer d'un test calculable et relier mathématiquement ses résultats à la décision recherchée. Pour réduire le risque par répétition, les tirages doivent être indépendants ou leur dépendance doit être prise en compte dans la borne.

Un petit échantillon choisi sans loi maîtrisée ne suffit pas. Si les tirages favorisent précisément les cas où deux objets différents semblent égaux, la garantie annoncée disparaît. Il faut alors corriger le générateur, calculer une borne adaptée à cette loi ou employer une méthode déterministe.

On veut tester si les deux expressions P(x) = x² et Q(x) = x donnent toujours la même valeur, où x désigne l'entier testé. Les données sont l'ensemble de tirage {0, 1, 2, …, 9}, une sélection uniforme et trois tirages indépendants.

1. Un entier est choisi au hasard parmi les dix valeurs.
2. Les deux expressions sont évaluées sur cet entier.
3. Si les résultats diffèrent, la réponse « non identiques » est certaine.
4. S'ils sont égaux, un nouveau tirage indépendant est effectué, dans la limite de trois essais.

Les expressions coïncident seulement pour 0 et 1. Un essai a donc 2 chances sur 10, soit 20 %, de masquer leur différence. Trois accords successifs ont une probabilité égale à 0,2 × 0,2 × 0,2 = 0,008, soit 0,8 %. Le contrôle consiste à compter les deux valeurs trompeuses, puis à multiplier trois fois la probabilité 0,2.

Pour comparer de très grandes expressions algébriques, on peut évaluer celles-ci sur des valeurs aléatoires. Une évaluation différente tranche immédiatement ; une suite d'accords conduit à annoncer la borne de risque restante.

Pour analyser un modèle dynamique comportant beaucoup de paramètres, des substitutions numériques aléatoires peuvent éviter des calculs symboliques devenus impraticables. Une méthode déterministe reste préférable lorsque la taille du modèle permet d'obtenir une preuve exacte dans le temps disponible.

Dans un logiciel, le choix porte aussi sur la garantie attendue. Un procédé de Monte-Carlo convient si une faible probabilité d'erreur est acceptable et chiffrée ; un procédé de Las Vegas convient lorsque toute réponse rendue doit être correcte, quitte à attendre davantage.

Un algorithme déterministe suit le même chemin et rend le même résultat pour une entrée et un état initial donnés. Dans l'exemple, tester successivement les dix entiers est déterministe ; en tirer trois au hasard est probabiliste.

Une heuristique cherche souvent une bonne réponse rapidement, sans nécessairement fournir une borne mathématique sur son erreur. Le test aléatoire de l'exemple est probabiliste parce que son risque de 0,8 % après trois essais est calculé sous des hypothèses explicites.

Le calcul stochastique étudie des phénomènes mathématiques qui évoluent eux-mêmes avec du hasard. Un algorithme probabiliste peut, lui, introduire le hasard uniquement comme outil de calcul, même lorsque le problème posé est entièrement déterministe.

Une borne faible n'est pas une impossibilité d'erreur. Dans l'exemple, trois accords laissent encore un risque exact de 0,8 % de déclarer identiques deux expressions différentes. Il faut conserver cette valeur dans l'interprétation du résultat.

La multiplication des risques suppose ici des tirages indépendants. Réutiliser trois fois le même entier laisse le risque à 20 %, et non à 0,8 %. Il faut renouveler effectivement le tirage ou recalculer la garantie correspondant aux dépendances.

Un générateur biaisé peut invalider la borne. Si 0 et 1 reçoivent ensemble une probabilité supérieure à 20 %, le risque d'un accord trompeur augmente. La loi réelle du générateur doit remplacer la loi uniforme dans le calcul.

Une réponse probabiliste ne résout pas automatiquement un défaut de modèle. Pour l'identifiabilité, si les observations ne contiennent pas assez d'information pour distinguer deux paramètres, multiplier les tirages ne crée pas cette information. Il faut enrichir les observations ou reformuler le modèle.

Le glossaire algorithme précise le cadre général : données d'entrée, suite d'opérations et résultat attendu.

La méthode de Monte-Carlo prolonge l'étude des calculs fondés sur des échantillons aléatoires et des garanties statistiques.

La notion de système dynamique éclaire le type de modèle où l'observabilité et l'identifiabilité deviennent des questions centrales.