Search

Let (Xn) be a sequence of independent identically distributed random variables with . A symmetric simple random walk is a discrete-time stochastic process (Sn)n ⩾ 0 defined by S0 = 0 and Sn = ∑ni = 1Xi for n ⩾ 1. Kn is called the number of returns to the origin if . Dobler (2015) showed that the distribution of Kn can be approximated by half-normal distribution and he also gave a uniform bound in terms of . After that, Sama-ae, Neammanee, and Chaidee (2016) gave a non uniform bound in terms of . Observe that, the exponent of z is 3. In this paper, we improve the exponent of z to be any natural number k which make the better constant than before.

The infinite two-sided loop-erased random walk (LERW) is a measure on infinite self-avoiding walks that can be viewed as giving the law of the `middle part' of an infinite LERW loop going through 0 and infinity. In this note we derive expressions for transition probabilities for this model in dimensions two and up. In the plane, the formula can be further expressed in terms of a Laplacian with signed weights acting on certain discrete harmonic functions at the tips of the walk, and taking a determinant. The discrete harmonic functions are closely related to a discrete version of the complex square-root., Comment: 21 pages. Minor corrections in second version

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.

We consider a random graph created by the long-range percolation on the nth stage finite subset of a fractal lattice called the pre-Sierpinski gasket. The long-range percolation is a stochastic model in which any pair of two points is connected by a random bond independently. On the random graph obtained as above, we consider a discrete-time random walk. We show that the mixing time of the random walk is of order \(2^{(s-d)n}\) if \(d

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are “easier to reach” by a random walk, but “more difficult to get out of.” We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self-contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective.

In this paper, we prove a number of related results on distance-regular graphs concerning electric resistance and simple random walk. We begin by proving several results on electric resistance; in particular we prove a sharp constant bounding the ratio of electrical resistances between any two pairs of points and give a counterexample to a conjecture made in a previous paper regarding the growth of resistances with respect to distance. We then show how a number of strong bounds on moments of hitting times, cover times, and related quantities for simple random walk may be deduced from the bound on resistance.

We study the mixing rate of non-backtracking random walks on graphs by looking at non-backtracking walks as walks on the directed edges of a graph. A result known as Ihara’s Theorem relates the adjacency matrix of a graph to a matrix related to non-backtracking walks on the directed edges. We prove a weighted version of Ihara’s Theorem which relates the transition probability matrix of a non-backtracking walk to the transition matrix for the usual random walk. This allows us to determine the spectrum of the transition probability matrix of a non-backtracking random walk in the case of regular graphs and biregular graphs. As a corollary, we obtain a result of Alon et al. in [1] that in most cases, a non-backtracking random walk on a regular graph has a faster mixing rate than the usual random walk. In addition, we obtain an analogous result for biregular graphs.

In this note we adapt a general result of Riordan [ Spanning subgraphs of random graphs , Combinatorics, Probability & Computing 9 (2000), no. 2, 125–148] from random graphs to random r -uniform hypergaphs. We also discuss several spanning structures such as cube-hypergraphs, lattices, spheres and Hamilton cycles in hypergraphs.

Consider a centred random walk in dimension one with a positive finite variance σ 2 , and let τ B be the hitting time for a bounded Borel set B with a non-empty interior. We prove the asymptotic P x ( τ B > n ) ∼ 2 / π σ − 1 V B ( x ) n − 1 / 2 and provide an explicit formula for the limit V B as a function of the initial position x of the walk. We also give a functional limit theorem for the walk conditioned to avoid B by the time n . As a main application, we consider the case that B is an interval and study the size of the largest gap G n (maximal spacing) within the range of the walk by the time n . We prove a limit theorem for G n , which is shown to be of the constant order, and describe its limit distribution. In addition, we prove an analogous result for the number of non-visited sites within the range of an integer-valued random walk.

We generalize the uniform spanning tree to construct a family of determinantal measures on essential spanning forests on periodic planar graphs in which every component tree is bi-infinite. Like the uniform spanning tree, these measures arise naturally from the Laplacian on the graph. ¶ More generally, these results hold for the “massive” Laplacian determinant which counts rooted spanning forests with weight $M$ per finite component. These measures typically have a form of conformal invariance, unlike the usual rooted spanning tree measure. We show that the spectral curve for these models is always a simple Harnack curve; this fact controls the decay of edge-edge correlations in these models. ¶ We construct a limit shape theory in these settings, where the limit shapes are defined by measured foliations of fixed isotopy type.

In this paper, we analyze the potential for new types of searches using the formalism of scattering random walks on Quantum Computers. Given a particular type of graph consisting of nodes and connections, a "Tree Maze", we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both exactly through numerical calculations as well as analytically using eigenvectors and eigenvalues of the quantum system.

Let ρ be a borelian probability measure on R having a moment of order 1 and a drift λ = ∫Rydρ(y) < 0. Consider the random walk on R+ starting at x ∈ R+ and defined for any n ∈N by \begin{eqnarray*} \left\{\begin{array}{rl} X_0&=x \\ X_{n+1} & = |X_n+Y_{n+1}| \end{array}\right. \end{eqnarray*} where (Yn) is an iid sequence of law ρ. We denote P the Markov operator associated to this random walk and, for any borelian bounded function f on R+, we call Poisson’s equation the equation f = g − Pg with unknown function g. In this paper, we prove that under a regularity condition on ρ and f, there is a solution to Poisson’s equation converging to 0 at infinity. Then, we use this result to prove the functional central limit theorem and it’s almost-sure version.

This article considers a random process related to a random walk on n by n upper triangular matrices over a finite field F q where q is an odd prime. The walk starts with the identity, and at each step, i is selected at random from { 2 , … , n } and either row i or the negative of row i is added to row i − 1 . This article shows that, for a given q , it takes order n 2 steps for the last column to get close to uniformly distributed over all possibilities for that column.

We consider a random walk Zn1,',ZnK+1∈i¾?K+1 with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor i¾?K2=2K+2 with respect to the case of the classical simple random walk without constraint. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 267-283, 2015

We consider a random walk on ℤ in random environment with possible jumps {−L, …, −1, 1}, in the case that the environment {ωi : i ∈ ℤ} 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 ℤ, respectively. Our method is based on the intrinsic branching structure within the (L, 1)-RWRE formulated in Hong and Wang (2013).

In this paper we look at an upper bound for the rate of convergence to stationarity of two specific random walks on the dihedral group. The first theorem discusses a random walk generated with equal probabilities by one rotation and one flip. We show that roughly p 2 steps are sufficient for the walk to become close to uniformly distributed on all of D 2 p where p ≥ 3 is an integer. Next we take a random walk on the dihedral group generated by a random k -subset of the dihedral group. The later theorem shows that it is sufficient to take roughly p 2 / ( k − 1 ) steps in the typical random walk to become close to uniformly distributed on all of D 2 p . We note that there are at least one rotation and one flip in the k -subset or the random walk generated by this subset has periodicity problems or will not generate all of D 2 p .

The looping constanti¾?i¾?d is the expected number of neighbors of the origin that lie on the infinite loop-erased random walk in i¾?d. Poghosyan, Priezzhev, and Ruelle, and independently, Kenyon and Wilson, proved recently that i¾?i¾?2=54. We consider the infinite volume limits as Gi¾?i¾?d of three different statistics: 1 The expected length of the cycle in a uniform spanning unicycle of G; 2 The expected density of a uniform recurrent state of the abelian sandpile model on G; and 3 The ratio of the number of spanning unicycles of G to the number of rooted spanning trees of G. We show that all three limits are rational functions of the looping constant i¾?i¾?d. In the case of i¾?2, their respective values are 8, 178 and 18. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 1-13, 2014

The uniform spanning tree has had a fruitful history in probability theory. Most notably, it was the study of the scaling limit of the UST that led Oded Schramm [Sch00] to introduce the SLE process, work which has revolutionised the study of two dimensional models in statistical physics. But in addition, the UST relates in an intrinsic fashion with another model, the loop erased random walk (or LEW), and the connections between these two processes allow each to be used as an aid to the study of the other. These notes give an introduction to the UST, mainly in Zd. The later sections concentrate on the UST in Z2, and study the relation between the intrinsic geometry of the UST and Euclidean distance. As an application, we study random walk on the UST, and calculate its asymptotic return probabilities. This survey paper contains many results from the papers [Lyo98, BLPS, BKPS04], not always attributed.

We consider the problem of sampling a uniformly random spanning tree of a graph. This is a classic algorithmic problem for which several exact and approximate algorithms are known. Random spanning trees have several connections to Laplacian matrices; this leads to algorithms based on fast matrix multiplication. The best algorithm for dense graphs can produce a uniformly random spanning tree of an n-vertex graph in time \(O(n^{2.38})\). This algorithm is intricate and requires explicitly computing the LU-decomposition of the Laplacian.

In this paper we extend the loop-erased random walk LERW to the directed hypergraph setting. We then generalize Wilson's algorithm for uniform sampling of spanning trees to directed hypergraphs. In several special cases, this algorithm perfectly samples spanning hypertrees in expected polynomial time. Our main application is to the reachability problem, also known as the directed all-terminal network reliability problem. This classical problem is known to be # P-complete, hence is most likely intractable Ball and Provan, SIAM J Comput 12 1983 777-788. We show that in the case of bi-directed graphs, a conjectured polynomial bound for the expected running time of the generalized Wilson algorithm implies a FPRAS for approximating reachability. Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 201-223, 2014

We give a simple formula to calculate the speed of weighted random walks on nonnegative integers and on spherically symmetric trees.

We use the known convergence of loop-erased random walk to radial SLE(2) to give a new proof that the scaling limit of loop-erased random walk excursion in the upper half-plane is chordal SLE(2). Our proof relies on a version of Wilson’s algorithm for weighted graphs which is used together with a Beurling-type estimate for random walk excursion. We also establish and use the convergence of the radial SLE path to the chordal SLE path as the bulk point tends to a boundary point. In the final section we sketch how to extend our results to more general simply connected domains.

A correspondence formula between the laws of dual Markov chains on Z with two transition jumps is established. This formula contributes to the study of random walks in stationary random environments. Counterexamples with more than two jumps are exhibited.

We consider the simple random walk on a random d -regular graph with n vertices, and investigate percolative properties of the set of vertices not visited by the walk until time , where u > 0 is a fixed positive parameter. It was shown in Cerný et al., (Ann Inst Henri Poincare Probab Stat 47 (2011) 929–968) that this so-called vacant set exhibits a phase transition at u = u⋆: there is a giant component if u u⋆. In this paper we show the existence of a critical window of size n-1/3 around u⋆. In this window the size of the largest cluster is of order n2/3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

We prove a law of large numbers for random walks in certain kinds of i.i.d. random environments in Z^d that is an extension of a result of Bolthausen, Sznitman and Zeitouni (2003). We use this result, along with the lace expansion for self-interacting random walks, to prove a monotonicity result for the first coordinate of the speed of the random walk under some strong assumptions on the distribution of the environment., Comment: Revised version. To appear in Stochastic Processes and Their Applications

Following Konno [1], it is natural to ask: What is the Ito’s formula for the discrete time quantum walk on a graph different than Z, the set of integers? In this paper we answer the question for the discrete time quantum walk on Z2, the square lattice.

We investigate the Zagreb index, one of the topological indices, of random recursive trees in this paper. Through a recurrence equation, the first two moments of Zn, the Zagreb index of a random recursive tree of size n, are obtained. We also show that the random process {Zn − E[Zn], n ≥ 1} is a martingale. Then the asymptotic normality of the Zagreb index of a random recursive tree is given by an application of the martingale central limit theorem. Finally, two other topological indices are also discussed in passing.

This paper studies particle propagation in a one-dimensional inhomogeneous medium where the laws of motion are generated by chaotic and deterministic local maps. Assuming that the particle's initial location is random and uniformly distributed, this dynamical system can be reduced to a random walk in a one-dimensional inhomogeneous environment with a forbidden direction. Our main result is a local limit theorem which explains in detail why, in the long run, the random walk's probability mass function does not converge to a Gaussian density, although the corresponding limiting distribution over a coarser diffusive space scale is Gaussian., Comment: 26 pages, 2 figures. To appear in Stochastic Processes and their Applications

Limit theorems are established for some functionals of the distances between two nodes in weighted random b-ary recursive trees. We consider the depth of the nth node and of a random node, the distance between two random nodes, the internal path length, and the Wiener index. As an application, these limit results imply, by an imbedding argument, corresponding limit theorems for further classes of random trees: plane-oriented recursive trees and random linear recursive trees.

The speed of the random walk on a tree is the rate of escaping its starting point. It depends on the way that the branching occurs in the sense that if the average number of branching is large, the speed is more likely to be positive. The speed on some models of random trees is calculated via calculating the hitting times of the consecutive levels of the tree.

We consider a simple random walk on a tree. Exact expressions are obtained for the expectation and the variance of the first passage time, thereby recovering the known result that these are integers. A relationship of the mean first passage matrix with the distance matrix is established and used to derive a formula for the inverse of the mean first passage matrix.

We study simple random walk on the uniform spanning tree on Z^2 . We obtain estimates for the transition probabilities of the random walk, the distance of the walk from its starting point after n steps, and exit times of both Euclidean balls and balls in the intrinsic graph metric. In particular, we prove that the spectral dimension of the uniform spanning tree on Z^2 is 16/13 almost surely., 37 pages

We study the problem of scenery reconstruction in arbitrary dimension using observations registered in boxes of size k (for k fixed), seen along a branching random walk. We prove that, using a large enough k for almost all the realizations of the branching random walk, almost all sceneries can be reconstructed up to equivalence.

We introduce the concept of an evolving random tree. The proposed model is a combination of a preferential attachment model and a uniform model. We consider the branch structure and maximum degree of the evolving random tree, which can partially explain the robustness under random attack and the vulnerability to targeted attack in the world wide web.

We study the relationship between the type of the random walk on some random trees and the structure of those trees in terms of fractal and resistance dimensions. This paper generalizes some results of Refs. 8–10.

In this paper, we look at the lower bounds of two specific random walks on the dihedral group. The first theorem discusses a random walk generated with equal probabilities by one rotation and one flip. We show that roughly p2 steps are necessary for the walk to become close to uniformly distributed on all of D2p where p≥3 is an integer. Next we take a random walk on the dihedral group generated by a random k-subset of the dihedral group. The latter theorem shows that it is necessary to take roughly p2/(k−1) steps in the typical random walk to become close to uniformly distributed on all of D2p. We note that there is at least one rotation and one flip in the k-subset, or the random walk generated by this subset has periodicity problems or will not generate all of D2p.

In this article, we mainly discuss the asymptotic behavior for multi-dimensional continuous-time random walk in random environment with holding times. By constructing a renewal structure and using the point “environment viewed from the particle”, under General Kalikow's Condition, we show the law of large numbers (LLN) and central limit theorem (CLT) for the escape speed of random walk.

A random walk that is skip-free to the left can only move down one level at a time but can skip up several levels. Such random walk features prominently in many places in applied probability including queuing theory and the theory of branching processes. This article exploits the special structure in this class of random walk to obtain a number of simplified derivations for results that are much more difficult in general cases. Although some of the results in this article have appeared elsewhere, our proof approach is different.

The spanning tree invariant of Lind and Tuncel [12] is observed in the context of loop systems of Markov chains. For n = 1 , 2 , 3 the spanning tree invariants of the loop systems of a Markov chain determined by an irreducible stochastic ( n × n ) -matrix P coincide if and only if P is doubly stochastic and, in this case, the common value of the spanning tree invariants of the loop systems is n .

Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. Alon, Benjamini, Lubetzky and Sodin studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length $n$ on a high-girth $n$-vertex regular expander, is typically $(1+o(1))\frac{\log n}{\log\log n}$, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes. In this work, we answer the above question by combining a generalized form of Brun's sieve with some extensions of the ideas in Alon et al. Let $N_t$ denote the number of vertices visited precisely $t$ times by a non-backtracking random walk of length $n$ on a regular $n$-vertex expander of fixed degree and girth $g$. We prove that if $g=\omega(1)$, then for any fixed $t$, $N_t/n$ is typically $\frac{1}{\mathrm{e}t!}+o(1)$. Furthermore, if $g=\Omega(\log\log n)$, then $N_t/n$ is typically $\frac{1+o(1)}{\mathrm{e}t!}$ uniformly on all $t \leq (1-o(1))\frac{\log n}{\log\log n}$ and 0 for all $t \geq (1+o(1))\frac{\log n}{\log\log n}$. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables., Comment: 19 pages

The speed of a random walk on a graph depends on the structure of that graph. We consider the simple random walks on infinite leafless trees, where the speed is closely related to the branching rate in such a way that the more the branching of the tree the more likely the speed is positive. We determine the speed of simple random walks on some random trees.

This paper is essentially an improved result from [V. I. Lotov and N. G. Orlova, Sb. Math., 194 (2003), pp. 927–939], where a formula was obtained for the distribution of the number of crossings of a strip by paths of a random walk defined by an infinite sequence of the partial sums of independent random variables having a common “two-sided geometric” distribution.

In this paper we provide a simple formula for the expected time for a random recursive tree to grow to a given height.

Starting from a sequence regarded as a walk through some set of values, we consider the associated loop-erased walk as a sequence of directed edges, with an edge from i to j if the loop-erased walk makes a step from i to j. We introduce a colouring of these edges by painting edges with a fixed colour as long as the walk does not loop back on itself, then switching to a new colour whenever a loop is erased, with each new colour distinct from all previous colours. The pattern of colours along the edges of the loop-erased walk then displays stretches of consecutive steps of the walk left untouched by the loop-erasure process. Assuming that the underlying sequence generating the loop-erased walk is a sequence of independent random variables, each uniform on [N] := {1, 2, . . ., N}, we condition the walk to start at N and stop the walk when it first reaches the subset [k], for some 1 ≤ k ≤ N − 1. We relate the distribution of the random length of this loop-erased walk to the distribution of the length of the first loop of the walk, via Cayley's enumerations of trees, and via Wilson's algorithm. For fixed N and k, and i = 1, 2, . . ., let Bi denote the events that the loop-erased walk from N to [k] has i + 1 or more edges, and the ith and (i + 1)th of these edges are coloured differently. We show that, given that the loop-erased random walk has j edges for some 1 ≤ j ≤ N − k, the events Bi for 1 ≤ i ≤ j − 1 are independent, with the probability of Bi equal to 1/(k + i + 1). This determines the distribution of the sequence of random lengths of differently coloured segments of the loop-erased walk, and yields asymptotic descriptions of these random lengths as N → ∞.

We define a class of weakly self-avoiding walks on the integers by conditioning a simple random walk of length n to have a p-fold self-intersection local time smaller than n β , where 1

In the present paper, linearly edge-reinforced random walk is studied on a large class of one-dimensional periodic graphs satisfying a certain reflection symmetry. It is shown that the edge-reinforced random walk is recurrent. Estimates for the position of the random walker are given. The edge-reinforced random walk has a unique representation as a random walk in a random environment, where the random environment is given by random weights on the edges. It is shown that these weights decay exponentially in space. The distribution of the random weights equals the distribution of the asymptotic proportion of time spent by the edge-reinforced random walker on the edges of the graph. The results generalize work of the authors in Merkl and Rolles (Ann Probab 33(6):2051–2093, 2005; 35(1):115–140, 2007) and Rolles (Probab Theory Related Fields 135(2):216–264, 2006) to a large class of graphs and to periodic initial weights with a reflection symmetry.

In the present paper the microscopic approach to random walk models is introduced. For any particular model it provides a rigorous way to derive the transport equations for the macroscopic density of walking particles. Although it is not more complicated than the standard random walk framework it has virtually no limitations with respect to the initial distribution of particles. As a consequence, the transport equations derived with this method almost automatically give answers to such important problems as aging and two point probability distribution.