Search

Loop-erased random walk (LERW) is one of the most well-studied critical lattice models. It is the self-avoiding random walk that one gets after erasing the loops from a simple random walk in order or, alternatively, by considering the branches in a spanning tree chosen uniformly at random. We prove that planar LERW parameterized by renormalized length converges in the lattice-size scaling limit to SLE2 parameterized by 5∕4-dimensional Minkowski content. In doing this, we also provide a method for proving similar convergence results for other models converging to SLE. Besides the main theorem, several of our results about LERW are of independent interest. We give, for example, two-point estimates, estimates on maximal content, and a “separation lemma” for two-sided LERW.

The Aldous–Broder algorithm provides a way of sampling a uniformly random spanning tree for finite connected graphs using simple random walk. Namely, start a simple random walk on a connected graph and stop at the cover time. The tree formed by all the first-entrance edges has the law of a uniform spanning tree. Here we show that the tree formed by all the last-exit edges also has the law of a uniform spanning tree. This answers a question of Tom Hayes and Cris Moore from 2010. The proof relies on a bijection that is related to the BEST theorem in graph theory. We also give other applications of our results, including new proofs of the reversibility of loop-erased random walk, of the Aldous–Broder algorithm itself, and of Wilson’s algorithm.

Let M be the infinite spanning-tree-weighted random planar map, which is the local limit of finite random planar maps sampled with probability proportional to the number of spanning trees they admit. We show that a.s. the M-graph-distance diameter of the external diffusion-limited aggregation (DLA) cluster on M run for m steps is of order m2/d+om(1), where d is the metric ball volume growth exponent for M (which was shown to exist by Ding and Gwynne (Comm. Math. Phys. 374 (2020) 1877–1934). By known bounds for d, one has 0.55051⋯≤2/d≤0.563315…. Along the way, we also prove that loop-erased random walk (LERW) on M typically travels graph distance m2/d+om(1) in m units of time and that the graph-distance diameter of a finite spanning-tree-weighted random planar map with n edges, with or without boundary, is of order n1/d+on(1) except on an event with probability decaying faster than any negative power of n. Our proofs are based on a special relationship between DLA and LERW on spanning-tree-weighted random planar maps as well as estimates for distances in such maps which come from the theory of Liouville quantum gravity.

Розглянуто новий клас випадкових блукань з видаленими петлями (LERW), які визначаються як функціонал від ланцюга Маркова. Ми пропонуємо схему, в якій, на відміну від класичних припущень щодо LERW, видалення петель відбувається на немарківській послідовності і крім того, не всі петлі видаляються. Спочатку ми розглядаємо приклад випадкового блукання з петлями, кількість яких в кожен момент часу не перевищує деякого заданого числа. Далі ми розглядаємо випадкові блукання, в яких петлі видаляються у випадкові моменти часу, які є моментами досягнення для ланцюга Маркова. Встановлено асимптотику нормованої довжини такого випадкового блукання. Оцінено також швидкість збіжності розподілу нормованої довжини випадкового блукання з видаленими петлями на скінченній групі до розподілу Релея. A new class of loop-erased random walks (LERW) on a finite set, defined as functionals from a Markov chain is presented. We propose a scheme in which, in contrast to the general settings of LERW, the loop-erasure is performed on a non-markovian sequence and moreover, not all loops are erased with necessity. We start with a special example of a random walk with loops, the number of which at every moment of time does not exceed a given fixed number. Further we consider loop-erased random walks, for which loops are erased at random moments of time that are hitting times for a Markov chain. The asymptotics of the normalized length of such loop-erased walks is established. We estimate also the speed of convergence of the normalized length of the loop-erased random walk on a finite group to the Rayleigh distribution.

We consider a random partition of the vertex set of an arbitrary graph that can be sampled using loop-erased random walks stopped at a random independent exponential time of parameter $q>0$, that we see as a tuning parameter.The related random blocks tend to cluster nodes visited by the random walk on time scale $1/q$. We explore the emerging macroscopic structure by analyzing 2-point correlations. To this aim, it is defined an interaction potential between pair of vertices, as the probability that they do not belong to the same block of the random partition. This interaction potential can be seen as an affinity measure for ``densely connected nodes'' and capture well-separated regions in network models presenting non-homogeneous landscapes. In this spirit, we compute this potential and its scaling limits on a complete graph and on a non-homogeneous weighted version with community structures. For the latter geometry we show a phase-transition for ``community detectability'' as a function of the tuning parameter and the edge weights., 30 pages, 1 figure

We compute the Green's function on the double cover of ${\mathbb Z}^2$, branched over a vertex or a face. We use this result to compute the local statistics of the "trunk" of the uniform spanning tree on the square lattice, i.e., the limiting probabilities of cylinder events conditional on the path connecting far away points passing through a specified edge. We also show how to compute the local statistics of large-scale triple points of the uniform spanning tree, where the trunk branches. The method reduces the problem to a dimer system with isolated monomers, and we compute the inverse Kasteleyn matrix using the Green's function on the double cover of the square lattice. For the trunk, the probabilities of cylinder events are in ${\mathbb Q}[\sqrt{2}]$, while for the triple points the probabilities are in ${\mathbb Q}[1/\pi]$., Comment: 36 pages, 18 figures

The determination of the Hausdorff dimension of the scaling limit of loop-erased random walk is closely related to the study of the one-point function of loop-erased random walk, i.e., the probability a loop-erased random walk passes through a given vertex. Recent work in the theoretical physics literature has investigated the Hausdorff dimension of loop-erased random walk in three dimensions by applying field theory techniques to study spin systems that heuristically encode the one-point function of loop-erased random walk. Inspired by this, we introduce two different spin systems whose correlation functions can be rigorously shown to encode the one-point function of loop-erased random walk., Comment: Accepted version

We consider the random walk pinning model. This is a random walk on Z d whose law is given as the Gibbs measure μ N , Y β , where the polymer measure μ N , Y β is defined by using the collision local time with another simple symmetric random walk Y on Z d up to time N . Then, at least two definitions of the phase transitions are known, described in terms of the partition function and the free energy. In this paper, we will show that the two critical points coincide and give an explicit formula for the free energy in terms of a variational representation. Also, we will prove that if β is smaller than the critical point, then X under μ N , Y β satisfies the central limit theorem and the invariance principle P Y -almost surely.

The discovery of community structure is the basis of understanding the topology structure and social function of the network. It is also an important factor for recommendation technology, information dissemination, event prediction, and more. In this paper, we consider the structure and characteristics of the social network and propose an algorithm based on semi-supervised matrix factorization and random walk. The proposed method first calculates the transition probability between nodes through the topology of the network. The random walk model is then used to obtain the final walk probability, and the feature matrix is constructed. At the same time, we combine a priori content information in the network to build a must-link matrix and a cannot-link matrix. We then merge them into the feature matrix of the random walk to form a new feature matrix. Finally, the expectation of the number of edges is defined according to the factorized membership matrix. Results demonstrate the effectiveness and better performance of our method.

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.

We suggest in this paper a Random Walk on Spheres (RWS) method for solving transient drift-diffusion-reaction problems which is an extension of our algorithm we developed recently [26] for solving steady-state drift-diffusion problems. Both two-dimensional and three-dimensional problems are solved. Survival probability, first passage time and the exit position for a sphere (disc) of the drift-diffusion-reaction process are explicitly derived from a generalized spherical integral relation we prove both for two-dimensional and three-dimensional problems. The distribution of the exit position on the sphere has the form of the von Mises–Fisher distribution which can be simulated efficiently. Rigorous expressions are derived in the case of constant velocity drift, but the algorithm is then extended to solve drift-diffusion-reaction problems with arbitrary varying drift velocity vector. The method can efficiently be applied to calculate the fluxes of the solution to any part of the boundary. This can be done by applying a reciprocity theorem which we prove here for the drift-diffusion-reaction problems with general boundary conditions. Applications of this approach to methods of cathodoluminescence (CL) and electron beam induced current (EBIC) imaging of defects and dislocations in semiconductors are presented.

The loop-erased random walk (LERW) in $\mathbb{Z}^{4}$ is the process obtained by erasing loops chronologically for a simple random walk. We prove that the escape probability of the LERW renormalized by $(\log n)^{\frac{1}{3}}$ converges almost surely and in $L^{p}$ for all $p>0$. Along the way, we extend previous results by the first author building on slowly recurrent sets. We provide two applications for the escape probability. We construct the two-sided LERW, and we construct a $\pm 1$ spin model coupled with the wired spanning forests on $\mathbb{Z}^{4}$ with the bi-Laplacian Gaussian field on $\mathbb{R}^{4}$ as its scaling limit.

In this work, we consider loop-erased random walk (LERW) in three dimensions and give an asymptotic estimate on the one-point function for LERW and the non-intersection probability of LERW and simple random walk in three dimensions for dyadic scales. These estimates will be crucial to the characterization of the convergence of LERW to its scaling limit in natural parametrization. As a step in the proof, we also obtain a coupling of two pairs of LERW and SRW with different starting points conditioned to avoid each other., Comment: 39 pages, 2 figures

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

We show that the trace of the null recurrent biased random walk on a Galton–Watson tree properly renormalized converges to the Brownian forest. Our result extends to the setting of the random walk in random environment on a Galton–Watson tree.

The correlated biased random walk with latency in one and two dimensions is discussed with regard to the portion of irreducible random movement and structured movement. It is shown how a quantitative analysis can be carried out by using computational mechanics. The stochastic matrix for both dynamics are reported. Latency introduces new states in the finite state machine description of the system in both dimensions, allowing for a full nearest neighbor coordination in the two dimensional case. Complexity analysis is used to characterize the movement, independently of the set of control parameters, making it suitable for the discussion of other random walk models. The complexity map of the system dynamics is reported for the two dimensional case.

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

Three characteristics of two-dimensional uniform spanning trees are nontrivially related to one another: the average density of a sandpile, the looping constant of a square lattice, and the return probability of a loop-erased random walk. We briefly trace the long history of the discovery of their unexpected rational values.

We derive a general formulation of the time domain random walk (TDRW) approach to model the hydrodynamic transport of inert solutes in complex geometries and heterogeneous media. We demonstrate its formal equivalence with the discretized advection-dispersion equation and show that the TDRW is equivalent to a continuous time random walk (CTRW) characterized by space-dependent transition times and transition probabilities. The transition times are exponentially distributed. We discuss the implementation of different concentration boundary conditions and initial conditions as well as the occurrence of numerical dispersion. Furthermore, we propose an extension of the TDRW scheme to account for mobile-immobile multirate mass transfer. Finally, the proposed TDRW scheme is validated by comparison to analytical solutions for spatially homogeneous and heterogeneous transport scenarios.

The aim of this paper is to consider reversible random walk in a random environment in one dimension and prove the Einstein relation for this model. It says that the derivative at 0 of the effective velocity under an additional local drift equals the diffusivity of the model without drift (Theorem 1.2). Our method here is very simple: we solve the Poisson equation (Pω−I)g=f and then use the pointwise ergodic theorem in Wiener (1939) [10] to treat the limit of the solutions to obtain the desired result. There are analogous results for Markov processes with discrete space and for diffusions in random environment.

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.

Problems of a random walk on a binary tree have been reformulated on any homogeneous tree. Cauchy problem of the random walk for homogeneous and nonhomogeneous equation having a Parisi matrix as a coefficient is formulated and solved with help of a special commutative ring of matrices. The ring containing the Parisi matrix is constructed. The method can be generalized on multidimensional case, for differential equations in non-Archimedean time, and for difference equations.

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.