In this work we consider information-theoretical observables to analyze short symbolic sequences, comprising time-series that represent the orientation of a single spin in a $2D$ Ising ferromagnet on a square lattice of size $L^2=128^2$, for differen
t system temperatures $T$. The latter were chosen from an interval enclosing the critical point $T_{rm c}$ of the model. At small temperatures the sequences are thus very regular, at high temperatures they are maximally random. In the vicinity of the critical point, nontrivial, long-range correlations appear. Here, we implement estimators for the entropy rate, excess entropy (i.e. complexity) and multi-information. First, we implement a Lempel-Ziv string parsing scheme, providing seemingly elaborate entropy rate and multi-information estimates and an approximate estimator for the excess entropy. Furthermore, we apply easy-to-use black-box data compression utilities, providing approximate estimators only. For comparison and to yield results for benchmarking purposes we implement the information-theoretic observables also based on the well-established M-block Shannon entropy, which is more tedious to apply compared to the the first two algorithmic entropy estimation procedures. To test how well one can exploit the potential of such data compression techniques, we aim at detecting the critical point of the $2D$ Ising ferromagnet. Among the above observables, the multi-information, which is known to exhibit an isolated peak at the critical point, is very easy to replicate by means of both efficient algorithmic entropy estimation procedures. Finally, we assess how good the various algorithmic entropy estimates compare to the more conventional block entropy estimates and illustrate a simple modification that yields enhanced results.
The principle characteristics of biased greedy random walks (BGRWs) on two-dimensional lattices with real-valued quenched disorder on the lattice edges are studied. Here, the disorder allows for negative edge-weights. In previous studies, considering
the negative-weight percolation (NWP) problem, this was shown to change the universality class of the existing, static percolation transition. In the presented study, four different types of BGRWs and an algorithm based on the ant colony optimization (ACO) heuristic were considered. Regarding the BGRWs, the precise configurations of the lattice walks constructed during the numerical simulations were influenced by two parameters: a disorder parameter rho that controls the amount of negative edge weights on the lattice and a bias strength B that governs the drift of the walkers along a certain lattice direction. Here, the pivotal observable is the probability that, after termination, a lattice walk exhibits a total negative weight, which is here considered as percolating. The behavior of this observable as function of rho for different bias strengths B is put under scrutiny. Upon tuning rho, the probability to find such a feasible lattice walk increases from zero to one. This is the key feature of the percolation transition in the NWP model. Here, we address the question how well the transition point rho_c, resulting from numerically exact and static simulations in terms of the NWP model can be resolved using simple dynamic algorithms that have only local information available, one of the basic questions in the physics of glassy systems.
We perform numerical simulations to study the optimal path problem on disordered hierarchical graphs with effective dimension d=2.32. Therein, edge energies are drawn from a disorder distribution that allows for positive and negative energies. This i
nduces a behavior which is fundamentally different from the case where all energies are positive, only. Upon changing the subtleties of the distribution, the scaling of the minimum energy path length exhibits a transition from self-affine to self-similar. We analyze the precise scaling of the path length and the associated ground-state energy fluctuations in the vincinity of the disorder critical point, using a decimation procedure for huge graphs. Further, using an importance sampling procedure in the disorder we compute the negative-energy tails of the ground-state energy distribution up to 12 standard deviations away from its mean. We find that the asymptotic behavior of the negative-energy tail is in agreement with a Tracy-Widom distribution. Further, the characteristic scaling of the tail can be related to the ground-state energy flucutations, similar as for the directed polymer in a random medium.
The information theoretic observables entropy (a measure of disorder), excess entropy (a measure of complexity) and multi information are used to analyze ground-state spin configurations for disordered and frustrated model systems in 2D and 3D. For b
oth model systems, ground-state spin configurations can be obtained in polynomial time via exact combinatorial optimization algorithms, which allowed us to study large systems with high numerical accuracy. Both model systems exhibit a continuous transition from an ordered to a disordered ground state as a model parameter is varied. By using the above information theoretic observables it is possible to detect changes in the spatial structure of the ground states as the critical point is approached. It is further possible to quantify the scaling behavior of the information theoretic observables in the vicinity of the critical point. For both model systems considered, the estimates of critical properties for the ground-state phase transitions are in good agreement with existing results reported in the literature.
We consider the negative weight percolation (NWP) problem on hypercubic lattice graphs with fully periodic boundary conditions in all relevant dimensions from d=2 to the upper critical dimension d=6. The problem exhibits edge weights drawn from disor
der distributions that allow for weights of either sign. We are interested in in the full ensemble of loops with negative weight, i.e. non-trivial (system spanning) loops as well as topologically trivial (small) loops. The NWP phenomenon refers to the disorder driven proliferation of system spanning loops of total negative weight. While previous studies where focused on the latter loops, we here put under scrutiny the ensemble of small loops. Our aim is to characterize -using this extensive and exhaustive numerical study- the loop length distribution of the small loops right at and below the critical point of the hypercubic setups by means of two independent critical exponents. These can further be related to the results of previous finite-size scaling analyses carried out for the system spanning loops. For the numerical simulations we employed a mapping of the NWP model to a combinatorial optimization problem that can be solved exactly by using sophisticated matching algorithms. This allowed us to study here numerically exact very large systems with high statistics.
We present a numerical analysis of the entropy rate and statistical complexity related to the spin flip dynamics of the 2D Ising Ferromagnet at different temperatures T. We follow an information theoretic approach and test three different entropy est
imation algorithms to asses entropy rate and statistical complexity of binary sequences. The latter are obtained by monitoring the orientation of a single spin on a square lattice of side-length L=256 at a given temperature parameter over time. The different entropy estimation procedures are based on the M-block Shannon entropy (a well established method that yields results for benchmarking purposes), non-sequential recursive pair substitution (providing an elaborate and an approximate estimator) and a convenient data compression algorithm contained in the zlib-library (providing an approximate estimator only). We propose an approximate measure of statistical complexity that emphasizes on correlations within the sequence and which is easy to implement, even by means of black-box data compression algorithms. Regarding the 2D Ising Ferromagnet simulated using Metropolis dynamics and for binary sequences of finite length, the proposed approximate complexity measure is peaked close to the critical temperature. For the approximate estimators, a finite-size scaling analysis reveals that the peak approaches the critical temperature as the sequence length increases. Results obtained using different spin-flip dynamics are briefly discussed. The suggested complexity measure can be extended to non-binary sequences in a straightforward manner.
We study numerically the geometrical properties of minimally weighted paths that appear in the negative-weight percolation (NWP) model on two-dimensional lattices assuming a combination of periodic and free boundary conditions (BCs). Each realization
of the disorder consists of a random fraction 1-rho of bonds with unit strength and a fraction rho of bond strengths drawn from a Gaussian distribution with zero mean and unit width. For each such sample, the path is forced to span the lattice along the direction with the free BCs. The path and a set of negatively weighted loops form a ground state (GS). A ground state on such a lattice can be determined performing a non-trivial transformation of the original graph and applying sophisticated matching algorithms. Here we examine whether the geometrical properties of the paths are in accordance with predictions of Schramm-Loewner evolution (SLE). Measuring the fractal dimension and reviewing Schramms left passage formula indicates that the paths cannot be described in terms of SLE.
We investigate the geometric properties of loops on two-dimensional lattice graphs, where edge weights are drawn from a distribution that allows for positive and negative weights. We are interested in the appearance of spanning loops of total negativ
e weight. The resulting percolation problem is fundamentally different from conventional percolation, as we have seen in a previous study of this model for the undiluted case. Here, we investigate how the percolation transition is affected by additional dilution. We consider two types of dilution: either a certain fraction of edges exhibit zero weight, or a fraction of edges is even absent. We study these systems numerically using exact combinatorial optimization techniques based on suitable transformations of the graphs and applying matching algorithms. We perform a finite-size scaling analysis to obtain the phase diagram and determine the critical properties of the phase boundary. We find that the first type of dilution does not change the universality class compared to the undiluted case whereas the second type of dilution leads to a change of the universality class.
We investigate the performance of the recently proposed stationary Fokker-Planck sampling method considering a combinatorial optimization problem from statistical physics. The algorithmic procedure relies upon the numerical solution of a linear secon
d order differential equation that depends on a diffusion-like parameter D. We apply it to the problem of finding ground states of 2d Ising spin glasses for the +-J-Model. We consider square lattices with side length up to L=24 with two different types of boundary conditions and compare the results to those obtained by exact methods. A particular value of D is found that yields an optimal performance of the algorithm. We compare this optimal value of D to a percolation transition, which occurs when studying the connected clusters of spins flipped by the algorithm. Nevertheless, even for moderate lattice sizes, the algorithm has more and more problems to find the exact ground states. This means that the approach, at least in its standard form, seems to be inferior to other approaches like parallel tempering.
We describe a percolation problem on lattices (graphs, networks), with edge weights drawn from disorder distributions that allow for weights (or distances) of either sign, i.e. including negative weights. We are interested whether there are spanning
paths or loops of total negative weight. This kind of percolation problem is fundamentally different from conventional percolation problems, e.g. it does not exhibit transitivity, hence no simple definition of clusters, and several spanning paths/loops might coexist in the percolation regime at the same time. Furthermore, to study this percolation problem numerically, one has to perform a non-trivial transformation of the original graph and apply sophisticated matching algorithms. Using this approach, we study the corresponding percolation transitions on large square, hexagonal and cubic lattices for two types of disorder distributions and determine the critical exponents. The results show that negative-weight percolation is in a different universality class compared to conventional bond/site percolation. On the other hand, negative-weight percolation seems to be related to the ferromagnet/spin-glass transition of random-bond Ising systems, at least in two dimensions.
