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.     

Exact dynamics of a continuous time random walker in the presence of a boundary: beyond the intuitive boundary condition approach

We derive the exact dynamics of a random walker with arbitrary non-Markovian transport and reaction rate distribution at a boundary, and present exact solutions in the continuum limit. We find that the ultimate escape probability of the particle is independent of the transport mechanism in contradiction to the long-standing belief based on the conventional approach. We also find a phase transition in the relaxation kinetics associated with the heterogeneity of the transport media.     

Stopping time of a one-dimensional bounded quantum walk

The stopping time of a one-dimensional bounded classical random walk(RW) is defined as the number of steps taken by a random walker to arrive at a fixed boundary for the first time.A quantum walk(QW) is a non-trivial generalization of RW,and has attracted a great deal of interest from researchers working in quantum physics and quantum information.In this paper,we develop a method to calculate the stopping time for a one-dimensional QW.Using our method,we further compare the properties of stopping time for QW and RW.We find that the mean value of the stopping time is the same for both of these problems.However,for short times,the probability for a walker performing a QW to arrive at the boundary is larger than that for a RW.This means that,although the mean stopping time of a quantum and classical walker are the same,the quantum walker has a greater probability of arriving at the boundary earlier than the classical walker.     

A myopic random walk on a finite chain

We solve analytically the problem of a biased random walk on a finite chain of ‘sites’ (1,2,…,N) in discrete time, with ‘myopic boundary conditions’—a walker at 1 (orN) at timen moves to 2 (orN − 1) with probability one at time (n + 1). The Markov chain has period two; there is no unique stationary distribution, and the moments of the displacement of the walker oscillate about certain mean values asn → ∞, with amplitudes proportional to 1/N. In the continuous-time limit, the oscillating behaviour of the probability distribution disappears, but the stationary distribution is depleted at the terminal sites owing to the boundary conditions. In the limit of continuous space as well, the problem becomes identical to that of diffusion on a line segment with the standard reflecting boundary conditions. The first passage time problem is also solved, and the differences between the walks with myopic and reflecting boundaries are brought out.     

Thymic Selection of T Cells as Diffusion with Intermittent Traps

T cells orchestrate adaptive immune responses by recognizing short peptides derived from pathogens, and by distinguishing them from self-peptides. To ensure the latter, immature T cells (thymocytes) diffuse within the thymus gland, where they encounter an ensemble of self-peptides presented on (immobile) antigen presenting cells. Potentially autoimmune T cells are eliminated if the thymocyte binds sufficiently strongly with any such antigen presenting cell. We model thymic selection of T cells as a random walker diffusing in a field of immobile traps that intermittently turn “on” and “off”. The escape probability of potentially autoimmune T cells is equivalent to the survival probability of such a random walker. In this paper we describe the survival probability of a random walker on a d-dimensional cubic lattice with randomly placed immobile intermittent traps, and relate it to the result of a well-studied problem where traps are always “on”. Additionally, when switching between the trap states is slow, we find a peculiar caging effect for the survival probability.     

Synchronization in a power-driven moving agent network

Motivated by the fact that couplings between individual units of many real-world complex systems are relevant to energy, we propose a power-driven moving agent network model as a simple representation. The presented network exhibits a directed and time-varying topological structure, where each agent associated with a chaotic oscillator is depicted as a random walker in a planar space, and interactions among agents are established via communication by assigning different emission powers to them. To investigate the effect of power distribution, synchronization is further explored for the power-driven moving agent network. Under the constraint of fast-switching, we theoretically show that synchronization of the agent network is determined by the power density which is independent of both the power distribution and the size of network. Several numerical simulations are given to validate the acquired results.     

A generalized simple random walk in one dimension related to the Gaussian polynomials

A generalization of the relation between the simple random walk on a regular lattice and the diffusion equation in a continuous space is described. In one dimension we consider a random walk of a walker with exponentially decreasing mobility with respect to time. It has an exact solution of the conditional probability, that is expressed in terms of the Gaussian polynomials, a generalization of binomial coefficients. Taking a suitable continuum limit we obtain the corresponding transport equation from the recursion relation of the discrete random walk process. The kernel of this differential equation is also directly obtained from that conditional probability by the same continuum limit.     

