*Phys Rev E ; 105(3-1): 034313, 2022 Mar.*

##### RESUMO

We numerically study the dynamics of the SIR disease model on small-world networks by using a large-deviation approach. This allows us to obtain the probability density function of the total fraction of infected nodes and of the maximum fraction of simultaneously infected nodes down to very small probability densities like 10^{-2500}. We analyze the structure of the disease dynamics and observed three regimes in all probability density functions, which correspond to quick mild, quick extremely severe, and sustained severe dynamical evolutions, respectively. Furthermore, the mathematical rate functions of the densities are investigated. The results indicate that the so-called large-deviation property holds for the SIR model. Finally, we measured correlations with other quantities like the duration of an outbreak or the peak position of the fraction of infections, also in the rare regions which are not accessible by standard simulation techniques.

*Phys Rev E ; 104(5-1): 054125, 2021 Nov.*

##### RESUMO

Consider the short-time probability distribution P(H,t) of the one-point interface height difference h(x=0,τ=t)-h(x=0,τ=0)=H of the stationary interface h(x,τ) described by the Kardar-Parisi-Zhang (KPZ) equation. It was previously shown that the optimal path, the most probable history of the interface h(x,τ) which dominates the upper tail of P(H,t), is described by any of two ramplike structures of h(x,τ) traveling either to the left, or to the right. These two solutions emerge, at a critical value of H, via a spontaneous breaking of the mirror symmetry xâ-x of the optimal path, and this symmetry breaking is responsible for a second-order dynamical phase transition in the system. We simulate the interface configurations numerically by employing a large-deviation Monte Carlo sampling algorithm in conjunction with the mapping between the KPZ interface and the directed polymer in a random potential at high temperature. This allows us to observe the optimal paths, which determine each of the two tails of P(H,t), down to probability densities as small as 10^{-500}. At short times we observe mirror-symmetry-broken traveling optimal paths for the upper tail, and a single mirror-symmetric path for the lower tail, in good quantitative agreement with analytical predictions. At long times, even at moderate values of H, where the optimal fluctuation method is not supposed to apply, we still observe two well-defined dominating paths. Each of them violates the mirror symmetry xâ-x and is a mirror image of the other.

*Phys Rev E ; 104(4-1): 044105, 2021 Oct.*

##### RESUMO

We study a phase transition in parameter learning of hidden Markov models (HMMs). We do this by generating sequences of observed symbols from given discrete HMMs with uniformly distributed transition probabilities and a noise level encoded in the output probabilities. We apply the Baum-Welch (BW) algorithm, an expectation-maximization algorithm from the field of machine learning. By using the BW algorithm we then try to estimate the parameters of each investigated realization of an HMM. We study HMMs with n=4,8, and 16 states. By changing the amount of accessible learning data and the noise level, we observe a phase-transition-like change in the performance of the learning algorithm. For bigger HMMs and more learning data, the learning behavior improves tremendously below a certain threshold in the noise strength. For a noise level above the threshold, learning is not possible. Furthermore, we use an overlap parameter applied to the results of a maximum a posteriori (Viterbi) algorithm to investigate the accuracy of the hidden state estimation around the phase transition.

*Phys Rev E ; 104(3-1): 034407, 2021 Sep.*

##### RESUMO

For system coupled to heat baths, typical nonequilibrated processes, e.g., induced by varying an external parameter without waiting for equilibration in between, are very different from the corresponding equilibrium infinitely slow processes. Nevertheless, there are connections between equilibrium and nonequilibrated behaviors, e.g., the theorems of Jarzynski and Crooks, which relate the distribution P(W) of nonequilibrium work to the free energy differences ΔF. Here we study the naturally arising question, whether those relevant but rare trajectories, which exhibit these work values, show a higher degree of similarity to equilibrium. For convenience, we have chosen a simple model of RNA secondary structures (or single-stranded DNA), here modeling a medium-size hairpin structure, under influence of a varying external force. This allows us to measure the work W during the resulting fast unfolding and refolding processes within Monte Carlo simulations, i.e., in nonequilibrium. Also we sample numerically efficiently directly in exact equilibrium, for comparison. Using a sophisticated large-deviation algorithm, we are able to measure work distributions with high precision down to probabilities as small as 10^{-46}, enabling us to verify the Crooks and Jarzynski theorems. Furthermore, we analyze force-extension curves and the configurations of the secondary structures during unfolding and refolding for typical equilibrium processes and nonequilibrated processes. We find that the nonequilibrated processes where the work values are close to those which are most relevant for applying Crooks and Jarzynski theorems, respectively, but which occur with exponential small probabilities, are most and quite similar to the equilibrium processes.

*Phys Rev E ; 102(5-1): 052108, 2020 Nov.*

##### RESUMO

