Quenched Limit Theorems for Nearest Neighbour Random Walks in 1D Random Environment

It is well known that random walks in a one dimensional random environment can exhibit subdiffusive behavior due to the presence of traps. In this paper we show that the passage times of different traps are asymptotically independent exponential random variables with parameters forming, asymptotically, a Poisson process. This allows us to prove weak quenched limit theorems in the subdiffusive regime where the contribution of traps plays the dominating role.     

Computer Simulations for Some One-Dimensional Models of Random Walks in Fluctuating Random Environment

We report some results of computer simulations for two models of random walks in random environment (rwre) on the one-dimensional lattice for fixed space–time configuration of the environment (“quenched rwre”): a “Markov model” with Markov dependence in time, and a “quasi stationary” model with long range space–time correlations. We compare with the corresponding results for a model with i.i.d. (in space time) environment. In the range of times available to us the quenched distributions of the random walk displacement are far from gaussian, but as the behavior is similar for all three models one cannot exclude asymptotic gaussianity, which is proved for the model with i.i.d. environment. We also report results on the random drift and on some time correlations which show a clear power decay     

Lingering Random Walks in Random Environment on a Strip

We consider a recurrent random walk (RW) in random environment (RE) on a strip. We prove that if the RE is i. i. d. and its distribution is not supported by an algebraic subsurface in the space of parameters defining the RE then the RW exhibits the (log t)² asymptotic behaviour. The exceptional algebraic subsurface is described by an explicit system of algebraic equations. One-dimensional walks with bounded jumps in a RE are treated as a particular case of the strip model. If the one dimensional RE is i. i. d., then our approach leads to a complete and constructive classification of possible types of asymptotic behaviour of recurrent random walks. Namely, the RW exhibits the (log t)² asymptotic behaviour if the distribution of the RE is not supported by a hyperplane in the space of parameters which shall be explicitly described. And if the support of the RE belongs to this hyperplane then the corresponding RW is a martingale and its asymptotic behaviour is governed by the Central Limit Theorem.     

Random Walks in Space Time Mixing Environments

We prove that random walks in random environments, that are exponentially mixing in space and time, are almost surely diffusive, in the sense that their scaling limit is given by the Wiener measure.     

Random walk in random environment: A counterexample without potential

We describe a family of random walks in random environment which have exponentially decaying correlations, nearest neighbor transition probabilities which are bounded away from 0, and are subdiffusive in any dimensiond<. The random environments have no potential ind>1.     

Classification on the Average of Random Walks

During the last decade many attempts have been made to characterize absence of spontaneous breaking of continuous symmetry for the Heisenberg model on graphs by using suitable classifications of random walks (refs. 4 and 10). We propose and study a new type problem for random walks on graphs, which is particularly interesting for disordered graphs. We compare this classification with the classical one and with an analogous one introduced in ref. 4. Various examples, that are not space-homogeneous, are provided.     

On Continuous-Time Self-Avoiding Random Walk in Dimension Four

We study the distribution of the end-to-end distance of continuous-time self-avoiding random walks (CTRW) in dimension four from two viewpoints. From a real-space renormalization-group map on probabilities, we conjecture the asymptotic behavior of the end-to-end distance of a weakly self-avoiding random walk (SARW) that penalizes two-body interactions of random walks in dimension four on a hierarchical lattice. Then we perform the Monte Carlo computer simulations of CTRW on the four-dimensional integer lattice, paying special attention to the difference in statistical behavior of the CTRW compared with the discrete-time random walks. In this framework, we verify the result already predicted by the renormalization-group method and provide new results related to enumeration of self-avoiding random walks and calculation of the mean square end-to-end distance and gyration radius of continous-time self-avoiding random walks.     

Random walks in generalized delayed recursive trees

Recently a great deal of effort has been made to explicitly determine the mean first-passage time （MFPT） between two nodes averaged over all pairs of nodes on a fractal network. In this paper, we first propose a family of generalized delayed recursive trees characterized by two parameters, where the existing nodes have a time delay to produce new nodes. We then study the MFPT of random walks on this kind of recursive tree and investigate the effect of the time delay on the MFPT. By relating random walks to electrical networks, we obtain an exact formula for the MFPT and verify it by numerical calculations. Based on the obtained results, we further show that the MFPT of delayed recursive trees is much shorter, implying that the efficiency of random walks is much higher compared with the non-delayed counterpart. Our study provides a deeper understanding of random walks on delayed fractal networks.     

Return Probability of Quantum and Correlated Random Walks

The analysis of the return probability is one of the most essential and fundamental topics in the study of classical random walks. In this paper, we study the return probability of quantum and correlated random walks in the one-dimensional integer lattice by the path counting method. We show that the return probability of both quantum and correlated random walks can be expressed in terms of the Legendre polynomial. Moreover, the generating function of the return probability can be written in terms of elliptic integrals of the first and second kinds for the quantum walk.     

Open Quantum Random Walks

A new model of quantum random walks is introduced, on lattices as well as on finite graphs. These quantum random walks take into account the behavior of open quantum systems. They are the exact quantum analogues of classical Markov chains. We explore the “quantum trajectory” point of view on these quantum random walks, that is, we show that measuring the position of the particle after each time-step gives rise to a classical Markov chain, on the lattice times the state space of the particle. This quantum trajectory is a simulation of the master equation of the quantum random walk. The physical pertinence of such quantum random walks and the way they can be concretely realized is discussed. Differences and connections with the already well-known quantum random walks, such as the Hadamard random walk, are established.     

