"On calcule l'écart-type (racine carré de la variance) on sait que 95% des valeurs ayant servi au calcul de la moyenne se situent entre -2 écart-type et +2 écart-type (1.96 pour les puristes), mais ça ne donne pas d'information sur la précision de la moyenne calculée."

Ben si. Tu as un intervalle de confiance qui te dit par exemple que la vraie moyenne est comprise à 95% entre ta moyenne estimée plus ou moins 2 écarts-type (estimés). Sous caution que la distribution suive une loi normale, ce qui ne peut pas être sujet à vérification avec seulement 3 ou 4 valeurs.

Bonjour Léon,
Alors, je pose ma question autrement : comment espérer avoir une évaluation de la précision du résultat à partir d'une seule observation, c'est à une seule mise en œuvre de la méthode de Mente-Carlo ?

Bonjour Nombtilist,
Oui, effectivement, la moyenne vraie sera certainement dans l'intervalle +/-2sigma. Et alors, c'est une information intéressante ?
En fait c'est même pas sûr du tout.
Pour une expérience comme l'hypercube (dimension 12) où le nombre de résultats possibles est compris entre 12 et quelques milliers, une seule application de la méthode ne donne qu'un seul résultat, donc, toute évaluation de la variance pour l'espérance cherchée est plus que douteuse.
Pour un tirage aléatoire, uniforme, la loi normale se vérifie dès une vingtaine ou une trentaine de tirages. Dans le cas présent, la série aléatoire uniforme est le numéro d'ordre du voisin et en aucun cas le nombre de sommets à traverser pour atteindre le dernier.  

Tu ne peux pas. Il faut répéter la méthode un bon millier de fois au minimum. Un boot-strap en somme me semble-t-il. En phylogénie, il me semble qu'il faut plus de 10 000 échantillonnages.

Je répondais à ton message de 18h38.

Bon, Léon, c'est justement ce qu'explique ce cours et c'est justement ce qui me chagrine.
Donc, apparemment tu as compris la question posée. Depuis que j'ai écrit ce topic, j'ai un peu réfléchi et je te donnerai le résultat de mes réflexions  demain, avec exemples.
En attendant, j'aimerais bien avoir aussi les réactions de Nombrilist.
Bonne soirée.

Pour reprendre: une expérience unique (i.e. une seule donnée en guise de résultat) ne sert à rien. Il faut des répétitions, c'est obligatoire. Et plus la variabilité est potentiellement grande, et plus il faut de répétition pour être confiants dans la moyenne et l'écart-type que l'on estime. Je ne sais pas si ça répond à ta question sur ce que j'en pense ?

Bonjour,
La méthode de Monte-Carlo consiste à effectuer un grand nombre de calculs d'une même équation, avec des valeurs aléatoires obtenues par un moyen quelconque.
On suppose que le générateur de nombres fournit une suite uniformément distribuée.
Le résultat de cette opération est obtenu en faisant la moyenne arithmétique des résultats des différents calculs. La question qui se pose est : comment évaluer l'incertitude sur cette valeur ie "un intervalle de confiance à 95% pour le résultat".

Gardons l'exemple de l'hypercube. Un résulatat de l'équation consiste à déterminer de façon aléatoire le rang du voisin dans une liste, puis de recommencer jusqu'à parvenir au sommet prévu. Le résultat obtenu est le nombre de sommets parcourus.
On répète cette opération un grand nombre de fois et on fait la moyenne des résultats obtenus.
On obtient donc UN résultat et on voudrait conaitre l'incertitude.
Il n'y a pas de relation directe entre le nombre de calculs élémentaires et l'incertitude sur le résultat, sauf naturellement que plus nombreux seront les calculs, plus faible sera l'incertitude.
La méthode que je propose permet d'évaluer cette incertitude.

