Random walks on cubic lattices with bond disorder

We consider diffusive systems with static disorder, such as Lorentz gases, lattice percolation, ants in a labyrinth, termite problems, random resistor networks, etc. In the case of diluted randomness we can apply the methods of kinetic theory to obtain systematic expansions of dc and ac transport properties in powers of the impurity concentrationc. The method is applied to a hopping model on ad-dimensional cubic lattice having two types of bonds with conductivity and ₀=1, with concentrationsc and 1–c, respectively. For the square lattice we explicitly calculate the diffusion coefficientD(c,) as a function ofc, to O(c²) terms included for different ratios of the bond conductivity. The probability of return at long times is given byP ₀(t) [4D(c,)t]^–d/2, which is determined by the diffusion coefficient of the disordered system.     

Bond percolation in two and three dimensions: Numerical evaluation of time-dependent transport properties

For random walks on two- and three-dimensional cubic lattices, numerical results are obtained for the static,D(), and time-dependent diffusion coefficientD(t), as well as for the velocity autocorrelation function (VACF). The results cover all times and include linear and quadratic terms in the density expansions. Within the context of kinetic theory this is the only model in two and three dimensions for which the time-dependent transport properties have been calculated explicitly, including the long-time tails.     

Single random walker on disordered lattices

Random walks on square lattice percolating clusters were followed for up to 2×105 steps. The mean number of distinct sites visited (S _N > gives a spectral dimension ofd _s = 1.30±0.03 consistent with superuniversality (d _s =4J3) but closer to the alternatived _s = 182/139, based on the low dimensionality correction. Simulations are also given for walkers on anenergetically disordered lattice, with a jump probability that depends on the local energy mismatch and the temperature. An apparent fractal behavior is observed for a low enough reduced temperature. Above this temperature, the walker exhibits a crossover from fractal-to-Euclidean behavior. Walks on two- and three-dimensional lattices are similar, except that those in three dimensions are more efficient.Supported by NSF Grant No. DMR 8303919 and Nato Grant No. SA 5205 RG 295J82.     

Survival probabilities for random walks on lattices with randomly distributed traps

I present here a numerical procedure to compute survival probabilities for random walks on lattices with randomly distributed traps. The procedure has some advantages over existing methods, and its performance is evaluated for the 1D simple random walk, for which some exact results are known. Thereafter, I apply the procedure to 1D random walks with variable step length and to 3D simple random walks.     

Random walks on a lattice

This paper discusses the mean-square displacement for a random walk on a two-dimensional lattice, whose transitions to nearest-neighbor sites are symmetric in the horizontal and vertical directions and depend on the column currently occupied. Under a uniform density condition for the step probabilities it is shown that the horizontal mean-square displacement aftern steps is asymptotically proportional ton, and independent of the particular column configuration. The model generalizes that of Seshadri, Lindenberg, and Shuler and the arguments are essentially probabilistic.     

A simple calculation for the average number of steps to trapping in lattice random walks

We show that the asymptotic results for the average number of steps to trapping at an irreversible trapping site on aD-dimensional finite lattice can be obtained from the generating function for random walks on aninfinite perfect lattice. This introduces a significant simplification into such calculations. An interesting corollary of these calculations is the conclusion that a random walker traverses, on the average, all the distinct nontrapping lattice sites before arriving on the trapping site.This work was supported in part by NSF Grants MPS72-04363-A03 and CHE75-20624.     

Laplace operator and random walk on one-dimensional nonhomogeneous lattice

A classical result of probability theory states that under suitable space and time renormalization, a random walk converges to Brownian motion. We prove an analogous result in the case of nonhomogeneous random walk on onedimensional lattice. Under suitable conditions on the nonhomogeneous medium, we prove convergence to Brownian motion and explicitly compute the diffusion coefficient. The proofs are based on the study of the spectrum of random matrices of increasing dimension.     

Hamiltonian cycles on random lattices of arbitrary genus

A Hamiltonian cycle of a graph is a closed path that visits every vertex once and only once. It has been difficult to count the number of Hamiltonian cycles on regular lattices with periodic boundary conditions, e.g. lattices on a torus, due to the presence of winding modes. In this paper, the exact number of Hamiltonian cycles on a random trivalent fat graph drawn faithfully on a torus is obtained. This result is further extended to the case of random graphs drawn on surfaces of an arbitrary genus. The conformational exponent y is found to depend on the genus linearly.     

度关联无标度网络上的有倾向随机行走

有倾向随机行走是研究网络上数据包路由策略的有效方法. 由于许多真实技术网络包括互联网都具有负的度关联特征, 因此本文研究这种网络上的有倾向随机行走性质. 研究表明: 在负关联网络上粒子可以在连接度较大的节点上均匀分布, 而连接度小的节点上粒子较少; 负关联网络上随机行走的速度比非关联网络更快; 找到了负关联网络上的最佳倾向性系数, 在此情况下负关联网络上随机行走的速度远快于非关联网络. 负关联网络既可以利用度小的节点容纳粒子, 又可以利用度大的节点快速传输, 这是负关联网络上高行走效率产生的机制.     

Statistical mechanics of random paths on disordered lattices

The dependence of the universality class on the statistical weight of unrestricted random paths is explicitly shown both for deterministic and statistical fractals such as the incipient infinite percolation cluster. Equally weighted paths (ideal chain) and kinetically generated paths (random walks) belong, in general, to different universality classes. For deterministic fractals exact renormalization group techniques are used. Asymptotic behaviors for the end-to-end distance ranging from power to logarithmic (localization) laws are observed for the ideal chain. In all these cases, random walks in the presence of nonperfect traps are shown to be in the same universality class of the ideal chain. Logarithmic behavior is reflected insingular renormalization group recursions. For the disordered case, numerical transfer matrix techniques are exploited on percolation clusters in two and three dimensions. The two-point correlation function scales with critical exponents not obeying standard scaling relations. The distribution of the number of chains and the number of chains returning to the starting point are found to be well approximated by a log-normal distribution. The logmoment of the number of chains is found to have an essential type of singularity consistent with the log-normal distribution. A non-self-averaging behavior is argued to occur on the basis of the results.     

Random walks on periodic and random lattices. II. Random walk properties via generating function techniques

We investigate the random walk properties of a class of two-dimensional lattices with two different types of columns and discuss the dependence of the properties on the densities and detailed arrangements of the columns. We show that the row and column components of the mean square displacement are asymptotically independent of the details of the arrangement of columns. We reach the same conclusion for some other random walk properties (return to the origin and number of distinct sites visited) for various periodic arrangements of a given relative density of the two types of columns. We also derive exact asymptotic results for the occupation probabilities of the two types of distinct sites on our lattices which validate the basic conjecture on bond and step ratios made in the preceding paper in this series.Supported in part by a grant from Charles and Renée Taubman and by the National Science Foundation, Grant CHE 78-21460.     

Random walks on lattices with randomly distributed traps I. The average number of steps until trapping

For a random walk on a lattice with a random distribution of traps we derive an asymptotic expansion valid for smallq for the average number of steps until trapping, whereq is the probability that a lattice point is a trap. We study the case of perfect traps (where the walk comes to an end) and the extension obtained by letting the traps be imperfect (i.e., by giving the walker a finite probability to remain free when stepping on a trap). Several classes of random walks of varying dimensionality are considered and special care is taken to show that the expansion derived is exact up to and including the last term calculated. The numerical accuracy of the expansion is discussed.     

Random walks on lattices with points of two colors. II. Some rigorous inequalities for symmetric random walks

We continue our investigation of a model of random walks on lattices with two kinds of points, black and white. The colors of the points are stochastic variables with a translation-invariant, but otherwise arbitrary, joint probability distribution. The steps of the random walk are independent of the colors. We are interested in the stochastic properties of the sequence of consecutive colors encountered by the walker. In this paper we first summarize and extend our earlier general results. Then, under the restriction that the random walk be symmetric, we derive a set of rigorous inequalities for the average length of the subwalk from the starting point to a first black point and of the subwalks between black points visited in succession. A remarkable difference in behavior is found between subwalks following an odd-numbered and subwalks following an evennumbered visit to a black point. The results can be applied to a trapping problem by identifying the black points with imperfect traps.     

Flory approximant for self-avoiding walks on fractals

A Flory approximant for the exponent describing the end-to-end distance of a self-avoiding walk (SAW) on fractals is derived. The approximant involves the fractal dimensionalities of the backbone and of the minimal path, and the exponent describing the resistance of the fractal. The approximant yields values which are very close to those available from exact and numerical calculations.     

A long-time tail for random walk in random scenery

Consider a simple random walk on ^d whose sites are colored black or white independently with probabilityq, resp. 1–q. Walk and coloring are independent. Letn _k be the number of steps by the walk between itskth and (k+1) th visits to a black site (i.e., the length of itskth white run), and let _k =E(n _k )–q ^–1. Our main result is a proof that (*) lim _k k ^d/2 _k = (1 –q)q ^{d/2 – 2}(d/2) ^d/2. Since it is known thatq ^{– 1} _k =E(n ₁ n _{k + 1} B) –E(n ₁ B)E(n _{k + 1} B), withB the event that the origin is black, (*) exhibits a long-time tail in the run length autocorrelation function. Numerical calculations of _k (1k100) ind=1, 2, and 3 show that there is an oscillatory behavior of _k for smallk. This damps exponentially fast, following which the power law sets in fairly rapidly. We prove that if the coloring is not independent, but is convex in the sense of FKG, then the decay of _k cannot be faster than (*).     

Distribution functions for random walk processes on networks: An analytic method

A novel analytic method for deriving and analyzing probability distribution functions of variables arising in random walk problems is presented. Applications of the method to quasi-one-dimensional systems show that the generating functions of interest possess simple poles, and no branch cuts outside the unit complex disk. This fact makes it possible to derive closed formulas for the full probability distribution functions and to analyze their properties. We find that transverse structures attached to a one-dimensional backbone can be responsible for the appearance of power laws in observables such as the distribution of first arrival times or the total current moving through a (model) photoexcited dirty semiconductor (our results compare well with experiment). We conclude that in some cases a geometrical effect, e.g., that of a transverse structure, may be indistinguishable from a dynamical effect (long waiting time); we also find universal shapes of distribution functions (humped structures) which are not characterized by power laws. The role of bias in determining properties of quasi-one-dimensional structures is examined. A master equation for generating functions is derived and applied to the computation of currents. Our method is also applied to a fractal structure, yielding nontrivial power laws. In all finite networks considered, all probability distributions decay exponentially for asymptotically long times.For a relatively recent review with some historical background see Ref. 2.     

On a conjecture of Alley and Alder for fluids and Lorentz models

We discuss a conjecture of Alley and Alder predicting a relation between the four-point and the two-point velocity autocorrelation functions for fluids and Lorentz models at sufficiently long times. If the conjecture is correct a modified Burnett coefficient can be defined, which has a finite value, contrary to the ordinary Burnett coefficient, which is divergent. The conjecture is tested for four classes of models with different methods: for three-dimensional fluids mode-coupling theory yields a negative result. The conjecture is confirmed for thed-dimensional deterministic Lorentz gas (d 2) and for a class ofd-dimensional stochastic Lorentz models (d 1) by low-density kinetic theory, as well as by rigorous results, available for one dimension. For yet another class of one-dimensional stochastic Lorentz models, which are exactly solvable in one dimension, the result is negative again. All four classes of models show long-time tails in the velocity autocorrelation function and have a finite diffusion coefficient.     

On the Lifschitz singularity and the tailing in the density of states for random lattice systems

We prove rigorously the existence of a Lifschitz singularity in the density of states at zero energy in some random lattice systems of noninteracting bosons and fermions in any numberv of dimensions. The basic tool is a simple modification of the method of Fukushima to yield the correct upper and lower bounds for allv. We also comment on the mathematical difference between the models treated and the system of phonons with mass disorder in the harmonic approximation, whose behavior is known to be of Debye form, not Lifschitz, at low temperatures.Supported by the Swiss National Science Foundation.On leave of absence from the Institute de Fisica, University of São Paulo, Brazil.     

无标度立体Koch网络上随机游走的平均吸收时间

作为一种基本的动力学过程,复杂网络上的随机游走是当前学术界研究的热点问题,其中精确计算带有陷阱的随机游走过程的平均吸收时间(mean trapping time,MTT)是该领域的一个难点.这里的MTT定义为从网络上任意一个节点出发首次到达设定陷阱的平均时间.本文研究了无标度立体Koch网络上带有一个陷阱的随机游走问题,解析计算了陷阱置于网络中度最大的节点这一情形的网络MTT指标.通过重正化群方法,利用网络递归生成的模式,给出了立体Koch网络上MTT的精确解,所得计算结果与数值解一致,并且从所得结果可以看出,立体Koch网络的MTT随着网络节点数N呈线性增长.最后,将所得结果与之前研究的完全图、规则网络、Sierpinski网络和T分形网络进行比较,结果表明Koch网络具有较高的传输效率.