Langevin Picture of Lévy Walks and Their Extensions

In this paper we derive Langevin picture of Lévy walks. Applying recent advances in the theory of coupled continuous time random walks we find a limiting process of the properly scaled Lévy walk. Next, we introduce extensions of Levy walks, in which jump sizes are some functions of waiting times. We prove that under proper scaling conditions, such generalized Lévy walks converge in distribution to the appropriate limiting processes. We also derive the corresponding fractional diffusion equations and investigate behavior of the mean square displacements of the limiting processes, showing that different coupling functions lead to various types of anomalous diffusion.     

Quantum walk under coherence non-generating channels

We investigate the probability distribution of the quantum walk under coherence non-generating channels. We definea model called generalized classical walk with memory. Under certain conditions, generalized classical random walk withmemory can degrade into classical random walk and classical random walk with memory. Based on its various spreadingspeed, the model may be a useful tool for building algorithms. Furthermore, the model may be useful for measuring thequantumness of quantum walk. The probability distributions of quantum walks are generalized classical random walkswith memory under a class of coherence non-generating channels. Therefore, we can simulate classical random walkand classical random walk with memory by coherence non-generating channels. Also, we find that for another class ofcoherence non-generating channels, the probability distributions are influenced by the coherence in the initial state of thecoin. Nevertheless, the influence degrades as the number of steps increases. Our results could be helpful to explore therelationship between coherence and quantum walk.     

Intersection-equivalence of Brownian paths and certain branching processes

We show that sample paths of Brownian motion (and other stable processes) intersect the same sets as certain random Cantor sets constructed by a branching process. With this approach, the classical result that two independent Brownian paths in four dimensions do not intersect reduces to the dying out of a critical branching process, and estimates due to Lawler (1982) for the long-range intersection probability of several random walk paths, reduce to Kolmogrov's 1938 law for the lifetime of a critical branching process. Extensions to random walks with long jumps and applications to Hausdorff dimension are also derived.     

First passage time distributions for finite one-dimensional random walks

We present closed expressions for the characteristic function of the first passage time distribution for biased and unbiased random walks on finite chains and continuous segments with reflecting boundary conditions. Earlier results on mean first passage times for one-dimensional random walks emerge as special cases. The divergences that result as the boundary is moved out to infinity are exhibited explicitly. For a symmetric random walk on a line, the distribution is an elliptic theta function that goes over into the known Lévy distribution with exponent 1/2 as the boundary tends to ∞.     

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.     

Lévy Walk with Multiple Internal States

Lévy walk with multiple internal states can effectively model the motion of particles that don’t immediately move back to the directions or areas which they come from. When the Lévy walk behaves superdiffusion, it is discovered that the non-immediately-repeating property, characterized by the constructed transition matrix, has no influence on the particle’s mean square displacement (MSD) or Pearson coefficient. This is a kind of stable property of Lévy walk. However, if the Lévy walk shows the dynamical behaviors of normal diffusion, then the effect of non-immediately-repeating emerges. For the Lévy walk with some particular transition matrices, it may display nonsymmetric dynamics; in these cases, the behaviors of their variances are detailedly discussed, especially some comparisons with the ones of the continuous time random walks are made (a striking difference is the changes of the exponents of the variances). The first passage time distribution and its average of Lévy walks are simulated, the results of which turn out that the first passage time can distinguish Lévy walks with different transition matrices, while the MSD can not.

     

Reflection principles for biased random walks and application to escape time distributions

We present a reflection principle for an arbitrarybiased continuous time random walk (comprising both Markovian and non-Markovian processes) in the presence of areflecting barrier on semi-infinite and finite chains. For biased walks in the presence of a reflecting barrier this principle (which cannot be derived from combinatorics) is completely different from its familiar form in the presence of an absorbing barrier. The result enables us to obtain closed-form solutions for the Laplace transform of the conditional probability for biased walks on finite chains for all three combinations of absorbing and reflecting barriers at the two ends. An important application of these solutions is the calculation of various first-passage-time and escape-time distributions. We obtain exact results for the characteristic functions of various kinds of escape time distributions for biased random walks on finite chains. For processes governed by a long-tailed event-time distribution we show that the mean time of escape from bounded regions diverges even in the presence of a bias—suggesting, in a sense, the absence of true long-range diffusion in such frozen processes.     

Extremal behavior of a coupled continuous time random walk

Coupled continuous time random walks (CTRWs) model normal and anomalous diffusion of random walkers by taking the sum of random jump lengths dependent on the random waiting times immediately preceding each jump. They are used to simulate diffusion-like processes in econophysics such as stock market fluctuations, where jumps represent financial market microstructure like log returns. In this and many other applications, the magnitude of the largest observations (e.g. a stock market crash) is of considerable importance in quantifying risk. We use a stochastic process called a coupled continuous time random maxima (CTRM) to determine the density governing the maximum jump length of a particle undergoing a CTRW. CTRM are similar to continuous time random walks but track maxima instead of sums. The many ways in which observations can depend on waiting times can produce an equally large number of CTRM governing density shapes. We compare densities governing coupled CTRM with their uncoupled counterparts for three simple observation/wait dependence structures.     

Exact and Efficient Sampling of Conditioned Walks

A computationally challenging and open problem is how to efficiently generate equilibrated samples of conditioned walks. We present here a general stochastic approach that allows one to produce these samples with their correct statistical weight and without rejections. The method is illustrated for a jump process conditioned to evolve within a cylindrical channel and forced to reach one of its ends. We obtain analytically the exact probability density function of the jumps and offer a direct method for gathering equilibrated samples of a random walk conditioned to stay in a channel with suitable boundary conditions. Unbiased walks of arbitrary length can thus be generated with linear computational complexity—even when the channel width is much smaller than the typical bond length of the unconditioned walk. By profiling the metric properties of the generated walks for various bond lengths we characterize the crossover between weak and strong confinement regimes with great detail.     