We study the stochastic block model, which is often used to model community structures and study community-detection algorithms. We consider the case of two blocks in regard to its largest connected component and largest biconnected component, respectively. We are especially interested in the distributions of their sizes including the tails down to probabilities smaller than 10^{-800}. For this purpose we use sophisticated Markov chain Monte Carlo simulations to sample graphs from the stochastic block model ensemble. We use these data to study the large-deviation rate function and conjecture that the large-deviation principle holds. Further we compare the distribution to the well-known Erdos-Rényi ensemble, where we notice subtle differences at and above the percolation threshold.

*Sci Rep ; 10(1): 17336, 2020 Oct 15.*

##### RESUMO

The determination of the parameters of cylindrical optical waveguides, e.g. the diameters [Formula: see text] of r layers of (semi-) transparent optical fibres, can be executed by inverse evaluation of the scattering intensities that emerge under monochromatic illumination. The inverse problem can be solved by optimising the mismatch [Formula: see text] between the measured and simulated scattering patterns. The global optimum corresponds to the correct parameter values. The mismatch [Formula: see text] can be seen as an energy landscape as a function of the diameters. In this work, we study the structure of the energy landscape for different values of the complex refractive indices [Formula: see text], for [Formula: see text] and [Formula: see text] layers. We find that for both values of r, depending on the values of [Formula: see text], two very different types of energy landscapes exist, respectively. One type is dominated by one global minimum and the other type exhibits a multitude of local minima. From an algorithmic viewpoint, this corresponds to easy and hard phases, respectively. Our results indicate that the two phases are separated by sharp phase-transition lines and that the shape of these lines can be described by one "critical" exponent b, which depends slightly on r. Interestingly, the same exponent also describes the dependence of the number of local minima on the diameters. Thus, our findings are comparable to previous theoretical studies on easy-hard transitions in basic combinatorial optimisation or decision problems like Travelling Salesperson and Satisfiability. To our knowledge our results are the first indicating the existence of easy-hard transitions for a real-world optimisation problem of technological relevance.

*Phys Rev E ; 102(1-1): 012131, 2020 Jul.*

##### RESUMO

We apply generalizations of the Swendson-Wang and Wolff cluster algorithms, which are based on the construction of Fortuin-Kasteleyn clusters, to the three-dimensional ±1 random-bond Ising model. The behavior of the model is determined by the temperature T and the concentration p of negative (antiferromagnetic) bonds. The ground state is ferromagnetic for 0≤p

*Phys Rev E ; 101(6-1): 062109, 2020 Jun.*

##### RESUMO

We study the entropy S of longest increasing subsequences (LISs), i.e., the logarithm of the number of distinct LISs. We consider two ensembles of sequences, namely, random permutations of integers and sequences drawn independent and identically distributed (i.i.d.) from a limited number of distinct integers. Using sophisticated algorithms, we are able to exactly count the number of LISs for each given sequence. Furthermore, we are not only measuring averages and variances for the considered ensembles of sequences, but we sample very large parts of the probability distribution p(S) with very high precision. Especially, we are able to observe the tails of extremely rare events which occur with probabilities smaller than 10^{-600}. We show that the distribution of the entropy of the LISs is approximately Gaussian with deviations in the far tails, which might vanish in the limit of long sequences. Further, we propose a large-deviation rate function which fits best to our observed data.

*Phys Rev E ; 101(3-1): 032102, 2020 Mar.*

##### RESUMO

We numerically estimate the leading asymptotic behavior of the length L_{n} of the longest increasing subsequence of random walks with step increments following Student's t-distribution with parameters in the range 1/2≤ν≤5. We find that the expected value E(L_{n})â¼n^{Î¸}lnn, with Î¸ decreasing from Î¸(ν=1/2)≈0.70 to Î¸(ν≥5/2)≈0.50. For random walks with a distribution of step increments of finite variance (ν>2), this confirms previous observation of E(L_{n})â¼sqrt[n]lnn to leading order. We note that this asymptotic behavior (including the subleading term) resembles that of the largest part of random integer partitions under the uniform measure and that, curiously, both random variables seem to follow Gumbel statistics. We also provide more refined estimates for the asymptotic behavior of E(L_{n}) for random walks with step increments of finite variance.

*Phys Rev E ; 101(1-1): 012134, 2020 Jan.*

##### RESUMO

The one-point distribution of the height for the continuum Kardar-Parisi-Zhang equation is determined numerically using the mapping to the directed polymer in a random potential at high temperature. Using an importance sampling approach, the distribution is obtained over a large range of values, down to a probability density as small as 10^{-1000} in the tails. The short-time behavior is investigated and compared with recent analytical predictions for the large-deviation forms of the probability of rare fluctuations, showing a spectacular agreement with the analytical expressions. The flat and stationary initial conditions are studied in the full space, together with the droplet initial condition in the half-space.

