Efficacité d'une simulation Monte Carlo

Il faut toujours garder à l'esprit qu'une simulation Monte Carlo se fait sur ordinateur. Tout calcul numérique nécessite donc un temps de calcul qui est, grosso modo, proportionnel à . L'exemple précédent nous amène à formuler la loi

qui se trouve être une loi universelle en simulation Monte Carlo. On ne peut pas modifier le dénominateur qui est dû au théorème de la limite centrale. L'objet de ce cours est de donner des méthodes qui permettent de diminuer , parfois de manière considérable.

Une méthode quantitative pour mesurer l'efficacité d'un algorithme est de le comparer avec un algorithme de référence. Supposons donc qu'il existe deux méthodes pour estimer et soient , les estimateurs respectifs avec . Soient et les unités de temps de calcul nécessaires pour générer les échantillons statistiques respectifs. Si

on dit que la première méthode est plus efficace que la deuxième.