On met en oeuvre la méthode de Monte-Carlo un certain nombre de fois, disons une vingtaine, dans les mêmes conditions, c'est à dire avec le même nombre de calculs. On obtient ainsi 20 résultats qui constituent une expérience aléatoire. De ces résultats on va tirer une moyenne, un écart-type et ainsi on aura une valeur de l'incertitude sur le résultat final.
Exemple :
Nombre = 20  Moyenne = 4168.10  emq=418.62  ep=279.08
Nombre = 20  Moyenne = 4138.65  emq=395.10  ep=263.40
Nombre = 20  Moyenne = 4284.35  emq=477.10  ep=318.07
Nombre = 20  Moyenne = 4230.80  emq=414.53  ep=276.35
Nombre = 20  Moyenne = 3978.75  emq=340.32  ep=226.88
Nombre = 20  Moyenne = 4035.00  emq=531.34  ep=354.23

Un grand nombre de calculs m'a permis d'estimer la "valeur vraie" à 4095.
Chacune de ces 6 expériences a consisté à calculer 20 moyennes de 100 calculs élémentaires.

Bonjour Léon,
Par définition, la valeur vraie est inconnue.
Mais dans le cas présent, sachant qu'on peut calculer la calculer de façon théorique, je te laisse le soin de vérifier si je ne suis pas trop loin de la vérité vraiment exacte.

En fait, j'ai simplement indiqué cette valeur de 4095 pour donner une idée de comparaison.
Je ne sais plus si je déjà dit, mais je n'aime pas beaucoup cette notion d'intervalle de confiance. Je crois que j'ai réussi jusqu'ici à me retenir de le dire.
En l'occurrence, ce n'est pas le sujet que je voulais aborder, seulement le fait qu'un nombre relativement petit de calculs, 100 en l'occurrence, mais avec la répétition de l'expérience, j'ai choisi 20, 30 serait préférable, permet d'avoir une valeur recevable de l'écart-type.
La valeur ep que j'ai indiquée signifie que 50% des écarts à la valeur vraie, inconnue, seront inférieurs à cet écart, si tu veux 95%, ça fait 2 emq.
Je crois qu'on a déjà eu des échanges à ce sujet.
Concernant la valeur 4095, l'écart-type est 17.5 soit ep=11.6.
Au lieu de dire "j'estime la valeur vraie à 4095", j'aurais du dire, "j'ai calculé une valeur plus précise, et j'ai trouvé 4095".
De toute façon, il ne s'agit que d'un exemple, et pour formaliser la méthode, il faudrait définir une façon de calculer cette valeur (nombre de calculs) que j'ai prise forfaitairement à 100.  

Par ailleurs, Dzlogic,

Ce que tu tentes de faire correspond à une sorte de "bootstrap".

Tu répètes N réalisations de Monte-Carlo que tu groupes pour obtenir une moyenne empirique.
Ensuite tu répètes ces mesures échantillonnées pour observer la distribution des moyennes empiriques.
Tu en déduis une sorte de distribution de l'erreur sur cette moyenne empirique.

Au plan "intuitif" et "pragmatique" ce n'est pas idiot...
Ce que tu obtiens ainsi c'est une sorte d'intervalle de fluctuation de la moyenne empirique.
Mais ça ne te garantit pas en général que tu trouveras une valeur proche de l'espérance mathématique.

Très schématiquement ce que ton procédé va calculer, c'est une moyenne empirique et un intervalle associé...
... qui "ressemblera" à ce qui va se produire si on simule un grand nombre de fois la marche aléatoire...
... tout en n'étant jamais certain que cette moyenne empirique est effectivement représentative de l'espérance mathématique...
... parce que tu n'es jamais à l'abris de "réalisations excentriques", rarissimes, mais susceptibles de biaiser plus ou mois fortement le calcul de l'espérance.

Dans l'exemple de la marche aléatoire dans l'hypercube, on peut raisonnablement penser qu'un bootstrap va fonctionner...
... parce que la nature du problème posé et sa mathématisation matricielle le laisse deviner (et le rend sûrement démontrable...).

Mais pour un problème quelconque en général, c'est plus délicat.

Sinon, on pourrait par exemple résoudre des problèmes NP complexes (du type voyageur de commerce) en grandes dimensions par une approche "Monte-Carlo bootstrapée", à moindre coût.
On peut le faire en pratique du reste... mais sans aucune garantie d'être proche ou pas de l'optimum réel.
  

