Efficiency of Monte Carlo sampling in chaotic systems

In this paper we investigate how the complexity of chaotic phase spaces affect the efficiency of importance sampling Monte Carlo simulations. We focus on flat-histogram simulations of the distribution of finite-time Lyapunov exponent in a simple chaotic system and obtain analytically that the computational effort: (i) scales polynomially with the finite time, a tremendous improvement over the exponential scaling obtained in uniform sampling simulations; and (ii) the polynomial scaling is suboptimal, a phenomenon known as critical slowing down. We show that critical slowing down appears because of the limited possibilities to issue a local proposal in the Monte Carlo procedure when it is applied to chaotic systems. These results show how generic properties of chaotic systems limit the efficiency of Monte Carlo simulations.

Figure 1

Computational effort of importance sampling Monte Carlo methods in chaotic systems. Each curve represents the average round-trip time $\tau$ (a measure of the computational effort, see Sec. 2d) of a representative simulation (flat-histogram) of the distribution of the (largest) finite-time Lyapunov exponent. While uniform sampling scales as $exp\left(\alpha N\right)$, importance sampling scales as $N^{\gamma }$ with $\gamma \ge 2$. Tent map: Eq. (16) with $a=3$; logistic map: $x_{n+1}=4x_n(1-x_n)$; standard map [1]: $K=8$, and we used ${\lambda }_N(x_0,v_0)$ in Eq (1) where $v_0$ was drawn isotropically in every proposal; coupled Hénon map: a six-dimensional open system, results retrieved from Ref. [11], the simulation is in the escape time distribution. The Wang-Landau algorithm [12] was used to estimate the distribution prior to perform the flat histogram, and the distribution agrees with the analytical one when available [10, 13].

Figure 2

The two-scale tent map, Eq. (16), and its finite-time $N$ symbolic sequences $s=[s_1...s_N]$.

Figure 3

Local proposals on the symbolic sequences of the tent map. (a) Shift proposes to shift the sequence, where the first symbol is dropped and a new symbol is added in the end (left) or vice-versa (right). (b) Precision shooting proposes a change in the symbol after the first “1” when counting from the right (left), or in the last symbol (right).

Figure 4

Equivalence between a Monte Carlo in the phase space of the tent map and in its symbolic sequences. Scaling of the average round-trip as function of the finite-time $N$ of a flat-histogram simulation: in its phase space (black circles); in its symbolic sequences (red rectangles); in its symbolic sequences using only shift proposals (blue diamonds). The dashed line represents the scaling $N^3$. We use $a=3$ in Eq. (16) and, for the simulation in the phase space, we use the procedure outlined in the previous section with the exact distribution Eq. (19) in Eq. (9), ${\delta }_0=0.1$ in Eq. (14), and the average round-trip computed over 100 round-trips. In simulations on the symbolic sequences, we use 50% probability for the same sequence and 25% for each neighbor interval in the precision shooting, but we observe no qualitative difference with other values.

Figure 5

Critical slowing down in Monte Carlo simulations on the symbolic sequences of the tent map. The variance in $\lambda {\sigma }_{\lambda }^2\left(t\right)$ is estimated as $1/M{\sum }_{i=1}^M{[{\lambda }_i\left(t\right)-\overline{\lambda }\left(t\right)]}^2$, where $\overline{\lambda }\left(t\right)=1/M{\sum }_{i=1}^M{\lambda }_i\left(t\right)$, of $M=1000$ independent flat-histogram simulations starting from states $s$ with a fixed ${\lambda }_0={\lambda }_{N,N/2}$ [see Eq. (17)]. Results are shown as a function of the number of Monte Carlo steps $t$, for different finite-times $N$, from $N=32$ to $N=2048$. $S=[{(N+1)}^2/12]/N$ is the variance of a flat histogram, divided by $N$ and emphasizes that ${\sigma }_{\lambda }^2\left({\tau }_s\right)$ scales with $N$, as expected from Eqs. (21) and (22). Two scalings, $\sqrt{t}$ and $t$, are shown as dashed lines. Inset shows the same simulations but using the canonic ensemble, Eq. (7), with $\beta =1$. The axes are the same as those of the main plot, but with ${\sigma }_{\lambda }^2$ normalized by Eq. (A6), Eq. (8) with Eq. (18), is reached. The scaling $\sqrt{t}$ is also shown in dashed line. Changing ${\lambda }_0$ in the flat histogram or $\beta$ in the canonic ensemble does not change the scaling and only shifts all curves; see Fig. 6.

Figure 6

Equivalence of flat-histogram simulation starting at a fixed $\lambda$ with a canonic simulations with a fixed $\beta$. In symbols, flat-histogram simulations equivalent to the ones described in the legend of Fig. 5 with $N=2048$ for different starting $\lambda \mathrm{s}$ given by Eq. (A1). ${\sigma }_{\lambda }\left(t\right)$ was rescaled by ${\sigma }_{\beta }^2\left(k\right)$ from Eq. (A6). In lines, canonic simulations equivalent to the ones of the inset of Fig. 5 with $N=2048$ and $\beta =\beta \left(k\right)$ given by Eq. (A5) to match the flat-histogram simulations.