Four-tap shift-register-sequence random-number generators

Postprocessing techniques for gradient percolation predictions on the square lattice

In this work, we revisit the classic problem of site percolation on a regular square lattice. In particular, we investigate the effect of quantization bias errors on percolation threshold predictions for large probability gradients and propose a mitigation strategy. We demonstrate through extensive computational experiments that the assumption of a linear relationship between probability gradient and percolation threshold used in previous investigations is invalid. Moreover, we demonstrate that, due to skewness in the distribution of occupation probabilities visited the average does not converge monotonically to the true percolation threshold. We identify several alternative metrics which do exhibit monotonic (albeit not linear) convergence and document their observed convergence rates.

How fast does a random walk cover a torus?

We present high statistics simulation data for the average time 〈T_{cover}(L)〉 that a random walk needs to cover completely a two-dimensional torus of size L×L. They confirm the mathematical prediction that 〈T_{cover}(L)〉∼(LlnL)^{2} for large L, but the prefactor seems to deviate significantly from the supposedly exact result 4/π derived by Dembo et al. [Ann. Math. 160, 433 (2004)ANMAAH0003-486X10.4007/annals.2004.160.433], if the most straightforward extrapolation is used. On the other hand, we find that this scaling does hold for the time T_{N(t)=1}(L) at which the average number of yet unvisited sites is 1, as also predicted previously. This might suggest (wrongly) that 〈T_{cover}(L)〉 and T_{N(t)=1}(L) scale differently, although the distribution of rescaled cover times becomes sharp in the limit L→∞. But our results can be reconciled with those of Dembo et al. by a very slow and nonmonotonic convergence of 〈T_{cover}(L)〉/(LlnL)^{2}, as had been indeed proven by Belius et al. [Probab. Theory Relat. Fields 167, 461 (2017)10.1007/s00440-015-0689-6] for Brownian walks, and was conjectured by them to hold also for lattice walks.

Critical Fragmentation Properties of Random Drilling: How Many Holes Need to Be Drilled to Collapse a Wooden Cube?

A solid wooden cube fragments into pieces as we sequentially drill holes through it randomly. This seemingly straightforward observation encompasses deep and nontrivial geometrical and probabilistic behavior that is discussed here. Combining numerical simulations and rigorous results, we find off-critical scale-free behavior and a continuous transition at a critical density of holes that significantly differs from classical percolation.

Dimer covering and percolation frustration

Covering a graph or a lattice with nonoverlapping dimers is a problem that has received considerable interest in areas, such as discrete mathematics, statistical physics, chemistry, and materials science. Yet, the problem of percolation on dimer-covered lattices has received little attention. In particular, percolation on lattices that are fully covered by nonoverlapping dimers has not evidently been considered. Here, we propose a procedure for generating random dimer coverings of a given lattice. We then compute the bond percolation threshold on random and ordered coverings of the square and the triangular lattices on the remaining bonds connecting the dimers. We obtain p_{c}=0.367713(2) and p_{c}=0.235340(1) for random coverings of the square and the triangular lattices, respectively. We observe that the percolation frustration induced as a result of dimer covering is larger in the low-coordination-number square lattice. There is also no relationship between the existence of long-range order in a covering of the square lattice and its percolation threshold. In particular, an ordered covering of the square lattice, denoted by shifted covering in this paper, has an unusually low percolation threshold and is topologically identical to the triangular lattice. This is in contrast to the other ordered dimer coverings considered in this paper, which have higher percolation thresholds than the random covering. In the case of the triangular lattice, the percolation thresholds of the ordered and random coverings are very close, suggesting the lack of sensitivity of the percolation threshold to microscopic details of the covering in highly coordinated networks.

Retention capacity of correlated surfaces

We extend the water retention model [C. L. Knecht et al., Phys. Rev. Lett. 108, 045703 (2012)] to correlated random surfaces. We find that the retention capacity of discrete random landscapes is strongly affected by spatial correlations among the heights. This phenomenon is related to the emergence of power-law scaling in the lake volume distribution. We also solve the uncorrelated case exactly for a small lattice and present bounds on the retention of uncorrelated landscapes.

How to share underground reservoirs

Many resources, such as oil, gas, or water, are extracted from porous soils and their exploration is often shared among different companies or nations. We show that the effective shares can be obtained by invading the porous medium simultaneously with various fluids. Partitioning a volume in two parts requires one division surface while the simultaneous boundary between three parts consists of lines. We identify and characterize these lines, showing that they form a fractal set consisting of a single thread spanning the medium and a surrounding cloud of loops. While the spanning thread has fractal dimension 1.55 ± 0.03, the set of all lines has dimension 1.69 ± 0.02. The size distribution of the loops follows a power law and the evolution of the set of lines exhibits a tricritical point described by a crossover with a negative dimension at criticality.

Bohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition

The BFW model introduced by Bohman, Frieze, and Wormald [Random Struct. Algorithms, 25, 432 (2004)], and recently investigated in the framework of discontinuous percolation by Chen and D'Souza [Phys. Rev. Lett. 106, 115701 (2011)], is studied on the square and simple-cubic lattices. In two and three dimensions, we find numerical evidence for a strongly discontinuous transition. In two dimensions, the clusters at the threshold are compact with a fractal surface of fractal dimension d(f)=1.49±0.02. On the simple-cubic lattice, distinct jumps in the size of the largest cluster are observed. We proceed to analyze the tree-like version of the model, where only merging bonds are sampled, for dimension two to seven. The transition is again discontinuous in any considered dimension. Finally, the dependence of the cluster-size distribution at the threshold on the spatial dimension is also investigated.

Gaussian model of explosive percolation in three and higher dimensions

The Gaussian model of discontinuous percolation, recently introduced by Araújo and Herrmann [Phys. Rev. Lett. 105, 035701 (2010)], is numerically investigated in three dimensions, disclosing a discontinuous transition. For the simple cubic lattice, in the thermodynamic limit we report a finite jump of the order parameter J=0.415±0.005. The largest cluster at the threshold is compact, but its external perimeter is fractal with fractal dimension d(A)=2.5±0.2. The study is extended to hypercubic lattices up to six dimensions and to the mean-field limit (infinite dimension). We find that, in all considered dimensions, the percolation transition is discontinuous. The value of the jump in the order parameter, the maximum of the second moment, and the percolation threshold are analyzed, revealing interesting features of the transition and corroborating its discontinuous nature in all considered dimensions. We also show that the fractal dimension of the external perimeter, for any dimension, is consistent with the one from bridge percolation and establish a lower bound for the percolation threshold of discontinuous models with a finite number of clusters at the threshold.

Correction-to-scaling exponent for two-dimensional percolation

We show that the correction-to-scaling exponents in two-dimensional percolation are bounded by Ω ≤ 72/91, ω = DΩ ≤ 3/2, and Δ₁ = νω ≤ 2, based upon Cardy's result for the crossing probability on an annulus. The upper bounds are consistent with many previous measurements of site percolation on square and triangular lattices and new measurements for bond percolation, suggesting that they are exact. They also agree with exponents for hulls proposed recently by Aharony and Asikainen, based upon results of den Nijs. A corrections scaling form evidently applicable to site percolation is also found.

Critical behavior of the susceptible-infected-recovered model on a square lattice

By means of numerical simulations and epidemic analysis, the transition point of the stochastic asynchronous susceptible-infected-recovered model on a square lattice is found to be c0=0.1765005(10), where c is the probability a chosen infected site spontaneously recovers rather than tries to infect one neighbor. This point corresponds to an infection/recovery rate of λ(c)=(1-c0)/c0=4.665 71(3) and a net transmissibility of (1-c0)/(1+3c0)=0.538 410(2), which falls between the rigorous bounds of the site and bond thresholds. The critical behavior of the model is consistent with the two-dimensional percolation universality class, but local growth probabilities differ from those of dynamic percolation cluster growth, as is demonstrated explicitly.

Percolation in networks with voids and bottlenecks

A general method is proposed for predicting the asymptotic percolation threshold of networks with bottlenecks, in the limit that the subnet mesh size goes to zero. The validity of this method is tested for bond percolation on filled checkerboard and "stack-of-triangle" lattices. Thresholds for the checkerboard lattices of different mesh sizes are estimated using the gradient percolation method, while for the triangular system they are found exactly using the triangle-triangle transformation. The values of the thresholds approach the asymptotic values of 0.64222 and 0.53993, respectively, as the mesh is made finer, consistent with a direct determination based upon the predicted critical corner-connection probability.

Pseudo-random-number generators and the square site percolation threshold

Selected pseudo-random-number generators are applied to a Monte Carlo study of the two-dimensional square-lattice site percolation model. A generator suitable for high precision calculations is identified from an application specific test of randomness. After extended computation and analysis, an ostensibly reliable value of p_{c}=0.59274598(4) is obtained for the percolation threshold.

Random numbers for large-scale distributed Monte Carlo simulations

