Un algorithme paradoxal

[leon1789]

Bonjour

Je vous propose un petit paradoxe concernant un algorithme (sans paramètre) dont on démontre d'une part qu'il termine à coup sûr, et d'autre part qu'il utilise en moyenne une infinité d'opérations ! Paradoxe ?

Evidemment, il existe des algos qui terminent à coup sûr et dont on ne peut pas borner le nombre d'opérations indépendamment des paramètres : par exemple, pour calculer le pgcd de deux entiers a et b, le nombre d'opérations dépend des entiers a et b, et en prenant des entiers a et b de plus en plus grands, on peut augmenter autant que l'on veut le nombre d'opérations. Mais dans l'exemple ci-dessous, nous ne sommes pas dans le même contexte car il n'y a pas de paramètre...

Voici le principe de l'algorithme : on veut tirer au hasard un entier k>0 en suivant la loi de probabilité P(X=k) = 1/k(k+1). Ceci est cohérent car .

Pour simuler en machine un tel tirage aléatoire, on utilise l'algo suivant qui transforme un tirage aléatoire uniforme dans ]0, 1[ (fonction prédéfinie dans tout langage, genre "rand") en un tirage sur N* suivant la loi donnée ci-dessus :

Code: Tout sélectionner

f := la fonction x +--> 1/x(x+1)
r := un nombre tiré au hasard dans ]0, 1[ suivant la loi uniforme
s := 0
i := 0
tant que s < r répéter la boucle
    i := i + 1
    s := s + f(i)
fin de boucle
retourner la valeur de i


(certes, on peut gagner une étape de calcul en initialisant i à 1 et s à f(1), mais cela ne change rien à l'affaire :lol3:)
(quitte à changer la fonction f, cet algo fonctionne pour toute loi de probabilité sur les entiers naturels)


*Est-ce que cet algorithme se termine ? Oui, car les sommes partielles tendent vers 1 et finiront tôt ou tard par dépasser r puisque r<1.


**Est-ce que cet algorithme donne un tirage aléatoire respectant la loi de probabilité P(X=k) = 1/k(k+1) ? Oui : la probabilité de renvoyer un certain entier k est la probabilité que r soit coïncé dans l'intervalle I dont les bornes sont les sommes partielles consécutives et , autrement dit . Or I est un intervalle de longueur f(k) = 1/k(k+1), et comme r est tiré de manière uniforme, il en résulte que


***Quel est le nombre moyen d'additions lorsque l'on fait tourner cet algo ? Pour retourner un nombre k, l'algorithme a besoin de calculer k additions (car k tours de boucle). De plus la probabilité de retourner k est P(X=k)=1/k(k+1), donc l'espérance du nombre d'additions (autrement dit le nombre "moyen" d'additions) est ! :doh:

Ainsi cet algorithme donne en un temps fini un résultat correct qui nécessite en moyenne une infinité d'additions... :ptdr:

[nuage]

Salut,
j'aurais tendance à penser qu'il y a une entourloupe langagière.

Quand une variable aléatoire n'a pas d'espérance, je ne voit pas ce qui permet de la relier à une valeur moyenne des réalisations.

On relie bien ces quantités via Bienaymé-Tchebicheff quand la variable aléatoire a une espérance et une variance.
Mais quand il y a ni l'une ni l'autre...

Une remarque pour finir : ce serait une mauvaise idée de faire une simulation. Dans ce cas on a une espérance est une variance, qui dépendent en particulier du langage et de la fonction rand.

[leon1789]

Une remarque pour finir : ce serait une mauvaise idée de faire une simulation. Dans ce cas on a une espérance est une variance, qui dépendent en particulier du langage et de la fonction rand.

Je suis d'accord que tout langage possède une fonction "rand" particulière qui influe sur le résultat et que le résultat théorique désiré ne peut être physiquement obtenu à la perfection (...puisque la fonction "rand" d'un logiciel ne tire pas un réel entre 0 et 1 de manière uniforme à la perfection.).

Mais l'expérimentation reste intéressante. J'ai lancé l'algo sur une machine dans une succession de tirages aléatoires : après N lancés, le nombre moyen d'additions était expérimentalement autour de ln(N). Mais tôt ou tard (parfois après plusieurs centaines de milliers de tirages aléatoires), l'algorithme se met à ramer parce qu'il tire un nombre r très proche de 1 et le nombre d'additions explose !

[leon1789]

Une remarque pour finir : ce serait une mauvaise idée de faire une simulation. Dans ce cas on a une espérance est une variance, qui dépendent en particulier du langage et de la fonction rand.

Je suis d'accord que tout langage possède une fonction "rand" particulière qui influe sur le résultat et que le résultat théorique désiré ne peut être physiquement obtenu à la perfection (...puisque la fonction "rand" d'un logiciel ne tire pas un réel entre 0 et 1 de manière uniforme à la perfection.).

Mais l'expérimentation reste intéressante. J'ai lancé l'algo sur une machine dans une succession de tirages aléatoires : après N lancés, le nombre moyen d'additions était expérimentalement autour de ln(N). Mais tôt ou tard (parfois après plusieurs centaines de milliers de tirages aléatoires), l'algorithme se met à ramer parce qu'il tire un nombre r très proche de 1 et le nombre d'additions explose !

[nuage]

Je suis d'accord que tout langage possède une fonction "rand" particulière qui influe sur le résultat et que le résultat théorique désiré ne peut être physiquement obtenu à la perfection (...puisque la fonction "rand" d'un logiciel ne tire pas un réel entre 0 et 1 de manière uniforme à la perfection.).

Mais l'expérimentation reste intéressante. J'ai lancé l'algo sur une machine dans une succession de tirages aléatoires : après N lancés, le nombre moyen d'additions était expérimentalement autour de ln(N). Mais tôt ou tard (parfois après plusieurs centaines de milliers de tirages aléatoires), l'algorithme se met à ramer parce qu'il tire un nombre r très proche de 1 et le nombre d'additions explose !

En fait il est sans doute utile de modéliser la simulation.

Disons qu'il y a un plus grand entier possible : K
On a alors pour et

Il est alors assez clair que la valeur moyenne observée sur N essais est de l'ordre de si N est petit devant K, disons . En d'autre termes : les événements suffisamment improbables ne se produisent pas.

Mais bien sur, c'est faux : il y a donc des cas où ça mouline.

[leon1789]

Je suis d'accord avec toi.