Extremal cover times for random walks on trees

Let C_ν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C_ν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that C_ν(T) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).     

Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

Biased random walks on directed trees

Summary. We define directed rooted labeled and unlabeled trees and find measures on the space of directed rooted unlabeled trees which are invariant with respect to transition probabilities corresponding to a biased random walk on a directed rooted labeled tree. We use these to calculate the speed of a biased random walk on directed rooted labeled trees. The results are mainly applied to directed trees with recurrent subtrees, where the random walker cannot escape. Received: 12 March 1997/ In revised form: 11 December 1997     

Deterministic random walks on regular trees

Jim Propp's rotor–router model is a deterministic analog 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 15 (2006) 815–822) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid ?^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 ≥ 3), we show that for any deviation D there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least D more chips than expected in the random walk model. However, to achieve a deviation of D it is necessary that at least exp(Ω(D²)) vertices contribute by being occupied by a number of chips not divisible by k at a certain time. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Counting trees with random walks

We give a simple proof of Tutte’s matrix-tree theorem, a well-known result providing a closed-form expression for the number of rooted spanning trees in a directed graph. Our proof stems from placing a random walk on a directed graph and then applying the Markov chain tree theorem to count trees. The connection between the two theorems is not new, but it appears that only one direction of the formal equivalence between them is readily available in the literature. The proof we now provide establishes the other direction. More generally, our approach is another example showing that random walks can serve as a powerful glue between graph theory and Markov chain theory, allowing formal statements from one side to be carried over to the other.     

Anisotropic branching random walks on homogeneous trees

Symmetric branching random walk on a homogeneous tree exhibits a weak survival phase: For parameter values in a certain interval, the population survives forever with positive probability, but, with probability one, eventually vacates every finite subset of the tree. In this phase, particle trails must converge to the geometric boundaryΩ of the tree. The random subset Λ of the boundary consisting of all ends of the tree in which the population survives, called the limit set of the process, is shown to have Hausdorff dimension no larger than one half the Hausdorff dimension of the entire geometric boundary. Moreover, there is strict inequality at the phase separation point between weak and strong survival except when the branching random walk is isotropic. It is further shown that in all cases there is a distinguished probability measure μ supported by Ω such that the Hausdorff dimension of Λ∩Ω_μ, where Ω_μ is the set of μ-generic points of Ω, converges to one half the Hausdorff dimension of Ω_μ at the phase separation point. Exact formulas are obtained for the Hausdorff dimensions of Λ and Λ∩Ω_μ, and it is shown that the log Hausdorff dimension of Λ has critical exponent 1/2 at the phase separation point. Received: 30 June 1998 / Revised version: 10 March 1999     

Exit times of N-dimensional random walks

Summary We study the exit time T of a sum of independent, identically distributed random vectors, X ₁, X ₂, ..., from a subset R of N dimensional Euclidean space when N2. We assume that R is invariant under positive dilations and that the boundary of R satisfies certain regularity conditions. The random vector X ₁ is to have mean zero and a nonsingular covariance matrix. We show that there is a critical exponent, e, independent of X ₁, X ₂, ..., such that 0<pET ^p/2<. In addition, if X ₁ is bounded and slightly more restrictive assumptions are imposed on R, then p>e implies ET ^p/2=.This paper constitutes a portion of the author's Ph.D. dissertation written at the University of Illinois     

Biased random walks on Galton–Watson trees

Summary. We consider random walks with a bias toward the root on the family tree T of a supercritical Galton–Watson branching process and show that the speed is positive whenever the walk is transient. The corresponding harmonic measures are carried by subsets of the boundary of dimension smaller than that of the whole boundary. When the bias is directed away from the root and the extinction probability is positive, the speed may be zero even though the walk is transient; the critical bias for positive speed is determined. Received: 7 July 1995 / In revised form: 9 January 1996     

The type problem for random walks on trees

We consider the question of whether the simple random walk (SRW) on an infinite tree is transient or recurrent. For random-trees (all vertices of distancen from the root of the tree have degreed _n , where {d _n } are independent random variables), we prove that the SRW is a.s. transient if lim inf _n n E(log(d _n-1))>1 and a.s. recurrent if lim sup _n n E(log(d _n-1))<1. For random trees in which the degrees of the vertices are independently 2 or 3, with distribution depending on the distance from the root, a partial classification of type is obtained.Research supported in part by NSF DMS 8710027.     

The Poisson boundary of lamplighter random walks on trees

Let be the homogeneous tree with degree q + 1 ≥ 3 and a finitely generated group whose Cayley graph is . The associated lamplighter group is the wreath product , where is a finite group. For a large class of random walks on this group, we prove almost sure convergence to a natural geometric boundary. If the probability law governing the random walk has finite first moment, then the probability space formed by this geometric boundary together with the limit distribution of the random walk is proved to be maximal, that is, the Poisson boundary. We also prove that the Dirichlet problem at infinity is solvable for continuous functions on the active part of the boundary, if the lamplighter “operates at bounded range”. Supported by ESF program RDSES and by Austrian Science Fund (FWF) P15577.     

