Random Walk on the Range of Random Walk

We study the random walk X on the range of a simple random walk on ℤ ^d in dimensions d≥4. When d≥5 we establish quenched and annealed scaling limits for the process X, which show that the intersections of the original simple random walk path are essentially unimportant. For d=4 our results are less precise, but we are able to show that any scaling limit for X will require logarithmic corrections to the polynomial scaling factors seen in higher dimensions. Furthermore, we demonstrate that when d=4 similar logarithmic corrections are necessary in describing the asymptotic behavior of the return probability of X to the origin.     

Random Walk on the Incipient Infinite Cluster for Oriented Percolation in High Dimensions

We consider simple random walk on the incipient infinite cluster for the spread-out model of oriented percolation on . In dimensions d > 6, we obtain bounds on exit times, transition probabilities, and the range of the random walk, which establish that the spectral dimension of the incipient infinite cluster is , and thereby prove a version of the Alexander–Orbach conjecture in this setting. The proof divides into two parts. One part establishes general estimates for simple random walk on an arbitrary infinite random graph, given suitable bounds on volume and effective resistance for the random graph. A second part then provides these bounds on volume and effective resistance for the incipient infinite cluster in dimensions d > 6, by extending results about critical oriented percolation obtained previously via the lace expansion.     

Non-backtracking Random Walk

We consider non-backtracking random walk (NBW) in the nearest-neighbor setting on the ? ^d -lattice and on tori. We evaluate the eigensystem of the m×m-dimensional transition matrix of NBW where m denote the degree of the graph. We use its eigensystem to show a functional central limit theorem for NBW on ? ^d and to obtain estimates on the convergence towards the stationary distribution for NBW on the torus.     

Random Walk on the High-Dimensional IIC

We study the asymptotic behavior of the exit times of random walk from Euclidean balls around the origin of the incipient infinite cluster in a manner inspired by Kumagai and Misumi (J Theor Probab 21:910–935, 2008). We do this by getting bounds on the effective resistance between the origin and the boundary of these Euclidean balls. We show that the geometric properties of long-range percolation clusters are significantly different from those of finite-range clusters. We also study the behavior of random walk on the backbone of the IIC and we prove that the Alexander–Orbach conjecture holds for the incipient infinite cluster in high dimensions, both for long-range percolation and for finite-range percolation.     

Two-dimensional Quantum Random Walk

We analyze several families of two-dimensional quantum random walks. The feasible region (the region where probabilities do not decay exponentially with time) grows linearly with time, as is the case with one-dimensional QRW. The limiting shape of the feasible region is, however, quite different. The limit region turns out to be an algebraic set, which we characterize as the rational image of a compact algebraic variety. We also compute the probability profile within the limit region, which is essentially a negative power of the Gaussian curvature of the same algebraic variety. Our methods are based on analysis of the space-time generating function, following the methods of Pemantle and Wilson (J. Comb. Theory, Ser. A 97(1):129–161, 2002).     

Numerical Simulations of Random Walk in Random Environment

This paper is concerned with the numerical simulation of a random walk in a random environment in dimension d = 2. Consider a nearest neighbor random walk on the 2-dimensional integer lattice. The transition probabilities at each site are assumed to be themselves random variables, but fixed for all time. This is the random environment. Consider a parallel strip of radius R centered on an axis through the origin. Let X _R be the probability that the walk that started at the origin exits the strip through one of the boundary lines. Then X _R is a random variable, depending on the environment. In dimension d = 1, the variable X _R converges in distribution to the Bernoulli variable, X = 0, 1 with equal probability, as R . Here the 2-dimensional problem is studied using Gauss-Seidel and multigrid algorithms.     

Random Walk with Barycentric Self-interaction