A novel identity from random walk theory

A novel expansion of binomial coefficients in terms of trigonometric functions has been obtained by comparing expressions for the time evolution of the probability distribution for a random walker on a ring obtained by separate combinatoric and eigenvalue approaches.     

Recurrence and Pólya Number of General One-Dimensional Random Walks

The recurrence properties of random walks can be characterized by Pólya number, i.e., the probability that the walker has returned to the origin at least once. In this paper, we consider recurrence properties for a general 1D random walk on a line, in which at each time step the walker can move to the left or right
with probabilities l and r, or remain at the same position with probability o (l+r+o=1). We calculate Pólya number P of this model and find a simple expression for P as, P=1-Δ, whereΔ is the absolute difference of l and r (Δ=|l-r|). We prove this rigorous expression by the method of creative telescoping, and our result suggests that the walk is recurrent if and only if the left-moving probability l equals to the right-moving probability r.     

Continuous time random walk with jump length correlated with waiting time

A coupled continuous time random walk (CTRW) model is proposed, in which the jump length of a walker is correlated with waiting time. The power law distribution is chosen as the probability density function of waiting time and the Gaussian-like distribution as the probability density function of jump length. Normal diffusion, subdiffusion and superdiffusion can be realized within the present model. It is shown that the competition between long-tailed distribution and correlation of jump length and waiting time will lead to different diffusive behavior.     

Statistics of Persistent Events in the Binomial Random Walk: Will the Drunken Sailor Hit the Sober Man?

The statistics of persistent events, recently introduced in the context of phase ordering dynamics, is investigated in the case of the one-dimensional lattice random walk in discrete time. We determine the survival probability of the random walker in the presence of an obstacle moving ballistically with velocity v, i.e., the probability that the random walker remains up to time n on the left of the obstacle. Three regimes are to be considered for the long-time behavior of this probability, according to the sign of the difference between v and the drift velocity V¯ of the random walker. In one of these regimes (v>V¯), the survival probability has a nontrivial limit at long times which is discontinuous at all rational values of v. An algebraic approach allows us to compute these discontinuities as well as several related quantities. The mathematical structure underlying the solvability of this model combines elementary number theory, algebraic functions, and algebraic curves defined over the rationals.     

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.     

Quantum dynamics on a lossy non-Hermitian lattice

We investigate quantum dynamics of a quantum walker on a finite bipartite non-Hermitian lattice,in which the particle can leak out with certain rate whenever it visits one of the two sublattices.Quantum walker initially located on one of the non-leaky sites will finally totally disappear after a length of evolution time and the distribution of decay probability on each unit cell is obtained.In one regime,the resultant distribution shows an expected decreasing behavior as the distance from the initial site increases.However,in the other regime,we find that the resultant distribution of local decay probability is very counterintuitive,in which a relatively high population of decay probability appears on the edge unit cell which is the farthest from the starting point of the quantum walker.We then analyze the energy spectrum of the non-Hermitian lattice with pure loss,and find that the intriguing behavior of the resultant decay probability distribution is intimately related to the existence and specific property of the edge states,which are topologically protected and can be well predicted by the non-Bloch winding number.The exotic dynamics may be observed experimentally with arrays of coupled resonator optical waveguides.     

Evolving networks with bimodal degree distribution

Networks with bimodal degree distribution are most robust to targeted and random attacks. We present a model for constructing a network with bimodal degree distribution. The procedure adopted is to add nodes to the network with a probability p and delete the links between nodes with probability (1 − p). We introduce an additional constraint in the process through an immunity score, which controls the dynamics of the growth process based on the feedback value of the last few time steps. This results in bimodal nature for the degree distribution. We study the standard quantities which characterize the networks, like average path length and clustering coefficient in the context of our growth process and show that the resultant network is in the small world family. It is interesting to note that bimodality in degree distribution is an emergent phenomenon.     