Entièrement d'accord avec LeDino.

"Mais ça ne te garantit pas en général que tu trouveras une valeur proche de l'espérance mathématique."

Quand plusieurs bootstrap te donnent la même distribution empirique à un pouillième près, tu peux quand même considérer que t'as tapé juste.

J'ai tout compris.
Juste avant de clore le sujet, quelle est la valeur "exacte", pour la dimension 12 comme je l'ai précisé dans mon message explicatif.

Je n'ai plus la valeur exacte de E(T12) sous la main...
... mais de mémoire elle est environ 1,12 fois plus grand que 2 puissance 12 = 4096.

La série E(Tn) devient équivalente à 2 puissance n à l'infini.

Bon, la valeur "exacte" est 4096, d'après tes souvenirs, évidemment c'est extrêmement différent de 4095 ???
Il est vrai que le premier chiffre est tout de même valable.

Non tu as mal lu (ou je me suis mal exprimé...).

La valeur exacte est environ 1,12 fois 4096, soit environ 4587.
Je te dis ça de mémoire parce que j'avais calculé le ratio E(Tn) sur 2^n pour différentes valeurs de n (pour vérifier qu'il tendait vers 1) et je me souviens que pour n=20 ce ratio valait 1,12.


Et avant de t'énerver pour un oui ou pour un non, tu pourrais essayer de prendre le temps de la réflexion et d'éviter de prendre les gens pour des cons.
Ca ferait vraiment des vacances pour tout le monde.

Et au passage, si tu veux la valeur exacte de E(Tn) pour tout n, sa formule a été donnée dans la discussion...
... donc tu peux la calculer toi même.

Et si tu avais pris la peine de calculer 2 puissance 12, tu aurais compris mon explication.

Bon, je me demande si je n'ai pas mal interprété ton dernier message, peut-être voulais-tu dire que le résultat cherché était environ (de mémoire) 12x4096, soit 4920 ?
Alors, il faudra le prouver, puisque je maintiens que le nombre est compris entre  4049 et 4141 (intervalle de confiance).
Si la question ne t'intéresse pas pourquoi tu interviens, juste pour dire que j'ai tort ?

Rectification, c'est 1.12 x 4096 = 1590, mais je maintiens mes limites.
Mais pardon de le rappeler, ce n'est pas le sujet de ce topic.

Bon, j'ai compris, tu as raison.

Pour vérification, je viens de faire une Monte-Carlo :
20 simulations de 100 marches aléatoires pour N=12...

J'obtiens :   E(T) ~ 4600

Et l'écart-type moyen sur une marche est d'ordre comparable (un peu plus de 4500).

Bonjour LeDino,
Effectivement, il y avait une erreur dans mon résultat, je n'en sais d'ailleurs pas la raison.
J'ai refait les calcul avec ma construction de graphe, et voilà un résultat
-----méthode graphe--------------------
N = 12  Nfois= 100  Moyenne : 4881
N = 12  Nfois= 100  Moyenne : 3909
N = 12  Nfois= 100  Moyenne : 4673
N = 12  Nfois= 100  Moyenne : 4062
N = 12  Nfois= 100  Moyenne : 4678
N = 12  Nfois= 100  Moyenne : 3490
N = 12  Nfois= 100  Moyenne : 5141
N = 12  Nfois= 100  Moyenne : 4542
N = 12  Nfois= 100  Moyenne : 3696
N = 12  Nfois= 100  Moyenne : 4700
N = 12  Nfois= 100  Moyenne : 4858
N = 12  Nfois= 100  Moyenne : 4764
N = 12  Nfois= 100  Moyenne : 3993
N = 12  Nfois= 100  Moyenne : 4308
N = 12  Nfois= 100  Moyenne : 3965
N = 12  Nfois= 100  Moyenne : 5323
N = 12  Nfois= 100  Moyenne : 4898
N = 12  Nfois= 100  Moyenne : 4165
N = 12  Nfois= 100  Moyenne : 4509
N = 12  Nfois= 100  Moyenne : 4567
Coefficient d'asymétrie G1= -0.2706  d'aplatissement G2= -3.3931
Nombre = 20  Moyenne = 4456.10  emq=489.85  ep=326.56
Classe 1  nb=   0  0.00%   théorique 0.35% |
Classe 2  nb=   0  0.00%   théorique    2% |
Classe 3  nb=   2  10.00%   théorique    7% |HHHHHHHHHH
Classe 4  nb=   4  20.00%   théorique   16% |HHHHHHHHHHHHHHHHHHHH
Classe 5  nb=   2  10.00%   théorique   25% |HHHHHHHHHH
Classe 6  nb=   7  35.00%   théorique   25% |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
Classe 7  nb=   3  15.00%   théorique   16% |HHHHHHHHHHHHHHH
Classe 8  nb=   2  10.00%   théorique    7% |HHHHHHHHHH
Classe 9  nb=   0  0.00%   théorique    2% |
Classe 10 nb=   0  0.00%   théorique 0.35% |

