Taming chaos to sample rare events: The effect of weak chaos.

Rare events in nonlinear dynamical systems are difficult to sample because of the sensitivity to perturbations of initial conditions and of complex landscapes in phase space. Here, we discuss strategies to control these difficulties and succeed in obtaining an efficient sampling within a Metropolis-Hastings Monte Carlo framework. After reviewing previous successes in the case of strongly chaotic systems, we discuss the case of weakly chaotic systems. We show how different types of nonhyperbolicities limit the efficiency of previously designed sampling methods, and we discuss strategies on how to account for them. We focus on paradigmatic low-dimensional chaotic systems such as the logistic map, the Pomeau-Maneville map, and area-preserving maps with mixed phase space.

Importance-sampling computation of statistical properties of coupled oscillators.

We introduce and implement an importance-sampling Monte Carlo algorithm to study systems of globally coupled oscillators. Our computational method efficiently obtains estimates of the tails of the distribution of various measures of dynamical trajectories corresponding to states occurring with (exponentially) small probabilities. We demonstrate the general validity of our results by applying the method to two contrasting cases: the driven-dissipative Kuramoto model, a paradigm in the study of spontaneous synchronization; and the conservative Hamiltonian mean-field model, a prototypical system of long-range interactions. We present results for the distribution of the finite-time Lyapunov exponent and a time-averaged order parameter. Among other features, our results show most notably that the distributions exhibit a vanishing standard deviation but a skewness that is increasing in magnitude with the number of oscillators, implying that nontrivial asymmetries and states yielding rare or atypical values of the observables persist even for a large number of oscillators.

Sampling Motif-Constrained Ensembles of Networks.

The statistical significance of network properties is conditioned on null models which satisfy specified properties but that are otherwise random. Exponential random graph models are a principled theoretical framework to generate such constrained ensembles, but which often fail in practice, either due to model inconsistency or due to the impossibility to sample networks from them. These problems affect the important case of networks with prescribed clustering coefficient or number of small connected subgraphs (motifs). In this Letter we use the Wang-Landau method to obtain a multicanonical sampling that overcomes both these problems. We sample, in polynomial time, networks with arbitrary degree sequences from ensembles with imposed motifs counts. Applying this method to social networks, we investigate the relation between transitivity and homophily, and we quantify the correlation between different types of motifs, finding that single motifs can explain up to 60% of the variation of motif profiles.

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.

Monte Carlo sampling in fractal landscapes.

We design a random walk to explore fractal landscapes such as those describing chaotic transients in dynamical systems. We show that the random walk moves efficiently only when its step length depends on the height of the landscape via the largest Lyapunov exponent of the chaotic system. We propose a generalization of the Wang-Landau algorithm which constructs not only the density of states (transient time distribution) but also the correct step length. As a result, we obtain a flat-histogram Monte Carlo method which samples fractal landscapes in polynomial time, a dramatic improvement over the exponential scaling of traditional uniform-sampling methods. Our results are not limited by the dimensionality of the landscape and are confirmed numerically in chaotic systems with up to 30 dimensions.

Effect of noise in open chaotic billiards.

We investigate the effect of white-noise perturbations on chaotic trajectories in open billiards. We focus on the temporal decay of the survival probability for generic mixed-phase-space billiards. The survival probability has a total of five different decay regimes that prevail for different intermediate times. We combine new calculations and recent results on noise perturbed Hamiltonian systems to characterize the origin of these regimes and to compute how the parameters scale with noise intensity and billiard openness. Numerical simulations in the annular billiard support and illustrate our results.