O'Reilly logo

Digital Signal Processing (DSP) with Python Programming by Maurice Charbit

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

4Monte-Carlo Methods

4.1. Fundamental theorems

As we saw in section 1.6, theorems 1.8 and 1.9 form the basis for statistical methods and are crucial to the validity of Monte-Carlo methods. These theorems set out the way in which empirical means converge toward statistical moments. Noting that a statistical moment is defined as the integral of a certain function, this statement says, in some ways, that you can approximate this integral using a mean based on random (or pseudo-random) sequences. Using these two theorems, we see that the convergence as a function of the number N of samples is of the order of N−1/2. It is therefore interesting to compare this value to those obtained using deterministic numerical methods, such as the trapezoid method or Simpson’s method. The deterministic method can be seen to have a convergence speed of the order of N−2/d, where d is the dimension of the space over which the function to integrate is defined. Consequently, Monte-Carlo methods present two advantages compared to deterministic methods, which are as follows: (i) the convergence speed does not depend on the dimension d, and (ii) their use does not depend on the regularity of the function being integrated.

In a less formal manner, the trapezoidal method can be seen as using a grid with a large number of points; many of them have a negligible effect on the calculated value of the integral; following the Monte-Carlo method, only the significant values are used. There is, however, one major ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required