Monte Carlo simulations are one of the major tools in statistical physics, complex system science, and other fields, and an increasing number of these simulations is run on distributed systems like clusters or grids. This raises the issue of generating random numbers in a parallel, distributed environment. In this contribution we demonstrate that multiple linear recurrences in finite fields are an ideal method to produce high quality pseudorandom numbers in sequential and parallel algorithms. Their known weakness (failure of sampling points in high dimensions) can be overcome by an appropriate delinearization that preserves all desirable properties of the underlying linear sequence.

Modeling 2D and 3D diffusion

Modeling obstructed diffusion is essential to the understanding of diffusion-mediated processes in the crowded cellular environment. Simple Monte Carlo techniques for modeling obstructed random walks are explained and related to Brownian dynamics and more complicated Monte Carlo methods. Random number generation is reviewed in the context of random walk simulations. Programming techniques and event-driven algorithms are discussed as ways to speed simulations.

Tails of the crossing probability

The scaling of the tails of the probability of a system to percolate only in the horizontal direction pi(hs) was investigated numerically for the correlated site-bond percolation model (q -state Potts model) for q=1 , 2, 3, 4 (where q is the number of spin states). We have to demonstrate that the crossing probability pi(hs) (p) far from the critical point p(c) has the shape pi(hs) (p) similar to D exp [cL (p- p(c) )(nu) ] where nu is the correlation length index, and p=1-exp (-beta) is the probability of a bond to be closed. For the tail region the correlation length is smaller than the lattice size. At criticality the correlation length reaches the sample size and we observe crossover to another scaling pi(hs) (p) similar to A exp {-b [L (p- p(c) )(nu)](x)}. Here x is a scaling index describing the central part of the crossing probability.

Entropy of pseudo-random-number generators

Since the work of Phys. Rev. Lett. 69, 3382 (1992)]] some pseudo-random-number generators are known to yield wrong results in cluster Monte Carlo simulations. In this contribution the fundamental mechanism behind this failure is discussed. Almost all random-number generators calculate a new pseudo-random-number x(i) from preceding values, x(i) =f( x(i-1), x(i-2), ..., x(i-q) ). Failure of these generators in cluster Monte Carlo simulations and related experiments can be attributed to the low entropy of the production rule f() conditioned on the statistics of the input values x(i-1), ..., x(i-q). Being a measure only of the arithmetic operations in the generator rule, the conditional entropy is independent of the lag in the recurrence or the period of the sequence. In that sense it measures a more profound quality of a random-number generator than empirical tests with their limited horizon.

Critical percolation in high dimensions

We present Monte Carlo estimates for site and bond percolation thresholds in simple hypercubic lattices with 4-13 dimensions. For d<6 they are preliminary, for d>or =6 they are between 20 and 10(4) times more precise than the best previous estimates. This was achieved by three ingredients: (i) simple and fast hashing that allowed us to simulate clusters of millions of sites on computers with less than 500 Mbytes memory; (ii) a histogram method that allowed us to obtain information for several p values from a single simulation; and (iii) a variance reduction technique that is especially efficient at high dimensions where it reduces error bars by a factor of up to approximately 30 and more. Based on these data we propose a scaling law for finite cluster size corrections.

Geometric random inner products: a family of tests for random number generators

We present a computational scheme, GRIP (geometric random inner products), for testing the quality of random number generators. The GRIP formalism utilizes geometric probability techniques to calculate the average scalar products of random vectors distributed in geometric objects, such as circles and spheres. We show that these average scalar products define a family of geometric constants which can be used to evaluate the quality of random number generators. We explicitly apply the GRIP tests to several random number generators frequently used in Monte Carlo simulations, and demonstrate a statistical property for good random number generators.

Convergence of threshold estimates for two-dimensional percolation

Using a recently introduced algorithm for simulating percolation in microcanonical (fixed-occupancy) samples, we study the convergence with increasing system size of a number of estimates for the percolation threshold for an open system with a square boundary, specifically for site percolation on a square lattice. We show that the convergence of the average-probability estimate is described by a nontrivial correction-to-scaling exponent as predicted previously, and measure the value of this exponent to be 0.90+/-0.02. For the median and cell-to-cell estimates of the percolation threshold we verify that convergence does not depend on this exponent, having instead a slightly faster convergence with a trivial analytic leading exponent.

Critical amplitude ratio of the susceptibility in the random-site two-dimensional Ising model