Detecting unknown paths on complex networks through random walks

In this article, we investigate the problem of detecting unknown paths on complex networks through random walks. To detect a given path on a network a random walker should pass through the path from its initial node to its terminal node in turn. We calculate probability ?(t) that a random walker detects a given path on a connected network in t steps when it starts out from source node s. We propose an iteration formula for calculating ?(t). Generating function of ?(t) is also derived. Major factors affecting ?(t), such as walking time t, path length l, starting point of the walker, structure of the path, and topological structure of the underlying network are further discussed. Among these factors, two most outstanding ones are walking time t and path length l. On the one hand, ?(t) increases as t increases, and ?(∞)=1, which shows that the longer the walking time, the higher the chance of detecting a given path, and the walker will discover the path sooner or later so long as it keeps wandering on the network. On the other hand, ?(t) drops substantially as path length l increases, which shows that the longer the path, the lower the chance for the walker to find it in a given time. Apart from path length, path structure also has obvious effect on ?(t). Starting point of the walker has only minor influence on ?(t), but topological structure of the underlying network has strong influence on ?(t). Simulations confirm our analytic results.     

Characterizing the structure of small-world networks

We give exact relations for small-world networks (SWN's) which are independent of the "degree distribution," i.e., the distribution of nearest-neighbor connections. For the original SWN model, we illustrate how these exact relations can be used to obtain approximations for the corresponding basic probability distribution. In the limit of large system sizes and small disorder, we use numerical studies to obtain a functional fit for this distribution. Finally, we obtain the scaling properties for the mean-square displacement of a random walker, which are determined by the scaling behavior of the underlying SWN.     

通过耦合降低随机行走的扩散速度(英文)

研究一个耦合的离散时间马尔可夫随机行走模型,将两个行走者耦合成对,通过改变演化到每一步时行走方向的分布情况,使得每个行走者有更大的概率向着它的共轭行走者的方向演化.在这种耦合方式下,增加耦合强度会使随机行走的扩散速度下降.最关键的问题是演化方向的分布情况,步长的分布情况只起次要作用.因为耦合,成对的行走者将进入某种同步状态.这种同步状态正是扩散速度下降的原因.     

Uncertainty Relation between Detection Probability and Energy Fluctuations

A classical random walker starting on a node of a finite graph will always reach any other node since the search is ergodic, namely it fully explores space, hence the arrival probability is unity. For quantum walks, destructive interference may induce effectively non-ergodic features in such search processes. Under repeated projective local measurements, made on a target state, the final detection of the system is not guaranteed since the Hilbert space is split into a bright subspace and an orthogonal dark one. Using this we find an uncertainty relation for the deviations of the detection probability from its classical counterpart, in terms of the energy fluctuations.     

Implementation of a one-dimensional quantum walk in both position and phase spaces

Quantum walks have been investigated as they have remarkably different features in contrast to classical random walks. We present a quantum walk in a one-dimensional architecture, consisting of two coins and a walker whose evolution is in both position and phase spaces alternately controlled by the two coins respectively. By analyzing the dynamics evolution of the walker in both the position and phase spaces, we observe an influence on the quantum walk in one space from that in the other space, which behaves like decoherence. We propose an implementation of the two-coin quantum walk in both position and phase spaces via cavity quantum electrodynamics(QED).     

Lattice random walks for sets of random walkers. First passage times

We have studied the mean first passage time for the first of aset of random walkers to reach a given lattice point on infinite lattices ofD dimensions. In contrast to the well-known result ofinfinite mean first passage times for one random walker in all dimensionsD, we findfinite mean first passage times for certain well-specified sets of random walkers in all dimensions, exceptD = 2. The number of walkers required to achieve a finite mean time for the first walker to reach the given lattice point is a function of the lattice dimensionD. ForD > 4, we find that only one random walker is required to yield a finite first passage time, provided that this random walker reaches the given lattice point with unit probability. We have thus found a simple random walk property which sticks atD > 4.Supported in part by a grant from Charles and Renée Taubman and by the National Science Foundation, Grant CHE78-21460.