We study the asymptotic behaviour of a d-dimensional self-interacting random walk (X _n ) _n∈? (?:={1,2,3,…}) which is repelled or attracted by the centre of mass \(G_{n} = n^{-1} \sum_{i=1}^{n} X_{i}\) of its previous trajectory. The walk’s trajectory (X ₁,…,X _n ) models a random polymer chain in either poor or good solvent. In addition to some natural regularity conditions, we assume that the walk has one-step mean drift

$\mathbb{E}[X_{n+1} - X_n \mid X_n - G_n = \mathbf{x}] \approx\rho\|\mathbf{x}\|^{-\beta}\hat{ \mathbf{x}}$

for ρ∈? and β≥0. When β<1 and ρ>0, we show that X _n is transient with a limiting (random) direction and satisfies a super-diffusive law of large numbers: n ^?1/(1+β) X _n converges almost surely to some random vector. When β∈(0,1) there is sub-ballistic rate of escape. When β≥0 and ρ∈? we give almost-sure bounds on the norms ‖X _n ‖, which in the context of the polymer model reveal extended and collapsed phases.

Analysis of the random walk, and in particular of X _n ?G _n , leads to the study of real-valued time-inhomogeneous non-Markov processes (Z _n ) _n∈? on [0,∞) with mean drifts of the form

$ \mathbb{E}[ Z_{n+1} - Z_n \mid Z_n = x ] \approx\rho x^{-\beta} - \frac {x}{n},$

(0.1)

where β≥0 and ρ∈?. The study of such processes is a time-dependent variation on a classical problem of Lamperti; moreover, they arise naturally in the context of the distance of simple random walk on ? ^d from its centre of mass, for which we also give an apparently new result. We give a recurrence classification and asymptotic theory for processes Z _n satisfying (0.1), which enables us to deduce the complete recurrence classification (for any β≥0) of X _n ?G _n for our self-interacting walk.

     

Wavefunction Collapse and Random Walk

Wavefunction collapse models modify Schrödinger's equation so that it describes the rapid evolution of a superposition of macroscopically distinguishable states to one of them. This provides a phenomenological basis for a physical resolution to the so-called measurement problem. Such models have experimentally testable differences from standard quantum theory. The most well developed such model at present is the Continuous Spontaneous Localization (CSL) model in which a universal fluctuating classical field interacts with particles to cause collapse. One side effect of this interaction is that the field imparts energy to the particles: experimental evidence on this has led to restrictions on the parameters of the model, suggesting that the coupling of the classical field to the particles must be mass-proportional. Another side effect is that the field imparts momentum to particles, causing a small blob of matter to undergo random walk. Here we explore this in order to supply predictions which could be experimentally tested. We examine the translational diffusion of a sphere and a disc, and the rotational diffusion of a disc, according to CSL. For example, we find that the rms distance an isolated 10^–5 cm radius sphere diffuses is (its diameter, 5 cm) in (20 sec, a day), and that a disc of radius 2 10^–5 cm and thickness 0.5 10^–5 cm diffuses through 2rad in about 70 sec (this assumes the standard CSL parameter values). The comparable rms diffusions of standard quantum theory are smaller than these by a factor 10^–3±1. It is shown that the CSL diffusion in air at STP is much reduced and, indeed, is swamped by the ordinary Brownian motion. It is also shown that the sphere's diffusion in a thermal radiation bath at room temperature is comparable to the CSL diffusion, but is utterly negligible at liquid He temperature. Thus, in order to observe CSL diffusion, the pressure and temperature must be low. At the low reported pressure of 5 10^–17 Torr, achieved at 4.2°K, the mean time between air molecule collisions with the (sphere, disc) is (80, 45)min. This is ample time for observation of the putative CSL diffusion with the standard parameters and, it is pointed out, with any parameters in the range over which the theory may be considered viable. This encourages consideration of how such an experiment may actually be performed, and the paper closes with some thoughts on this subject.     

Random Walk Quantum Clustering Algorithm Based on Space