On the Relationship Between Continuous- and Discrete-Time Quantum Walk

Quantum walk is one of the main tools for quantum algorithms. Defined by analogy to classical random walk, a quantum walk is a time-homogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. But whereas a continuous-time random walk can be obtained as the limit of a sequence of discrete-time random walks, the two types of quantum walk appear fundamentally different, owing to the need for extra degrees of freedom in the discrete-time case. In this article, I describe a precise correspondence between continuous- and discrete- time quantum walks on arbitrary graphs. Using this correspondence, I show that continuous-time quantum walk can be obtained as an appropriate limit of discrete-time quantum walks. The correspondence also leads to a new technique for simulating Hamiltonian dynamics, giving efficient simulations even in cases where the Hamiltonian is not sparse. The complexity of the simulation is linear in the total evolution time, an improvement over simulations based on high-order approximations of the Lie product formula. As applications, I describe a continuous-time quantum walk algorithm for element distinctness and show how to optimally simulate continuous-time query algorithms of a certain form in the conventional quantum query model. Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.     

A Perron–Frobenius Type of Theorem for Quantum Operations

We define a special class of quantum operations we call Markovian and show that it has the same spectral properties as a corresponding Markov chain. We then consider a convex combination of a quantum operation and a Markovian quantum operation and show that under a norm condition its spectrum has the same properties as in the conclusion of the Perron–Frobenius theorem if its Markovian part does. Moreover, under a compatibility condition of the two operations, we show that its limiting distribution is the same as the corresponding Markov chain. We apply our general results to partially decoherent quantum random walks with decoherence strength \(0 \le p \le 1\). We obtain a quantum ergodic theorem for partially decoherent processes. We show that for \(0 < p \le 1\), the limiting distribution of a partially decoherent quantum random walk is the same as the limiting distribution for the classical random walk.     

Space use by foragers consuming renewable resources

Through the analysis of unbiased random walks on fractal trees and continuous time random walks, we show that even if a process is characterized by a mean square displacement (MSD) growing linearly with time (standard behaviour) its diffusion properties can be not trivial. In particular, we show that the following scenarios are consistent with a linear increase of MSD with time: (i) the high-order moments, ?x(t) ^q ? for q > 2 and the probability density of the process exhibit multiscaling; (ii) the random walk on certain fractal graphs, with non integer spectral dimension, can display a fully standard diffusion; (iii) positive order moments satisfying standard scaling does not imply an exact scaling property of the probability density.     

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.     

Survival,Extinction and Approximation of Discrete-time Branching Random Walks

We consider a general discrete-time branching random walk on a countable set X. We relate local, strong local and global survival with suitable inequalities involving the first-moment matrix M of the process. In particular we prove that, while the local behavior is characterized by M, the global behavior cannot be completely described in terms of properties involving M alone. Moreover we show that locally surviving branching random walks can be approximated by sequences of spatially confined and stochastically dominated branching random walks which eventually survive locally if the (possibly finite) state space is large enough. An analogous result can be achieved by approximating a branching random walk by a sequence of multitype contact processes and allowing a sufficiently large number of particles per site. We compare these results with the ones obtained in the continuous-time case and we give some examples and counterexamples.     

Analytical representations of non-Gaussian laws of random walks

An analytical representation of a random process with independent increments in some space (random walks introduced by Pearson) is considered. The law of random walk distribution in space is derived from the general representation of stochastic elementary hops (distribution law of hop probability) using Kadanoff’s concept of the unit increment as one hop. For limited hop laws and laws of hop distributions with all moments there naturally arises Chandrasekhar’s result that describes ordinary physical diffusion. For laws of hop distributions without the second and highest moments there also arise known Lévy walks (flights) sometimes treated as superdiffusion. For the intermediate case, where the distributions of hops have at least the second moment and not all finite moments (these hops are sometimes called truncated Lévy walks), the asymptotic form of the random walk distribution was obtained for the first time. The results obtained are compared with the experimental laws known in econophysics. Satisfactory agreement is observed between the developed theory and the empirical data for insufficiently studied truncated Lévy walks.     

The non-isotropic two-dimensional random walk

Abstract

A formula is obtained for the joint probability density function of the angle and length of the resultant of an N-step non-isotropic random walk in two dimensions for arbitrary step angle and radius probability density and for any fixed number of steps. The problem is attacked by applying the theory of generalized functions concentrated on smooth manifolds. The analysis is presented initially for the case where only the angles are random. The characteristic function is defined for the walk in terms of angular and radial frequencies and the inversion is obtained in terms of a sum of Hankel transforms. The Hankel transform sum is transformed by showing that it can be interpreted in terms of the motions of the two-dimensional Euclidean plane corresponding to the rotations and translations resulting from a sequence of fixed steps. This transformation results in an expression involving integrations over two manifolds defined by delta functions. The properties of the manifolds defined by the delta functions are then considered and this results in some simplification of the formulae. The analysis is then generalized to the case where both the phase and length of each step in the walk are random. Finally, seven examples are presented including the general two-step walk and three walks which lead to generalized K density functions for the resultant.     

A measure of the symmetry of random walks

We derive the probability density for a simple measure of the asymmetry of a one-dimensional random walk, namely the ratio of the minimum of the two maximum displacements in the positive and negative directions, to the maximum. We show that in the diffusion limit the asymmetry is independent of time. These results are shown to apply to random walks in which individual steps have a stable law distribution as well as to multidimensional random walks.