J'avoue que je n'ai pas prêté vraiment attention aux valeurs, seulement à la répartition des écarts, puisque c'était ça le sujet de mon intervention.
Lorsque j'ai posé ma question je n'avais pas la solution, et vu les réactions, lorsque j'ai exposé la méthode, j'avoue que c'était avec un certain énervement.
Bon, je crois que le sujet est clos, j'ai donné des chiffres faux (pour une raison que j'ignore) et c'est la seule chose que l'on retiendra de ce topic.

Juste une petite réponse sur le dernier point évoqué.
La première fois que j'ai parlé de ces notions (loi normale etc.) le l'ai fait avec toutes les précautions d'usage, tout simplement parce j'ai l'habitude d'être poli et que par ailleurs je sais que ces notions sont mal connues.
On m'a traité de mystique, d'incompétent sénile, dernièrement on m'a demandé si je fumais la moquette, si j'avais eu un AVC, tout ça est très normal et j'ai tort de le prendre mal.
Je n'insisterai pas plus sur ce sujet et je n'ai aucun compte à régler

Pour essayer de rester dans le sujet.
Non, je n'ai pas revu mon programme mais je l'ai relu soigneusement et je ne sais pas pourquoi les résultats sont faux. Ce module utilise la méthode de Nombrilist et j'aurais dû me rendre compte plus vite qu'il y avait des écarts importants avec le calcul fait à partir de la méthode que j'ai utilisée d'abord, c'est à dire la construction d'un hypercube.

Le principe qui justifie la méthode de Monte-Carlo consiste au fait que si on réalise une expérience aléatoire, la moyenne est la valeur la plus probable et les écarts entre les différentes valeurs observées et la moyenne respectent la répartition de la loi normale.
Dans le cas présent, l'expérience n'est pas UNE mise en œuvre de la méthode, mais plusieurs mises en œuvre.
En effet, le nombre de sommets parcourus n'a aucune raison d'être distribué suivant une suite identiquement distribuée. Ce qui est comparable, c'est un ensemble d'applications de la méthode, toutes choses égales par ailleurs.
Pour une application, le nombre de calculs à faire dépend naturellement du problème à traiter. Comme par définition, on ne connait pas la loi de répartition, on ne peut que trouver une méthode pour fixer ce nombre de calculs et non pas "trouver une formule a priori". J'ai bien précisé que ce point restait à définir.

Pour en revenir à ce qui m'a fait ouvrir ce topic, c'est que le cours cité n'évoque en aucun cas ce point. Les méthodes pour diminuer la variance (2è partie) supposent, bien que ce ne soit pas explicitement dit, que l'on connaisse la loi de répartition.

Le terme "empirique" m'amuse toujours. Un bonne traduction serait "on a toujours fait comme ça".
Surtout en matière de probabilité, il n'y a rien d'empirique, tout ça est parfaitement mathématique et parfaitement rigoureux, en partant de 2 ou 3 hypothèses bien précises. (le terme "hypothèse" est mal choisi, plutôt postulat ou constat)