We present a different way of probing the universality class of the site-diluted two-dimensional Ising model. We analyze Monte Carlo data for the magnetic susceptibility, introducing a fitting procedure in the critical region applicable even for a single sample with quenched disorder. This gives us the possibility to fit simultaneously the critical exponent, the critical amplitude, and the sample-dependent pseudocritical temperature. The critical amplitude ratio of the magnetic susceptibility is seen to be independent of the concentration q of the empty sites for all investigated values of q < or =0.25. At the same time the average effective exponent gamma(eff) is found to vary with the concentration q, which may be argued to be due to logarithmic corrections to the power law of the pure system. These corrections are canceled in the susceptibility amplitude ratio as predicted by theory. The central charge of the corresponding field theory was computed and compared well with the theoretical predictions.

Percolation threshold, Fisher exponent, and shortest path exponent for four and five dimensions

We develop a method of constructing percolation clusters that allows us to build very large clusters using very little computer memory by limiting the maximum number of sites for which we maintain state information to a number of the order of the number of sites in the largest chemical shell of the cluster being created. The memory required to grow a cluster of mass s is of the order of s(straight theta) bytes where straight theta ranges from 0.4 for two-dimensional (2D) lattices to 0.5 for six (or higher)-dimensional lattices. We use this method to estimate d(min), the exponent relating the minimum path l to the Euclidean distance r, for 4D and 5D hypercubic lattices. Analyzing both site and bond percolation, we find d(min)=1.607+/-0.005 (4D) and d(min)=1.812+/-0.006 (5D). In order to determine d(min) to high precision, and without bias, it was necessary to first find precise values for the percolation threshold, p(c): p(c)=0.196889+/-0.000003 (4D) and p(c)=0.14081+/-0.00001 (5D) for site and p(c)=0.160130+/-0.000003 (4D) and p(c)=0.118174+/-0.000004 (5D) for bond percolation. We also calculate the Fisher exponent tau determined in the course of calculating the values of p(c): tau=2.313+/-0.003 (4D) and tau=2.412+/-0.004 (5D).

Largest cluster in subcritical percolation

The statistical behavior of the size (or mass) of the largest cluster in subcritical percolation on a finite lattice of size N is investigated (below the upper critical dimension, presumably d(c)=6). It is argued that as N-->infinity the cumulative distribution function converges to the Fisher-Tippett (or Gumbel) distribution e(-e(-z)) in a certain weak sense (when suitably normalized). The mean grows as s(*)(xi) log N, where s(*)(xi)(p) is a "crossover size. " The standard deviation is bounded near s(*)(xi)pi/sqrt[6] with persistent fluctuations due to discreteness. These predictions are verified by Monte Carlo simulations on d=2 square lattices of up to 30 million sites, which also reveal finite-size scaling. The results are explained in terms of a flow in the space of probability distributions as N-->infinity. The subcritical segment of the physical manifold (0<p<p(c)) approaches a line of limit cycles where the flow is approximately described by a "renormalization group" from the classical theory of extreme order statistics.

Site percolation thresholds for Archimedean lattices

Precise thresholds for site percolation on eight Archimedean lattices are determined by the hull-walk gradient-percolation simulation method, with the results p(c)=0.697 043, honeycomb or (6(3)), 0.807 904 (3,12(2)), 0.747 806 (4,6,12), 0.729 724 (4,8(2)), 0.579 498 (3(4),6), 0.621 819 (3,4,6,4), 0.550 213 (3(3),4(2)), and 0.550 806 (3(2),4,3,4), with errors of about +/- 3 x 10(-6). [The remaining Archimedean lattices are the square (4(4)), triangular (3(6)), and Kagomé (3,6,3,6), for which p(c) is already known exactly or to a high degree of accuracy.] The numerical result for the (3,12(2)) lattice is consistent with the exact value [1-2 sin(pi/18)](1/2). The values of p(c) for all 11 Archimedean lattices, as well as a number of nonuniform lattices, are found to be well correlated by a nearly linear function of a generalized Scher-Zallen filling factor. This correlation is much more accurate than recently proposed correlations based solely upon coordination number.

Framework for testing random numbers in parallel calculations

We propose a framework for testing the quality of random numbers in parallel calculations. The key idea is to study cross-correlations between distinct sequences of random numbers via correlations between various diffusing random walkers, each of which is governed by a distinct random number sequence. The asymptotic power-law behavior of the corresponding correlation functions yields exponents, which can be compared with exact theoretical results. Correlations prior to the asymptotic regime can be further investigated by other complementary methods. We demonstrate this approach by three efficient tests, which find correlations in various commonly used pseudorandom number generators. Finally, we discuss some ideas for applying this framework in other contexts.