Sample records for branching random walk

  1. A random walk with a branching system in random environments

    Ying-qiu LI; Xu LI; Quan-sheng LIU


    We consider a branching random walk in random environments, where the particles are reproduced as a branching process with a random environment (in time), and move independently as a random walk on Z with a random environment (in locations). We obtain the asymptotic properties on the position of the rightmost particle at time n, revealing a phase transition phenomenon of the system.

  2. Recurrence and Transience for Branching Random Walks in an iid Random Environment

    Müller, Sebastian


    We give three different criteria for transience of a Branching Markov Chain. These conditions enable us to give a classification of Branching Random Walks in Random Environment (BRWRE) on Cayley Graphs in recurrence and transience. This classification is stated explicitly for BRWRE on $\\Z^d.$ Furthermore, we emphasize the interplay between Branching Markov Chains and the spectral radius. We prove properties of the spectral radius of the Random Walk in Random Environment with the help of appro...

  3. Branching-rate expansion around annihilating random walks.

    Benitez, Federico; Wschebor, Nicolás


    We present some exact results for branching and annihilating random walks. We compute the nonuniversal threshold value of the annihilation rate for having a phase transition in the simplest reaction-diffusion system belonging to the directed percolation universality class. Also, we show that the accepted scenario for the appearance of a phase transition in the parity conserving universality class must be improved. In order to obtain these results we perform an expansion in the branching rate around pure annihilation, a theory without branching. This expansion is possible because we manage to solve pure annihilation exactly in any dimension. PMID:23005353

  4. Branching structure for an (L-1) random walk in random environment and its applications

    Hong, Wenming


    By decomposing the random walk path, we construct a multitype branching process with immigration in random environment for corresponding random walk with bounded jumps in random environment. Then we give two applications of the branching structure. Firstly, we specify the explicit invariant density by a method different with the one used in Br\\'emont [3] and reprove the law of large numbers of the random walk by a method known as the environment viewed from particles". Secondly, the branching structure enables us to prove a stable limit law, generalizing the result of Kesten-Kozlov-Spitzer [11] for the nearest random walk in random environment. As a byproduct, we also prove that the total population of a multitype branching process in random environment with immigration before the first regeneration belongs to the domain of attraction of some \\kappa -stable law.

  5. Branching and annihilating random walks: exact results at low branching rate.

    Benitez, Federico; Wschebor, Nicolás


    We present some exact results on the behavior of branching and annihilating random walks, both in the directed percolation and parity conserving universality classes. Contrary to usual perturbation theory, we perform an expansion in the branching rate around the nontrivial pure annihilation (PA) model, whose correlation and response function we compute exactly. With this, the nonuniversal threshold value for having a phase transition in the simplest system belonging to the directed percolation universality class is found to coincide with previous nonperturbative renormalization group (RG) approximate results. We also show that the parity conserving universality class has an unexpected RG fixed point structure, with a PA fixed point which is unstable in all dimensions of physical interest. PMID:23767512

  6. Randomized random walk on a random walk

    This paper discusses generalizations of the model introduced by Kehr and Kunter of the random walk of a particle on a one-dimensional chain which in turn has been constructed by a random walk procedure. The superimposed random walk is randomised in time according to the occurrences of a stochastic point process. The probability of finding the particle in a particular position at a certain instant is obtained explicitly in the transform domain. It is found that the asymptotic behaviour for large time of the mean-square displacement of the particle depends critically on the assumed structure of the basic random walk, giving a diffusion-like term for an asymmetric walk or a square root law if the walk is symmetric. Many results are obtained in closed form for the Poisson process case, and these agree with those given previously by Kehr and Kunter. (author)

  7. Random Walks on Random Graphs

    Cooper, Colin; Frieze, Alan

    The aim of this article is to discuss some of the notions and applications of random walks on finite graphs, especially as they apply to random graphs. In this section we give some basic definitions, in Section 2 we review applications of random walks in computer science, and in Section 3 we focus on walks in random graphs.

  8. Random walks on combs

    Durhuus, B; Wheater, J; Durhuus, Bergfinnur; Jonsson, Thordur; Wheater, John


    We develop techniques to obtain rigorous bounds on the behaviour of random walks on combs. Using these bounds we calculate exactly the spectral dimension of random combs with infinite teeth at random positions or teeth with random but finite length. We also calculate exactly the spectral dimension of some fixed non-translationally invariant combs. We relate the spectral dimension to the critical exponent of the mass of the two-point function for random walks on random combs, and compute mean displacements as a function of walk duration. We prove that the mean first passage time is generally infinite for combs with anomalous spectral dimension.

  9. Fixed points of a generalized smoothing transformation and applications to the branching random walk

    Liu, Quansheng


    Let {Ai : i ≥ 1} be a sequence of non-negative random variables and let M be the class of all probability measures on [0,∞]. Define a transformation T on M by letting Tμ be the distribution of ∑i=1∞AiZi, where the Zi are independent random variables with distribution μ, which are also independent of {Ai}. Under first moment assumptions imposed on {Ai}, we determine exactly when T has a non-trivial fixed point (of finite or infinite mean) and we prove that all fixed ...

  10. Random walks, random fields, and disordered systems

    Černý, Jiří; Kotecký, Roman


    Focusing on the mathematics that lies at the intersection of probability theory, statistical physics, combinatorics and computer science, this volume collects together lecture notes on recent developments in the area. The common ground of these subjects is perhaps best described by the three terms in the title: Random Walks, Random Fields and Disordered Systems. The specific topics covered include a study of Branching Brownian Motion from the perspective of disordered (spin-glass) systems, a detailed analysis of weakly self-avoiding random walks in four spatial dimensions via methods of field theory and the renormalization group, a study of phase transitions in disordered discrete structures using a rigorous version of the cavity method, a survey of recent work on interacting polymers in the ballisticity regime and, finally, a treatise on two-dimensional loop-soup models and their connection to conformally invariant systems and the Gaussian Free Field. The notes are aimed at early graduate students with a mod...

  11. Aging Random Walks

    Böttcher, S


    Aging refers to the property of two-time correlation functions to decay very slowly on (at least) two time scales. This phenomenon has gained recent attention due to experimental observations of the history dependent relaxation behavior in amorphous materials (``Glasses'') which pose a challenge to theorist. Aging signals the breaking of time-translational invariance and the violation of the fluctuation dissipation theorem during the relaxation process. But while the origin of aging in disordered media is profound, and the discussion is clad in the language of a well-developed theory, systems as simple as a random walk near a wall can exhibit aging. Such a simple walk serves well to illustrate the phenomenon and some of the physics behind it.

  12. Fractional random walk lattice dynamics

    Michelitsch, Thomas; Riascos, Alejandro Perez; Nowakowski, Andrzeij; Nicolleau, Franck


    We analyze time-discrete and continuous `fractional' random walks on undirected regular networks with special focus on cubic periodic lattices in $n=1,2,3,..$ dimensions.The fractional random walk dynamics is governed by a master equation involving {\\it fractional powers of Laplacian matrices $L^{\\frac{\\alpha}{2}}$}where $\\alpha=2$ recovers the normal walk.First we demonstrate thatthe interval $0\\textless{}\\alpha\\leq 2$ is admissible for the fractional random walk. We derive analytical expressions for fractional transition matrix and closely related the average return probabilities. We further obtain thefundamental matrix $Z^{(\\alpha)}$, and the mean relaxation time (Kemeny constant) for the fractional random walk.The representation for the fundamental matrix $Z^{(\\alpha)}$ relates fractional random walks with normal random walks.We show that the fractional transition matrix elements exihibit for large cubic $n$-dimensional lattices a power law decay of an $n$-dimensional infinite spaceRiesz fractional deriva...

  13. Random walk loop soup

    Lawler, Gregory F.; Ferreras, José A. Trujillo


    The Brownian loop soup introduced in Lawler and Werner (2004) is a Poissonian realization from a sigma-finite measure on unrooted loops. This measure satisfies both conformal invariance and a restriction property. In this paper, we define a random walk loop soup and show that it converges to the Brownian loop soup. In fact, we give a strong approximation result making use of the strong approximation result of Koml\\'os, Major, and Tusn\\'ady. To make the paper self-contained, we include a proof...


    洪文明; 孙鸿雁


    We consider a random walk on Z in random environment with possible jumps{-L, · · · ,-1, 1}, in the case that the environment{ωi: i∈Z}are i.i.d.. We establish the renewal theorem for the Markov chain of “the environment viewed from the particle” in both annealed probability and quenched probability, which generalize partially the results of Kesten (1977) and Lalley (1986) for the nearest random walk in random environment on Z, respectively. Our method is based on the intrinsic branching structure within the (L, 1)-RWRE formulated in Hong and Wang (2013).

  15. Topics in random walks in random environment

    Over the last twenty-five years random motions in random media have been intensively investigated and some new general methods and paradigms have by now emerged. Random walks in random environment constitute one of the canonical models of the field. However in dimension bigger than one they are still poorly understood and many of the basic issues remain to this day unresolved. The present series of lectures attempt to give an account of the progresses which have been made over the last few years, especially in the study of multi-dimensional random walks in random environment with ballistic behavior. (author)

  16. Quantum Random Walks do not need a Coin Toss

    Patel, Apoorva; Raghunathan, K. S.; Rungta, Pranaw


    Classical randomized algorithms use a coin toss instruction to explore different evolutionary branches of a problem. Quantum algorithms, on the other hand, can explore multiple evolutionary branches by mere superposition of states. Discrete quantum random walks, studied in the literature, have nonetheless used both superposition and a quantum coin toss instruction. This is not necessary, and a discrete quantum random walk without a quantum coin toss instruction is defined and analyzed here. O...

  17. Persistence of random walk records

    We study records generated by Brownian particles in one dimension. Specifically, we investigate an ordinary random walk and define the record as the maximal position of the walk. We compare the record of an individual random walk with the mean record, obtained as an average over infinitely many realizations. We term the walk ‘superior’ if the record is always above average, and conversely, the walk is said to be ‘inferior’ if the record is always below average. We find that the fraction of superior walks, S, decays algebraically with time, S ∼ t−β, in the limit t → ∞, and that the persistence exponent is nontrivial, β = 0.382 258…. The fraction of inferior walks, I, also decays as a power law, I ∼ t−α, but the persistence exponent is smaller, α = 0.241 608…. Both exponents are roots of transcendental equations involving the parabolic cylinder function. To obtain these theoretical results, we analyze the joint density of superior walks with a given record and position, while for inferior walks it suffices to study the density as a function of position. (paper)

  18. 随机环境中的分枝随机游动的若干极限定理%Some limit theorems on branching random walks in random environments

    方亮; 胡晓予


    假设{Zn;n=0,1,2,…}是一个随机环境中的分枝随机游动(即质点在产生后代的过程中,还作直线上随机游动),ξ={ξ0,ξ1,ξ2,…}为环境过程.记Z(n,x)为落在区间(-∞,x]中的第n代质点的个数,∫ξn(s)=∑∞j=o pξn(j)Sj为第n代个体的生成函数,mξn=∫1ξn(1).证明了在特定条件下,存在随机序列{tn}使得Z(n,tn)(∏n-1 i=0 mξi)-1均方收敛到一个随机变量.对于依赖于代的分枝随机游动,仍有类似的结论.%Suppose {Zn;n = 0,1,2,…} is a branching random walk in the random environment, and ξ ={ξ0,ξ1 ,ξ2, … } is the environment process. Let Z(n,x) be the number of the nth generation located in the interval ( - ∞, x ], fξn (s) = ∑j=0 ∞ Pξn (j) sj be the generating function of the distribution of the particle in the nth generation, and mξn = fξn' ( 1 ). We show that under the specific conditions, there exists a sequence of random variables { tn } , so that Z( n,tn) ( Πi=0 n-1 mξi )-1 converges in L2. For branching random walks in varying environments, we have similar results.

  19. Numerical studies of planar closed random walks

    Lattice numerical simulations for planar closed random walks and their winding sectors are presented. The frontiers of the random walks and of their winding sectors have a Hausdorff dimension dH = 4/3. However, when properly defined by taking into account the inner 0-winding sectors, the frontiers of the random walks have a Hausdorff dimension dH≈1.77

  20. Random Walks Estimate Land Value

    Blanchard, Ph


    Expected urban population doubling calls for a compelling theory of the city. Random walks and diffusions defined on spatial city graphs spot hidden areas of geographical isolation in the urban landscape going downhill. First--passage time to a place correlates with assessed value of land in that. The method accounting the average number of random turns at junctions on the way to reach any particular place in the city from various starting points could be used to identify isolated neighborhoods in big cities with a complex web of roads, walkways and public transport systems.

  1. Perturbing transient Random Walk in a Random Environment with cookies of maximal strength

    Bauernschubert, Elisabeth


    We consider a left-transient random walk in a random environment on Z that will be disturbed by cookies inducing a drift to the right of strength 1. The number of cookies per site is i.i.d. and independent of the environment. Criteria for recurrence and transience of the random walk are obtained. For this purpose we use subcritical branching processes in random environments with immigration and formulate criteria for recurrence and transience for these processes.

  2. Deterministic Walks in Random Media

    Deterministic walks over a random set of N points in one and two dimensions (d=1,2 ) are considered. Points ('cities') are randomly scattered in Rd following a uniform distribution. A walker ('tourist'), at each time step, goes to the nearest neighbor city that has not been visited in the past τ steps. Each initial city leads to a different trajectory composed of a transient part and a final p -cycle attractor. Transient times (for d=1,2 ) follow an exponential law with a τ -dependent decay time but the density of p cycles can be approximately described by D(p)∝p-α (τ) . For τmuchgt1 and τ/Nmuchlt1 , the exponent is independent of τ . Some analytical results are given for the d=1 case

  3. Fluctuations of Quantum Random Walks on Circles

    Inui, Norio; Konishi, Yoshinao; Konno, Norio; Soshi, Takahiro


    Temporal fluctuations in the Hadamard walk on circles are studied. A temporal standard deviation of probability that a quantum random walker is positive at a given site is introduced to manifest striking differences between quantum and classical random walks. An analytical expression of the temporal standard deviation on a circle with odd sites is shown and its asymptotic behavior is considered for large system size. In contrast with classical random walks, the temporal fluctuation of quantum...

  4. Numerical studies of planar closed random walks

    Desbois, Jean; Ouvry, Stephane


    Lattice numerical simulations for planar closed random walks and their winding sectors are presented. The frontiers of the random walks and of their winding sectors have a Hausdorff dimension $d_H=4/3$. However, when properly defined by taking into account the inner 0-winding sectors, the frontiers of the random walks have a Hausdorff dimension $d_H\\approx 1.77$.

  5. Transition matrix from a random walk

    Schulman, Lawrence S


    Given a random walk a method is presented to produce a matrix of transition probabilities that is consistent with that random walk. The method is tested by using a transition matrix to produce a path and then using that path to create the estimate. The two matrices are then compared.

  6. Random recursive trees and the elephant random walk

    Kürsten, Rüdiger


    One class of random walks with infinite memory, so-called elephant random walks, are simple models describing anomalous diffusion. We present a surprising connection between these models and bond percolation on random recursive trees. We use a coupling between the two models to translate results from elephant random walks to the percolation process. We calculate, besides other quantities, exact expressions for the first and the second moment of the root cluster size and of the number of nodes in child clusters of the first generation. We further introduce another model, the skew elephant random walk, and calculate the first and second moment of this process.




    The range of roaldom walk on Zd in symmetric random environment is investigated. As results, it is proved that the strong law of large numbers for the range of random walk oil Zd in some random environments holds if d > 3, and a weak law of large numbers holds for d = 1.

  8. Elements of random walk and diffusion processes

    Ibe, Oliver C


    Presents an important and unique introduction to random walk theory Random walk is a stochastic process that has proven to be a useful model in understanding discrete-state discrete-time processes across a wide spectrum of scientific disciplines. Elements of Random Walk and Diffusion Processes provides an interdisciplinary approach by including numerous practical examples and exercises with real-world applications in operations research, economics, engineering, and physics. Featuring an introduction to powerful and general techniques that are used in the application of physical and dynamic

  9. Scaling of random walk betweenness in networks

    Narayan, O


    The betweenness centrality of graphs using random walk paths instead of geodesics is studied. A scaling collapse with no adjustable parameters is obtained as the graph size $N$ is varied; the scaling curve depends on the graph model. A normalized random betweenness, that counts each walk passing through a node only once, is also defined. It is argued to be more useful and seen to have simpler scaling behavior. In particular, the probability for a random walk on a preferential attachment graph to pass through the root node is found to tend to unity as $N\\rightarrow\\infty.$

  10. Quenched moderate deviations principle for random walk in random environment


    We derive a quenched moderate deviations principle for the one-dimensional nearest random walk in random environment,where the environment is assumed to be stationary and ergodic.The approach is based on hitting time decomposition.

  11. Non symmetric random walk on infinite graph

    Marcin J. Zygmunt


    We investigate properties of a non symmetric Markov's chain on an infinite graph. We show the connection with matrix valued random walk polynomials which satisfy the orthogonality formula with respect to non a symmetric matrix valued measure.

  12. Non symmetric random walk on infinite graph

    Marcin J. Zygmunt


    Full Text Available We investigate properties of a non symmetric Markov's chain on an infinite graph. We show the connection with matrix valued random walk polynomials which satisfy the orthogonality formula with respect to non a symmetric matrix valued measure.

  13. Levy random walks on multiplex networks

    Guo, Quantong; Zheng, Zhiming; Moreno, Yamir


    Random walks constitute a fundamental mechanism for many dynamics taking place on complex networks. Besides, as a more realistic description of our society, multiplex networks have been receiving a growing interest, as well as the dynamical processes that occur on top of them. Here, inspired by one specific model of random walks that seems to be ubiquitous across many scientific fields, the Levy flight, we study a new navigation strategy on top of multiplex networks. Capitalizing on spectral graph and stochastic matrix theories, we derive analytical expressions for the mean first passage time and the average time to reach a node on these networks. Moreover, we also explore the efficiency of Levy random walks, which we found to be very different as compared to the single layer scenario, accounting for the structure and dynamics inherent to the multiplex network. Finally, by comparing with some other important random walk processes defined on multiplex networks, we find that in some region of the parameters, a ...

  14. Tempered stable laws as random walk limits

    Chakrabarty, Arijit; Meerschaert, Mark M.


    Stable laws can be tempered by modifying the L\\'evy measure to cool the probability of large jumps. Tempered stable laws retain their signature power law behavior at infinity, and infinite divisibility. This paper develops random walk models that converge to a tempered stable law under a triangular array scheme. Since tempered stable laws and processes are useful in statistical physics, these random walk models can provide a basic physical model for the underlying physical phenomena.

  15. Oscillatory Fractional Brownian Motion and Hierarchical Random Walks

    Bojdecki, Tomasz; Gorostiza, Luis G.; Talarczyk, Anna


    We introduce oscillatory analogues of fractional Brownian motion, sub-fractional Brownian motion and other related long range dependent Gaussian processes, we discuss their properties, and we show how they arise from particle systems with or without branching and with different types of initial conditions, where the individual particle motion is the so-called c-random walk on a hierarchical group. The oscillations are caused by the discrete and ultrametric structure of the hierarchical group,...

  16. Branching diffusions in random environment

    Böinghoff, Christian


    We consider the diffusion approximation of branching processes in random environment (BPREs). This diffusion approximation is similar to and mathematically more tractable than BPREs. We obtain the exact asymptotic behavior of the survival probability. As in the case of BPREs, there is a phase transition in the subcritical regime due to different survival opportunities. In addition, we characterize the process conditioned to never go extinct and establish a backbone construction. In the strongly subcritical regime, mean offspring numbers are increased but still subcritical in the process conditioned to never go extinct. Here survival is solely due to an immortal individual, whose offspring are the ancestors of additional families. In the weakly subcritical regime, the mean offspring number is supercritical in the process conditioned to never go extinct. Thus this process survives with positive probability even if there was no immortal individual.

  17. The associated random walk and martingales in random walks with stationary increments

    Grey, D R


    We extend the notion of the associated random walk and the Wald martingale in random walks where the increments are independent and identically distributed to the more general case of stationary ergodic increments. Examples are given where the increments are Markovian or Gaussian, and an application in queueing is considered.

  18. Equal Superposition Transformations and Quantum Random Walks

    Parashar, Preeti


    The largest ensemble of qubits which satisfy the general transformation of equal superposition is obtained by different methods, namely, linearity, no-superluminal signalling and non-increase of entanglement under LOCC. We also consider the associated quantum random walk and show that all unitary balanced coins give the same asymmetric spatial probability distribution. It is further illustrated that unbalanced coins, upon appropriate superposition, lead to new unbiased walks which have no cla...

  19. A Note on Multitype Branching Process with Bounded Immigration in Random Environment

    Hua Ming WANG


    In this paper,we study the total number of progeny,W,before regenerating of multitype branching process with immigration in random environment.We show that the tail probability of |W| is of order t-κ as t → ∞,with κ some constant.As an application,we prove a stable law for (L-1) random walk in random environment,generalizing the stable law for the nearest random walk in random environment (see "Kesten,Kozlov,Spitzer:A limit law for random walk in a random environment.Compositio Math.,30,145-168 (1975)").

  20. Sunspot random walk and 22-year variation

    Love, Jeffrey J.; Rigler, E. Joshua


    We examine two stochastic models for consistency with observed long-term secular trends in sunspot number and a faint, but semi-persistent, 22-yr signal: (1) a null hypothesis, a simple one-parameter random-walk model of sunspot-number cycle-to-cycle change, and, (2) an alternative hypothesis, a two-parameter random-walk model with an imposed 22-yr alternating amplitude. The observed secular trend in sunspots, seen from solar cycle 5 to 23, would not be an unlikely result of the accumulation of multiple random-walk steps. Statistical tests show that a 22-yr signal can be resolved in historical sunspot data; that is, the probability is low that it would be realized from random data. On the other hand, the 22-yr signal has a small amplitude compared to random variation, and so it has a relatively small effect on sunspot predictions. Many published predictions for cycle 24 sunspots fall within the dispersion of previous cycle-to-cycle sunspot differences. The probability is low that the Sun will, with the accumulation of random steps over the next few cycles, walk down to a Dalton-like minimum. Our models support published interpretations of sunspot secular variation and 22-yr variation resulting from cycle-to-cycle accumulation of dynamo-generated magnetic energy.

  1. Quantum random walks with decoherent coins

    The quantum random walk has been much studied recently, largely due to its highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum walk on the line: the presence of decoherence in the quantum ''coin'' which drives the walk. We find exact analytical expressions for the time dependence of the first two moments of position, and show that in the long-time limit the variance grows linearly with time, unlike the unitary walk. We compare this to the results of direct numerical simulation, and see how the form of the position distribution changes from the unitary to the usual classical result as we increase the strength of the decoherence

  2. Self-avoiding random walk in superspace

    The model is presented, where all the critical exponents are calculated exactly. It corresponds to a self-avoiding random walk in superspace of dimension D≤4. For the correlation length the validity of Flory's conjecture (ν=3/(D+2)) is confirmed. (orig.)

  3. Random walk centrality for temporal networks

    Rocha, Luis Enrique Correa


    Nodes can be ranked according to their relative importance within the network. Ranking algorithms based on random walks are particularly useful because they connect topological and diffusive properties of the network. Previous methods based on random walks, as for example the PageRank, have focused on static structures. However, several realistic networks are indeed dynamic, meaning that their structure changes in time. In this paper, we propose a centrality measure for temporal networks based on random walks which we call TempoRank. While in a static network, the stationary density of the random walk is proportional to the degree or the strength of a node, we find that in temporal networks, the stationary density is proportional to the in-strength of the so-called effective network. The stationary density also depends on the sojourn probability q which regulates the tendency of the walker to stay in the node. We apply our method to human interaction networks and show that although it is important for a node ...

  4. Random walk term weighting for information retrieval

    Blanco, R.; Lioma, Christina


    We present a way of estimating term weights for Information Retrieval (IR), using term co-occurrence as a measure of dependency between terms.We use the random walk graph-based ranking algorithm on a graph that encodes terms and co-occurrence dependencies in text, from which we derive term weight...

  5. Random Walks and Sustained Competitive Advantage

    Jerker Denrell


    Strategy is concerned with sustained interfirm profitability differences. Observations of such sustained differences are often attributed to unobserved systematic a priori differences in firm characteristics. This paper shows that sustained interfirm profitability differences may be very likely even if there are no a priori differences among firms. As a result of the phenomenon of long leads in random walks, even a random resource accumulation process is likely to produce persistent resource ...

  6. Estimates of random walk exit probabilities and application to loop-erased random walk

    Kozdron, Michael J.; Lawler, Gregory F.


    We prove an estimate for the probability that a simple random walk in a simply connected subset A of Z^2 starting on the boundary exits A at another specified boundary point. The estimates are uniform over all domains of a given inradius. We apply these estimates to prove a conjecture of S. Fomin in 2001 concerning a relationship between crossing probabilities of loop-erased random walk and Brownian motion.

  7. Random Walks on Stochastic Temporal Networks

    Hoffmann, Till; Lambiotte, Renaud


    In the study of dynamical processes on networks, there has been intense focus on network structure -- i.e., the arrangement of edges and their associated weights -- but the effects of the temporal patterns of edges remains poorly understood. In this chapter, we develop a mathematical framework for random walks on temporal networks using an approach that provides a compromise between abstract but unrealistic models and data-driven but non-mathematical approaches. To do this, we introduce a stochastic model for temporal networks in which we summarize the temporal and structural organization of a system using a matrix of waiting-time distributions. We show that random walks on stochastic temporal networks can be described exactly by an integro-differential master equation and derive an analytical expression for its asymptotic steady state. We also discuss how our work might be useful to help build centrality measures for temporal networks.

  8. Random walk centrality in interconnected multilayer networks

    Solé-Ribalta, Albert; De Domenico, Manlio; Gómez, Sergio; Arenas, Alex


    Real-world complex systems exhibit multiple levels of relationships. In many cases they require to be modeled as interconnected multilayer networks, characterizing interactions of several types simultaneously. It is of crucial importance in many fields, from economics to biology and from urban planning to social sciences, to identify the most (or the less) influent nodes in a network using centrality measures. However, defining the centrality of actors in interconnected complex networks is not trivial. In this paper, we rely on the tensorial formalism recently proposed to characterize and investigate this kind of complex topologies, and extend two well known random walk centrality measures, the random walk betweenness and closeness centrality, to interconnected multilayer networks. For each of the measures we provide analytical expressions that completely agree with numerically results.

  9. Random walk centrality in interconnected multilayer networks

    Solé-Ribalta, Albert; Gómez, Sergio; Arenas, Alex


    Real-world complex systems exhibit multiple levels of relationships. In many cases they require to be modeled as interconnected multilayer networks, characterizing interactions of several types simultaneously. It is of crucial importance in many fields, from economics to biology and from urban planning to social sciences, to identify the most (or the less) influential nodes in a network using centrality measures. However, defining the centrality of actors in interconnected complex networks is not trivial. In this paper, we rely on the tensorial formalism recently proposed to characterize and investigate this kind of complex topologies, and extend two well known random walk centrality measures, the random walk betweenness and closeness centrality, to interconnected multilayer networks. For each of the measures we provide analytical expressions that completely agree with numerically results.

  10. Environment-dependent continuous time random walk

    Lin Fang; Bao Jing-Dong


    A generalized continuous time random walk model which is dependent on environmental damping is proposed in which the two key parameters of the usual random walk theory:the jumping distance and the waiting time, are replaced by two new ones:the pulse velocity and the flight time. The anomalous diffusion of a free particle which is characterized by the asymptotical mean square displacement ~tα is realized numerically and analysed theoretically, where the value of the power index a is in a region of 0<α<2. Particularly, the damping leads to a sub-diffusion when the impact velocities are drawn from a Gaussian density function and the super-diffusive effect is related to statistical extremes, which are called rare-though-dominant events.

  11. Random Walk on the Prime Numbers

    The one-dimensional random walk (RW), where steps up and down are performed according to the occurrence of special primes is defined. Some quantities characterizing RW are investigated. The mean fluctuation function F(l) displays perfect power law dependence F(l) ∼ l1/2 indicating that the defined RW is not correlated. The number of returns of this special RW to the origin is investigated. It turns out, that this single, very special, realization of RW is typical one in the sense, that the usual characteristics used to measure RW, take the values close to the ones averaged over all random walks. The fractal structure on the subset of primes is also found. (author)

  12. Random Walk Picture of Basketball Scoring

    Gabel, Alan


    We present evidence, based on play-by-play data from all 6087 games from the 2006/07--2009/10 seasons of the National Basketball Association (NBA), that basketball scoring is well described by a weakly-biased continuous-time random walk. The time between successive scoring events follows an exponential distribution, with little memory between different scoring intervals. Using this random-walk picture that is augmented by features idiosyncratic to basketball, we account for a wide variety of statistical properties of scoring, such as the distribution of the score difference between opponents and the fraction of game time that one team is in the lead. By further including the heterogeneity of team strengths, we build a computational model that accounts for essentially all statistical features of game scoring data and season win/loss records of each team.

  13. Dynamic random walks theory and applications

    Guillotin-Plantard, Nadine


    The aim of this book is to report on the progress realized in probability theory in the field of dynamic random walks and to present applications in computer science, mathematical physics and finance. Each chapter contains didactical material as well as more advanced technical sections. Few appendices will help refreshing memories (if necessary!).· New probabilistic model, new results in probability theory· Original applications in computer science· Applications in mathematical physics· Applications in finance

  14. A Random Walk Picture of Basketball

    Gabel, Alan; Redner, Sidney


    We analyze NBA basketball play-by-play data and found that scoring is well described by a weakly-biased, anti-persistent, continuous-time random walk. The time between successive scoring events follows an exponential distribution, with little memory between events. We account for a wide variety of statistical properties of scoring, such as the distribution of the score difference between opponents and the fraction of game time that one team is in the lead.

  15. Directed Random Walk on the Lattices of Genus Two

    Nazarenko, A V


    The object of the present investigation is an ensemble of self-avoiding and directed graphs belonging to eight-branching Cayley tree (Bethe lattice) generated by the Fucsian group of a Riemann surface of genus two and embedded in the Pincar\\'e unit disk. We consider two-parametric lattices and calculate the multifractal scaling exponents for the moments of the graph lengths distribution as functions of these parameters. We show the results of numerical and statistical computations, where the latter are based on a random walk model.

  16. Deterministic Random Walks on Regular Trees

    Cooper, Joshua; Friedrich, Tobias; Spencer, Joel; 10.1002/rsa.20314


    Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid $\\Z^d$ and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips on this vertex deviates from the expected number the random walk would have gotten there by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite $k$-ary tree ($k \\ge 3$), we show that for any deviation $D$ there is an initial configuration of chips such that after running the Propp model for a ...

  17. Random walk search in unstructured P2P

    Jia Zhaoqing; You Jinyuan; Rao Ruonan; Li Minglu


    Unstructured P2P has power-law link distribution, and the random walk in power-law networks is analyzed. The analysis results show that the probability that a random walker walks through the high degree nodes is high in the power-law network, and the information on the high degree nodes can be easily found through random walk. Random walk spread and random walk search method (RWSS) is proposed based on the analysis result. Simulation results show that RWSS achieves high success rates at low cost and is robust to high degree node failure.

  18. Coupled continuous time random walks in finance

    Meerschaert, M M; Meerschaert, Mark M.; Scalas, Enrico


    Continuous time random walks (CTRWs) are used in physics to model anomalous diffusion, by incorporating a random waiting time between particle jumps. In finance, the particle jumps are log-returns and the waiting times measure delay between transactions. These two random variables (log-return and waiting time) are typically not independent. For these coupled CTRW models, we can now compute the limiting stochastic process (just like Brownian motion is the limit of a simple random walk), even in the case of heavy tailed (power-law) price jumps and/or waiting times. The probability density functions for this limit process solve fractional partial differential equations. In some cases, these equations can be explicitly solved to yield descriptions of long-term price changes, based on a high-resolution model of individual trades that includes the statistical dependence between waiting times and the subsequent log-returns. In the heavy tailed case, this involves operator stable space-time random vectors that genera...

  19. Relative Complexity of random walks in random sceneries

    Aaronson, Jon


    Relative complexity measures the complexity of a probability preserving transformation relative to a factor being a sequence of random variables whose exponential growth rate is the relative entropy of the extension. We prove distributional limit theorems for the relative complexity of certain zero entropy extensions: RWRSs whose associated random walks satisfy the alpha-stable CLT (alpha>1). The results give invariants for relative isomorphism of these.

  20. Random walk of passive tracers among randomly moving obstacles

    Gori, Matteo; Floriani, Elena; Nardecchia, Ilaria; Pettini, Marco


    Background: This study is mainly motivated by the need of understanding how the diffusion behaviour of a biomolecule (or even of a larger object) is affected by other moving macromolecules, organelles, and so on, inside a living cell, whence the possibility of understanding whether or not a randomly walking biomolecule is also subject to a long-range force field driving it to its target. Method: By means of the Continuous Time Random Walk (CTRW) technique the topic of random walk in random environment is here considered in the case of a passively diffusing particle in a crowded environment made of randomly moving and interacting obstacles. Results: The relevant physical quantity which is worked out is the diffusion cofficient of the passive tracer which is computed as a function of the average inter-obstacles distance. Coclusions: The results reported here suggest that if a biomolecule, let us call it a test molecule, moves towards its target in the presence of other independently interacting molecules, its m...

  1. On Polya-Friedman random walks

    Huillet, Thierry [Laboratoire de Physique Theorique et Modelisation, CNRS-UMR 8089 et Universite de Cergy-Pontoise, 2 Avenue Adolphe Chauvin, 95032, Cergy-Pontoise (France)], E-mail:


    The Polya process is an urn scheme arising in the context of contagion spreading. It exhibits unstable persistence effects. The Friedman urn process is dual to the Polya one with antipersistent stabilizing effects. It appears in a safety campaign problem. A Polya-Friedman urn process is investigated with a tuning persistence parameter extrapolating the latter two extreme processes. The study includes the diffusion approximations of both the Polya-Friedman proportion process and the population gap random walk. The structure of the former is a generalized Wright-Fisher diffusion appearing in population genetics. The correlation structure of the latter presents an anomalous character at a critical value of the persistence parameter.

  2. On Polya-Friedman random walks

    The Polya process is an urn scheme arising in the context of contagion spreading. It exhibits unstable persistence effects. The Friedman urn process is dual to the Polya one with antipersistent stabilizing effects. It appears in a safety campaign problem. A Polya-Friedman urn process is investigated with a tuning persistence parameter extrapolating the latter two extreme processes. The study includes the diffusion approximations of both the Polya-Friedman proportion process and the population gap random walk. The structure of the former is a generalized Wright-Fisher diffusion appearing in population genetics. The correlation structure of the latter presents an anomalous character at a critical value of the persistence parameter

  3. Cut Times for Simple Random Walk

    Lawler, Gregory


    Let $S(n)$ be a simple random walk taking values in $Z^d$. A time $n$ is called a cut time if \\[ S[0,n] \\cap S[n+1,\\infty) = \\emptyset . \\] We show that in three dimensions the number of cut times less than $n$ grows like $n^{1 - \\zeta}$ where $\\zeta = \\zeta_d$ is the intersection exponent. As part of the proof we show that in two or three dimensions \\[ P(S[0,n] \\cap S[n+1,2n] = \\emptyset ) \\sim n^{-\\zeta}, \\] where $\\sim$ denotes that each side is bounded by a constant times the other side.

  4. Random walk with an exponentially varying step

    de La Torre, A. C.; Maltz, A.; Mártin, H. O.; Catuogno, P.; García-Mata, I.


    A random walk with exponentially varying step, modeling damped or amplified diffusion, is studied. Each step is equal to the previous one multiplied by a step factor s (01/s relating different processes. For s2, the process is retrodictive (i.e., every final position can be reached by a unique path) and the set of all possible final points after infinite steps is fractal. For step factors in the interval [1/2,2], some cases result in smooth density distributions, other cases present overlapping self-similarity and there are values of the step factor for which the distribution is singular without a density function.

  5. Random walk immunization strategy on scale-free networks

    Weidong PEI; Zengqiang CHEN; Zhuzhi YUAN


    A novel immunization strategy called the random walk immunization strategy on scale-free networks is proposed. Different from other known immunization strategies, this strategy works as follows: a node is randomly chosen from the network. Starting from this node, randomly walk to one of its neighbor node; if the present node is not immunized, then immunize it and continue the random walk; otherwise go back to the previous node and randomly walk again. This process is repeated until a certain fraction of nodes is immunized. By theoretical analysis and numerical simulations, we found that this strategy is very effective in comparison with the other known immunization strategies.

  6. A family of self-avoiding random walks interpolating the loop-erased random walk and a self-avoiding walk on the Sierpinski gasket

    Hattori, Kumiko; Ogo, Noriaki; Otsuka, Takafumi


    We show that the `erasing-larger-loops-first' (ELLF) method, which was first introduced for erasing loops from the simple random walk on the Sierpinski gasket, does work also for non-Markov random walks, in particular, self-repelling walks to construct a new family of self-avoiding walks on the Sierpinski gasket. The one-parameter family constructed in this method continuously connects the loop-erased random walk and a self-avoiding walk which has the same asymptotic behavior as the `standard...

  7. The persistence length of two dimensional self avoiding random walks

    Eisenberg, E.; Baram, A.


    The decay of directional correlations in self-avoiding random walks on the square lattice is investigated. Analysis of exact enumerations and Monte Carlo data suggest that the correlation between the directions of the first step and the j-th step of the walk decays faster than 1/j, indicating that the persistence length of the walk is finite.

  8. The Not-so-Random Drunkard's Walk

    Ehrhardt, George


    This dataset contains the results of a quasi-experiment, testing Karl Pearson's "drunkard's walk" analogy for an abstract random walk. Inspired by the alternate hypothesis that drunkards stumble to the side of their dominant hand, it includes data on intoxicated test subjects walking a 10' line. Variables include: the…

  9. Self-Attractive Random Walks: The Case of Critical Drifts

    Ioffe, Dmitry; Velenik, Yvan


    Self-attractive random walks (polymers) undergo a phase transition in terms of the applied drift (force): If the drift is strong enough, then the walk is ballistic, whereas in the case of small drifts self-attraction wins and the walk is sub-ballistic. We show that, in any dimension d ≥ 2, this transition is of first order. In fact, we prove that the walk is already ballistic at critical drifts, and establish the corresponding LLN and CLT.

  10. Self-Attractive Random Walks: The Case of Critical Drifts

    Ioffe, Dmitry


    Self-attractive random walks undergo a phase transition in terms of the applied drift: If the drift is strong enough, then the walk is ballistic, whereas in the case of small drifts self-attraction wins and the walk is sub-ballistic. We show that, in any dimension at least 2, this transition is of first order. In fact, we prove that the walk is already ballistic at critical drifts, and establish the corresponding LLN and CLT.

  11. Understanding deterministic diffusion by correlated random walks

    Low-dimensional periodic arrays of scatterers with a moving point particle are ideal models for studying deterministic diffusion. For such systems the diffusion coefficient is typically an irregular function under variation of a control parameter. Here we propose a systematic scheme of how to approximate deterministic diffusion coefficients of this kind in terms of correlated random walks. We apply this approach to two simple examples which are a one-dimensional map on the line and the periodic Lorentz gas. Starting from suitable Green-Kubo formulae we evaluate hierarchies of approximations for their parameter-dependent diffusion coefficients. These approximations converge exactly yielding a straightforward interpretation of the structure of these irregular diffusion coefficients in terms of dynamical correlations. (author)

  12. Renewal theorems for random walks in random scenery

    Guillotin-Plantard, Nadine


    Random walks in random scenery are processes defined by $Z_n:=\\sum_{k=1}^n\\xi_{X_1+...+X_k}$, where $(X_k,k\\ge 1)$ and $(\\xi_y,y\\in\\mathbb Z)$ are two independent sequences of i.i.d. random variables. We suppose that the distributions of $X_1$ and $\\xi_0$ belong to the normal domain of attraction of strictly stable distributions with index $\\alpha\\in[1,2]$ and $\\beta\\in(0,2)$ respectively. We are interested in the asymptotic behaviour as $|a|$ goes to infinity of quantities of the form $\\sum_{n\\ge 1}{\\mathbb E}[h(Z_n-a)]$ (when $(Z_n)_n$ is transient) or $\\sum_{n\\ge 1}{\\mathbb E}[h(Z_n)-h(Z_n-a)]$ (when $(Z_n)_n$ is recurrent) where $h$ is some complex-valued function defined on $\\mathbb{R}$ or $\\mathbb{Z}$.

  13. The parabolic Anderson model random walk in random potential

    König, Wolfgang


    This is a comprehensive survey on the research on the parabolic Anderson model – the heat equation with random potential or the random walk in random potential – of the years 1990 – 2015. The investigation of this model requires a combination of tools from probability (large deviations, extreme-value theory, e.g.) and analysis (spectral theory for the Laplace operator with potential, variational analysis, e.g.). We explain the background, the applications, the questions and the connections with other models and formulate the most relevant results on the long-time behavior of the solution, like quenched and annealed asymptotics for the total mass, intermittency, confinement and concentration properties and mass flow. Furthermore, we explain the most successful proof methods and give a list of open research problems. Proofs are not detailed, but concisely outlined and commented; the formulations of some theorems are slightly simplified for better comprehension.

  14. Random walk models for top-N recommendation task

    Yin ZHANG; Jiang-qin WU; Yue-ting ZHUANG


    Recently there has been an increasing interest in applying random walk based methods to recommender systems.We employ a Gaussian random field to model the top-N recommendation task as a semi-supervised learning problem.taking into account the degree of each node on the user-item bipartite graph,and induce an effective absorbing random walk (ARW) algorithm for the top-N recommendation task.Our random walk approach directly generates the top-N recommendations for individuals,rather than predicting the ratings of the recommendations.Experimental results on the two real data sets show that our random walk algorithm significantly outperforms the state-of-the-art random walk based personalized ranking algorithm as well as the popular item-based collaborative filtering method.

  15. Behavior of random walk on discrete point processes

    Berger, Noam


    We consider a model for random walks on random environments (RWRE) with random subset of Z^d as the vertices, and uniform transition probabilities on 2d points (two "coordinate nearest points" in each of the d coordinate directions). We give partial characterization of transience and recurrence in the different dimensions. Finally we prove Central Limit Theorem (CLT) for such random walks, under a condition on the distance between coordinate nearest points.

  16. Pseudo memory effects, majorization and entropy in quantum random walks

    Bracken, Anthony J [Centre for Mathematical Physics and Department of Mathematics, University of Queensland, Brisbane 4072 (Australia); Ellinas, Demosthenes [Division of Mathematics, Technical University of Crete, GR-73100 Chania Crete (Greece); Tsohantjis, Ioannis [Division of Physics, Technical University of Crete, GR-73100 Chania Crete (Greece)


    A quantum random walk on the integers exhibits pseudo memory effects, in that its probability distribution after N steps is determined by reshuffling the first N distributions that arise in a classical random walk with the same initial distribution. In a classical walk, entropy increase can be regarded as a consequence of the majorization ordering of successive distributions. The Lorenz curves of successive distributions for a symmetric quantum walk reveal no majorization ordering in general. Nevertheless, entropy can increase, and computer experiments show that it does so on average. Varying the stages at which the quantum coin system is traced out leads to new quantum walks, including a symmetric walk for which majorization ordering is valid but the spreading rate exceeds that of the usual symmetric quantum walk. (letter to the editor)

  17. Pseudo Memory Effects, Majorization and Entropy in Quantum Random Walks

    Bracken, A J; Tsohantjis, I; Bracken, Anthony J.; Ellinas, Demosthenes; Tsohantjis, Ioannis


    A quantum random walk on the integers exhibits pseudo memory effects, in that its probability distribution after N steps is determined by reshuffling the first N distributions that arise in a classical random walk with the same initial distribution. In a classical walk, entropy increase can be regarded as a consequence of the majorization ordering of successive distributions. The Lorenz curves of successive distributions for a symmetric quantum walk reveal no majorization ordering in general. Nevertheless, entropy can increase, and computer experiments show that it does so on average. Varying the stages at which the quantum coin system is traced out leads to new quantum walks, including a symmetric walk for which majorization ordering is valid but the spreading rate exceeds that of the usual symmetric quantum walk.

  18. Random walk in dynamically disordered chains: Poisson white noise disorder

    Exact solutions are given for a variety of models of random walks in a chain with time-dependent disorder. Dynamic disorder is modeled by white Poisson noise. Models with site-independent (global) and site-dependent (local) disorder are considered. Results are described in terms of an affective random walk in a nondisordered medium. In the cases of global disorder the effective random walk contains multistep transitions, so that the continuous limit is not a diffusion process. In the cases of local disorder the effective process is equivalent to usual random walk in the absence of disorder but with slower diffusion. Difficulties associated with the continuous-limit representation of random walk in a disordered chain are discussed. In particular, the authors consider explicit cases in which taking the continuous limit and averaging over disorder sources do not commute

  19. Near-Optimal Random Walk Sampling in Distributed Networks

    Sarma, Atish Das; Pandurangan, Gopal


    Performing random walks in networks is a fundamental primitive that has found numerous applications in communication networks such as token management, load balancing, network topology discovery and construction, search, and peer-to-peer membership management. While several such algorithms are ubiquitous, and use numerous random walk samples, the walks themselves have always been performed naively. In this paper, we focus on the problem of performing random walk sampling efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds and messages required to obtain several random walk samples in a continuous online fashion. We present the first round and message optimal distributed algorithms that present a significant improvement on all previous approaches. The theoretical analysis and comprehensive experimental evaluation of our algorithms show that they perform very well in different types of networks of differing topologies. In particular, our results show h...

  20. Random walk in random environment in a two-dimensional stratified medium with orientations

    Devulder, Alexis


    We consider a model of random walk in ${\\mathbb Z}^2$ with (fixed or random) orientation of the horizontal lines (layers) and with iid probability to stay on these lines. We prove the transience of the walk for any fixed orientations under general hypotheses. We also establish a result of convergence in distribution for this walk with suitable normalizations under more precise assumptions.

  1. Painting a Graph with Competing Random Walks

    Miller, Jason


    Let $X_1, X_2$ be independent random walks on $\\Z_n^d$, $d \\geq 3$, each starting from the uniform distribution. Initially, each site of $\\Z_n^d$ is unmarked and, whenever $X_i$ visits such a site, it is set irreversibly to $i$. The mean of $|\\CA_i|$, the cardinality of the set $\\CA_i$ of sites painted by $i$ once all of $\\Z_n^d$ has been visited, is $n^d/2$ by symmetry. We prove the following conjecture due to Pemantle and Peres: for each $d \\geq 3$ there exists a constant $\\alpha_d$ such that $\\lim_{n \\to \\infty} \\var(|\\CA_i|) / h_d(n) = \\tfrac{1}{4}\\alpha_d$ where $h_3(n) = n^4$, $h_4(n) = n^4 (\\log n)$, and $h_d(n) = n^d$ for $d \\geq 5$. We will also identify $\\alpha_d$ explicitly. This is a special case of a more general theorem which gives the asymptotics of $\\var(|\\CA_i|)$ for a large class of transient, vertex transitive graphs; other examples include the hypercube and the Caley graph of the symmetric group generated by transpositions.

  2. My Random Walks in Anderson's Garden

    Baskaran, G


    Anderson's Garden is a drawing presented to Philip W. Anderson on the eve of his 60th birthday celebration, in 1983. This cartoon (Fig. 1), whose author is unknown, succinctly depicts some of Anderson's pre-1983 works, as a blooming garden. As an avid reader of Anderson's papers, random walk in Anderson's garden had become a part of my routine since graduate school days. This was of immense help and prepared me for a wonderful collaboration with the gardener himself, on the resonating valence bond (RVB) theory of High Tc cuprates and quantum spin liquids, at Princeton. The result was bountiful - the first (RVB mean field) theory for i) quantum spin liquids, ii) emergent fermi surfaces in Mott insulators and iii) superconductivity in doped Mott insulators. Beyond mean field theory - i) emergent gauge fields, ii) Ginzbuerg Landau theory with RVB gauge fields, iii) prediction of superconducting dome, iv) an early identification and study of a non-fermi liquid normal state of cuprates and so on. Here I narrate th...

  3. The quenched invariance principle for random walks in random environments admitting a bounded cycle representation

    Deuschel, Jean-Dominique; Kösters, Holger


    We derive a quenched invariance principle for random walks in random environments whose transition probabilities are defined in terms of weighted cycles of bounded length. To this end, we adapt the proof for random walks among random conductances by Sidoravicius and Sznitman (Probab. Theory Related Fields 129 (2004) 219--244) to the non-reversible setting.

  4. Directed self-avoiding walks on a randomly dilute lattice

    Nadal, J.P.; Vannimenus, J.


    We consider a model of Directed Self-Avoiding Walks (DSAW) on a dilute lattice, using various approaches (Cayley Tree, weak-disorder expansion, Monte-Carlo generation of walks up to 2 000 steps). This simple model appears to contain the essential features of the controversial problem of self-avoiding walks in a random medium. It is shown in particular that with any amount of disorder the mean value for the number of DSAW is different from its most probable value.

  5. Quantum random walk in periodic potential on a line

    Li, Min; Zhang, Yong-Sheng; Guo, Guang-Can


    We investigated the discrete-time quantum random walks on a line in periodic potential. The probability distribution with periodic potential is more complex compared to the normal quantum walks, and the standard deviation $\\sigma$ has interesting behaviors for different period $q$ and parameter $\\theta$. We studied the behavior of standard deviation with variation in walk steps, period, and $\\theta$. The standard deviation increases approximately linearly with $\\theta$ and decreases with $1/q...

  6. Random walks on the BMW monoid: an algebraic approach

    Wolff, Sarah


    We consider Metropolis-based systematic scan algorithms for generating Birman-Murakami-Wenzl (BMW) monoid basis elements of the BMW algebra. As the BMW monoid consists of tangle diagrams, these scanning strategies can be rephrased as random walks on links and tangles. We translate these walks into left multiplication operators in the corresponding BMW algebra. Taking this algebraic perspective enables the use of tools from representation theory to analyze the walks; in particular, we develop ...

  7. Algebraic area enclosed by random walks on a lattice

    Desbois, Jean


    We compute the moments ≤ft of the area enclosed by an N-steps random walk on a 2D lattice. We consider separately the cases where the walk comes back to the origin or not. We also compute, for both cases, the characteristic function ≤ft at order 1/{N}2.

  8. Variational data assimilation using targetted random walks

    Cotter, S. L.


    The variational approach to data assimilation is a widely used methodology for both online prediction and for reanalysis. In either of these scenarios, it can be important to assess uncertainties in the assimilated state. Ideally, it is desirable to have complete information concerning the Bayesian posterior distribution for unknown state given data. We show that complete computational probing of this posterior distribution is now within the reach in the offline situation. We introduce a Markov chain-Monte Carlo (MCMC) method which enables us to directly sample from the Bayesian posterior distribution on the unknown functions of interest given observations. Since we are aware that these methods are currently too computationally expensive to consider using in an online filtering scenario, we frame this in the context of offline reanalysis. Using a simple random walk-type MCMC method, we are able to characterize the posterior distribution using only evaluations of the forward model of the problem, and of the model and data mismatch. No adjoint model is required for the method we use; however, more sophisticated MCMC methods are available which exploit derivative information. For simplicity of exposition, we consider the problem of assimilating data, either Eulerian or Lagrangian, into a low Reynolds number flow in a two-dimensional periodic geometry. We will show that in many cases it is possible to recover the initial condition and model error (which we describe as unknown forcing to the model) from data, and that with increasing amounts of informative data, the uncertainty in our estimations reduces. © 2011 John Wiley & Sons, Ltd.

  9. A scaling law for random walks on networks

    Perkins, Theodore J.; Foxall, Eric; Glass, Leon; Edwards, Roderick


    The dynamics of many natural and artificial systems are well described as random walks on a network: the stochastic behaviour of molecules, traffic patterns on the internet, fluctuations in stock prices and so on. The vast literature on random walks provides many tools for computing properties such as steady-state probabilities or expected hitting times. Previously, however, there has been no general theory describing the distribution of possible paths followed by a random walk. Here, we show that for any random walk on a finite network, there are precisely three mutually exclusive possibilities for the form of the path distribution: finite, stretched exponential and power law. The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution. We use our theory to explain path distributions in domains such as sports, music, nonlinear dynamics and stochastic chemical kinetics.

  10. Large deviations for random walk in a random environment

    Yilmaz, Atilla


    In this work, we study the large deviation properties of random walk in a random environment on $\\mathbb{Z}^d$ with $d\\geq1$. We start with the quenched case, take the point of view of the particle, and prove the large deviation principle (LDP) for the pair empirical measure of the environment Markov chain. By an appropriate contraction, we deduce the quenched LDP for the mean velocity of the particle and obtain a variational formula for the corresponding rate function $I_q$. We propose an Ansatz for the minimizer of this formula. This Ansatz is easily verified when $d=1$. In his 2003 paper, Varadhan proves the averaged LDP for the mean velocity and gives a variational formula for the corresponding rate function $I_a$. Under the non-nestling assumption (resp. Kalikow's condition), we show that $I_a$ is strictly convex and analytic on a non-empty open set $\\mathcal{A}$, and that the true velocity $\\xi_o$ is an element (resp. in the closure) of $\\mathcal{A}$. We then identify the minimizer of Varadhan's variati...

  11. Implement Quantum Random Walks with Linear Optics Elements

    Zhao, Zhi; Du, Jiangfeng; Li, Hui; Yang, Tao; Chen, Zeng-Bing; Pan, Jian-Wei


    The quantum random walk has drawn special interests because its remarkable features to the classical counterpart could lead to new quantum algorithms. In this paper, we propose a feasible scheme to implement quantum random walks on a line using only linear optics elements. With current single-photon interference technology, the steps that could be experimentally implemented can be extended to very large numbers. We also show that, by decohering the quantum states, our scheme for quantum rando...

  12. Improving Random Walk Estimation Accuracy with Uniform Restarts

    Avrachenkov, Konstantin; Ribeiro, Bruno; Towsley, Don


    This work proposes and studies the properties of a hybrid sampling scheme that mixes independent uniform node sampling and random walk (RW)-based crawling. We show that our sampling method combines the strengths of both uniform and RW sampling while minimizing their drawbacks. In particular, our method increases the spectral gap of the random walk, and hence, accelerates convergence to the stationary distribution. The proposed method resembles PageRank but unlike PageRank preserves time-rever...

  13. Convergence of a random walk method for the Burgers equation

    In this paper we consider a random walk algorithm for the solution of Burgers' equation. The algorithm uses the method of fractional steps. The non-linear advection term of the equation is solved by advecting ''fluid'' particles in a velocity field induced by the particles. The diffusion term of the equation is approximated by adding an appropriate random perturbation to the positions of the particles. Though the algorithm is inefficient as a method for solving Burgers' equation, it does model a similar method, the random vortex method, which has been used extensively to solve the incompressible Navier-Stokes equations. The purpose of this paper is to demonstrate the strong convergence of our random walk method and so provide a model for the proof of convergence for more complex random walk algorithms; for instance, the random vortex method without boundaries

  14. A conditional quenched CLT for random walks among random conductances on $\\mathbb{Z}^d$

    Gallesco, Christophe; Popov, Serguei; Vachkovskaia, Marina


    Consider a random walk among random conductances on $\\mathbb{Z}^d$ with $d\\geq 2$. We study the quenched limit law under the usual diffusive scaling of the random walk conditioned to have its first coordinate positive. We show that the conditional limit law is the product of a Brownian meander and a $(d-1)$-dimensional Brownian motion.

  15. Statistics of branched flow in a weak correlated random potential

    Kaplan, Lev


    Recent images of electron flow through a two-dimensional electron gas (2DEG) device show branching behavior that is reproduced in numerical simulations of motion in a correlated random potential [cond-mat/0010348]. We show how such branching naturally arises from caustics in the classical flow and find a simple scaling behavior of the branching under variation of the random potential strength. Analytic results describing the statistical properties of the branching are confirmed by classical a...

  16. Search for Directed Networks by Different Random Walk Strategies

    ZHU Zi-Qi; JIN Xiao-Ling; HUANG Zhi-Long


    A comparative study is carried out on the effciency of five different random walk strategies searching on directed networks constructed based on several typical complex networks.Due to the difference in search effciency of the strategies rooted in network clustering,the clustering coeFfcient in a random walker's eye on directed networks is defined and computed to be half of the corresponding undirected networks.The search processes are performed on the directed networks based on Erd(o)s-Rényi model,Watts-Strogatz model,Barabási-Albert model and clustered scale-free network model.It is found that self-avoiding random walk strategy is the best search strategy for such directed networks.Compared to unrestricted random walk strategy,path-iteration-avoiding random walks can also make the search process much more effcient. However,no-triangle-loop and no-quadrangle-loop random walks do not improve the search effciency as expected,which is different from those on undirected networks since the clustering coefficient of directed networks are smaller than that of undirected networks.

  17. A New Random Walk for Replica Detection in WSNs.

    Aalsalem, Mohammed Y; Khan, Wazir Zada; Saad, N M; Hossain, Md Shohrab; Atiquzzaman, Mohammed; Khan, Muhammad Khurram


    Wireless Sensor Networks (WSNs) are vulnerable to Node Replication attacks or Clone attacks. Among all the existing clone detection protocols in WSNs, RAWL shows the most promising results by employing Simple Random Walk (SRW). More recently, RAND outperforms RAWL by incorporating Network Division with SRW. Both RAND and RAWL have used SRW for random selection of witness nodes which is problematic because of frequently revisiting the previously passed nodes that leads to longer delays, high expenditures of energy with lower probability that witness nodes intersect. To circumvent this problem, we propose to employ a new kind of constrained random walk, namely Single Stage Memory Random Walk and present a distributed technique called SSRWND (Single Stage Memory Random Walk with Network Division). In SSRWND, single stage memory random walk is combined with network division aiming to decrease the communication and memory costs while keeping the detection probability higher. Through intensive simulations it is verified that SSRWND guarantees higher witness node security with moderate communication and memory overheads. SSRWND is expedient for security oriented application fields of WSNs like military and medical. PMID:27409082

  18. First steps in random walks from tools to applications

    Klafter, J


    The name ""random walk"" for a problem of a displacement of a point in a sequence of independent random steps was coined by Karl Pearson in 1905 in a question posed to readers of ""Nature"". The same year, a similar problem was formulated by Albert Einstein in one of his Annus Mirabilis works. Even earlier such a problem was posed by Louis Bachelier in his thesis devoted to the theory of financial speculations in 1900. Nowadays the theory of random walks has proved useful in physics andchemistry (diffusion, reactions, mixing in flows), economics, biology (from animal spread to motion of subcel

  19. Random walk in random environment in a two-dimensional stratified medium with orientations

    Devulder, Alexis; Pene, Francoise


    We consider a model of random walk in ${\\mathbb Z}^2$ with (fixed or random) orientation of the horizontal lines (layers) and with non constant iid probability to stay on these lines. We prove the transience of the walk for any fixed orientations under general hypotheses. This contrasts with the model of Campanino and Petritis, in which probabilities to stay on these lines are all equal. We also establish a result of convergence in distribution for this walk with suitable normalizations under...

  20. Riemann Hypothesis and Random Walks: the Zeta case

    LeClair, André


    In previous work it was shown that if certain series based on sums over primes of non-principal Dirichlet characters have a conjectured random walk behavior, then the Euler product formula for its $L$-function is valid to the right of the critical line $\\Re (s) > 1/2$, and the Riemann Hypothesis for this class of $L$-functions follows. Building on this work, here we propose how to extend this line of reasoning to the Riemann zeta function and other principal Dirichlet $L$-functions. We use our results to argue that $ S_\\delta (t) \\equiv \\lim_{\\delta \\to 0^+} \\dfrac{1}{\\pi} \\arg \\zeta (\\tfrac{1}{2}+ \\delta + i t ) = O(1)$, and that it is nearly always on the principal branch. We conjecture that a 1-point correlation function of the Riemann zeros has a normal distribution. This leads to the construction of a probabilistic model for the zeros. Based on these results we describe a new algorithm for computing very high Riemann zeros as a kind of stochastic process, and we calculate the $10^{100}$-th zero to over 1...

  1. The Cover Time of Deterministic Random Walks for General Transition Probabilities

    Shiraga, Takeharu


    The deterministic random walk is a deterministic process analogous to a random walk. While there are some results on the cover time of the rotor-router model, which is a deterministic random walk corresponding to a simple random walk, nothing is known about the cover time of deterministic random walks emulating general transition probabilities. This paper is concerned with the SRT-router model with multiple tokens, which is a deterministic process coping with general transition probabilities ...

  2. Generalized Quantum Random Walk in Momentum Space

    Romanelli, A; Siri, R; Abal, G; Donangelo, R


    We introduce a discrete-time quantum walk on a one-dimensional momentum space including both discrete jumps and continuous drift. Its time evolution has two diferent stages. Initially a Markovian diffusion develops during a characteristic time interval, after which dynamical localization sets in, as in the well known Quantum Kicked Rotor system. For some exceptional values of the model's parameter the system exhibits resonant behavior and the system model behaves as the standard discrete time quantum walker on the line.

  3. Continuous time `true' self-avoiding random walk on Z

    Toth, Balint


    We consider the continuous time version of the `true' or `myopic' self-avoiding random walk with site repulsion in 1d. The Ray-Knight-type method which was applied to the discrete time and edge repulsion case, is applicable to this model with some modifications. We present a limit theorem for the local time of the walk and a local limit theorem for the displacement.

  4. Tail estimates for one-dimensional non-nearest-neighbor random walk in random environment


    Suppose that the integers are assigned i.i.d. random variables {(β gx , . . . , β 1x , α x )} (each taking values in the unit interval and the sum of them being 1), which serve as an environment. This environment defines a random walk {X n } (called RWRE) which, when at x, moves one step of length 1 to the right with probability α x and one step of length k to the left with probability β kx for 1≤ k≤ g. For certain environment distributions, we determine the almost-sure asymptotic speed of the RWRE and show that the chance of the RWRE deviating below this speed has a polynomial rate of decay. This is the generalization of the results by Dembo, Peres and Zeitouni in 1996. In the proof we use a large deviation result for the product of random matrices and some tail estimates and moment estimates for the total population size in a multi-type branching process with random environment.

  5. Visual Tracking via Random Walks on Graph Model.

    Li, Xiaoli; Han, Zhifeng; Wang, Lijun; Lu, Huchuan


    In this paper, we formulate visual tracking as random walks on graph models with nodes representing superpixels and edges denoting relationships between superpixels. We integrate two novel graphs with the theory of Markov random walks, resulting in two Markov chains. First, an ergodic Markov chain is enforced to globally search for the candidate nodes with similar features to the template nodes. Second, an absorbing Markov chain is utilized to model the temporal coherence between consecutive frames. The final confidence map is generated by a structural model which combines both appearance similarity measurement derived by the random walks and internal spatial layout demonstrated by different target parts. The effectiveness of the proposed Markov chains as well as the structural model is evaluated both qualitatively and quantitatively. Experimental results on challenging sequences show that the proposed tracking algorithm performs favorably against state-of-the-art methods. PMID:26292358

  6. Limited Random Walk Algorithm for Big Graph Data Clustering

    Zhang, Honglei; Kiranyaz, Serkan; Gabbouj, Moncef


    Graph clustering is an important technique to understand the relationships between the vertices in a big graph. In this paper, we propose a novel random-walk-based graph clustering method. The proposed method restricts the reach of the walking agent using an inflation function and a normalization function. We analyze the behavior of the limited random walk procedure and propose a novel algorithm for both global and local graph clustering problems. Previous random-walk-based algorithms depend on the chosen fitness function to find the clusters around a seed vertex. The proposed algorithm tackles the problem in an entirely different manner. We use the limited random walk procedure to find attracting vertices in a graph and use them as features to cluster the vertices. According to the experimental results on the simulated graph data and the real-world big graph data, the proposed method is superior to the state-of-the-art methods in solving graph clustering problems. Since the proposed method uses the embarrass...

  7. On a zero-drift nearest-neighbour random walk

    Cohen, J.W.


    The present study concerns the analysis of the hitting point identity for a nearest-neighbour random walk of which the one-step transition to the $NE$, $SE$, $SW$ and $NW$ are the only transitions with nonzero probabilities. The one-step transition vector has a symmetrical probability distribution with zero drifts. The state space of the random walk is the set of lattice points in the first quarter plane, the point at the coordinate axes are all absorbing states. The distribution of the hitti...

  8. Image segmentation using random-walks on the histogram

    Morin, Jean-Philippe; Desrosiers, Christian; Duong, Luc


    This document presents a novel method for the problem of image segmentation, based on random-walks. This method shares similarities with the Mean-shift algorithm, as it finds the modes of the intensity histogram of images. However, unlike Mean-shift, our proposed method is stochastic and also provides class membership probabilities. Also, unlike other random-walk based methods, our approach does not require any form of user interaction, and can scale to very large images. To illustrate the usefulness, efficiency and scalability of our method, we test it on the task of segmenting anatomical structures present in cardiac CT and brain MRI images.

  9. Application of continuous-time random walk to statistical arbitrage

    Sergey Osmekhin


    Full Text Available An analytical statistical arbitrage strategy is proposed, where the distribution of the spread is modelled as a continuous-time random walk. Optimal boundaries, computed as a function of the mean and variance of the firstpassage time ofthe spread,maximises an objective function. The predictability of the trading strategy is analysed and contrasted for two forms of continuous-time random walk processes. We found that the waiting-time distribution has a significant impact on the prediction of the expected profit for intraday trading

  10. Non-Gaussian propagator for elephant random walks

    da Silva, M. A. A.; Cressoni, J. C.; Schütz, Gunter M.; Viswanathan, G. M.; Trimper, Steffen


    For almost a decade the consensus has held that the random walk propagator for the elephant random walk (ERW) model is a Gaussian. Here we present strong numerical evidence that the propagator is, in general, non-Gaussian and, in fact, non-Lévy. Motivated by this surprising finding, we seek a second, non-Gaussian solution to the associated Fokker-Planck equation. We prove mathematically, by calculating the skewness, that the ERW Fokker-Planck equation has a non-Gaussian propagator for the superdiffusive regime. Finally, we discuss some unusual aspects of the propagator in the context of higher order terms needed in the Fokker-Planck equation.

  11. A local limit theorem for random walks in random scenery and on randomly oriented lattices

    Castell, Fabienne; Pène, Françoise; Schapira, Bruno


    Random walks in random scenery are processes defined by $Z_n:=\\sum_{k=1}^n\\xi_{X_1+...+X_k}$, where $(X_k,k\\ge 1)$ and $(\\xi_y,y\\in\\mathbb Z)$ are two independent sequences of i.i.d. random variables. We assume here that their distributions belong to the normal domain of attraction of stable laws with index $\\alpha\\in (0,2]$ and $\\beta\\in (0,2]$ respectively. These processes were first studied by H. Kesten and F. Spitzer, who proved the convergence in distribution when $\\alpha\

  12. A family of random walks with generalized Dirichlet steps

    We analyze a class of continuous time random walks in Rd,d≥2, with uniformly distributed directions. The steps performed by these processes are distributed according to a generalized Dirichlet law. Given the number of changes of orientation, we provide the analytic form of the probability density function of the position (Xd(t),t>0) reached, at time t > 0, by the random motion. In particular, we analyze the case of random walks with two steps. In general, it is a hard task to obtain the explicit probability distributions for the process (Xd(t),t>0). Nevertheless, for suitable values for the basic parameters of the generalized Dirichlet probability distribution, we are able to derive the explicit conditional density functions of (Xd(t),t>0). Furthermore, in some cases, by exploiting the fractional Poisson process, the unconditional probability distributions of the random walk are obtained. This paper extends in a more general setting, the random walks with Dirichlet displacements introduced in some previous papers

  13. Number variance for hierarchical random walks and related fluctuations

    Bojdecki, Tomasz; Talarczyk, Anna


    We study an infinite system of independent symmetric random walks on a hierarchical group, in particular, the c-random walks. Such walks are used, e.g., in population genetics. The number variance problem consists in investigating if the variance of the number of "particles" N_n(L) lying in the ball of radius L at a given time n remains bounded, or even better, converges to a finite limit, as $L\\to \\infty$. We give a necessary and sufficient condition and discuss its relationship to transience/recurrence property of the walk. Next we consider normalized fluctuations of N_n(L) around the mean as $n\\to \\infty$ and L is increased in an appropriate way. We prove convergence of finite dimensional distributions to a Gaussian process whose properties are discussed. As the c-random walks mimic symmetric stable processes on R, we compare our results to those obtained by Hambly and Jones (2007,2009), where the number variance problem for an infinite system of symmetric stable processes on R was studied. Since the hiera...

  14. Directed self-avoiding walks in random media

    Two types of directed self-avoiding walks (SAW's), namely, three-choice directed SAW and outwardly directed SAW, have been studied on infinite percolation clusters on the square lattice in two dimensions. The walks on the percolation clusters are generated via a Monte Carlo technique. The longitudinal extension RN and the transverse fluctuation WN have been measured as a function of the number of steps N. Slight swelling is observed in the longitudinal direction on the random lattices. A crossover from shrinking to swelling of the transverse fluctuations is found at a certain length Nc of the walks. The exponents related to the transverse fluctuations are seen to be unchanged in the random media even as the percolation threshold is reached. The scaling function form of the extensions are verified

  15. Measuring the fractal dimension of an optical random walk

    Savo, Romolo; Svensson, Tomas; Vynck, Kevin; Wiersma, Diederik S


    Random walks often grasp the essence of transport processes in complex systems, representing a model for a large variety of phenomena, from human travel, to molecular kinetics, to the propagation of light and sound in disordered media. Transport is generally driven by the topology of the system, which can range from a simply random distribution of scattering elements, to very rich self-similar structures like random fractals. In this context the fractal dimension of the random walk trajectory, $d_\\mathrm{w}$, crucially determines the nature of the resulting transport process and provides information on the way the spatial evolution scales with time. In living cells and turbulent flow it has been possible to study anomalous dynamics showing $d_\\mathrm{w}\

  16. Killed multidimensional random walks and multinomial sequential estimation

    Bibbona, Enrico


    A sufficient condition for the uniqueness of multinomial sequential unbiased estimators is provided generalizing a classical result for binomial samples. Unbiased estimators are applied to infer the parameters of multidimensional or multinomial random walks which are observed until they reach a boundary.

  17. States recognition in random walk Markov chain via binary Entropy

    Morteza Khodabin


    Full Text Available In this paper, a new method for specification of recurrence or transient of states in one and two dimensional simple random walk based on upper and lower bounds of {it r}-combinations from a set of m elements $(C^{m}_{r}$ via binary entropy is introduced.

  18. Adaptive importance sampling of random walks on continuous state spaces

    The authors consider adaptive importance sampling for a random walk with scoring in a general state space. Conditions under which exponential convergence occurs to the zero-variance solution are reviewed. These results generalize previous work for finite, discrete state spaces in Kollman (1993) and in Kollman, Baggerly, Cox, and Picard (1996). This paper is intended for nonstatisticians and includes considerable explanatory material

  19. On the critical exponent for random walk intersections

    The exponent ζd for the probability of nonintersection of 2 random walks starting at the same point is considered. It is proved that 1/2 2 ≤ 3/4. Monte Carlo simulations are done to suggest ζ2 = 0.61 hor-ellipsis and ζ3 ∼ 0.29

  20. On the recurrence set of planar Markov Random Walks

    Hervé, Loïc


    In this paper, we investigate the properties of recurrent planar Markov random walks. More precisely, we study the set of recurrent points with the use of local limit theorems. The Nagaev-Guivarc'h spectral method provides several examples for which these local limit theorems are satisfied as soon as the (standard or non-standard) central limit theorem holds.

  1. Quantum random walk approximation on locally compact quantum groups

    Lindsay, J Martin; Skalski, Adam G.


    A natural scheme is established for the approximation of quantum Levy 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.

  2. Inference of random walk models to describe leukocyte migration

    Jones, Phoebe J. M.; Sim, Aaron; Taylor, Harriet B.; Bugeon, Laurence; Dallman, Magaret J.; Pereira, Bernard; Stumpf, Michael P. H.; Liepe, Juliane


    While the majority of cells in an organism are static and remain relatively immobile in their tissue, migrating cells occur commonly during developmental processes and are crucial for a functioning immune response. The mode of migration has been described in terms of various types of random walks. To understand the details of the migratory behaviour we rely on mathematical models and their calibration to experimental data. Here we propose an approximate Bayesian inference scheme to calibrate a class of random walk models characterized by a specific, parametric particle re-orientation mechanism to observed trajectory data. We elaborate the concept of transition matrices (TMs) to detect random walk patterns and determine a statistic to quantify these TM to make them applicable for inference schemes. We apply the developed pipeline to in vivo trajectory data of macrophages and neutrophils, extracted from zebrafish that had undergone tail transection. We find that macrophage and neutrophils exhibit very distinct biased persistent random walk patterns, where the strengths of the persistence and bias are spatio-temporally regulated. Furthermore, the movement of macrophages is far less persistent than that of neutrophils in response to wounding.

  3. Averaging in SU(2) open quantum random walk

    Clement, Ampadu


    We study the average position and the symmetry of the distribution in the SU(2) open quantum random walk (OQRW). We show that the average position in the central limit theorem (CLT) is non-uniform compared with the average position in the non-CLT. The symmetry of distribution is shown to be even in the CLT.

  4. Averaging in SU(2) open quantum random walk

    We study the average position and the symmetry of the distribution in the SU(2) open quantum random walk (OQRW). We show that the average position in the central limit theorem (CLT) is non-uniform compared with the average position in the non-CLT. The symmetry of distribution is shown to be even in the CLT

  5. Movie Recommendation using Random Walks over the Contextual Graph

    Bogers, Toine

    algorithm that makes it easy to include different types of contextual information. It models the browsing process of a user on a movie database website by taking random walks over the contextual graph. We present our approach in this paper and highlight a number of future extensions with additional...

  6. One-Dimensional Random Walks with One-Step Memory

    Piaskowski, Kevin; Nolan, Michael


    Formalized studies of random walks have been done dating back to the early 20th century. Since then, well-defined conclusions have been drawn, specifically in the case of one and two-dimensional random walks. An important theorem was formulated by George Polya in 1912. He stated that for a one or two-dimensional lattice random walk with infinite number of steps, N, the probability that the walker will return to its point of origin is unity. The work done in this particular research explores Polya's theorem for one-dimensional random walks that are non-isotropic and have the property of one-step memory, i.e. the probability of moving in any direction is non-symmetric and dependent on the previous step. The key mathematical construct used in this research is that of a generating function. This helps compute the return probability for an infinite N. An explicit form of the generating function was devised and used to calculate return probabilities for finite N. Return probabilities for various memory parameters were explored analytically and via simulations. Currently, further analysis is being done to try and find a relationship between memory parameters and number of steps, N.

  7. Random walks of a quantum particle on a circle

    When the quantum planar rotor is put on a lattice, its dynamics can be approximated by random walks on a circle. This allows for fast and accurate Monto Carlo simulations to determine the topological charge of different configurations of the system and thereby the Θ-dependency of the lowest energy levels

  8. Maximum occupation time of a transient excited random walk on Z

    Rastegar, Reza


    We consider a transient excited random walk on $Z$ and study the asymptotic behavior of the occupation time of a currently most visited site. In particular, our results imply that, in contrast to the random walks in random environment, a transient excited random walk does not spend an asymptotically positive fraction of time at its favorite (most visited up to a date) sites.

  9. Directed random walk on an oriented percolation cluster

    Birkner, Matthias; Depperschmidt, Andrej; Gantert, Nina


    We consider directed random walk on the infinite percolation cluster generated by supercritical oriented percolation, or equivalently the space-time embedding of the `ancestral lineage' of an individual in the stationary discrete-time contact process. We prove a law of large numbers and an annealed central limit theorem (i.e., averaged over the realisations of the cluster) with a regeneration approach. Via an analysis of joint renewals of two independent walks on the same cluster, we obtain furthermore a quenched central limit theorem (i.e. for almost any realisation of the cluster) in dimensions $1+d$ with $d\\geq 2$.

  10. Ballistic phase of self-interacting random walks

    Ioffe, Dmitry; Velenik, Yvan Alain


    We explain a unified approach to a study of ballistic phase for a large family of self-interacting random walks with a drift and self-interacting polymers with an external stretching force. The approach is based on a recent version of the Ornstein-Zernike theory developed in earlier works. It leads to local limit results for various observables (e.g. displacement of the end-point or number of hits of a fixed finite pattern) on paths of n-step walks (polymers) on all possible deviation scales ...

  11. Recurrence and Transience Criteria for Random Walk in a Random Environment

    Key, Eric S.


    Oseledec's Multiplicative Ergodic Theorem is used to give recurrence and transience criteria for random walk in a random environment on the integers. These criteria generalize those given by Solomon in the nearest-neighbor case. The methodology for random environments is then applied to Markov chains with periodic transition functions to obtain recurrence and transience criteria for these processes as well.

  12. Coverage maximization under resource constraints using proliferating random walks

    Sudipta Saha; Niloy Ganguly; Abhijit Guria


    Dissemination of information has been one of the prime needs in almost every kind of communication network. The existing algorithms for this service, try to maximize the coverage, i.e., the number of distinct nodes to which a given piece of information could be conveyed under the constraints of time and energy. However, the problem becomes challenging for unstructured and decentralized environments. Due to its simplicity and adaptability, random walk (RW) has been a very useful tool for such environments. Different variants of this technique have been studied. In this paper, we study a history-based non-uniform proliferating random strategy where new walkers are dynamically introduced in the sparse regions of the network. Apart from this, we also study the breadth-first characteristics of the random walk-based algorithms through an appropriately designed metrics.

  13. An Analysis of Random-Walk Cuckoo Hashing

    Frieze, Alan; Melsted, Páll; Mitzenmacher, Michael

    In this paper, we provide a polylogarithmic bound that holds with high probability on the insertion time for cuckoo hashing under the random-walk insertion method. Cuckoo hashing provides a useful methodology for building practical, high-performance hash tables. The essential idea of cuckoo hashing is to combine the power of schemes that allow multiple hash locations for an item with the power to dynamically change the location of an item among its possible locations. Previous work on the case where the number of choices is larger than two has required a breadth-first search analysis, which is both inefficient in practice and currently has only a polynomial high probability upper bound on the insertion time. Here we significantly advance the state of the art by proving a polylogarithmic bound on the more efficient random-walk method, where items repeatedly kick out random blocking items until a free location for an item is found.

  14. Metadisorder for designer light in random-walk systems

    Yu, Sunkyu; Hong, Jiho; Park, Namkyoo


    Disorder plays a critical role in signal transport, by controlling the correlation of systems. In wave physics, disordered potentials suppress wave transport due to their localized eigenstates from random-walk scattering. Although the variation of localization with tunable disorder has been intensively studied as a bridge between ordered and disordered media, the general trend of disorder-enhanced localization has remained unchanged, failing in envisaging the existence of delocalization in highly-disordered potentials. Here, we propose the concept of 'metadisorder': tunable random-walk systems having a designed eigenstate with unnatural localization. We demonstrate that one of the eigenstates in a randomly-coupled system can always be arbitrarily molded, regardless of the degree of disorder, by adjusting the self-energy of each element. Ordered waves are then achieved in highly-disordered systems, including planewaves and globally- collective resonances. We also devise counterintuitive functionalities in diso...

  15. Statistics of knots and entangled random walks

    Nechaer, S


    In this book, the author announces the class of problems called "entropy of knots" and gives an overview of modern physical applications of existing topological invariants.He constructs statistical models on knot diagrams and braids using the representations of Jones-Kauffman and Alexander invariants and puts forward the question of limit distribution of these invariants for randomly generated knots. The relation of powers of corresponding algebraic invariants to the Lyapunov exponents of the products of noncommutative matrices is described. Also the problem of conditional joint limit distribu

  16. On The Number of Times where a Simple Random Walk reaches a Nonnegative Height

    Katzenbeisser, Walter; Panny, Wolfgang


    The purpose of this note is to generalize the distribution of the local time of a purely binomial random walk for simple random walks allowing for three directions with different probabilities. (author's abstract)

  17. Quantum decomposition of random walk on Cayley graph of finite group

    Kang, Yuanbao


    In the paper, A quantum decomposition (QD, for short) of random walk on Cayley graph of finite group is introduced, which contains two cases. One is QD of quantum random walk operator (QRWO, for short), another is QD of Quantum random walk state (QRWS, for short). Using these findings, I finally obtain some applications for quantum random walk (QRW, for short), which are of interest in the study of QRW, highlighting the role played by QRWO and QRWS.

  18. Level 1 quenched large deviation principle for random walk in dynamic random environment

    Drewitz, David Campos Alexander


    Consider a random walk on a continuous time-dependent random environment on the hiper-cubic lattice. Recently, Rassoul-Agha, Seppalainen and Yilmaz proved a general large deviation principle under mild ergodicity assumptions on the random environment for such a random walk, establishing first a level 2 and 3 large deviation principle. Here we present an alternative short proof of the level 1 large deviations under mild ergodicity assumptions on the environment, which provides the existence and convexity of the rate function, in the continuous time case. Our methods are based on the use of sub-additive ergodic theorem as presented by Varadhan in 2003.

  19. Random walk after the big bang

    The dynamics of inflation is that of a relaxation random process. We examine boundary conditions for this process and give a simple proof for the existence of eternal inflation that takes into account the field dependence of the effective cosmological constant and the finite duration of the inflationary phase. Next, natural initial conditions are formulated that lead to a specific interpretation of the wave function in quantum cosmology. We demonstrate that the Hartle-Hawking wave function describes the equilibrium regime for the stochastic process (with the correct quantum-field-theory limit), but only if the cosmological constant is sufficiently large or if it decays sufficiently slowly. We show in which sense inflation is certain even with the Hartle-Hawking wave function, and propose a new framework for the ''tunneling'' wave function. On the basis of boundary conditions, we argue that the dynamics of the stochastic phase and, hence, the main features of the present Universe, are independent of the physics above the Planck scale

  20. Chover-Type Laws of the Iterated Logarithm for Continuous Time Random Walks

    Kyo-Shin Hwang; Wensheng Wang


    A continuous time random walk is a random walk subordinated to a renewal process used in physics to model anomalous diffusion. In this paper, we establish Chover-type laws of the iterated logarithm for continuous time random walks with jumps and waiting times in the domains of attraction of stable laws.

  1. On the Emergence of Shortest Paths by Reinforced Random Walks

    Figueiredo, Daniel R


    The co-evolution between network structure and functional performance is a fundamental and challenging problem whose complexity emerges from the intrinsic interdependent nature of structure and function. Within this context, we investigate the interplay between the efficiency of network navigation (i.e., path lengths) and network structure (i.e., edge weights). We propose a simple and tractable model based on iterative biased random walks where edge weights increase over time as function of the traversed path length. Under mild assumptions, we prove that biased random walks will eventually only traverse shortest paths in their journey towards the destination. We further characterize the transient regime proving that the probability to traverse non-shortest paths decays according to a power-law. We also highlight various properties in this dynamic, such as the trade-off between exploration and convergence, and preservation of initial network plasticity. We believe the proposed model and results can be of inter...

  2. A generalized model via random walks for information filtering

    Ren, Zhuo-Ming; Kong, Yixiu; Shang, Ming-Sheng; Zhang, Yi-Cheng


    There could exist a simple general mechanism lurking beneath collaborative filtering and interdisciplinary physics approaches which have been successfully applied to online E-commerce platforms. Motivated by this idea, we propose a generalized model employing the dynamics of the random walk in the bipartite networks. Taking into account the degree information, the proposed generalized model could deduce the collaborative filtering, interdisciplinary physics approaches and even the enormous expansion of them. Furthermore, we analyze the generalized model with single and hybrid of degree information on the process of random walk in bipartite networks, and propose a possible strategy by using the hybrid degree information for different popular objects to toward promising precision of the recommendation.

  3. Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks

    Cooper, Joshua N


    We analyze a deterministic form of the random walk on the integer line called the {\\em liar machine}, similar to the rotor-router model, finding asymptotically tight pointwise and interval discrepancy bounds versus random walk. This provides an improvement in the best-known winning strategies in the binary symmetric pathological liar game with a linear fraction of responses allowed to be lies. Equivalently, this proves the existence of adaptive binary block covering codes with block length $n$, covering radius $\\leq fn$ for $f\\in(0,1/2)$, and cardinality $O(\\sqrt{\\log \\log n}/(1-2f))$ times the sphere bound $2^n/\\binom{n}{\\leq \\lfloor fn\\rfloor}$.

  4. Visual Saliency and Attention as Random Walks on Complex Networks

    Costa, L F


    The unmatched versatility of vision in mammals is totally dependent on purposive eye movements and selective attention guided by saliencies in the presented images. The current article shows how concepts and tools from the areas of random walks, Markov chains, complex networks and artificial image analysis can be naturally combined in order to provide a unified and biologically plausible model for saliency detection and visual attention, which become indistinguishable in the process. Images are converted into complex networks by considering pixels as nodes while connections are established in terms of fields of influence defined by visual features such as tangent fields induced by luminance contrasts, distance, and size. Random walks are performed on such networks in order to emulate attentional shifts and even eye movements in the case of large shapes, and the frequency of visits to each node is conveniently obtained from the eigenequation defined by the stochastic matrix associated to the respectively drive...

  5. Continuous Time Random Walks for the Evolution of Lagrangian Velocities

    Dentz, Marco; Comolli, Alessandro; Borgne, Tanguy Le; Lester, Daniel R


    We develop a continuous time random walk (CTRW) approach for the evolution of Lagrangian velocities in steady heterogeneous flows based on a stochastic relaxation process for the streamwise particle velocities. This approach describes persistence of velocities over a characteristic spatial scale, unlike classical random walk methods, which model persistence over a characteristic time scale. We first establish the relation between Eulerian and Lagrangian velocities for both equidistant and isochrone sampling along streamlines, under transient and stationary conditions. Based on this, we develop a space continuous CTRW approach for the spatial and temporal dynamics of Lagrangian velocities. While classical CTRW formulations have non-stationary Lagrangian velocity statistics, the proposed approach quantifies the evolution of the Lagrangian velocity statistics under both stationary and non-stationary conditions. We provide explicit expressions for the Lagrangian velocity statistics, and determine the behaviors of...

  6. Random Walk Hypothesis (Rwh) In The Bursa Malaysia Stock Exchange

    Ng, Swee Khiang


    The assumptions of the random walk hypothesis (RWH) are tested for Bursa Malaysia Stock Exchange (formerly known as Kuala Lumpur Stock Exchange) indices during the sample period of 1990 to 2005. The entire period is divided into two sub-periods, which are before and after the Asian financial crisis. The findings suggested that the stock price indices did not follow the assumptions of RWH during the entire period. In the sample period before the Asian financial crisis, the behaviour of stock p...

  7. The linear Ising model and its analytic continuation, random walk

    B. H. Lavenda


    A generalization of Gauss's principle is used to derive the error laws corresponding to Types II and VII distributions in Pearson's classification scheme. Student's $r$-pdf (Type II) governs the distribution of the internal energy of a uniform, linear chain, Ising model, while analytic continuation of the uniform exchange energy converts it into a Student $t$-density (Type VII) for the position of a random walk in a single spatial dimension. Higher dimensional spaces, corresponding to larger ...

  8. Random walks, liquidity molasses and critical response in financial markets

    J. -P. Bouchaud; J. Kockelkoren; Potters, M


    Stock prices are observed to be random walks in time despite a strong, long term memory in the signs of trades (buys or sells). Lillo and Farmer have recently suggested that these correlations are compensated by opposite long ranged fluctuations in liquidity, with an otherwise permanent market impact, challenging the scenario proposed in Quantitative Finance 4, 176 (2004), where the impact is *transient*, with a power-law decay in time. The exponent of this decay is precisely tuned to a criti...

  9. Simple Random Walk Statistics. Part I: Discrete Time Results

    Katzenbeisser, Walter; Panny, Wolfgang


    In a famous paper Dwass [I9671 proposed a method to deal with rank order statistics, which constitutes a unifying framework to derive various distributional results. In the present paper an alternative method is presented, which allows to extend Dwass's results in several ways, viz. arbitrary endpoints, horizontal steps, and arbitrary probabilities for the three step types. Regarding these extensions the pertaining rank order statistics are extended as well to simple random walk statistics. T...

  10. Continuous-time random walk theory of superslow diffusion

    Denisov, S. I.; Kantz, H.


    Superslow diffusion, i.e., the long-time diffusion of particles whose mean-square displacement (variance) grows slower than any power of time, is studied in the framework of the decoupled continuous-time random walk model. We show that this behavior of the variance occurs when the complementary cumulative distribution function of waiting times is asymptotically described by a slowly varying function. In this case, we derive a general representation of the laws of superslow diffusion for both ...

  11. Modulated speckle simulations based on the random-walk model

    Lencina, Alberto; Vaveliuk, Pablo; Tebaldi, Myriam C.; Bolognini, Néstor Alberto


    The random walk model is employed to simulate modulated speckle patterns. We demonstrate that the geo metrical image approximation fails to describe the modulated speckle pattern. A new approach to analyzing this phenomenon is proposed. The validity of the approximations employed is verified by comparison of the simulation with the experimental results. Speckle metrological applications and phase measurement tech niques could be improved by taking advantage of this model.

  12. Solving the accuracy-diversity dilemma via directed random walks

    Liu, Jian-Guo; Guo, Qiang; 10.1103/PhysRevE.85.016118


    Random walks have been successfully used to measure user or object similarities in collaborative filtering (CF) recommender systems, which is of high accuracy but low diversity. A key challenge of CF system is that the reliably accurate results are obtained with the help of peers' recommendation, but the most useful individual recommendations are hard to be found among diverse niche objects. In this paper we investigate the direction effect of the random walk on user similarity measurements and find that the user similarity, calculated by directed random walks, is reverse to the initial node's degree. Since the ratio of small-degree users to large-degree users is very large in real data sets, the large-degree users' selections are recommended extensively by traditional CF algorithms. By tuning the user similarity direction from neighbors to the target user, we introduce a new algorithm specifically to address the challenge of diversity of CF and show how it can be used to solve the accuracy-diversity dilemma....

  13. Graph Clustering Based on Mixing Time of Random Walks

    Avrachenkov, Konstantin; El Chamie, Mahmoud; Neglia, Giovanni


    Clustering of a graph is the task of grouping its nodes in such a way that the nodes within the same cluster are well connected, but they are less connected to nodes in different clusters. In this paper we propose a clustering metric based on the random walks' properties to evaluate the quality of a graph clustering. We also propose a randomized algorithm that identifies a locally optimal clustering of the graph according to the metric defined. The algorithm is intrinsically distributed and a...

  14. The Beurling estimate for a class of random walks

    Lawler, Gregory F.; Limic, Vlada


    An estimate of Beurling states that if K is a curve from 0 to the unit circle in the complex plane, then the probability that a Brownian motion starting at -eps reaches the unit circle without hitting the curve is bounded above by c eps^{1/2}. This estimate is very useful in analysis of boundary behavior of conformal maps, especially for connected but rough boundaries. The corresponding estimate for simple random walk was first proved by Kesten. In this note we extend this estimate to random ...

  15. Holey random walks: optics of heterogeneous turbid composites.

    Svensson, Tomas; Vynck, Kevin; Grisi, Marco; Savo, Romolo; Burresi, Matteo; Wiersma, Diederik S


    We present a probabilistic theory of random walks in turbid media with nonscattering regions. It is shown that important characteristics such as diffusion constants, average step lengths, crossing statistics, and void spacings can be analytically predicted. The theory is validated using Monte Carlo simulations of light transport in heterogeneous systems in the form of random sphere packings and good agreement is found. The role of step correlations is discussed and differences between unbounded and bounded systems are investigated. Our results are relevant to the optics of heterogeneous systems in general and represent an important step forward in the understanding of media with strong (fractal) heterogeneity in particular. PMID:23496473

  16. Random-walk baryogenesis via primordial black holes

    Semiz, İbrahim


    Gravitation violates baryon number $B$: A star has a huge amount of it, while a black hole forming from the star has none. Consider primordial black holes before the hadronic annihiliation in the early universe, encountering and absorbing baryons and antibaryons: Each such absorption changes $B$ of the universe by one unit, up or down. But the absorption events are $uncorrelated$ $and$ $random$, hence they amount to a random walk in $B$-space, leading to the expectation of a net $|B|$ at the ...

  17. Strong approximation for the general Kesten-Spitzer random walk in independent random scenery


    This paper is to prove that, if a one-dimensional random wa lkcan be approximated by a Brownian motion, then the related random walk in a g eneral independent scenery can be approximated by a Brownian motion in Brownian scenery.

  18. Some Probability Properties of Random Walk in Time-Random Environment

    Zhang Xiao-min; Li Bo


    A general formulation of the stochastic model for random walk in time-random environment and an equivalent definition is established in this paper. Moreover, some basic probability relations similar to the classical case which are very useful in the corresponding research of fractal properties are given. At the end, a typical example is provided to show the recurrence and transience.

  19. A Novel Algorithm of Quantum Random Walk in Server Traffic Control and Task Scheduling

    Dong Yumin


    Full Text Available A quantum random walk optimization model and algorithm in network cluster server traffic control and task scheduling is proposed. In order to solve the problem of server load balancing, we research and discuss the distribution theory of energy field in quantum mechanics and apply it to data clustering. We introduce the method of random walk and illuminate what the quantum random walk is. Here, we mainly research the standard model of one-dimensional quantum random walk. For the data clustering problem of high dimensional space, we can decompose one m-dimensional quantum random walk into m one-dimensional quantum random walk. In the end of the paper, we compare the quantum random walk optimization method with GA (genetic algorithm, ACO (ant colony optimization, and SAA (simulated annealing algorithm. In the same time, we prove its validity and rationality by the experiment of analog and simulation.

  20. Free Dirac evolution as a quantum random walk

    Bracken, A J; Smyrnakis, I


    Any positive-energy state of a free Dirac particle that is initially highly-localized, evolves in time by spreading at speeds close to the speed of light. This general phenomenon is explained by the fact that the Dirac evolution can be approximated arbitrarily closely by a quantum random walk, where the roles of coin and walker systems are naturally attributed to the spin and position degrees of freedom of the particle. Initially entangled and spatially localized spin-position states evolve with asymptotic two-horned distributions of the position probability, familiar from earlier studies of quantum walks. For the Dirac particle, the two horns travel apart at close to the speed of light.

  1. History dependent quantum random walks as quantum lattice gas automata

    Quantum Random Walks (QRW) were first defined as one-particle sectors of Quantum Lattice Gas Automata (QLGA). Recently, they have been generalized to include history dependence, either on previous coin (internal, i.e., spin or velocity) states or on previous position states. These models have the goal of studying the transition to classicality, or more generally, changes in the performance of quantum walks in algorithmic applications. We show that several history dependent QRW can be identified as one-particle sectors of QLGA. This provides a unifying conceptual framework for these models in which the extra degrees of freedom required to store the history information arise naturally as geometrical degrees of freedom on the lattice

  2. Intermittent random walks: transport regimes and implications on search strategies

    We construct a transport model for particles that alternate rests of random duration and flights with random velocities. The model provides a balance equation for the mesoscopic particle density obtained from the continuous-time random walk framework. By assuming power laws for the distributions of waiting times and flight durations (for any velocity distribution with finite moments) we have found that the model can yield all the transport regimes ranging from subdiffusion to ballistic depending on the values of the characteristic exponents of the distributions. In addition, if the exponents satisfy a simple relationship it is shown how the competition between the tails of the distributions gives rise to a diffusive transport. Finally, we explore how the details of this intermittent transport process affect the success probability in an optimal search problem where an individual searcher looks for a target distributed (heterogeneously) in space. All the results are conveniently checked with numerical simulations

  3. Memoryless Routing in Convex Subdivisions: Random Walks are Optimal

    Chen, Dan; Dujmovic, Vida; Morin, Pat


    A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex t for a packet currently located at vertex v is made based only on the coordinates of v, t, and the neighbourhood, N(v), of v. The current paper explores the limitations of such algorithms by showing that, for any (randomized) memoryless routing algorithm A, there exists a convex subdivision on which A takes Omega(n^2) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by Bose etal (2002,2004) requires 2^{\\Omega(n)} time to route between some pair of vertices.

  4. Scaling exponents for a monkey on a tree: fractal dimensions of randomly branched polymers.

    Janssen, Hans-Karl; Stenull, Olaf


    We study asymptotic properties of diffusion and other transport processes (including self-avoiding walks and electrical conduction) on large, randomly branched polymers using renormalized dynamical field theory. We focus on the swollen phase and the collapse transition, where loops in the polymers are irrelevant. Here the asymptotic statistics of the polymers is that of lattice trees, and diffusion on them is reminiscent of the climbing of a monkey on a tree. We calculate a set of universal scaling exponents including the diffusion exponent and the fractal dimension of the minimal path to two-loop order and, where available, compare them to numerical results. PMID:23004722

  5. Infinitely dimensional control Markov branching chains in random environments

    HU; Dihe


    First of all we introduce the concepts of infinitely dimensional control Markov branching chains in random environments (β-MBCRE) and prove the existence of such chains, then we introduce the concepts of conditional generating functionals and random Markov transition functions of such chains and investigate their branching property. Base on these concepts we calculate the moments of the β-MBCRE and obtain the main results of this paper such as extinction probabilities, polarization and proliferation rate. Finally we discuss the classification ofβ-MBCRE according to the different standards.

  6. Universality in random-walk models with birth and death

    Models of random walks are considered in which walkers are born at one site and die at all other sites. Steady-state distributions of walkers exhibit dimensionally dependent critical behavior as a function of the birth rate. Exact analytical results for a hyperspherical lattice yield a second-order phase transition with a nontrivial critical exponent for all positive dimensions D≠2, 4. Numerical studies of hypercubic and fractal lattices indicate that these exact results are universal. This work elucidates the adsorption transition of polymers at curved interfaces. copyright 1995 The American Physical Society

  7. Nonlocal operators, parabolic-type equations, and ultrametric random walks

    Chacón-Cortes, L. F., E-mail:; Zúñiga-Galindo, W. A., E-mail: [Centro de Investigacion y de Estudios Avanzados del I.P.N., Departamento de Matematicas, Av. Instituto Politecnico Nacional 2508, Col. San Pedro Zacatenco, Mexico D.F., C.P. 07360 (Mexico)


    In this article, we introduce a new type of nonlocal operators and study the Cauchy problem for certain parabolic-type pseudodifferential equations naturally associated to these operators. Some of these equations are the p-adic master equations of certain models of complex systems introduced by Avetisov, V. A. and Bikulov, A. Kh., “On the ultrametricity of the fluctuation dynamicmobility of protein molecules,” Proc. Steklov Inst. Math. 265(1), 75–81 (2009) [Tr. Mat. Inst. Steklova 265, 82–89 (2009) (Izbrannye Voprosy Matematicheskoy Fiziki i p-adicheskogo Analiza) (in Russian)]; Avetisov, V. A., Bikulov, A. Kh., and Zubarev, A. P., “First passage time distribution and the number of returns for ultrametric random walks,” J. Phys. A 42(8), 085003 (2009); Avetisov, V. A., Bikulov, A. Kh., and Osipov, V. A., “p-adic models of ultrametric diffusion in the conformational dynamics of macromolecules,” Proc. Steklov Inst. Math. 245(2), 48–57 (2004) [Tr. Mat. Inst. Steklova 245, 55–64 (2004) (Izbrannye Voprosy Matematicheskoy Fiziki i p-adicheskogo Analiza) (in Russian)]; Avetisov, V. A., Bikulov, A. Kh., and Osipov, V. A., “p-adic description of characteristic relaxation in complex systems,” J. Phys. A 36(15), 4239–4246 (2003); Avetisov, V. A., Bikulov, A. H., Kozyrev, S. V., and Osipov, V. A., “p-adic models of ultrametric diffusion constrained by hierarchical energy landscapes,” J. Phys. A 35(2), 177–189 (2002); Avetisov, V. A., Bikulov, A. Kh., and Kozyrev, S. V., “Description of logarithmic relaxation by a model of a hierarchical random walk,” Dokl. Akad. Nauk 368(2), 164–167 (1999) (in Russian). The fundamental solutions of these parabolic-type equations are transition functions of random walks on the n-dimensional vector space over the field of p-adic numbers. We study some properties of these random walks, including the first passage time.

  8. Memory biased random walk approach to synthetic clickstream generation

    Antulov-Fantulin, Nino; Zlatic, Vinko; Grcar, Miha; Smuc, Tomislav


    Personalized recommender systems rely on personal usage data of each user in the system. However, privacy policies protecting users' rights prevent this data of being publicly available to a wider researcher audience. In this work, we propose a memory biased random walk model (MBRW) based on real clickstream graphs, as a generator of synthetic clickstreams that conform to statistical properties of the real clickstream data, while, at the same time, adhering to the privacy protection policies. We show that synthetic clickstreams can be used to learn recommender system models which achieve high recommender performance on real data and at the same time assuring that strong de-minimization guarantees are provided.

  9. Community Detection in Complex Networks with Quantum Random Walks

    Tsomokos, Dimitris I


    Complex networks are structurally disordered systems that often display clustering behavior. The emergent clusters, also known as communities, consist of nodes that are more connected among themselves than they are connected with the rest of the network. Analyzing community structure is an important problem in network theory, with numerous applications in different fields. In this work I investigate the evolution of a continuous-time quantum random walk on a social network with benchmark community structure and show that it can be used to perform community detection.

  10. Fractional telegrapher's equation from fractional persistent random walks

    Masoliver, Jaume


    We generalize the telegrapher's equation to allow for anomalous transport. We derive the space-time fractional telegrapher's equation using the formalism of the persistent random walk in continuous time. We also obtain the characteristic function of the space-time fractional process and study some particular cases and asymptotic approximations. Similarly to the ordinary telegrapher's equation, the time-fractional equation also presents distinct behaviors for different time scales. Specifically, transitions between different subdiffusive regimes or from superdiffusion to subdiffusion are shown by the fractional equation as time progresses.

  11. Random-walk baryogenesis via primordial black holes

    Semiz, İbrahim


    Gravitation violates baryon number $B$: A star has a huge amount of it, while a black hole forming from the star has none. Consider primordial black holes before the hadronic annihiliation in the early universe, encountering and absorbing baryons and antibaryons: Each such absorption changes $B$ of the universe by one unit, up or down. But the absorption events are $uncorrelated$ $and$ $random$, hence they amount to a random walk in $B$-space, leading to the expectation of a net $|B|$ at the end. While the scale of this effect is most uncertain, it must exist. We explore some ramifications, including the change of net $|B|$ with expansion, connection with universe topology, and possible observational signatures.

  12. Random walks in small-world exponential treelike networks

    In this paper, we investigate random walks in a family of small-world trees having an exponential degree distribution. First, we address a trapping problem, that is, a particular case of random walks with an immobile trap located at the initial node. We obtain the exact mean trapping time defined as the average of the first-passage times (FPT) from all nodes to the trap, which scales linearly with the network order N in large networks. Then, we determine analytically the mean sending time, which is the mean of the FPTs from the initial node to all other nodes, and show that it grows with N, varying approximately as NlnN. After that, we compute the precise global mean first-passage time among all pairs of nodes and find that it also varies approximately as NlnN in the large limit of N. After obtaining the relevant quantities, we compare them with each other and relate our results to the efficiency for information transmission by regarding the walker as an information messenger. Finally, we compare our results with those previously reported for other trees with different structural properties (e.g., degree distribution), such as the standard fractal trees and the scale-free small-world trees, and show that the shortest path between a pair of nodes in a tree is responsible for the scaling of the FPT between the two nodes

  13. Do MENA stock market returns follow a random walk process?

    Salim Lahmiri


    Full Text Available In this research, three variance ratio tests: the standard variance ratio test, the wild bootstrap multiple variance ratio test, and the non-parametric rank scores test are adopted to test the random walk hypothesis (RWH of stock markets in Middle East and North Africa (MENA region using most recent data from January 2010 to September 2012. The empirical results obtained by all three econometric tests show that the RWH is strongly rejected for Kuwait, Tunisia, and Morocco. However, the standard variance ratio test and the wild bootstrap multiple variance ratio test reject the null hypothesis of random walk in Jordan and KSA, while non-parametric rank scores test do not. We may conclude that Jordan and KSA stock market are weak efficient. In sum, the empirical results suggest that return series in Kuwait, Tunisia, and Morocco are predictable. In other words, predictable patterns that can be exploited in these markets still exit. Therefore, investors may make profits in such less efficient markets.



    Suppose {Xn} is a random walk in time-random environment with state space Zd, |Xn| approaches infinity, then under some reasonable conditions of stability, the upper bound of the discrete Packing dimension of the range of {Xn} is any stability index α.Moreover, if the environment is stationary, a similar result for the lower bound of the discrete Hausdorff dimension is derived. Thus, the range is a fractal set for almost every environment.

  15. The Laplace Functional and Moments for Markov Branching Chains in Random Environments

    HU Di-he; ZHANG Shu-lin


    The concepts of random Markov matrix, Markov branching chain in random environment (MBCRE) and Laplace functional of Markov branching chain in random environment (LFMBCRE) are introduced. The properties of LFMBCRE and the explicit formulas of moments of MBCRE are given.

  16. The persistence length of two-dimensional self-avoiding random walks

    The decay of directional correlations in self-avoiding random walks on the square lattice is investigated. Analysis of exact enumerations and Monte Carlo data suggest that the correlation between the directions of the first step and the jth step of the walk decays faster than j-1, indicating that the persistence length of the walk is finite. (letter to the editor)

  17. Random Walks in a One-Dimensional Lévy Random Environment

    Bianchi, Alessandra; Cristadoro, Giampaolo; Lenci, Marco; Ligabò, Marilena


    We consider a generalization of a one-dimensional stochastic process known in the physical literature as Lévy-Lorentz gas. The process describes the motion of a particle on the real line in the presence of a random array of marked points, whose nearest-neighbor distances are i.i.d. and long-tailed (with finite mean but possibly infinite variance). The motion is a continuous-time, constant-speed interpolation of a symmetric random walk on the marked points. We first study the quenched random walk on the point process, proving the CLT and the convergence of all the accordingly rescaled moments. Then we derive the quenched and annealed CLTs for the continuous-time process.

  18. Upper large deviations for Branching Processes in Random Environment with heavy tails

    Bansaye, Vincent


    Branching Processes in a Random Environment (BPREs) $(Z_n:n\\geq0)$ are a generalization of Galton Watson processes where in each generation the reproduction law is picked randomly in an i.i.d. manner. We determine here the upper large deviation of the process when the reproduction law may have heavy tails. The behavior of BPREs is related to the associated random walk of the environment, whose increments are distributed like the logarithmic mean of the offspring distributions. We obtain an expression of the upper rate function of $(Z_n:n\\geq0)$, that is the limit of $-\\log \\mathbb{P}(Z_n\\geq e^{\\theta n})/n$ when $n\\to \\infty$. It depends on the rate function of the associated random walk of the environment, the logarithmic cost of survival $\\gamma:=-\\lim_{n\\to\\infty} \\log \\mathbb{P}(Z_n>0)/n$ and the polynomial decay $\\beta$ of the tail distribution of $Z_1$. We give interpretations of this rate function in terms of the least costly ways for the process $(Z_n: n \\geq 0)$ of attaining extraordinarily large va...

  19. Scaling analysis of random walks with persistence lengths: Application to self-avoiding walks

    Granzotti, C. R. F.; Martinez, A. S.; da Silva, M. A. A.


    We develop an approach for performing scaling analysis of N -step random walks (RWs). The mean square end-to-end distance, , is written in terms of inner persistence lengths (IPLs), which we define by the ensemble averages of dot products between the walker's position and displacement vectors, at the j th step. For RW models statistically invariant under orthogonal transformations, we analytically introduce a relation between and the persistence length, λN, which is defined as the mean end-to-end vector projection in the first step direction. For self-avoiding walks (SAWs) on 2D and 3D lattices we introduce a series expansion for λN, and by Monte Carlo simulations we find that λ∞ is equal to a constant; the scaling corrections for λN can be second- and higher-order corrections to scaling for . Building SAWs with typically 100 steps, we estimate the exponents ν0 and Δ1 from the IPL behavior as function of j . The obtained results are in excellent agreement with those in the literature. This shows that only an ensemble of paths with the same length is sufficient for determining the scaling behavior of , being that the whole information needed is contained in the inner part of the paths.

  20. Limit theorems for one and two-dimensional random walks in random scenery

    Castell, Fabienne; Pène, Françoise


    Random walks in random scenery are processes defined by $Z_n:=\\sum_{k=1}^n\\xi_{X_1+...+X_k}$, where $(X_k,k\\ge 1)$ and $(\\xi_y,y\\in{\\mathbb Z}^d)$ are two independent sequences of i.i.d. random variables with values in ${\\mathbb Z}^d$ and $\\mathbb R$ respectively. We suppose that the distributions of $X_1$ and $\\xi_0$ belong to the normal basin of attraction of stable distribution of index $\\alpha\\in(0,2]$ and $\\beta\\in(0,2]$. When $d=1$ and $\\alpha\

  1. Composition of many spins, random walks and statistics

    Polychronakos, Alexios P


    The multiplicities of the decomposition of the product of an arbitrary number $n$ of spin $s$ states into irreducible $SU(2)$ representations are computed. Two complementary methods are presented, one based on random walks in representation space and another based on the partition function of the system in the presence of a magnetic field. The large-$n$ scaling limit of these multiplicities is derived, including nonperturbative corrections, and related to semiclassical features of the system. A physical application of these results to ferromagnetism is explicitly worked out. Generalizations involving several types of spins, as well as spin distributions, are also presented. The corresponding problem for (anti-)symmetric composition of spins is also considered and shown to obey remarkable duality and bosonization relations and exhibit qualitatively different large-$n$ scaling properties.

  2. Dynamics of market indices, Markov chains, and random walking problem

    Krivoruchenko, M I


    Dynamics of the major USA market indices DJIA, S&P, Nasdaq, and NYSE is analyzed from the point of view of the random walking problem with two-step correlations of the market moves. The parameters characterizing the stochastic dynamics are determined empirically from the historical quotes for the daily, weekly, and monthly series. The results show existence of statistically significant correlations between the subsequent market moves. The weekly and monthly parameters are calculated in terms of the daily parameters, assuming that the Markov chains with two-step correlations give a complete description of the market stochastic dynamics. We show that the macro- and micro-parameters obey the renorm group equation. The comparison of the parameters determined from the renorm group equation with the historical values shows that the Markov chains approach gives reasonable predictions for the weekly quotes and underestimates the probability for continuation of the down trend in the monthly quotes. The return and ...

  3. Self-avoiding random walks on the hexagonal lattice

    The authors use the algorithm recently introduced by A. Berretti and A.D. Sokal to compute numerically the critical exponents for the self-avoiding random walk on the hexagonal lattice. They find γ = 1.3509 +/- 0.0057 +/- 0.0023; v = 0.7580 +/- 0.0049 +/- 0.0046; α = 0.519 +/- 0.082 +/- 0.077 where the first error is the systematic one due to corrections to scaling and the second is the statistical error. For the effective coordination number μ they find μ = 1.84779 +/- 0.00006 +/- 0.0017. The results support the Nienhuis conjecture γ = 43/32 and provide a rough numerical check of the hyperscaling relation dv = 2 - α. An additional analysis, taking the Nienhuis value of μ = (2 + 2/sup 1/2/)/sup 1/2/ for granted, gives γ = 1.3459 +/- 0.0040 +/- 0.0008

  4. Correlated continuous time random walk and option pricing

    Lv, Longjin; Xiao, Jianbin; Fan, Liangzhong; Ren, Fuyao


    In this paper, we study a correlated continuous time random walk (CCTRW) with averaged waiting time, whose probability density function (PDF) is proved to follow stretched Gaussian distribution. Then, we apply this process into option pricing problem. Supposing the price of the underlying is driven by this CCTRW, we find this model captures the subdiffusive characteristic of financial markets. By using the mean self-financing hedging strategy, we obtain the closed-form pricing formulas for a European option with and without transaction costs, respectively. At last, comparing the obtained model with the classical Black-Scholes model, we find the price obtained in this paper is higher than that obtained from the Black-Scholes model. A empirical analysis is also introduced to confirm the obtained results can fit the real data well.

  5. A random walk in the land of precompound decay

    Several aspects of precompound-decay (preequilibrium) reactions, relevant for the application to fusion-reactor design, are considered. Preequilibrium angular distributions are discussed in the framework of the generalized exciton model. A critical discussion of the theory is given and various refinements are suggested. A comparison is made with experimental data on 14 MeV neutron-induced reactions for a large number of nuclides covering the whole mass range. The exciton model is further generalized to the description of multiparticle emission. Preequilibrium effects in multiple emission are investigated. Computational aspects of preequilibrium theory are examined whereby the exact solution for the mean exciton-state lifetimes is derived in closed form. A random-walk model of precompound decay is developed. The dynamics of the nuclear relaxation process and the fluctuations originating from its stochastic nature are studied in detail. Uncertainty calculations are presented for the exciton-state lifetimes and the emission cross-sections. (Auth.)

  6. Information Filtering via Biased Random Walk on Coupled Social Network

    Da-Cheng Nie


    Full Text Available The recommender systems have advanced a great deal in the past two decades. However, most researchers focus their attentions on mining the similarities among users or objects in recommender systems and overlook the social influence which plays an important role in users’ purchase process. In this paper, we design a biased random walk algorithm on coupled social networks which gives recommendation results based on both social interests and users’ preference. Numerical analyses on two real data sets, Epinions and Friendfeed, demonstrate the improvement of recommendation performance by taking social interests into account, and experimental results show that our algorithm can alleviate the user cold-start problem more effectively compared with the mass diffusion and user-based collaborative filtering methods.

  7. Asteroid orbits with Gaia using random-walk statistical ranging

    Muinonen, Karri; Fedorets, Grigori; Pentikäinen, Hanna; Pieniluoma, Tuomo; Oszkiewicz, Dagmara; Granvik, Mikael; Virtanen, Jenni; Tanga, Paolo; Mignard, François; Berthier, Jérôme; Dell`Oro, Aldo; Carry, Benoit; Thuillot, William


    We describe statistical inverse methods for the computation of initial asteroid orbits within the data processing and analysis pipeline of the ESA Gaia space mission. Given small numbers of astrometric observations across short time intervals, we put forward a random-walk ranging method, in which the orbital-element phase space is uniformly sampled, up to a limiting χ2-value, with the help of the Markov-chain Monte Carlo technique (MCMC). The sample orbits obtain weights from the a posteriori probability density value and the MCMC rejection rate. For the first time, we apply the method to Gaia astrometry of asteroids. The results are nominal in that the method provides realistic estimates for the orbital uncertainties and meets the efficiency requirements for the daily, short-term processing of unknown objects.

  8. Renormalized field theory of collapsing directed randomly branched polymers.

    Janssen, Hans-Karl; Wevelsiep, Frank; Stenull, Olaf


    We present a dynamical field theory for directed randomly branched polymers and in particular their collapse transition. We develop a phenomenological model in the form of a stochastic response functional that allows us to address several interesting problems such as the scaling behavior of the swollen phase and the collapse transition. For the swollen phase, we find that by choosing model parameters appropriately, our stochastic functional reduces to the one describing the relaxation dynamics near the Yang-Lee singularity edge. This corroborates that the scaling behavior of swollen branched polymers is governed by the Yang-Lee universality class as has been known for a long time. The main focus of our paper lies on the collapse transition of directed branched polymers. We show to arbitrary order in renormalized perturbation theory with epsilon expansion that this transition belongs to the same universality class as directed percolation. PMID:19905335

  9. Random walk generated by random permutations of {1, 2, 3, ..., n + 1}

    We study properties of a non-Markovian random walk X(n)l, l = 0, 1, 2, ..., n, evolving in discrete time l on a one-dimensional lattice of integers, whose moves to the right or to the left are prescribed by the rise-and-descent sequences characterizing random permutations π of [n + 1] = {1, 2, 3, ..., n + 1}. We determine exactly the probability of finding the end-point Xn = X(n)n of the trajectory of such a permutation-generated random walk (PGRW) at site X, and show that in the limit n → ∞ it converges to a normal distribution with a smaller, compared to the conventional Polya random walk, diffusion coefficient. We formulate, as well, an auxiliary stochastic process whose distribution is identical to the distribution of the intermediate points X(n)l, l < n, which enables us to obtain the probability measure of different excursions and to define the asymptotic distribution of the number of 'turns' of the PGRW trajectories

  10. Maximal Displacement for Bridges of Random Walks in a Random Environment

    Gantert, Nina


    It is well known that the distribution of simple random walks on $\\bf{Z}$ conditioned on returning to the origin after $2n$ steps does not depend on $p= P(S_1 = 1)$, the probability of moving to the right. Moreover, conditioned on $\\{S_{2n}=0\\}$ the maximal displacement $\\max_{k\\leq 2n} |S_k|$ converges in distribution when scaled by $\\sqrt{n}$ (diffusive scaling). We consider the analogous problem for transient random walks in random environments on $\\bf{Z}$. We show that under the quenched law $P_\\omega$ (conditioned on the environment $\\omega$), the maximal displacement of the random walk when conditioned to return to the origin at time $2n$ is no longer necessarily of the order $\\sqrt{n}$. If the environment is nestling (both positive and negative local drifts exist) then the maximal displacement conditioned on returning to the origin at time $2n$ is of order $n^{\\kappa/(\\kappa+1)}$, where the constant $\\kappa>0$ depends on the law on environment. On the other hand, if the environment is marginally nestli...

  11. Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?

    Czégel, Dániel; Palla, Gergely


    Signs of hierarchy are prevalent in a wide range of systems in nature and society. One of the key problems is quantifying the importance of hierarchical organisation in the structure of the network representing the interactions or connections between the fundamental units of the studied system. Although a number of notable methods are already available, their vast majority is treating all directed acyclic graphs as already maximally hierarchical. Here we propose a hierarchy measure based on random walks on the network. The novelty of our approach is that directed trees corresponding to multi level pyramidal structures obtain higher hierarchy scores compared to directed chains and directed stars. Furthermore, in the thermodynamic limit the hierarchy measure of regular trees is converging to a well defined limit depending only on the branching number. When applied to real networks, our method is computationally very effective, as the result can be evaluated with arbitrary precision by subsequent multiplications of the transition matrix describing the random walk process. In addition, the tests on real world networks provided very intuitive results, e.g., the trophic levels obtained from our approach on a food web were highly consistent with former results from ecology.

  12. Genetic Analysis of Daily Maximum Milking Speed by a Random Walk Model in Dairy Cows

    Karacaören, Burak; Janss, Luc; Kadarmideen, Haja

    Data were obtained from dairy cows stationed at research farm ETH Zurich for maximum milking speed. The main aims of this paper are a) to evaluate if the Wood curve is suitable to model mean lactation curve b) to predict longitudinal breeding values by random regression and random walk models of...... maximum milking speed. Wood curve did not provide a good fit to the data set. Quadratic random regressions gave better predictions compared with the random walk model. However random walk model does not need to be evaluated for different orders of regression coefficients. In addition with the Kalman...

  13. Fractal Dimension of Randomly Branched Polymers in a Good Solvent

    巴信武; 张书文; 王海军; 王素娟; 韩颖慧


    We propose a concept of subchains for randomly branched polymers. As a direct application of this concept,the asymptotic expression of the average mean square radius of gyration is determined to give the fractal dimensions, in which the excluded volume effect is taken into consideration. Furthermore, we investigate a scaling relation that is associated with the Flory exponent v, the fractal dimension df and the polydispersity exponent τ.

  14. Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?

    Czégel, Dániel


    Signs of hierarchy are prevalent in a wide range of systems in nature and society. One of the key problems is quantifying the importance of hierarchical organisation in the structure of the network representing the interactions or connections between the fundamental units of the studied system. Although a number of notable methods are already available, their vast majority is treating all directed acyclic graphs as already maximally hierarchical. Here we propose a hierarchy measure based on random walks on the network. The novelty of our approach is that directed trees corresponding to multi level pyramidal structures obtain higher hierarchy scores compared to directed chains and directed stars. Furthermore, in the thermodynamic limit the hierarchy measure of regular trees is converging to a well defined limit depending only on the branching number. When applied to real networks, our method is computationally very effective, as the result can be evaluated with arbitrary precision by subsequent multiplications...

  15. Stretched Exponential Relaxation in Disordered Complex Systems: Fractal Time Random Walk Model

    Ekrem Aydmer


    We have analytically derived the relaxation function for one-dimensional disordered complex systems in terms of autocorrelation function of fractal time random walk by using operator formalism. We have shown that the relaxation function has stretched exponential, i.e. the Kohlrausch-Williams-Watts character for a fractal time random walk process.

  16. On the Eigenspaces of Lamplighter Random Walks and Percolation Clusters on Graphs

    Lehner, Franz


    We show that the Plancherel measure of the lamplighter random walk on a graph coincides with the expected spectral measure of the absorbing random walk on the Bernoulli percolation clusters. In the subcritical regime the spectrum is pure point and we construct a complete orthonormal basis of finitely supported eigenfunctions.

  17. Ranking Competitors Using Degree-Neutralized Random Walks

    Shin, Seungkyu; Park, Juyong


    Competition is ubiquitous in many complex biological, social, and technological systems, playing an integral role in the evolutionary dynamics of the systems. It is often useful to determine the dominance hierarchy or the rankings of the components of the system that compete for survival and success based on the outcomes of the competitions between them. Here we propose a ranking method based on the random walk on the network representing the competitors as nodes and competitions as directed edges with asymmetric weights. We use the edge weights and node degrees to define the gradient on each edge that guides the random walker towards the weaker (or the stronger) node, which enables us to interpret the steady-state occupancy as the measure of the node's weakness (or strength) that is free of unwarranted degree-induced bias. We apply our method to two real-world competition networks and explore the issues of ranking stabilization and prediction accuracy, finding that our method outperforms other methods includ...

  18. Intracellular transport of insulin granules is a subordinated random walk.

    Tabei, S M Ali; Burov, Stanislav; Kim, Hee Y; Kuznetsov, Andrey; Huynh, Toan; Jureller, Justin; Philipson, Louis H; Dinner, Aaron R; Scherer, Norbert F


    We quantitatively analyzed particle tracking data on insulin granules expressing fluorescent fusion proteins in MIN6 cells to better understand the motions contributing to intracellular transport and, more generally, the means for characterizing systems far from equilibrium. Care was taken to ensure that the statistics reflected intrinsic features of the individual granules rather than details of the measurement and overall cell state. We find anomalous diffusion. Interpreting such data conventionally requires assuming that a process is either ergodic with particles working against fluctuating obstacles (fractional brownian motion) or nonergodic with a broad distribution of dwell times for traps (continuous-time random walk). However, we find that statistical tests based on these two models give conflicting results. We resolve this issue by introducing a subordinated scheme in which particles in cages with random dwell times undergo correlated motions owing to interactions with a fluctuating environment. We relate this picture to the underlying microtubule structure by imaging in the presence of vinblastine. Our results provide a simple physical picture for how diverse pools of insulin granules and, in turn, biphasic secretion could arise. PMID:23479621

  19. Global Warming as a Manifestation of a Random Walk.

    Gordon, A. H.


    Global and hemispheric series of surface temperature anomalies are examined in an attempt to isolate any specific features of the structure of the series that might contribute to the global warming of about 0.5°C which has been observed over the past 100 years. It is found that there are no significant differences between the means of the positive and negative values of the changes in temperature from one year to the next; neither do the relative frequencies of the positive and negative values differ from the frequencies that would be expected by chance with a probability near 0.5. If the interannual changes are regarded as changes of unit magnitude and plotted in a Cartesian frame of reference with time measured along the x axis and yearly temperature differences along the y axis, the resulting path closely resembles the kind of random walk that occurs during a coin-tossing game.We hypothesize that the global and hemispheric temperature series are the result of a Markov process. The climate system is subjected to various forms of random impulses. It is argued that the system fails to return to its former state after reacting to an impulse but tends to adjust to a new state of equilibrium as prescribed by the shock. This happens because a net positive feedback accompanies each shock and slightly alters the environmental state.

  20. A central limit theorem for random walk in random environment on marked Galton-Watson trees

    Faraud, Gabriel


    In this article we focus on a general model of random walk on random marked trees. We prove a recurrence criterion, analogue to the recurrence criterion proved by R. Lyons and Robin Pemantle (1992) in a slightly different model. In the critical case, we obtain a criterion for the positive/null recurrence. Several regimes appear, as proved (in a similar model), by Y. Hu and Z. Shi (2007). We focus on the "diffusive" regime and improve their result in this case, by obtaining a functional Centra...

  1. Critical exponents of random XX and XY chains: Exact results via random walks

    Rieger, H.; Juhász, R.; Iglói, F.


    We study random XY and (dimerized) XX spin-1/2 quantum spin chains at their quantum phase transition driven by the anisotropy and dimerization, respectively. Using exact expressions for magnetization, correlation functions and energy gap, obtained by the free fermion technique, the critical and off-critical (Griffiths-McCoy) singularities are related to persistence properties of random walks. In this way we determine exactly the decay exponents for surface and bulk transverse and longitudinal correlations, correlation length exponent and dynamical exponent.

  2. Quenched large deviations for multidimensional random walk in random environment: a variational formula

    Rosenbluth, Jeffrey M


    We take the point of view of the particle in a multidimensional nearest neighbor random walk in random environment (RWRE). We prove a quenched large deviation principle and derive a variational formula for the quenched rate function. Most of the previous results in this area rely on the subadditive ergodic theorem. We employ a different technique which is based on a minimax theorem. Large deviation principles for RWRE have been proven for i.i.d. nestling environments subject to a moment condition and for ergodic uniformly elliptic environments. We assume only that the environment is ergodic and the transition probabilities satisfy a moment condition.




    The concepts of branching chain in random environmnet and canonical branching chain in random environment axe introduced. Moreover the existence of these chains is proved. Finally the exact formulas of mathematical expectation and variance of branching chain in random environment axe also given.

  4. Discrete Randomness in Discrete Time Quantum Walk: Study Via Stochastic Averaging

    Ellinas, D.; Bracken, A. J.; Smyrnakis, I.


    The role of classical noise in quantum walks (QW) on integers is investigated in the form of discrete dichotomic random variable affecting its reshuffling matrix parametrized as a SU2)/U (1) coset element. Analysis in terms of quantum statistical moments and generating functions, derived by the completely positive trace preserving (CPTP) map governing evolution, reveals a pronounced eventual transition in walk's diffusion mode, from a quantum ballistic regime with rate O(t) to a classical diffusive regime with rate O(√{t}), when condition (strength of noise parameter)2 × (number of steps) = 1, is satisfied. The role of classical randomness is studied showing that the randomized QW, when treated on the stochastic average level by means of an appropriate CPTP averaging map, turns out to be equivalent to a novel quantized classical walk without randomness. This result emphasizes the dual role of quantization/randomization in the context of classical random walk.

  5. Giant vacant component left by a random walk in a random d-regular graph

    Cerny, Jiri; Windisch, David


    We study the trajectory of a simple random walk on a d-regular graph with d>2 and locally tree-like structure as the number n of vertices grows. Examples of such graphs include random d-regular graphs and large girth expanders. For these graphs, we investigate percolative properties of the set of vertices not visited by the walk until time un, where u>0 is a fixed positive parameter. We show that this so-called vacant set exhibits a phase transition in u in the following sense: there exists an explicitly computable threshold u* such that, with high probability as n grows, if uu*, then it has a volume of order log(n). The critical value u* coincides with the critical intensity of a random interlacement process (introduced by Sznitman [arXiv:0704.2560]) on a d-regular tree. We also show that the random interlacement model describes the structure of the vacant set in local neighbourhoods.

  6. Branching out

    Biggins, J D


    Results on the behaviour of the rightmost particle in the $n$th generation in the branching random walk are reviewed and the phenomenon of anomalous spreading speeds, noticed recently in related deterministic models, is considered. The relationship between such results and certain coupled reaction-diffusion equations is indicated.

  7. Finite element analysis of random interacting branched cracks

    Combination of mechanical loads and aggressive environment causes a development of random interacting branched cracks in materials with grain structure (e.g. Inconel 600 in PWR steam generator tubing). Understanding and predicting behavior of such cracks are important for the safety of nuclear facilities and also for economical reasons in common process industry. Reliable and robust analysis of such cracks is possible only with numerical methods, among which finite element method is the most suitable for the task. The paper proposes procedure, which enables analysis of large number of random interacting branched cracks for linear elastic materials. The proposed procedure consists of numerical analysis of crack pattern with finite element method (using the general-purpose finite element code ABAQUS with calculation of J-integral) and mixed mode decomposition of J-integral using displacements at crack surfaces. Proposed procedure is used to evaluate different patterns of random two-dimensional complex shaped cracks in general biaxial stress field. The accuracy of the numerical results obtained is compared with reference solutions from the literature. (author)

  8. Network heterogeneity and node capacity lead to heterogeneous scaling of fluctuations in random walks on graphs

    Kosmidis, Kosmas; Beber, Moritz; Hütt, Marc-Thorsten


    Random walks are one of the best investigated dynamical processes on graphs. A particularly fascinating phenomenon is the scaling relationship of fluctuations $\\sigma $ with the average flux $\\langle f \\rangle $. Here we analyze how network topology and nodes with finite capacity lead to deviations from a simple scaling law $\\sigma \\sim \\langle f \\rangle ^\\alpha$. Sources of randomness are the random walk itself (internal noise) and the fluctuation of the number of walkers (external noise). W...

  9. Limit theorems for random walks on a strip in subdiffusive regime

    Dolgopyat, Dmitry; Goldsheid, Ilya


    We study the asymptotic behaviour of occupation times of a transient random walk in quenched random environment on a strip in a sub-diffusive regime. The asymptotic behaviour of hitting times, which is a more traditional object of study, is the exactly same. As a particular case, we solve a long standing problem of describing the asymptotic behaviour of a random walk with bounded jumps on a one-dimensional lattice

  10. Learning Markov Random Walks for robust subspace clustering and estimation.

    Liu, Risheng; Lin, Zhouchen; Su, Zhixun


    Markov Random Walks (MRW) has proven to be an effective way to understand spectral clustering and embedding. However, due to less global structural measure, conventional MRW (e.g., the Gaussian kernel MRW) cannot be applied to handle data points drawn from a mixture of subspaces. In this paper, we introduce a regularized MRW learning model, using a low-rank penalty to constrain the global subspace structure, for subspace clustering and estimation. In our framework, both the local pairwise similarity and the global subspace structure can be learnt from the transition probabilities of MRW. We prove that under some suitable conditions, our proposed local/global criteria can exactly capture the multiple subspace structure and learn a low-dimensional embedding for the data, in which giving the true segmentation of subspaces. To improve robustness in real situations, we also propose an extension of the MRW learning model based on integrating transition matrix learning and error correction in a unified framework. Experimental results on both synthetic data and real applications demonstrate that our proposed MRW learning model and its robust extension outperform the state-of-the-art subspace clustering methods. PMID:25005156

  11. Free-Dirac-particle evolution as a quantum random walk

    Bracken, A. J.; Ellinas, D.; Smyrnakis, I.


    It is known that any positive-energy state of a free Dirac particle that is initially highly localized evolves in time by spreading at speeds close to the speed of light. As recently indicated by Strauch, this general phenomenon, and the resulting “two-horned” distributions of position probability along any axis through the point of initial localization, can be interpreted in terms of a quantum random walk, in which the roles of “coin” and “walker” are naturally associated with the spin and translational degrees of freedom in a discretized version of Dirac’s equation. We investigate the relationship between these two evolutions analytically and show how the evolved probability density on the x axis for the Dirac particle at any time t can be obtained from the asymptotic form of the probability distribution for the position of a “quantum walker.” The case of a highly localized initial state is discussed as an example.

  12. Lagrangian modelling of plankton motion: From deceptively simple random walks to Fokker-Planck and back again

    Visser, Andre

    The movement of plankton, either by turbulent mixing or their own inherent motility, can be simulated in a Lagrangian framework as a random walk. Validation of random walk simulations is essential. There is a continuum of mathematically valid stochastic integration schemes upon which random walk...

  13. The Limit Theorems for Random Walk with State Space R in a Space-time Random Environment

    Wei Gang WANG; Zhen Long GAO; Di He HU


    We consider a discrete time random walk on real number space in a space-time random environment. We state that when the random environment is i.i.d., under the marginal annealed law, the law of large numbers, iterated law and CLT of the process are correct. Using a martingale approach, we also state an a.s. invariance principle for random walks in general random environment whose hypothesis requires a subdiffusive bound on the variance of the quenched mean, under an ergodic invariant measure for the environment chain.

  14. Quantum Random Walks and their Convergence to Evans-Hudson Flows

    Lingaraj Sahu


    Using coordinate-free basic operators on toy Fock spaces, quantum random walks are defined following the ideas of Attal and Pautrat. Extending the result for one dimensional noise, strong convergence of quantum random walks associated with bounded structure maps to Evans–Hudson flow is proved under suitable assumptions. Starting from the bounded generator of a given uniformly continuous quantum dynamical semigroup on a von Neumann algebra, we have constructed quantum random walks which converges strongly and the strong limit gives an Evans–Hudson dilation for the semigroup.

  15. Development and application of random walk model of atmospheric diffusion in emergency response of nuclear accidents

    Plume concentration prediction is one of the main contents of radioactive consequence assessment for early emergency to nuclear accidents. This paper describes random characteristics of atmospheric diffusion itself, introduces random walk model of atmospheric diffusion (Random Walk), and compare with Lagrangian puff model (RIMPUFF) in the nuclear emergency decision support system (RODOS) developed by European Community for verification. The results show the concentrations calculated by the two models are quite close except that plume area calculated by Random Walk is a little smaller than that by RIMPUFF. The random walk model for atmospheric diffusion can simulate the atmospheric diffusion in case of nuclear accidents and provide more actual information for early emergency and consequence assessment as one atmospheric diffusion module of the nuclear emergency decision support system. (authors)

  16. Collapse transition of randomly branched polymers: renormalized field theory.

    Janssen, Hans-Karl; Stenull, Olaf


    We present a minimal dynamical model for randomly branched isotropic polymers, and we study this model in the framework of renormalized field theory. For the swollen phase, we show that our model provides a route to understand the well-established dimensional-reduction results from a different angle. For the collapse θ transition, we uncover a hidden Becchi-Rouet-Stora supersymmetry, signaling the sole relevance of tree configurations. We correct the long-standing one-loop results for the critical exponents, and we push these results on to two-loop order. For the collapse θ' transition, we find a runaway of the renormalization group flow, which lends credence to the possibility that this transition is a fluctuation-induced first-order transition. Our dynamical model allows us to calculate for the first time the fractal dimension of the shortest path on randomly branched polymers in the swollen phase as well as at the collapse transition and related fractal dimensions. PMID:21728509

  17. Random walk in a finite directed graph subject to a synchronizing road coloring

    Yano, Kouji


    A constructive proof is given to the fact that any ergodic Markov chain can be realized as a random walk subject to a synchronizing road coloring. Redundancy (ratio of extra entropy) in such a realization is also studied.

  18. Crime Trends vs. Random Walk. : The pitfalls of ad hoc chart reading.

    von Hofer, Hanns


    This research note questions the common practice of ad hoc chart reading without formulating a sensible statistical model of the data beforehand and argues that the random walk model should not be overlooked when analyzing time series of crime data.

  19. Analytic calculation of hadron spectrum by random walk approximation in lattice QCD

    The authors explain the detail of how to calculate the meson and baryon spectrum by random walk approximation analytically. The results are compared with experimental values and Monte-Carlo results. (Auth.)

  20. Age-dependent branching processes in random environments


    We consider an age-dependent branching process in random environments. The environments are represented by a stationary and ergodic sequence ξ = (ξ0,ξ1,...) of random variables. Given an environment ξ, the process is a non-homogenous Galton-Watson process, whose particles in n-th generation have a life length distribution G(ξn) on R+, and reproduce independently new particles according to a probability law p(ξn) on N. Let Z(t) be the number of particles alive at time t. We first find a characterization of the conditional probability generating function of Z(t) (given the environment ξ) via a functional equation, and obtain a criterion for almost certain extinction of the process by comparing it with an embedded Galton-Watson process. We then get expressions of the conditional mean EξZ(t) and the global mean EZ(t), and show their exponential growth rates by studying a renewal equation in random environments.

  1. Central limit theorem for biased random walk on multi-type Galton-Watson trees

    Dembo, Amir; Sun, Nike


    Let T be a rooted supercritical multi-type Galton-Watson (MGW) tree with types coming from a finite alphabet, conditioned to non-extinction. The lambda-biased random walk (X_t, t>=0) on T is the nearest-neighbor random walk which, when at a vertex v with d(v) offspring, moves closer to the root with probability lambda/[lambda+d(v)], and to each of the offspring with probability 1/[lambda+d(v)]. This walk is recurrent for lambda>=rho and transient for 0

  2. Computer simulations of randomly branching polymers: annealed versus quenched branching structures

    Rosa, Angelo; Everaers, Ralf


    We present computer simulations of three systems of randomly branching polymers in d = 3 dimensions: ideal trees and self-avoiding trees with annealed and quenched connectivities. In all cases, we performed a detailed analysis of trees connectivities, spatial conformations and statistical properties of linear paths on trees, and compare the results to the corresponding predictions of Flory theory. We confirm that, overall, the theory predicts correctly that trees with quenched ideal connectivity exhibit less overall swelling in good solvent than corresponding trees with annealed connectivity even though they are more strongly stretched on the path level. At the same time, we emphasize the inadequacy of the Flory theory in predicting the behaviour of other, and equally relevant, observables like contact probabilities between tree nodes. We show, then, that contact probabilities can be aptly characterized by introducing a novel critical exponent, {θ }{path}, which accounts for how they decay as a function of the node-to-node path distance on the tree.

  3. Random walk study of electron motion in helium in crossed electromagnetic fields

    Englert, G. W.


    Random walk theory, previously adapted to electron motion in the presence of an electric field, is extended to include a transverse magnetic field. In principle, the random walk approach avoids mathematical complexity and concomitant simplifying assumptions and permits determination of energy distributions and transport coefficients within the accuracy of available collisional cross section data. Application is made to a weakly ionized helium gas. Time of relaxation of electron energy distribution, determined by the random walk, is described by simple expressions based on energy exchange between the electron and an effective electric field. The restrictive effect of the magnetic field on electron motion, which increases the required number of collisions per walk to reach a terminal steady state condition, as well as the effect of the magnetic field on electron transport coefficients and mean energy can be quite adequately described by expressions involving only the Hall parameter.

  4. Application of random walk model to fit temperature in 46 gamma world cities from 1901 to 1998

    Shaomin Yan; Guang Wu


    Very recently, we have applied the random walk model to fit the global temperature anomaly, CRUTEM3. With encouraging results, we apply the random walk model to fit the temperature walk that is the conversion of recorded tem-perature and real recorded temperature in 46 gamma world cities from 1901 to 1998 in this study. The results show that the random walk model can fit both temperature walk and real recorded temperature although the fitted results from other climate models are unavailable f...




    Random walks are one of the best investigated dynamical processes on graphs. A particularly fascinating phenomenon is the scaling relationship of fluctuations σ with the average flux 〈f〉. Here we analyze how network topology and nodes with finite capacity lead to deviations from a simple scaling law σ ~ 〈f〉α. Sources of randomness are the random walk itself (internal noise) and the fluctuation of the number of walkers (external noise). We obtained exact results for the extreme case of a star ...

  6. Random Walks with Bivariate Levy-Stable Jumps in Comparison with Levy Flights

    In this paper we compare the Levy flight model on a plane with the random walk resulting from bivariate Levy-stable random jumps with the uniform spectral measure. We show that, in general, both processes exhibit similar properties, i.e. they are characterized by the presence of the jumps with extremely large lengths and uniformly distributed directions (reflecting the same heavy-tail behavior and the spherical symmetry of the jump distributions), connecting characteristic clusters of short steps. The bivariate Levy-stable random walks, belonging to the class of the well investigated stable processes, can enlarge the class of random-walk models for transport phenomena if other than uniform spectral measures are considered. (author)

  7. Generalized Continuous-Time Random Walks (CTRW), Subordination by Hitting Times and Fractional Dynamics

    Kolokoltsov, Vassili N.


    Functional limit theorem for continuous-time random walks (CTRW) are found in general case of dependent waiting times and jump sizes that are also position dependent. The limiting anomalous diffusion is described in terms of fractional dynamics. Probabilistic interpretation of generalized fractional evolution is given in terms of the random time change (subordination) by means of hitting times processes.

  8. Simple random walk on the uniform infinite planar quadrangulation: Subdiffusivity via pioneer points

    Benjamini, Itai


    We study the pioneer points of the simple random walk on the uniform infinite planar quadrangulation (UIPQ) using an adaptation of the peeling procedure of Angel to the quadrangulation case. Our main result is that, up to polylogarithmic factors, $n^3$ pioneer points have been discovered before the walk exits the ball of radius $n$ in the UIPQ. As a result we verify the KPZ relation in the particular case of the pioneer exponent and prove that the walk is subdiffusive with exponent less than 1/3. Along the way, new geometric controls on the UIPQ are established.

  9. A new Monte-Carlo approach to the critical properties of self-avoiding random walks

    Aragão De Carvalho, C.; Caracciolo, S.


    We investigate the critical properties of self-avoiding random walks on hypercubic lattices in dimensions three and four. We consider the statistical ensembles of all such walks as a function of an inverse temperature β and associate to each walk the statistical weight βL, where L is its length. This allows us to use a novel and very efficient Monte-Carlo procedure. A new interpretation of the exponent γ, suitable for numerical investigations, is presented. In dimension four, the logarithmic ...

  10. The broken supersymmetry phase of a self-avoiding random walk

    We consider a weakly self-avoiding random walk on a hierarchical lattice in d = 4 dimensions. We show that for choices of the killing rate a less than the critical value ac the dominant walks fill space, which corresponds to a spontaneously broken supersymmetry phase. We identify the asymptotic density to which walks fill space, ρ(a), to be a supersymmetric order parameter for this transition. We prove that ρ(a) ∼ (ac - a) (-log(ac -a))1/2 as a → ac, which is mean-field behavior with logarithmic corrections, as expected for a system in its upper critical dimension. (orig.)

  11. Transient superdiffusion in random walks with a q-exponentially decaying memory profile

    Moura, Thiago R. S.; Viswanathan, G. M.; da Silva, M. A. A.; Cressoni, J. C.; da Silva, L. R.


    We propose a random walk model with q-exponentially decaying memory profile. The q-exponential function is a generalization of the ordinary exponential function. In the limit q → 1, the q-exponential becomes the ordinary exponential function. This model presents a Markovian diffusive regime that is characterized by finite memory correlations. It is well known, that central limit theorems prohibit superdiffusion for Markovian walks with finite variance of step sizes. In this problem we report the outcome of a transient superdiffusion for finite sized walks.

  12. The Scaling Limit of Self-Avoiding Random Walk in High Dimensions

    Slade, Gordon


    The Brydges-Spencer lace expansion is used to prove that the scaling limit of the finite-dimensional distributions of self-avoiding random walk in the $d$-dimensional cubic lattice $\\mathbb{Z}^d$ is Gaussian, if $d$ is sufficiently large. It is also shown that the critical exponent $\\gamma$ for the number of self-avoiding walks is equal to 1, if $d$ is sufficiently large.

  13. A local CLT for convolution equations with an application to weakly self-avoiding random walks

    Avena, Luca; Bolthausen, Erwin; Ritzmann, Christine


    We prove error bounds in a central limit theorem for solutions of certain convolution equations. The main motivation for investigating these equations stems from applications to lace expansions, in particular to weakly self-avoiding random walks in high dimensions. As an application we treat such self-avoiding walks in continuous space. The bounds obtained are sharper than the ones obtained by other methods.

  14. Length of clustering algorithms based on random walks with an application to neuroscience

    Highlights: ► Study of the choice of the length used by a clustering algorithm called Walktrap. ► Study of the convergence rate of random walks on graph. ► Description of the cutoff phenomenon for random walks on graph. ► Introduction of a dynamical hierarchical clustering algorithm for finite sequences of graphs. - Abstract: In this paper we show how the notions of conductance and cutoff can be used to determine the length of the random walks in some clustering algorithms. We consider graphs which are globally sparse but locally dense. They present a community structure: there exists a partition of the set of vertices into subsets which display strong internal connections but few links between each other. Using a distance between nodes built on random walks we consider a hierarchical clustering algorithm which provides a most appropriate partition. The length of these random walks has to be chosen in advance and has to be appropriate. Finally, we introduce an extension of this clustering algorithm to dynamical sequences of graphs on the same set of vertices.

  15. Random self-similar trees and a hierarchical branching process

    Kovchegov, Yevgeniy


    We study self-similarity in random binary rooted trees. In a well-understood case of Galton-Watson trees, a distribution is called self-similar if it is invariant with respect to the operation of pruning, which cuts the tree leaves. This only happens in the critical case (a constant process progeny), which also exhibits other special symmetries. We extend the prune-invariance set-up to a non-Markov situation and trees with edge lengths. In this general case the class of self-similar processes becomes much richer and covers a variety of practically important situations. The main result is construction of the hierarchical branching processes that satisfy various self-similarity constraints (distributional, mean, in edge-lengths) depending on the process parameters. Taking the limit of averaged stochastic dynamics, as the number of trajectories increases, we obtain a deterministic system of differential equations that describes the process evolution. This system is used to establish a phase transition that separ...

  16. Novel pseudo-random number generator based on quantum random walks.

    Yang, Yu-Guang; Zhao, Qian-Qian


    In this paper, we investigate the potential application of quantum computation for constructing pseudo-random number generators (PRNGs) and further construct a novel PRNG based on quantum random walks (QRWs), a famous quantum computation model. The PRNG merely relies on the equations used in the QRWs, and thus the generation algorithm is simple and the computation speed is fast. The proposed PRNG is subjected to statistical tests such as NIST and successfully passed the test. Compared with the representative PRNG based on quantum chaotic maps (QCM), the present QRWs-based PRNG has some advantages such as better statistical complexity and recurrence. For example, the normalized Shannon entropy and the statistical complexity of the QRWs-based PRNG are 0.999699456771172 and 1.799961178212329e-04 respectively given the number of 8 bits-words, say, 16Mbits. By contrast, the corresponding values of the QCM-based PRNG are 0.999448131481064 and 3.701210794388818e-04 respectively. Thus the statistical complexity and the normalized entropy of the QRWs-based PRNG are closer to 0 and 1 respectively than those of the QCM-based PRNG when the number of words of the analyzed sequence increases. It provides a new clue to construct PRNGs and also extends the applications of quantum computation. PMID:26842402

  17. Optimized quantum random-walk search algorithm for multi-solution search

    张宇超; 鲍皖苏; 汪翔; 付向群


    This study investigates the multi-solution search of the optimized quantum random-walk search algorithm on the hypercube. Through generalizing the abstract search algorithm which is a general tool for analyzing the search on the graph to the multi-solution case, it can be applied to analyze the multi-solution case of quantum random-walk search on the graph directly. Thus, the computational complexity of the optimized quantum random-walk search algorithm for the multi-solution search is obtained. Through numerical simulations and analysis, we obtain a critical value of the proportion of solutions q. For a given q, we derive the relationship between the success rate of the algorithm and the number of iterations when q is no longer than the critical value.

  18. Self-avoiding random walk with multiple site weightings and restrictions.

    Krawczyk, J; Prellberg, T; Owczarek, A L; Rechnitzer, A


    We introduce a new class of models for polymer collapse, given by random walks on regular lattices which are weighted according to multiple site visits. A Boltzmann weight omegal is assigned to each (l+1)-fold visited lattice site, and self-avoidance is incorporated by restricting to a maximal number K of visits to any site via setting omegal=0 for l>or=K. In this Letter we study this model on the square and simple cubic lattices for the case K=3. Moreover, we consider a variant of this model, in which we forbid immediate self-reversal of the random walk. We perform simulations for random walks up to n=1024 steps using FlatPERM, a flat histogram stochastic growth algorithm. We find evidence that the existence of a collapse transition depends sensitively on the details of the model and has an unexpected dependence on dimension. PMID:16907227

  19. Quantum random walks in a coherent atomic system via electromagnetically induced transparency

    We propose a scheme to realize the quantum random walk in a coherent five-level atomic system via electromagnetically induced transparency (EIT). From optical Bloch equations describing the dynamics of the electromagnetic field and atomic population and coherence, we show that two circular-polarized components of a probe field display different dispersion properties and hence acquire different phase-shift modifications when passing through atomic cells. We demonstrate that the quantum coherence and interference owing to the EIT effect result in a low absorption of the probe field and hence provide a possibility of realizing a many-step phase-shift quantum random walk. The scheme may be used to experimentally highlight the characteristics of quantum random walk and lead to a promising application for quantum computation

  20. Random Walks on Directed Networks: Inference and Respondent-driven Sampling

    Malmros, Jens; Britton, Tom


    Respondent driven sampling (RDS) is a method often used to estimate population properties (e.g. sexual risk behavior) in hard-to-reach populations. It combines an effective modified snowball sampling methodology with an estimation procedure that yields unbiased population estimates under the assumption that the sampling process behaves like a random walk on the social network of the population. Current RDS estimation methodology assumes that the social network is undirected, i.e. that all edges are reciprocal. However, empirical social networks in general also have non-reciprocated edges. To account for this fact, we develop a new estimation method for RDS in the presence of directed edges on the basis of random walks on directed networks. We distinguish directed and undirected edges and consider the possibility that the random walk returns to its current position in two steps through an undirected edge. We derive estimators of the selection probabilities of individuals as a function of the number of outgoing...



    The investigation for branching processes has a long history by their strong physics background, but only a few authors have investigated the branching processes in random environments. First of all, the author introduces the concepts of the multitype canonical Markov branching chain in random environment (CMBCRE) and multitype Markov branching chain in random environment (MBCRE) and proved that CMBCRE must be MBCRE, and any MBCRE must be equivalent to another CMBCRE in distribution. The main results of this article are the construction of CMBCRE and some of its probability properties.

  2. Rate of escape of random walks on wreath products and related groups

    Revelle, David


    This article examines the rate of escape for a random walk on $G\\wr \\Z$ and proves laws of the iterated logarithm for both the inner and outer radius of escape. The class of G for which these results hold includes finite, G as well as groups of the form $H\\wr \\Z$, so the construction can be iterated. Laws of the iterated logarithm are also found for random walk on Baumslag--Solitar groups and a discrete version of the Sol geometry.

  3. The Laplacian-$b$ random walk and the Schramm-Loewner evolution

    Lawler, Gregory F.


    The Laplacian-$b$ random walk is a measure on self-avoiding paths that at each step has translation probabilities weighted by the $b$th power of the probability that a simple random walk avoids the path up to that point. We give a heuristic argument as to what the scaling limit should be and call this process the Laplacian-$b$ motion, $LM_b$. In simply connected domains, this process is the Schramm-Loewner evolution with parameter $\\kappa = 6/(2b+1)$. In no...

  4. Directed Random Walk on the Lattices of Genus Two

    Nazarenko, A. V.


    The object of the present investigation is an ensemble of self-avoiding and directed graphs belonging to eight-branching Cayley tree (Bethe lattice) generated by the Fucsian group of a Riemann surface of genus two and embedded in the Pincar\\'e unit disk. We consider two-parametric lattices and calculate the multifractal scaling exponents for the moments of the graph lengths distribution as functions of these parameters. We show the results of numerical and statistical computations, where the ...

  5. Quantum random walk on the line as a markovian process

    Romanelli, A; Siri, R; Abal, G; Auyuanet, A; Donangelo, R J


    We analyze in detail the discrete--time quantum walk on the line by separating the quantum evolution equation into Markovian and interference terms. As a result of this separation, it is possible to show analytically that the quadratic increase in the variance of the quantum walker's position with time is a direct consequence of the coherence of the quantum evolution. If the evolution is decoherent, as in the classical case, the variance is shown to increase linearly with time, as expected. Furthermore we show that this system has an evolution operator analogous to that of a resonant quantum kicked rotor. As this rotator may be described through a quantum computational algorithm, one may employ this algorithm to describe the time evolution of the quantum walker.

  6. Multitype branching processes with immigration in random environment and polling systems

    Vatutin, Vladimir


    For multitype branching processes with immigration evolving in a random environment and producing a final product we find the tail distribution of the size of the final product accumulated in the system for a life period. Using this result we investigate the tail distribution of the busy periods of the branching type polling systems with random service disciplines and random positive switch-over times

  7. Continuous-Time Classical and Quantum Random Walk on Direct Product of Cayley Graphs

    S. Salimi; M.A. Jafarizadeh


    In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on complicated graphs. Using this method, we calculate the probability of continuous-time classical and quantum random walks on many of finite direct product Cayley graphs (complete cycle, complete Kn, charter and n-cube). Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.

  8. Simulation of the diffusion process in composite porous media by random walks

    ZHANG Yong


    A new random-walk interpolation scheme was developed to simulate solute transport through composite porous media with different porosities as well as different diffusivities. The significant influences of the abrupt variations of porosity and diffusivity on solute transport were simulated by tracking random walkers through a linear interpolation domain across the heterogeneity interface. The displacements of the random walkers within the interpolation region were obtained explicitly by establishing the equivalence between the Fokker-Planck equation and the advection-dispersion equation. Applications indicate that the random-walk interpolation method can simulate one- and two-dimensional, 2nd-order diffusion processes in composite media without local mass conservation errors. In addition, both the theoretical derivations and the numerical simulations show that the drift and dispersion of particles depend on the type of Markov process selected to reflect the dynamics of random walkers. If the nonlinear Langevin equation is used, the gradient of porosity and the gradient of diffusivity strongly affect the drift displacement of particles. Therefore, random-walking particles driven by the gradient of porosity,the gradient of diffusivity, and the random diffusion, can imitate the transport of solute under only pure diffusion in composite porous media containing abrupt variations of porosity and diffusivity.

  9. Pointwise upper estimates for transition probability of continuous time random walks on graphs

    Chen, Xinxing


    Let $X$ be a continuous time random walk on a weighted graph. Given the on-diagonal upper bounds of transition probabilities at two vertices $x_1$ and $x_2$, we use an adapted metric initiated by Davies, and obtain Gaussian upper estimates for the off-diagonal transition probability $P_{x_1}(X_t=x_2)$.

  10. Elliptic equation for random walks. Application to transport in microporous media

    Shapiro, Alexander


    We consider a process of random walks with arbitrary residence time distribution. We show that in many cases this process may not be described by the classical (Fick) parabolic diffusion equation, but an elliptic equation. An additional term proportional to the second time derivative takes into a...