In the random quantum walk, which is a quantum simulation of the classical walk, data points interacted when selecting the appropriate walk strategy by taking advantage of quantum-entanglement features; thus, the results obtained when the quantum walk is used are different from those when the classical walk is adopted. A new quantum walk clustering algorithm based on space is proposed by applying the quantum walk to clustering analysis. In this algorithm, data points are viewed as walking participants, and similar data points are clustered using the walk function in the pay-off matrix according to a certain rule. The walk process is simplified by implementing a space-combining rule. The proposed algorithm is validated by a simulation test and is proved superior to existing clustering algorithms, namely, Kmeans, PCA + Kmeans, and LDA-Km. The effects of some of the parameters in the proposed algorithm on its performance are also analyzed and discussed. Specific suggestions are provided.     

A Semi-Deterministic Random Walk with Resetting

We consider a discrete-time random walk (xt) which, at random times, is reset to the starting position and performs a deterministic motion between them. We show that the quantity determines if the system is averse, neutral or inclined towards resetting. It also classifies the stationary distribution. Double barrier probabilities, first passage times and the distribution of the escape time from intervals are determined.     

On the Multi-dimensional Elephant Random Walk

The purpose of this paper is to investigate the asymptotic behavior of the multi-dimensional elephant random walk (MERW). It is a non-Markovian random walk which has a complete memory of its entire history. A wide range of literature is available on the one-dimensional ERW. Surprisingly, no references are available on the MERW. The goal of this paper is to fill the gap by extending the results on the one-dimensional ERW to the MERW. In the diffusive and critical regimes, we establish the almost sure convergence, the law of iterated logarithm and the quadratic strong law for the MERW. The asymptotic normality of the MERW, properly normalized, is also provided. In the superdiffusive regime, we prove the almost sure convergence as well as the mean square convergence of the MERW. All our analysis relies on asymptotic results for multi-dimensional martingales.

     

Modes of a Gaussian Random Walk

It is demonstrated that a one-dimensional gaussian random walk (GRW) possesses an underlying structure in the form of random oscillatory modes. These modes are not sinusoids, but can be isolated by a well-defined procedure. They have average wavelengths and amplitudes, both of which can be determined by experiments or by theoretical calculations. This paper reports such determinations by both methods and also develops a theory that is ultimately shown to agree with experiments. Both theory and simulations show that the average wavelength and the average amplitude scale with the order of the mode in exactly the same way that the modes of the well-known Weierstrass fractal scale with mode order. This is remarkable since the wave generated by the Weierstrass function, , is fully determined for the variable x whereas the GRW is stochastic. By increasing the size of the steps in the GRW, it is possible to selectively remove the fastest modes, while leaving the remaining modes almost unchanged. For a GRW, the parameters corresponding to a and g in the Weierstrass function are found to be 2.0 and 4.0, respectively. These values are independent of the variance associated with the GRW. Application of the random modes is reserved for a later paper.     

Scaling Argument of Anisotropic Random Walk

In this paper, we analytically discuss the scaling properties of the average square end-to-end distance 〈R²〉for anisotropic random walk in D-dimensional space (D≥2), and the returning probability P_n( r₀) for the walker into a certain neighborhood of the origin. We will not only give the calculating formula for 〈R²〉and P_n(r₀), but also point out that if there is a symmetric axis for the distribution of the probability density of a single step displacement, we always obtain 〈R²_⊥n〉～n, where ⊥ refers to the projections of the displacement perpendicular to each symmetric axes of the walk; in D-dimensional space with D symmetric axes perpendicular to each other, we always have 〈R_n²〉～n and the random walk will be like a purely random motion; if the number of inter-perpendicular symmetric axis is smaller than the dimensions of the space, we must have 〈R_n²〉～n² for very large n and the walk will be like a ballistic motion. It is worth while to point out that unlike the isotropic random walk in one and two dimensions, which is certain to return into the neighborhood of the origin, generally there is only a nonzero probability for the anisotropic random walker in two dimensions to return to the neighborhood.     