Si on veut affiner la méthode, il faudrait avoir un plus grand nombre d'exemples, à moins que l'on soit sûr que la marche aléatoire représente un schéma général et généralisable.      

Je n'oublie pas que nous ne sommes pas d'accord sur les hypothèses de départ.

dizlogic,
depuis la première fois que tu as parlé de la loi normale, tu soutiens que toute expérience aléatoire suit la loi normale, loi normale qui, d'après toi, n'a pas de paramètre...Etc etc. Cela recadre un peu tes propos et la réaction de toutes les personnes qui ont essayé en vain de te faire prendre conscience l'énormité de cette affirmation. Mais comme tu confonds une variable aléatoire X et une somme de variables aléatoires X_1 + .... + X_n , ce n'est pas possible de te faire comprendre les hypothèses et la conclusion du TCL. Tu déformes et extrapoles les théorèmes, c'est vraiment dommage.

Concernant ce topic, je n'ai plus grand-chose à dire.
C'est une méthode que j'ai découverte il y a peu et que je n'ai jamais utilisée, mais comme elle correspondait à une logique que je connaissais, ça m'a intéressé.
La lecture du cours m'a fait un peu tiquer, d'où ce topic.
De toute façon, les termes employés m'échappent un peu.
Pour moi, il y a une liste de valeurs ou observations équiprobables.
La moyenne arithmétique est la valeurs le plus probable. Elle n'est ni empirique, ni je ne sais trop quoi, c'est le résultat d'un calcul.
Si cette moyenne était calculable par la théorie, alors c'est cette valeur qu'on utiliserait pour les calculs. Par exemple, si on mesure les 3 angles d'un triangle, alors on connait la valeur théorique de leur somme.
Si on mesure un angle en faisant 16 observations, alors la valeur la plus probable est la moyenne arithmétique des 16 observations. Y'a pas vraiment à chercher des complications.
Mais on me dit que c'est pas vrai, donc j'en parle plus.

La raison pour laquelle j'interviens de temps en temps, c'est tout simplement quand je lis des choses où je ne suis pas d'accord. Il y a quelques exceptions, par exemple, l'hypercube, ce truc m'a amusé, alors j'ai indiqué la méthode que j'ai employée et j'ai donné mes résultats. C'est tout.
Ma spécialité, c'est plutôt les calages, les calculs d'erreur et quand j'en parle, on me dit "c'est pas vrai" sans autre forme de procès. Donc j'essaye d'être le plus discret possible.

On se croisera peut être sur un prochain topic.

Juste une réponse sur le ton humoristique que j'ai déjà employé :
Si ce que j'ai dit au sujet des calages, calculs d'erreur et autres applications de ces notions relatives à la loi normale, sont fausses, il serait bon d'en informer certains organismes, je pense par exemple à l'IGN.
Pour être plus sérieux, à mon grand étonnement, personne ne m'a demandé de détails, de justifications, d'explications. C'est assez désolant.

Crois-tu que l'IGN tienne vraiment à connaitre toutes les erreurs écrites sur tous les forums ?

Des détails, tu en as donnés ! Des détails, on t'en a donnés aussi. Maintenant, à chacun d'en tirer profit ou désolation.

A mon avis, tu as tout compris (ou au contraire rien du tout) puisque c'est exactement le sujet de mon topic.

Le sujet du topic, mais quel est-il ? Tu diverges à chacun de tes messages...

Bonsoir.
Juste une remarque pour rire :
dans le cas de l'hyper-cube de dimension 12 il faut en moyenne environ 4598.9 mouvements pour passer d'un sommet au sommet opposé.
Le programme de calcul avec Xcas :
            esperance(n):={local j,(s:=1),(a:=1); for(j:=1;j<n;j++){ a:=(n+j*a)/(n-j);s:=s+a;} return(s)}
Faire  evalf(esperance(12)) pour une valeur approchée.
On peut utiliser ce résultat pour avoir une valeur plus précise de l'écart-type avec la méthode de Monte-Carlo.
Je dois avouer que je n'ai essayé de le calculer.

Bonne continuation.