Search

We answer positively a question of Kaimanovich and Vershik from 1979, showing that the final configuration of lamps for simple random walk on the lamplighter group over ${\Bbb Z}^d$ ($d \ge 3$) is the Poisson boundary. For $d \ge 5$, this had been shown earlier by Erschler (2011). We extend this to walks of more general types on more general groups.

It is known that spheres have negative type, but only subsets with at most one pair of antipodal points have strict negative type. These are conditions on the (angular) distances within any finite subset of points. We show that subsets with at most one pair of antipodal points have strong negative type, a condition on every probability distribution of points. This implies that the function of expected distances to points determines uniquely the probability measure on such a set. It also implies that the distance covariance test for stochastic independence, introduced by Sz\'ekely, Rizzo and Bakirov, is consistent against all alternatives in such sets. Similarly, it allows tests of goodness of fit, equality of distributions, and hierarchical clustering with angular distances. We prove this by showing an analogue of the Cram\'er--Wold theorem., Comment: 6 pp. arXiv admin note: text overlap with arXiv:1408.2600

There is a slight gap and error in Remark 3.4 of Ann. Probab. 41, no. 5 (2013), 3284–3305, that was not noticed before the first errata were published (Ann. Probab. 46, no. 4 (2018), 2400–2405). We take this opportunity to provide some additional updates as well.

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.

Shalom and Tao showed that a polynomial upper bound on the size of a single, large enough ball in a Cayley graph implies that the underlying group has a nilpotent subgroup with index and degree of polynomial growth both bounded effectively. The third and fourth authors proved the optimal bound on the degree of polynomial growth of this subgroup, at the expense of making some other parts of the result ineffective. In the present paper we prove the optimal bound on the degree of polynomial growth without making any losses elsewhere. As a consequence, we show that there exist explicit positive numbers $\varepsilon_d$ such that in any group with growth at least a polynomial of degree $d$, the growth is at least $\varepsilon_dn^d$. We indicate some applications in probability; in particular, we show that the gap at $1$ for the critical probability for Bernoulli site percolation on a Cayley graph, recently proven to exist by Panagiotis and Severo, is at least $\exp\bigl\{-\exp\bigl\{17 \exp\{100 \cdot 8^{100}\}\bigr\}\bigr\}$., 6 pp; v2 changed title and added to introduction; v3 added two authors, totally rewritten, now 12 pp, improved results; v4, 17 pp., now includes explicit gap in percolation

In the trace reconstruction problem, an unknown bit string ${\bf x}\in\{0,1 \}^n$ is sent through a deletion channel where each bit is deleted independently with some probability $q\in(0,1)$, yielding a contracted string $\widetilde{\bf x}$. How many i.i.d.\ samples of $\widetilde{\bf x}$ are needed to reconstruct $\bf x$ with high probability? We prove that there exist ${\bf x},{\bf y} \in\{0,1 \}^n$ such that at least $c\, n^{5/4}/\sqrt{\log n}$ traces are required to distinguish between ${\bf x}$ and ${\bf y}$ for some absolute constant $c$, improving the previous lower bound of $c\,n$. Furthermore, our result improves the previously known lower bound for reconstruction of random strings from $c \log^2 n$ to $c \log^{9/4}n/\sqrt{\log \log n} $., Minor changes. 23 pages, 3 figures

We extend a result of Lyons (2016) from fractional tiling of finite graphs to a version for infinite random graphs. The most general result is as follows. Let $\bf P$ be a unimodular probability measure on rooted networks $(G, o)$ with positive weights $w_G$ on its edges and with a percolation subgraph $H$ of $G$ with positive weights $w_H$ on its edges. Let ${\bf P}_{(G, o)}$ denote the conditional law of $H$ given $(G, o)$. Assume that $��:= {\bf P}_{(G, o)}\bigl[{o \in V(H)}\bigr] > 0$ is a constant $\bf P$-a.s. We show that if $\bf P$-a.s. whenever $e \in E(G)$ is adjacent to $o$, \[ {\bf E}_{(G, o)}\bigl[{w_H(e) \bigm| e \in E(H)}\bigr] {\bf P}_{(G, o)}\bigl[{e \in E(H) \bigm| o\in V(H)}\bigr] \le w_G(e) \,, \] then \[ \forall t > 0 \quad {\bf E}\bigl[{p_t(o; G)}\bigr] \le {\bf E}\bigl[{p_t(o; H) \bigm| o \in V(H)}\bigr] \,. \], 9 pp., 4 figures