*Phys Rev E ; 102(6-1): 062141, 2020 Dec.*

##### RESUMO

We study an agent-based model of animals marking their territory and evading adversarial territory in one dimension with respect to the distribution of the size of the resulting territories. In particular, we use sophisticated sampling methods to determine it over a large part of territory sizes, including atypically small and large configurations, which occur with probability of less than 10^{-30}. We find hints for the validity of a large deviation principle, the shape of the rate function for the right tail of the distribution, and insight into the structure of atypical realizations.

*Chaos ; 29(11): 113103, 2019 Nov.*

##### RESUMO

Energy grids play an important role in modern society. In recent years, there was a shift from using few central power sources to using many small power sources, due to efforts to increase the percentage of renewable energies. Therefore, the properties of extremely stable and unstable networks are of interest. In this paper, distributions of the basin stability, a nonlinear measure to quantify the ability of a power grid to recover from perturbations, and its correlations with other measurable quantities, namely, diameter, flow backup capacity, power-sign ratio, universal order parameter, biconnected component, clustering coefficient, two core, and leafs, are studied. The energy grids are modeled by an Erdos-Rényi random graph ensemble and a small-world graph ensemble, where the latter is defined in such a way that it does not exhibit dead ends. Using large-deviation techniques, we reach very improbable power grids that are extremely stable as well as ones that are extremely unstable. The 1/t-algorithm, a variation of Wang-Landau, which does not suffer from error saturation, and additional entropic sampling are used to achieve good precision even for very small probabilities ranging over eight decades.

*Phys Rev E ; 100(3-1): 032135, 2019 Sep.*

##### RESUMO

We study the energy landscape of the traveling salesperson problem (TSP) using exact ground states and a novel linear programming approach to generate excited states with closely defined properties. We look at four different ensembles, notably the classic finite dimensional Euclidean TSP and the mean-field-like (1,2)-TSP, which has its origin directly in the mapping of the Hamiltonian circuit problem on the TSP. Our data supports previous conjectures that the Euclidean TSP does not show signatures of replica symmetry breaking neither in two nor in higher dimension. On the other hand the (1,2)-TSP exhibits some signature which does not exclude broken replica symmetry, making it a candidate for further studies in the future.

*Phys Rev E ; 99(4-1): 042104, 2019 Apr.*

##### RESUMO

We study numerically the length distribution of the longest increasing subsequence (LIS) for random permutations and one-dimensional random walks. Using sophisticated large-deviation algorithms, we are able to obtain very large parts of the distribution, especially also covering probabilities smaller than 10^{-1000}. This enables us to verify for the length of the LIS of random permutations the analytically known asymptotics of the rate function and even the whole Tracy-Widom distribution. We observe a rather fast convergence in the larger than typical part to this limiting distribution. For the length L of LIS of random walks no analytical results are known to us. We test a proposed scaling law and observe convergence of the tails into a collapse for increasing system size. Further, we obtain estimates for the leading-order behavior of the rate functions in both tails.

*PLoS One ; 14(4): e0215309, 2019.*

##### RESUMO

Here we study linear programming applied to the random K-SAT problem, a fundamental problem in computational complexity. The K-SAT problem is to decide whether a Boolean formula with N variables and structured as a conjunction of M clauses, each being a disjunction of K variables or their negations is satisfiable or not. The ensemble of random K-SAT attracted considerable interest from physicists because for a specific ratio αs = M/N it undergoes in the limit of large N a sharp phase transition from a satisfiable to an unsatisfiable phase. In this study we will concentrate on finding for linear programming algorithms "easy-hard" transitions between phases of different typical hardness of the problems on either side. Linear programming is widely applied to solve practical optimization problems, but has been only rarely considered in the physics community. This is a deficit, because those typically studied types of algorithms work in the space of feasible {0, 1}N configurations while linear programming operates outside the space of valid configurations hence gives a very different perspective on the typical-case hardness of a problem. Here, we demonstrate that the technique leads to one simple-to-understand transition for the well known 2-SAT problem. On the other hand we detect multiple transitions in 3-SAT and 4-SAT. We demonstrate that, in contrast to the previous work on vertex cover and therefore somewhat surprisingly, the hardness transitions are not driven by changes of any of various standard percolation or solution space properties of the problem instances. Thus, here a more complex yet undetected property must be related to the easy-hard transition.

##### Assuntos

Algoritmos , Modelos Teóricos , Transição de Fase , Programação Linear , Simulação por Computador*Phys Rev E ; 100(6-1): 062301, 2019 Dec.*

##### RESUMO

We have studied the distribution of traffic flow q for the Nagel-Schreckenberg model by computer simulations. We applied a large-deviation approach, which allowed us to obtain the distribution P(q) over more than one hundred decades in probability, down to probabilities like 10^{-140}. This allowed us to characterize the flow distribution over a large range of the support and identify the characteristics of rare and even very rare traffic situations. We observe a change of the distribution shape when increasing the density of cars from the free flow to the congestion phase. Furthermore, we characterize typical and rare traffic situations by measuring correlations of q to other quantities like density of standing cars or number and size of traffic jams.