Central Limit Theorems for Open Quantum Random Walks on the Crystal Lattices

We consider the open quantum random walks on the crystal lattices and investigate the central limit theorems for the walks. On the integer lattices the open quantum random walks satisfy the central limit theorems as was shown by Attal et al (Ann Henri Poincaré 16(1):15–43, 2015). In this paper we prove the central limit theorems for the open quantum random walks on the crystal lattices. We then provide with some examples for the Hexagonal lattices. We also develop the Fourier analysis on the crystal lattices. This leads to construct the so called dual processes for the open quantum random walks. It amounts to get Fourier transform of the probability densities, and it is very useful when we compute the characteristic functions of the walks. In this paper we construct the dual processes for the open quantum random walks on the crystal lattices providing with some examples.

     

Existence of the Harmonic Measure for Random Walks on Graphs and in Random Environments

We give a sufficient condition for the existence of the harmonic measure from infinity of transient random walks on weighted graphs. In particular, this condition is verified by the random conductance model on ? ^d , d≥3, when the conductances are i.i.d. and the bonds with positive conductance percolate. The harmonic measure from infinity also exists for random walks on supercritical clusters of ?². This is proved using results of Barlow (Ann. Probab. 32:3024–3084, 2004) and Barlow and Hambly (Electron. J. Probab. 14(1):1–27, 2009).     

Random walks with imperfect trapping in the decoupled-ring approximation

We investigate random walks on a lattice with imperfect traps. In one dimension, we perturbatively compute the survival probability by reducing the problem to a particle diffusing on a closed ring containing just one single trap. Numerical simulations reveal this solution, which is exact in the limit of perfect traps, to be remarkably robust with respect to a significant lowering of the trapping probability. We demonstrate that for randomly distributed traps, the long-time asymptotics of our result recovers the known stretched exponential decay. We also study an anisotropic three-dimensional version of our model. We discuss possible applications of some of our findings to the decay of excitons in semiconducting organic polymer materials, and emphasize the crucial influence of the spatial trap distribution on the kinetics. Received 23 July 2001 / Received in final form 14 May 2002 Published online 13 August 2002     

二维量子随机行走及其物理实现

近年来量子随机行走相关课题因其非经典的特性,已经成为越来越多科研人员的研究热点。这篇文章中我们回顾了一维经典随机行走和一维量子随机行走模型,并且在分析两种二维经典随机行走模型的基础上,我们构建二维量子随机行走模型。通过对随机行走者的位置分布标准差的计算,我们可以证明基于这种二维量子随机行走模型的算法优于其他上述随机行走。除此之外,我们提出一个利用线性光学方法的实验方案,实现这种二维量子随机行走模型。     

Random Quantum Circuits are Approximate 2-designs

Given a universal gate set on two qubits, it is well known that applying random gates from the set to random pairs of qubits will eventually yield an approximately Haar-distributed unitary. However, this requires exponential time. We show that random circuits of only polynomial length will approximate the first and second moments of the Haar distribution, thus forming approximate 1- and 2-designs. Previous constructions required longer circuits and worked only for specific gate sets. As a corollary of our main result, we also improve previous bounds on the convergence rate of random walks on the Clifford group.     

Locally Perturbed Random Walks with Unbounded Jumps

Szász and Telcs (J. Stat. Phys. 26(3), 1981) have shown that for the diffusively scaled, simple symmetric random walk, weak convergence to the Brownian motion holds even in the case of local impurities if d≥2. The extension of their result to finite range random walks is straightforward. Here, however, we are interested in the situation when the random walk has unbounded range. Concretely we generalize the statement of Szász and Telcs (J. Stat. Phys. 26(3), 1981) to unbounded random walks whose jump distribution belongs to the domain of attraction of the normal law. We do this first: for diffusively scaled random walks on Z ^d (d≥2) having finite variance; and second: for random walks with distribution belonging to the non-normal domain of attraction of the normal law. This result can be applied to random walks with tail behavior analogous to that of the infinite horizon Lorentz-process; these, in particular, have infinite variance, and convergence to Brownian motion holds with the superdiffusive \(\sqrt{n\log n}\) scaling.     

Random walks on complex networks

We investigate random walks on complex networks and derive an exact expression for the mean first-passage time (MFPT) between two nodes. We introduce for each node the random walk centrality C, which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.     

Random walk on topologically biased anisotropic percolation clusters and transport properties

Unbiased random walks are performed on topologically biased anisotropic percolation clusters (APC). Topologically biased APCs are generated using suitable anisotropic percolation models. New walk dimensions are found to characterize the anisotropic behaviour of the unbiased random walk on the biased topology. Critical properties of electro and magneto conductivities are characterized estimating respective dynamical critical exponents. A dynamical scaling theory relating dynamical and static critical exponents has been developed. The dynamical critical exponents satisfy the scaling relations within error bar.     

Equidistribution of Random Walks on Spheres

We study the equidistribution on spheres of the n-step transition probabilities of random walks on graphs. We give sufficient conditions for this property being satisfied and for the weaker property of asymptotical equidistribution. We analyze the asymptotical behaviour of the Green function of the simple random walk on ² and we provide a class of random walks on Cayley graphs of groups, whose transition probabilities are not even asymptotically equidistributed.