We present a short, elementary proof not involving Fourier transforms of the theorem of Cramér and Wold that a Borel probability measure is determined by its values on half-spaces.

Spectral embedding of graphs uses the top k non-trivial eigenvectors of the random walk matrix to embed the graph into R^k. The primary use of this embedding has been for practical spectral clustering algorithms [SM00,NJW02]. Recently, spectral embedding was studied from a theoretical perspective to prove higher order variants of Cheeger's inequality [LOT12,LRTV12]. We use spectral embedding to provide a unifying framework for bounding all the eigenvalues of graphs. For example, we show that for any finite graph with n vertices and all k >= 2, the k-th largest eigenvalue is at most 1-Omega(k^3/n^3), which extends the only other such result known, which is for k=2 only and is due to [LO81]. This upper bound improves to 1-Omega(k^2/n^2) if the graph is regular. We generalize these results, and we provide sharp bounds on the spectral measure of various classes of graphs, including vertex-transitive graphs and infinite graphs, in terms of specific graph parameters like the volume growth. As a consequence, using the entire spectrum, we provide (improved) upper bounds on the return probabilities and mixing time of random walks with considerably shorter and more direct proofs. Our work introduces spectral embedding as a new tool in analyzing reversible Markov chains. Furthermore, building on [Lyo05], we design a local algorithm to approximate the number of spanning trees of massive graphs.

We show that solutions to multidimensional SDEs with Lipschitz coefficients and driven by Brownian motion never reach the set where all coefficients vanish unless the initial position belongs to that set., 2pp

We correct a few more minor errors in our paper, Electron. J. Probab. 12, Paper 54 (2007), 1454–1508.

Classical ergodic theory for integer-group actions uses entropy as a complete invariant for isomorphism of IID (independent, identically distributed) processes (a.k.a. product measures). This theory holds for amenable groups as well. Despite recent spectacular progress of Bowen, the situation for non-amenable groups, including free groups, is still largely mysterious. We present some illustrative results and open questions on free groups, which are particularly interesting in combinatorics, statistical physics, and probability. Our results include bounds on minimum and maximum bisection for random cubic graphs that improve on all past bounds., Comment: 18 pages, 1 figure

We correct several statements and proofs in our paper, Ann. Probab. 41, no. 5 (2013), 3284–3305.

Dyadic lattice graphs and their duals are commonly used as discrete approximations to the hyperbolic plane. We use them to give examples of random rooted graphs that are stationary for simple random walk, but whose duals have only a singular stationary measure. This answers a question of Curien and shows behaviour different from the unimodular case. The consequence is that planar duality does not combine well with stationary random graphs. We also study harmonic measure on dyadic lattice graphs and show its singularity., Comment: 30 pages, 18 figures

We use spectral embeddings to give upper bounds on the spectral function of the Laplace--Beltrami operator on homogeneous spaces in terms of the volume growth of balls. In the case of compact manifolds, our bounds extend the 1980 lower bound of Peter Li for the smallest positive eigenvalue to all eigenvalues. We also improve Li's bound itself. Our bounds translate to explicit upper bounds on the heat kernel for both compact and noncompact homogeneous spaces., Comment: 25 pages, 2 figures