*Entropy (Basel) ; 21(2)2019 Feb 18.*

##### RESUMO

Spin glasses are prototypical random systems modelling magnetic alloys. One important way to investigate spin glass models is to study domain walls. For two dimensions, this can be algorithmically understood as the calculation of a shortest path, which allows for negative distances or weights. This led to the creation of the negative weight percolation (NWP) model, which is presented here along with all necessary basics from spin glasses, graph theory and corresponding algorithms. The algorithmic approach involves a mapping to the classical matching problem for graphs. In addition, a summary of results is given, which were obtained during the past decade. This includes the study of percolation transitions in dimension from d = 2 up to and beyond the upper critical dimension d u = 6 , also for random graphs. It is shown that NWP is in a different universality class than standard percolation. Furthermore, the question of whether NWP exhibits properties of Stochastic-Loewner Evolution is addressed and recent results for directed NWP are presented.

*Phys Rev E ; 98(1-1): 012301, 2018 Jul.*

##### RESUMO

Networks that are fragmented into small disconnected components are prevalent in a large variety of systems. These include the secure communication networks of commercial enterprises, government agencies, and illicit organizations, as well as networks that suffered multiple failures, attacks, or epidemics. The structural and statistical properties of such networks resemble those of subcritical random networks, which consist of finite components, whose sizes are nonextensive. Surprisingly, such networks do not exhibit the small-world property that is typical in supercritical random networks, where the mean distance between pairs of nodes scales logarithmically with the network size. Unlike supercritical networks whose structure has been studied extensively, subcritical networks have attracted relatively little attention. A special feature of these networks is that the statistical and geometric properties vary between different components and depend on their sizes and topologies. The overall statistics of the network can be obtained by a summation over all the components with suitable weights. We use a topological expansion to perform a systematic analysis of the degree distribution and the distribution of shortest path lengths (DSPL) on components of given sizes and topologies in subcritical Erdos-Rényi (ER) networks. From this expansion we obtain an exact analytical expression for the DSPL of the entire subcritical network, in the asymptotic limit. The DSPL, which accounts for all the pairs of nodes that reside on the same finite component (FC), is found to follow a geometric distribution of the form P_{FC}(L=â|L<∞)=(1-c)c^{â-1}, where c<1 is the mean degree. Using computer simulations we calculate the DSPL in subcritical ER networks of increasing sizes and confirm the convergence to this asymptotic result. We also obtain exact asymptotic results for the mean distance, ãLã_{FC}, and for the standard deviation of the DSPL, σ_{L,FC}, and show that the simulation results converge to these asymptotic results. Using the duality relations between subcritical and supercritical ER networks, we obtain the DSPL on the nongiant components of ER networks above the percolation transition.

*Phys Rev E ; 98(1-1): 012108, 2018 Jul.*

##### RESUMO

Here we study the two-dimensional Kaya-Berker model, with a site occupancy p of one sublattice, by using a polynomial-time exact ground-state algorithm. Thus, we were able to obtain T=0 results in exact equilibrium for rather large system sizes up to 777^{2} lattice sites. We obtained the sublattice magnetization and the corresponding Binder parameter. We found a critical point p_{c}=0.64(1) beyond which the sublattice magnetization vanishes. This is clearly smaller than previous results which were obtained by using nonexact approaches for much smaller systems. For each realization we also created minimum-energy domain walls from two ground-state calculations, for periodic and antiperiodic boundary conditions. The analysis of the mean and the variance of the domain-wall energy shows that there is no thermodynamic stable spin-glass phase at nonzero temperature, in contrast to previous claims about this model. For large values of p, the standard deviation of the domain-wall decreases with the system size like a power law with exponent roughly Î¸≃-0.1, which is different from the standard two-dimensional Ising spin glass where Î¸≃-0.29.

*Phys Rev E ; 97(6-1): 062159, 2018 Jun.*

##### RESUMO

A global picture of a random particle movement is given by the convex hull of the visited points. We obtained numerically the probability distributions of the volume and surface of the convex hulls of a selection of three types of self-avoiding random walks, namely, the classical self-avoiding walk, the smart-kinetic self-avoiding walk, and the loop-erased random walk. To obtain a comprehensive description of the measured random quantities, we applied sophisticated large-deviation techniques, which allowed us to obtain the distributions over a large range of support down to probabilities far smaller than P=10^{-100}. We give an approximate closed form of the so-called large-deviation rate function Φ which generalizes above the upper critical dimension to the previously studied case of the standard random walk. Further, we show correlations between the two observables also in the limits of atypical large or small values.