Expected cover times of random walks on symmetric graphs

We give very simple proofs for an (N–1)H _N–1 lower bound and anN ² upper bound for the expected cover time of symmetric graphs.     

Strong uniform times and finite random walks

There are several techniques for obtaining bounds on the rate of convergence to the stationary distribution for Markov chains with strong symmetry properties, in particular random walks on finite groups. An elementary method, strong uniform times, is often effective. We prove such times always exist, and relate this method to coupling and Fourier analysis.     

Limit theorems for reinforced random walks on certain trees

Consider a linearly edge-reinforced random walk defined on the b-ary tree, b≥70. We prove the strong law of large numbers for the distance of this process from the root. We give a sufficient condition for this strong law to hold for general edge-reinforced random walks and random walks in a random environment. We also provide a central limit theorem. Supported in part by a Purdue Research Foundation fellowship this work is part of the author's PhD thesis.     

Branching random walks and contact processes on homogeneous trees

Summary. Branching random walks and contact processes on the homogeneous tree in which each site has d+1 neighbors have three possible types of behavior (for d≧ 2): local survival, local extinction with global survival, and global extinction. For branching random walks, we show that if there is local extinction, then the probability that an individual ever has a descendent at a site n units away from that individual’s location is at most d ^{− n/2} , while if there is global extinction, this probability is at most d ⁻ⁿ . Next, we consider the structure of the set of invariant measures with finite intensity for the system, and see how this structure depends on whether or not there is local and/or global survival. These results suggest some problems and conjectures for contact processes on trees. We prove some and leave others open. In particular, we prove that for some values of the infection parameter λ, there are nontrivial invariant measures which have a density tending to zero in all directions, and hence are different from those constructed by Durrett and Schinazi in a recent paper. Received: 26 April 1996/In revised form: 20 June 1996     

Exceptional times and invariance for dynamical random walks

Consider a sequence of i.i.d. random variables. Associate to each X _i (0) an independent mean-one Poisson clock. Every time a clock rings replace that X-variable by an independent copy and restart the clock. In this way, we obtain i.i.d. stationary processes {X _i (t)} _{t ≥0} (i=1,2,···) whose invariant distribution is the law ν of X ₁(0). Benjamini et al. (2003) introduced the dynamical walk S _n (t)=X ₁(t)+···+X _n (t), and proved among other things that the LIL holds for n↦S _n (t) for all t. In other words, the LIL is dynamically stable. Subsequently (2004b), we showed that in the case that the X _i (0)'s are standard normal, the classical integral test is not dynamically stable. Presently, we study the set of times t when n↦S _n (t) exceeds a given envelope infinitely often. Our analysis is made possible thanks to a connection to the Kolmogorov ɛ-entropy. When used in conjunction with the invariance principle of this paper, this connection has other interesting by-products some of which we relate. We prove also that the infinite-dimensional process converges weakly in to the Ornstein–Uhlenbeck process in For this we assume only that the increments have mean zero and variance one. In addition, we extend a result of Benjamini et al. (2003) by proving that if the X _i (0)'s are lattice, mean-zero variance-one, and possess (2+ɛ) finite absolute moments for some ɛ>0, then the recurrence of the origin is dynamically stable. To prove this we derive a gambler's ruin estimate that is valid for all lattice random walks that have mean zero and finite variance. We believe the latter may be of independent interest. The research of D. Kh. is partially supported by a grant from the NSF.     

Almost sure convergence for stochastically biased random walks on trees

We are interested in the biased random walk on a supercritical Galton?CWatson tree in the sense of Lyons (Ann. Probab. 18:931?C958, 1990) and Lyons, Pemantle and Peres (Probab. Theory Relat. Fields 106:249?C264, 1996), and study a phenomenon of slow movement. In order to observe such a slow movement, the bias needs to be random; the resulting random walk is then a tree-valued random walk in random environment. We investigate the recurrent case, and prove, under suitable general integrability assumptions, that upon the system??s non-extinction, the maximal displacement of the walk in the first n steps, divided by (log n)³, converges almost surely to a known positive constant.     

Hitting times for random walks on subdivision and triangulation graphs

Let G be a connected graph. The subdivision graph of G, denoted by S(G), is the graph obtained from G by inserting a new vertex into every edge of G. The triangulation graph of G, denoted by R(G), is the graph obtained from G by adding, for each edge uv, a new vertex whose neighbours are u and v. In this paper, we first provide complete information for the eigenvalues and eigenvectors of the probability transition matrix of a random walk on S(G) (res. R(G)) in terms of those of G. Then we give an explicit formula for the expected hitting time between any two vertices of S(G) (res. R(G)) in terms of those of G. Finally, as applications, we show that, the relations between the resistance distances, the number of spanning trees and the multiplicative degree-Kirchhoff index of S(G) (res. R(G)) and G can all be deduced from our results directly.