We show that for finite-range, symmetric random walks on general transient Cayley graphs, the expected occupation time of any given ball of radius $r$ is $O(r^{5/2})$.. We also study the volume-growth property of the wired spanning forests on general Cayley graphs, showing that the expected number of vertices in the component of the identity inside any given ball of radius $r$ is $O(r^{11/2})$., Comment: 15 pages, 1 figure; T.Zheng is added as an author due to her key contribution to the improvement on the exponents from the first version

We correct several statements and proofs in our paper, Electron. J. Probab. 12, Paper 54 (2007), 1454–1508.

We show that under mild conditions, a Gaussian analytic function $\boldsymbol F$ that a.s. does not belong to a given weighted Bergman space or Bargmann-Fock space has the property that a.s. no non-zero function in that space vanishes where $\boldsymbol F$ does. This establishes a conjecture of Shapiro (1979) on Bergman spaces and allows us to resolve a question of Zhu (1993) on Bargmann-Fock spaces. We also give a similar result on the union of two (or more) such zero sets, thereby establishing another conjecture of Shapiro (1979) on Bergman spaces and allowing us to strengthen a result of Zhu (1993) on Bargmann-Fock spaces., Comment: 17 pp

Starting around the late 1950s, several research communities began relating the geometry of graphs to stochastic processes on these graphs. This book, twenty years in the making, ties together research in the field, encompassing work on percolation, isoperimetric inequalities, eigenvalues, transition probabilities, and random walks. Written by two leading researchers, the text emphasizes intuition, while giving complete proofs and more than 850 exercises. Many recent developments, in which the authors have played a leading role, are discussed, including percolation on trees and Cayley graphs, uniform spanning forests, the mass-transport technique, and connections on random walks on graphs to embedding in Hilbert space. This state-of-the-art account of probability on networks will be indispensable for graduate students and researchers alike.

Uniform spanning trees on finite graphs and their analogues on infinite graphs are a well-studied area. On a Cayley graph of a group, we show that they are related to the first ℓ2-Betti number of the group. Our main aim, however, is to present the basic elements of a higher-dimensional analogue on finite and infinite CW-complexes, which relate to the higher ℓ2-Betti numbers. One consequence is a uniform isoperimetric inequality extending work of Lyons, Pichot, and Vassout. We also present an enumeration similar to recent work of Duval, Klivans and Martin.

We give a positive answer, in the measurable-group-theory context, to von Neumann's problem of knowing whether a non-amenable countable discrete group contains a non-cyclic free subgroup. We also get an embedding result of the free-group von Neumann factor into restricted wreath product factors., 10 pages, to appear in Inventiones Mathematicae

It is shown that 2β1() � h() for any countable group , where β1() is the first l 2 -Betti number and h() the uniform isoperimetric constant. In particular, a countable group with non-vanishing first l 2 -Betti number is uniformly non-amenable. We then define isoperimetric constants in the framework of measured equivalence re- lations. For an ergodic measured equivalence relation R of type II1, the uniform isoperi- metric constant h(R) of R is invariant under orbit equivalence and satisfies

Determinantal point processes have arisen in diverse settings in recent years and have been investigated intensively. We study basic combinatorial and probabilistic aspects in the discrete case. Our main results concern relationships with matroids, stochastic domination, negative association, completeness for infinite matroids, tail triviality, and a method for extension of results from orthogonal projections to positive contractions. We also present several new avenues for further investigation, involving Hilbert spaces, combinatorics, homology, and group representations, among other areas.

Let X and Y be independent transient Markov chains on the same state space that have the same transition probabilities. Let L denote the ``loop-erased path'' obtained from the path of X by erasing cycles when they are created. We prove that if the paths of X and Y have infinitely many intersections a.s., then L and Y also have infinitely many intersections a.s., Comment: To appear in Ann. Inst. H. Poincar\'e Probab. Statist

Call a percolation process on edges of a graph change intolerant if the status of each edge is almost surely determined by the status of the other edges. We give necessary and sufficient conditions for change intolerance of the wired spanning forest when the underlying graph is a spherically symmetric tree.