Localization for a Random Walk in Slowly Decreasing Random Potential

We consider a continuous time random walk X in a random environment on ?⁺ such that its potential can be approximated by the function V:?⁺→? given by $V(x)=\sigma W(x) -\frac {b}{1-\alpha}x^{1-\alpha}$ where σW a Brownian motion with diffusion coefficient σ>0 and parameters b, α are such that b>0 and 0<α<1/2. We show that P-a.s. (where P is the averaged law) $\lim_{t\to\infty} \frac{X_{t}}{(C^{*}(\ln\ln t)^{-1}\ln t)^{\frac{1}{\alpha}}}=1$ with $C^{*}=\frac{2\alpha b}{\sigma^{2}(1-2\alpha)}$ . In fact, we prove that by showing that there is a trap located around $(C^{*}(\ln\ln t)^{-1}\ln t)^{\frac{1}{\alpha}}$ (with corrections of smaller order) where the particle typically stays up to time t. This is in sharp contrast to what happens in the “pure” Sinai’s regime, where the location of this trap is random on the scale ln² t.     

Quantum Random Walk Approximation on Locally Compact Quantum Groups

A natural scheme is established for the approximation of quantum Lévy processes on locally compact quantum groups by quantum random walks. We work in the somewhat broader context of discrete approximations of completely positive quantum stochastic convolution cocycles on C*-bialgebras.     

Discrete Green's Function for Lattice Random Walk

１　Ｉｎｔｒｏｄｕｃｔｉｏｎ　　Ｏｐｔｉｃａｌｔｏｍｏｇｒａｐｈｙｐｒｏｖｉｄｅｓａｎａｌｔｅｒｎａｔｉｖｅｔｅｃｈｎｏｌｏｇｙｔｏｐｒｏｂｅｂｒｅａｓｔｃａｎｃｅｒａｎｄｍｏｎｉｔｏｒｈｕｍａｎｔｉｓｓｕｅ’ｓｆｕｎｃｔｉｏｎａｌｐａｒａｍｅｔｅｒｎｏｎｉｎｖａｓｉｖｅｌｙ［１,２］．Ｐｈｏｔｏｎｍｉｇｒａｔｉｏｎｉｎｔｉｓｓｕｅｐｌａｙｓａｋｅｙｒｏｌｅｉｎｏｐｔｉｃａｌｔｏｍｏｇｒａｐｈｙ．Ｒｅｃｅｎｔｌｙ,ａｌａｔｔｉｃｅｒａｎｄｏｍｗａｌｋｍｏｄｅｌ［３,４］ｉｓｅｍｐｌｏｙｅｄｔｏｄ…     

Discrete Green's Function for Lattice Random Walk

A lattice random walk model based on particles scattering on discrete lattice of homogenous space is introduced. The discrete Green's function (DFG) for two-dimensional and three-dimensional lattice random walk of photon is found and proved by mathematical induction. The convolution theorem of photon lattice random walk is presented. They can be used with the method of images to calculate the photon density distribution in semi-infinite and finite slab homogenous turbid media such as tissue.     

Random Walk Weakly Attracted to a Wall

We consider a random walk X _n in ℤ₊, starting at X ₀=x≥0, with transition probabilities

Infinite Random Matrices and Ergodic Measures

We introduce and study a 2-parameter family of unitarily invariant probability measures on the space of infinite Hermitian matrices. We show that the decomposition of a measure from this family on ergodic components is described by a determinantal point process on the real line. The correlation kernel for this process is explicitly computed. At certain values of parameters the kernel turns into the well-known sine kernel which describes the local correlation in Circular and Gaussian Unitary Ensembles. Thus, the random point configuration of the sine process is interpreted as the random set of “eigenvalues” of infinite Hermitian matrices distributed according to the corresponding measure. Received: 22 January 2001 / Accepted: 30 May 2001