Russell Lyons

(with Yuval Peres) A Book Entitled Probability on Trees and Networks

Course Notes

Course notes on stochastic processes (following Sheldon Ross's graduate textbook, Stochastic Processes).

Lecture notes on martingales (extending Patrick Billingsley's textbook, Probability and Measure).

Weak and weak* topologies (an alternative to Helly's theorem presented as homework).

Uniqueness and continuity for characteristic functions (a soft development presented as extra-credit homework).

Some handouts to accompany Statistical Models: Theory and Practice (revised ed.) by David Freedman:

• Correlation and normal distributions (This covers material in Statistics by Freedman, Pisani and Purves. It is here because it defines multivariate normal distributions.)
  
• Review of linear algebra
  
• The t-distribution
  
• Chapter 4: Multiple Regression
  
• Multicollinearity
  
• Exercise 4.5.5
  
• To be or not to be (in the model)?
  
• Chapter 5: More on Multiple Regression
  
• The F- and t-distributions together
  
• Standardized regressions
  

Papers Available Electronically in PostScript or PDF:

Often the electronic versions of papers here fix errors that are noted after publication. Whether or not such corrections are made here, errata appear after the corresponding paper link as well as in the separate errata section.

Titles:

• (with Matteo D'Achille, Nicolas Curien, Nathanael Enriquëz, and Meltem Ünel) Ideal Poisson--Voronoi tessellations on hyperbolic spaces
  
• (with Graham White) Monotonicity for continuous-time random walks
  
• (with Avinoam Mann, Romain Tessera, and Matthew Tointon) Explicit universal minimal constants for polynomial growth of groups
  
• (with Yiping Hu and Pengfei Tang) A reverse Aldous--Broder algorithm
  
• Strong negative type in spheres
  
• Exit boundaries of multidimensional SDEs
  
• (with Yuval Peres and Xin Sun) Induced graphs of uniform spanning forests
  
• Problem 198
  
• (with Nina Holden) Lower bounds for trace reconstruction
  
• (with Graham White) A stationary planar random graph with singular stationary dual: Dyadic lattice graphs
  
• A note on tail triviality for determinantal point processes
  
• Monotonicity of average return probabilities for random walks in random environments
  
• (with Alex Zhai) Zero sets for spaces of analytic functions
  
• (with Yuval Peres, Xin Sun, and Tianyi Zheng) Occupation measure of random walks and wired spanning forests in balls of Cayley graphs
  
• (with Chris Judge) Upper bounds for the spectral function on homogeneous spaces via volume growth
  
• (with Shayan Oveis Gharan) Sharp bounds on random walk eigenvalues via spectral embedding
  
• (with Kevin Zumbrun) A calculus proof of the Cramér-Wold theorem
  
• Comparing graphs of different sizes
  
• (with Yuval Peres) Poisson boundaries of lamplighter groups: proof of the Kaimanovich-Vershik conjecture
  
• Hyperbolic space has strong negative type
  
• Determinantal probability: basic properties and conjectures
  
• (with Andreas Thom) Invariant coupling of determinantal measures on sofic groups
  
• Factors of IID on trees
  
• (with Yuval Peres) Cycle density in infinite Ramanujan graphs
  
• (with Itai Benjamini and Oded Schramm) Unimodular random trees
  
• (with Omer Angel and Alexander S. Kechris) Random orderings and unique ergodicity of automorphism groups
  
• Fixed price of groups and percolation
  
• Distance covariance in metric spaces
  
• The spread of evidence-poor medicine via flawed social-network analysis
  
• (with Fedor Nazarov) Perfect matchings as IID factors on non-amenable groups
  
• (with Alexander E. Holroyd and Terry Soo) Poisson splitting by factors
  
• Random complexes and l²-Betti numbers
  
• Identities and inequalities for tree entropy
  
• (with Ron Peled and Oded Schramm) Growth of the number of spanning trees of the Erdős-Rényi giant component
  
• (with Damien Gaboriau) A measurable-group-theoretic solution to von Neumann's problem
  
• (with Mikaël Pichot and Stéphane Vassout) Uniform non-amenability, cost, and the first l²-Betti number
  
• (with Benjamin J. Morris and Oded Schramm) Ends in uniform spanning forests
  
• (with Antal A. Járai) Ladder sandpiles
  
• (with Nicholas James and Yuval Peres) A transient Markov chain without cutpoints
  
• (with David Aldous) Processes on unimodular random networks
  
• (with Itai Benjamini and Ori Gurel-Gurevich) Recurrence of random walk traces
  
• (with Lewis Bowen, Charles Radin, and Peter Winkler) A solidification phenomenon in random packings
  
• (with Lewis Bowen, Charles Radin, and Peter Winkler) Fluid/solid transition in a hard-core system
  
• (with Yuval Peres and Oded Schramm) Minimal spanning forests
  
• (with Jessica L. Felker) High-precision entropy values for spanning trees in lattices
  
• Asymptotic enumeration of spanning trees
  
• Szegő limit theorems
  
• (with Peter Paule and Axel Riese) A computer proof of a series evaluation in terms of harmonic numbers
  
• (with Jeffrey E. Steif) Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination
  
• Determinantal probability measures
  
• (with Yuval Peres and Oded Schramm) Markov chain intersections and the loop-erased walk
  
• (with Deborah Heicklen) Change intolerance in spanning forests
  
• (with Olle Häggström and Johan Jonasson) Explicit isoperimetric constants and phase transitions in the random-cluster model
  
• (with Olle Häggström and Johan Jonasson) Coupling and Bernoullicity in random-cluster and Potts models
  
• Phase transitions on nonamenable graphs
  
• (with Oded Schramm) Stationary measures for random walks in a random environment with random scenery
  
• (with Oded Schramm) Indistinguishability of percolation clusters
  
• (with Alano Ancona and Yuval Peres) Crossing estimates and convergence of Dirichlet functions along random walk and diffusion paths
  
• Singularity of some random continued fractions
  
• (with Itai Benjamini and Oded Schramm) Percolation perturbations in potential theory and random walks
  
• (with Itai Benjamini, Yuval Peres, and Oded Schramm) Uniform spanning forests
  
• A bird's-eye view of uniform spanning trees and forests,
  
• (with Robin Pemantle and Yuval Peres) Resistance bounds for first-passage percolation and maximum flow
  
• (with Itai Benjamini, Yuval Peres, and Oded Schramm) Group-invariant percolation on graphs
  
• (with Itai Benjamini, Yuval Peres, and Oded Schramm) Critical percolation on any nonamenable group has no infinite clusters
  
• (with Michael Larsen) Coalescing particles on an interval
  
• (with Kevin Zumbrun) Normality of tree-growing search strategies
  
• Probabilistic aspects of infinite trees and some applications
  
• (with Robin Pemantle and Yuval Peres) Random walks on the Lamplighter Group
  
• (with Robin Pemantle and Yuval Peres) Biased random walks on Galton-Watson trees
  
• (with Robin Pemantle and Yuval Peres) Unsolved problems concerning random walks on trees
  
• Diffusions and random shadows on negatively-curved manifolds
  
• (with Thomas G. Kurtz, Robin Pemantle, and Yuval Peres) A conceptual proof of the Kesten-Stigum theorem for multi-type branching processes
  
• A simple path to Biggins' martingale convergence for branching random walk
  
• How fast and where does a random walker move in a random tree?
  
• (with Robin Pemantle and Yuval Peres) Conceptual proofs of L log L criteria for mean behavior of branching processes
  
• Seventy years of Rajchman measures
  
• Random walks and the growth of groups
  
• (with Robin Pemantle and Yuval Peres) Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure
  
• (with Kevin Zumbrun) Homogeneous partial derivatives of radial functions
  
• Random walks, capacity, and percolation on trees
  
• (with Robin Pemantle) Random walk in a random environment and first-passage percolation on trees
  
• The local structure of some measure-algebra homomorphisms
  
• Random walks and percolation on trees
  
• The Ising model and percolation on trees and tree-like graphs
  
• Topologies on measure spaces and the Radon-Nikodým theorem
  
• Strong laws of large numbers for weakly correlated random variables
  
• A new type of sets of uniqueness
  
• (with Alexander S. Kechris) Ordinal rankings on measures annihilating thin sets
  
• Singular measures with spectral gaps
  
• Mixing and asymptotic distribution modulo 1
  
• The size of some classes of thin sets
  
• On the structure of sets of uniqueness
  
• Wiener's theorem, the Radon-Nikodym theorem, and M₀(T)
  
• Fourier-Stieltjes coefficients and asymptotic distribution modulo 1
  
• Characterizations of measures whose Fourier-Stieltjes transforms vanish at infinity
  
• Characterizations of measures whose Fourier-Stieltjes transforms vanish at infinity (Ph.D. thesis)
  
• Measure-theoretic quantifiers and Haar measure
  
• A lower bound on the Cesàro operator
  
• (with H. Mieras and C.L. Bennett) Time domain integral equation approach to EM scattering by dielectric solids
  
• (with H. Mieras and C.L. Bennett) Space-time integral equation approach to dielectric targets
  
• E2691
  
• E2573
  

Abstracts and Links:

• (with Matteo D'Achille, Nicolas Curien, Nathanael Enriquëz, and Meltem Ünel) Ideal Poisson--Voronoi tessellations on hyperbolic spaces,
  We study the limit in low intensity of Poisson--Voronoi tessellations in hyperbolic spaces $ \mathbb{H}_{d}$ for $d \geq 2$. In contrast to the Euclidean setting, a limiting nontrivial ideal tessellation $ \mathcal{V}_{d}$ appears as the intensity tends to $0$. The tessellation $ \mathcal{V}_{d}$ is a natural, isometry-invariant decomposition of $ \mathbb{H}_{d}$ into countably many unbounded polytopes, each with a unique end. We study its basic properties, in particular, the geometric features of its cells. [Version of 24 Oct. 2024]
  • Gallery of additional images as well as videos for this paper

• (with Graham White) Monotonicity for continuous-time random walks, Ann. Probab 51, no. 3 (2023), 1112--1138
  Consider continuous-time random walks on Cayley graphs where the rate assigned to each edge depends only on the corresponding generator. We show that the limiting speed is monotone increasing in the rates for infinite Cayley graphs that arise from Coxeter systems, but not for all Cayley graphs. On finite Cayley graphs, we show that the distance --- in various senses --- to stationarity is monotone decreasing in the rates for Coxeter systems and for abelian groups, but not for all Cayley graphs. We also find several examples of surprising behaviour in the dependence of the distance to stationarity on the rates. This includes a counterexample to a conjecture on entropy of Benjamini, Lyons, and Schramm. We also show that the expected distance at any fixed time for random walks on $\Z^+$ is monotone increasing in the rates for arbitrary rate functions, which is not true on all of $\Z$. Various intermediate results are also of interest. [Published version]

• (with Avinoam Mann, Romain Tessera, and Matthew Tointon) Explicit universal minimal constants for polynomial growth of groups, J. Group Theory 26, no. 1 (2023), 29--53   (or published version)
  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\}$. [Version of 18 March 2022]

• (with Yiping Hu and Pengfei Tang) A reverse Aldous--Broder algorithm, Ann. Inst. H. Poincaré Probab. Statist. 57, no. 2 (2021), 890--900.
  The Aldous--Broder algorithm provides a way of sampling a uniform 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. [Published version]

• Strong negative type in spheres, Pacific J. Math. 307, no. 2 (2020), 383--390.
  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ékely, 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ér--Wold theorem. [Version of 4 April 2020]

• Exit boundaries of multidimensional SDEs, Electron. Commun. Probab. 24 (2019), paper no. 24, 2pp.
  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. [Published version]

• (with Yuval Peres and Xin Sun) Induced graphs of uniform spanning forests, Ann. Inst. H. Poincaré Probab. Statist. 56, no. 4 (2020), 2732--2744.
  Given a subgraph $H$ of a graph $G$, the induced graph of $H$ is the largest subgraph of $G$ whose vertex set is the same as that of $H$. Our paper concerns the induced graphs of the components of $\wsf(G)$, the wired spanning forest on $G$, and, to a lesser extent, $\fsf(G)$, the free uniform spanning forest. We show that the induced graph of each component of $\wsf(\mathbb Z^d$) is almost surely recurrent when $d\ge 8$. Moreover, the effective resistance between two points on the ray of the tree to infinity within a component grows linearly when $d\ge9$. For any vertex-transitive graph $G$, we establish the following resampling property: Given a vertex $o$ in $G$, let $\tree$ be the component of $\wsf(G)$ containing $o$ and $\graph$ be its induced graph. Conditioned on $\graph$, the tree $\tree$ is distributed as $\wsf(\graph)$. For any graph $G$, we also show that if $\tree$ is the component of $\fsf(G)$ containing $o$ and $\graph$ is its induced graph, then conditioned on $\graph$, the tree $\tree$ is distributed as $\fsf(\graph)$. [Published version]

• Problem 198, EMS Newsletter, no. 109 (2018), p. 59 .
  Solution to Problem 198, EMS Newsletter, no. 111 (2019), p. 58 .
  We present a 4-part puzzle on Brownian motion in the plane. [Published version]

• (with Nina Holden) Lower bounds for trace reconstruction, Ann. Appl. Probab. 30, no. 2 (2020), 503--525.
  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 we need at least $c\, n^{5/4}/\sqrt{\log n}$ traces 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} $. [Published version]
  • Erratum, Ann. Appl. Probab. 32, no. 4 (2022), 3201--3203.

• (with Graham White) A stationary planar random graph with singular stationary dual: Dyadic lattice graphs, Probab. Theory Related Fields 176 (2020), 1011--1043.
  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. [Version of 27 June 2019; published version here.]

• A note on tail triviality for determinantal point processes, Electron. Commun. Probab. 23 (2018), no. 72, 1--3.
  We give a very short proof that determinantal point processes have a trivial tail $\sigma$-field. This conjecture of the author has been proved by Osada and Osada as well as by Bufetov, Qiu, and Shamov. The former set of authors relied on the earlier result of the present author that the conjecture held in the discrete case, as does the present short proof. [Published version]

• Monotonicity of average return probabilities for random walks in random environments, Contemp. Math. 719 (2018), 1--9.
  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 $\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 $\P_{(G, o)}$ denote the conditional law of $H$ given $(G, o)$. Assume that $\alpha := \P_{(\gh, \bp)}\big[o \in \verts(H)\big] > 0$ is a constant $\P$-a.s. We show that if $\P$-a.s. whenever $e \in \edges(\gh)$ is adjacent to $\bp$, $$ \E_{(\gh, \bp)}\big[w_H(e) \bigm| e \in \edges(H)\big] \, \P_{(\gh, \bp)}\big[e \in \edges(H) \bigm| \bp\in \verts(H)\big] \le w_G(e) \,, $$ then $$ \forall t > 0 \quad \E\big[p_t(o; G)\big] \le \E\big[p_t(o; H) \bigm| o \in \verts(H)\big] \,. $$ [Version of 3 Jan. 2019]

• (with Alex Zhai) Zero sets for spaces of analytic functions, Ann. Inst. Fourier 68, no. 6 (2018), 2311--2328.
  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. [Published version]
  • Errata

• (with Yuval Peres, Xin Sun, and Tianyi Zheng) Occupation measure of random walks and wired spanning forests in balls of Cayley graphs, Ann. Fac. Sci. Toulouse Math., Ser. 6, 29, no. 1 (2020), 97--109.
  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})$. [Version of 6 Nov. 2018]
  • Errata

• (with Chris Judge) Upper bounds for the spectral function on homogeneous spaces via volume growth, Rev. Mat. Iberoam. 35, no. 6 (2019), 1835--1858.
  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. [Version of 5 Feb. 2018; published version here.]

• (with Shayan Oveis Gharan) Sharp bounds on random walk eigenvalues via spectral embedding, Int. Math. Res. Not. IMRN 2018, no. 24 (2018), 7555--7605.
  Spectral embedding of graphs uses the top $k$ non-trivial eigenvectors of the random walk matrix to embed the graph into $\mathbb{R}^k$. The primary use of this embedding has been for practical spectral clustering algorithms (Shi--Malik 2000, Ng--Jordan--Weiss 2001). Recently, spectral embedding was studied from a theoretical perspective to prove higher order variants of Cheeger's inequality (Lee-Oveis Gharan-Trevisan 2012, Louis--Raghavendra--Tetali--Vempala 2012).

  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 \ge 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 Landau and Odlyzko (1981). 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 Lyons (2005), we design a local algorithm to approximate the number of spanning trees of massive graphs. [Published version]

  • Errata

• (with Kevin Zumbrun) A calculus proof of the Cramér-Wold theorem, Proc. Amer. Math. Soc. 146, no. 3 (2018), 1331--1334.
  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. [Version of 22 April 2017]
  • Erratum

• Comparing graphs of different sizes, Combin. Probab. Comput. 26, no. 5 (2017), 681--696.
  We consider two notions describing how one finite graph may be larger than another. Using them, we prove several theorems for such pairs that compare the number of spanning trees, the return probabilities of random walks, and the number of independent sets, among other combinatorial quantities. Our methods involve inequalities for determinants, for traces of functions of operators, and for entropy. [Version of 17 Oct. 2016]

• (with Yuval Peres) Poisson boundaries of lamplighter groups: Proof of the Kaimanovich-Vershik conjecture, J. Europ. Math. Soc.23, no. 4 (2021), 1133--1160.
  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 $\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. [Version of 22 April 2020]

• Hyperbolic space has strong negative type, Illinois J. Math. 58, no. 4 (2014), 1009--1013.
  It is known that hyperbolic spaces have strict negative type, a condition on the distances of any finite subset of points. We show that they have strong negative type, a condition on every probability distribution of points (with integrable distance to a fixed point). This implies that the function of expected distances to points determines the probability measure uniquely. It also implies that the distance covariance test for stochastic independence, introduced by Székely, Rizzo and Bakirov, is consistent against all alternatives in hyperbolic spaces. We prove this by showing an analogue of the Cramér-Wold device. [Published version]
  • Errata

• Determinantal probability: basic properties and conjectures, Proc. International Congress of Mathematicians 2014, Seoul, Korea, vol. IV, 137--161.
  We describe the fundamental constructions and properties of determinantal probability measures and point processes, giving streamlined proofs. We illustrate these with some important examples. We pose several general questions and conjectures. [Version of 22 May 2014]   [Published version here]
  • Errata

• (with Andreas Thom) Invariant coupling of determinantal measures on sofic groups, Ergodic Theory Dynamical Systems 36, no. 2 (2016), 574--607.
  To any positive contraction $Q$ on $\ell^2(W)$, there is associated a determinantal probability measure $\P^Q$ on $2^W$, where $W$ is a denumerable set. Let $\gp$ be a countable sofic finitely generated group and $G = (\gp, \edge)$ be a Cayley graph of $\gp$. We show that if $Q_1$ and $Q_2$ are two $\gp$-equivariant positive contractions on $\ell^2(\gp)$ or on $\ell^2(\edge)$ with $Q_1 \le Q_2$, then there exists a $\gp$-invariant monotone coupling of the corresponding determinantal probability measures witnessing the stochastic domination $\P^{Q_1} \dom \P^{Q_2}$. In particular, this applies to the wired and free uniform spanning forests, which was known before only when $\gp$ is residually amenable. In the case of spanning forests, we also give a second more explicit proof, which has the advantage of showing an explicit way to create the free uniform spanning forest as a limit over a sofic approximation. Another consequence of our main result is to prove that all determinantal probability measures $\P^Q$ as above are $\dbar$-limits of finitely dependent processes. Thus, when $\gp$ is amenable, $\P^Q$ is isomorphic to a Bernoulli shift, which was known before only when $\gp$ is abelian. We also prove analogous results for sofic unimodular random rooted graphs. [Published version ©Cambridge University Press]

• Factors of IID on trees, Combin. Probab. Comput. 26, no. 2 (2017), 285--300.
  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. [Version of 3 Sep. 2016]
  • Errata

• (with Yuval Peres) Cycle density in infinite Ramanujan graphs, Ann. Probab. 43, no. 6 (2015), 3337--3358.
  We introduce a technique using non-backtracking random walk for estimating the spectral radius of simple random walk. This technique relates the density of non-trivial cycles in simple random walk to that in non-backtracking random walk. We apply this to infinite Ramanujan graphs, which are regular graphs whose spectral radius equals that of the tree of the same degree. Kesten showed that the only infinite Ramanujan graphs that are Cayley graphs are trees. This result was extended to unimodular random rooted regular graphs by Abért, Glasner and Virág. We show that an analogous result holds for all regular graphs: the frequency of times spent by simple random walk in a non-trivial cycle is a.s. 0 on every infinite Ramanujan graph. We also give quantitative versions of that result, which we apply to answer another question of Abért, Glasner and Virág, showing that on an infinite Ramanujan graph, the probability that simple random walk encounters a short cycle tends to 0 a.s. as the time tends to infinity. We consider unimodular random rooted trees (URTs) and invariant forests in Cayley graphs. [Published version]

• (with Itai Benjamini and Oded Schramm) Unimodular random trees, Ergodic Theory Dynamical Systems, 35, no. 2 (2015), 359--373.
  We consider unimodular random rooted trees (URTs) and invariant forests in Cayley graphs. We show that URTs of bounded degree are the same as the law of the component of the root in an invariant percolation on a regular tree. We use this to give a new proof that URTs are sofic, a result of Elek. We show that ends of invariant forests in the hyperbolic plane converge to ideal boundary points. We also note that uniform integrability of the degree distribution of a family of finite graphs implies tightness of that family for local convergence, also known as random weak convergence. [Published version ©Cambridge University Press]

• (with Omer Angel and Alexander S. Kechris) Random orderings and unique ergodicity of automorphism groups, J. Europ. Math. Soc. 16 (2014), 2059--2095.
  We show that the only random orderings of finite graphs that are invariant under isomorphism and induced subgraph are the uniform random orderings. We show how this implies the unique ergodicity of the automorphism group of the random graph. We give similar theorems for other structures, including, for example, metric spaces. These give the first examples of uniquely ergodic groups, other than compact groups and extremely amenable groups, after Glasner and Weiss's example of the group of all permutations of the integers. We also contrast these results to those for certain special classes of graphs and metric spaces in which such random orderings can be found that are not uniform. [Published version]

• Fixed price of groups and percolation, Ergodic Theory Dynamical Systems 33, no. 1 (2013), 183--185.
  We prove that for every finitely generated group Γ, at least one of the following holds: (1) Γ has fixed price; (2) each of its Cayley graphs G has infinitely many infinite clusters for some Bernoulli percolation on G. [Published version; ©Cambridge University Press]

• Distance covariance in metric spaces, Ann. Probab. 41, no. 5 (2013), 3284--3305.
  We extend the theory of distance (Brownian) covariance from Euclidean spaces, where it was introduced by Székely, Rizzo and Bakirov, to general metric spaces. We show that for testing independence, it is necessary and sufficient that the metric space be of strong negative type. In particular, we show that this holds for separable Hilbert spaces, which answers a question of Kosorok. Instead of the manipulations of Fourier transforms used in the original work, we use elementary inequalities for metric spaces and embeddings in Hilbert spaces. [Published version]
  • Errata to "Distance covariance in metric spaces", Ann. Probab. 46, no. 4 (2018), 2400--2405.
  • Second errata to "Distance covariance in metric spaces", Ann. Probab. 49, No. 5 (2021), 2668--2670.
  • Just after the proof of Proposition 2.4, $\mathrm{dcov}(\theta)/[D(\mu)D(\nu)]$ should be $\mathrm{dcov}(\theta)/\sqrt{\mathrm{dcov}(X,X)\mathrm{dcov}(Y,Y)}$.

• The spread of evidence-poor medicine via flawed social-network analysis, Stat., Politics, Policy 2, 1 (2011), Article 2. DOI: 10.2202/2151-7509.1024
  The chronic widespread misuse of statistics is usually inadvertent, not intentional. We find cautionary examples in a series of recent papers by Christakis and Fowler that advance statistical arguments for the transmission via social networks of various personal characteristics, including obesity, smoking cessation, happiness, and loneliness. Those papers also assert that such influence extends to three degrees of separation in social networks. We shall show that these conclusions do not follow from Christakis and Fowler's statistical analyses. In fact, their studies even provide some evidence against the existence of such transmission. The errors that we expose arose, in part, because the assumptions behind the statistical procedures used were insufficiently examined, not only by the authors, but also by the reviewers. Our examples are instructive because the practitioners are highly reputed, their results have received enormous popular attention, and the journals that published their studies are among the most respected in the world. An educational bonus emerges from the difficulty we report in getting our critique published. We discuss the relevance of this episode to understanding statistical literacy and the role of scientific review, as well as to reforming statistics education. [Published version with erratum]
  Media Coverage:
  • Slate April 2010 (cover story)
  • Food & Beverage Litigation Update June 2011
  • Slate July 2011 (cover story)
  • Boston Globe July 2011 (front page)
  • New York Times August 2011, podcast starts about 14:20 from the beginning
  • Irish Medical Times August 2011
  • Indiana University press release August 2011
  • Biomedical Computation Review Fall 2011 (part of cover story)
  • The Drum (Australian Broadcasting Corporation) April 2012
  • The Guardian September 2013
  • The Los Angeles Times March 2014

• (with Fedor Nazarov) Perfect matchings as IID factors on non-amenable groups, Europ. J. Combin. 32 (2011), 1115--1125.
  We prove that in every bipartite Cayley graph of every non-amenable group, there is a perfect matching that is obtained as a factor of independent uniform random variables. We also discuss expansion properties of factors and improve the Hoffman spectral bound on independence number of finite graphs. [Version of 4 Aug. 2010]
  • Errata

• (with Alexander E. Holroyd and Terry Soo) Poisson splitting by factors, Ann. Probab. 39, no. 5 (2011), 1938--1982.
  Given a homogeneous Poisson process on $\R^d$ with intensity $\lambda$, we prove that it is possible to partition the points into two sets, as a deterministic function of the process, and in an isometry-equivariant way, so that each set of points forms a homogeneous Poisson process, with any given pair of intensities summing to $\lambda$. In particular, this answers a question of Ball, who proved that in $d=1$, the Poisson points may be similarly partitioned (via a translation-equivariant function) so that one set forms a Poisson process of lower intensity, and asked whether the same was possible for all $d$. We do not know whether it is possible similarly to add points (again chosen as a deterministic function of a Poisson process) to obtain a Poisson process of higher intensity, but we prove that this is not possible under an additional finitariness condition. [Published version]

• Random complexes and l²-Betti numbers, J. Topology Anal. 1, no. 2 (2009), 153--175.
  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 $\ell^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 $\ell^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. [Version of 27 May 2015]    
  • Click here for a sample of the matroidal measure P₂ in a 3x3x3 cube.
  • Errata

• Identities and inequalities for tree entropy, Combin. Probab. Comput. 19, no. 2 (2010), 303--313.
  The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some new expressions for tree entropy; one uses Fuglede-Kadison determinants, while another uses effective resistance. We use the latter to prove that tree entropy respects stochastic domination. We also prove that tree entropy is non-negative in the unweighted case, a special case of which establishes Lück's Determinant Conjecture for Cayley-graph Laplacians. We use techniques from the theory of operators affiliated to von Neumann algebras. [Published version; ©Cambridge University Press]
  • Errata

• (with Ron Peled and Oded Schramm) Growth of the number of spanning trees of the Erdős-Rényi giant component, Combin. Probab. Comput. 17 (2008), 711--726.
  The number of spanning trees in the giant component of the random graph $\G(n, c/n)$ ($c>1$) grows like $\exp\big\{m\big(f(c)+o(1)\big)\big\}$ as $n\to\infty$, where $m$ is the number of vertices in the giant component. The function $f$ is not known explicitly, but we show that it is strictly increasing and infinitely differentiable. Moreover, we give an explicit lower bound on $f'(c)$. A key lemma is the following. Let $\PGW(\lambda)$ denote a Galton-Watson tree having Poisson offspring distribution with parameter $\lambda$. Suppose that $\lambda^*>\lambda>1$. We show that $\PGW(\lambda^*)$ conditioned to survive forever stochastically dominates $\PGW(\lambda)$ conditioned to survive forever. [Published version, ©Cambridge University Press]

• (with Damien Gaboriau) A measurable-group-theoretic solution to von Neumann's problem, Invent. Math. 177, no. 3 (2009), 533--540.
  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. [Version of 14 Feb. 2009]
  
  • Bourbaki seminar exposition by Cyril Houdayer

• (with Mikaël Pichot and Stéphane Vassout) Uniform non-amenability, cost, and the first l²-Betti number, Geometry, Groups, and Dynamics 2 (2008), 595--617.
  It is shown that $2\beta_1(\G)\leq h(\G)$ for any countable group $\G$, where $\beta_1(\G)$ is the first $\ell^2$-Betti number and $h(\G)$ the uniform isoperimetric constant. In particular, a countable group with non-vanishing first $\ell^2$-Betti number is uniformly non-amenable.

  We then define isoperimetric constants in the framework of measured equivalence relations. For an ergodic measured equivalence relation $R$ of type $\IIi$, the uniform isoperimetric constant $h(R)$ of $R$ is invariant under orbit equivalence and satisfies $$ 2\beta_1(R)\leq 2C(R)-2\leq h(R) \,, $$ where $\beta_1(\R)$ is the first $\ell^2$-Betti number and $C(R)$ the cost of $R$ in the sense of Levitt (in particular $h(R)$ is a non-trivial invariant). In contrast with the group case, uniformly non-amenable measured equivalence relations of type $\IIi$ always contain non-amenable subtreeings.

  An ergodic version $h_e(\G)$ of the uniform isoperimetric constant $h(\G)$ is defined as the infimum over all essentially free ergodic and measure preserving actions $\alpha$ of $\G$ of the uniform isoperimetric constant $h(R_\alpha)$ of the equivalence relation $R_\alpha$ associated to $\alpha$. By establishing a connection with the cost of measure-preserving equivalence relations, we prove that $h_e(\G)=0$ for any lattice $\G$ in a semi-simple Lie group of real rank at least 2 (while $h_e(\G)$ does not vanish in general). [Version of 21 Sep. 2008; note that theorem numbering is different in the published version]

  • Errata

• (with Benjamin J. Morris and Oded Schramm) Ends in uniform spanning forests, Electr. J. Probab. 13, Paper 58 (2008), 1701--1725.
  It has hitherto been known that in a transitive unimodular graph, each tree in the wired spanning forest has only one end a.s. We dispense with the assumptions of transitivity and unimodularity, replacing them with a much broader condition on the isoperimetric profile that requires just slightly more than uniform transience. [Published version]
  • Errata

• (with Antal A. Járai) Ladder sandpiles, Markov Proc. Rel. Fields 13 (2007), 493--518.
  We study Abelian sandpiles on graphs of the form $G \times I$, where $G$ is an arbitrary finite connected graph, and $I \subset \Z$ is a finite interval. We show that for any fixed $G$ with at least two vertices, the stationary measures $\mu_I = \mu_{G \times I}$ have two extremal weak limit points as $I \uparrow \Z$. The extremal limits are the only ergodic measures of maximum entropy on the set of infinite recurrent configurations. We show that under any of the limiting measures, one can add finitely many grains in such a way that almost surely all sites topple infinitely often. We also show that the extremal limiting measures admit a Markovian coding. [Published version]

• (with Nicholas James and Yuval Peres) A transient Markov chain without cutpoints, Probability and Statistics: Essays in Honor of David A. Freedman, IMS Collections 2 (2008), 24--29.
  We give an example of a transient reversible Markov chain that a.s. has only a finite number of cutpoints. We explain how this is relevant to a conjecture of Diaconis and Freedman and a question of Kaimanovich. We also answer Kaimanovich's question when the Markov chain is a nearest-neighbor random walk on a tree. [Published version]

• (with David Aldous) Processes on unimodular random networks, Electr. J. Probab. 12, Paper 54 (2007), 1454--1508.
  We investigate unimodular random networks. Our motivations include their characterization via reversibility of an associated random walk and their similarities to unimodular quasi-transitive graphs. We extend various theorems concerning random walks, percolation, spanning forests, and amenability from the known context of unimodular quasi-transitive graphs to the more general context of unimodular random networks. We give properties of a trace associated to unimodular random networks with applications to stochastic comparison of continuous-time random walk. [Version of 26 June 2023, which has most of the corrections noted in the two errata below; note that Proposition 4.9 was inadvertently changed by the publisher to Theorem 4.9]
  • Errata to "Processes on unimodular random networks", Electron. J. Probab. 22 (2017), paper no. 51, 4 pp.
  • Second errata to "Processes on unimodular random networks", Electron. J. Probab. 24 (2019), paper no. 25, 1--2.
  • original published version

• (with Itai Benjamini and Ori Gurel-Gurevich) Recurrence of random walk traces, Ann. Probab. 35, no. 2 (2007) 732--738.
  We show that the edges crossed by a random walk in a network form a recurrent graph a.s. In fact, the same is true when those edges are weighted by the number of crossings. [Published version]

• (with Lewis Bowen, Charles Radin, and Peter Winkler) A solidification phenomenon in random packings, SIAM J. Math. Anal. 38, no. 4 (2006), 1075--1089.
  We prove that uniformly random packings of copies of a certain simply-connected figure in the plane exhibit global connectedness at all sufficiently high densities, but not at low densities. [Version of 16 Dec. 2005]

• (with Lewis Bowen, Charles Radin, and Peter Winkler) Fluid/solid transition in a hard-core system, Phys. Rev. Lett. 96, 025701 (2006)
  We prove that a system of particles in space, interacting only with a certain hard-core constraint, undergoes a fluid/solid phase transition. [Published version]

• (with Yuval Peres and Oded Schramm) Minimal spanning forests, Ann. Probab. 34, no. 5 (2006), 1665--1692.
  We study minimal spanning forests in infinite graphs, which are weak limits of minimal spanning trees from finite subgraphs corresponding to i.i.d. random labels on the edges. These limits can be taken with free or wired boundary conditions, and are denoted $\fmsf$ (free minimal spanning forest) and $\wmsf$ (wired minimal spanning forest), respectively. The $\wmsf$ is the union of the trees that arise from invasion percolation started at all vertices. We show that on any Cayley graph where critical percolation has no infinite clusters, all the component trees in the $\wmsf$ have one end a.s. In $\Z^d$ this was proved by Alexander, but a different method is needed for the nonamenable case. We show that on any connected graph, the union of the $\fmsf$ and independent Bernoulli percolation (with arbitrarily small parameter) is a.s. connected. In conjunction with a recent result of Gaboriau, this implies that in any Cayley graph, the expected degree of the $\fmsf$ is at least the expected degree of the $\fsf$ (the weak limit of uniform spanning trees). We show that on any graph, each component tree in the $\wmsf$ has $\pc = 1$ a.s., where $\pc$ denotes the critical probability for having an infinite cluster in Bernoulli percolation. We show that the number of infinite clusters for Bernoulli($\pu$) percolation is at most the number of components of the $\fmsf$, where $\pu$ denotes the critical probability for having a unique infinite cluster. [Published version]
  • Errata

• (with Jessica L. Felker) High-precision entropy values for spanning trees in lattices, J. Phys. A. 36 (2003), 8361--8365.
  Shrock and Wu have given numerical values for the exponential growth rate of the number of spanning trees in Euclidean lattices. We give a new technique for numerical evaluation that gives much more precise values, together with rigorous bounds on the accuracy. In particular, the new values resolve one of their questions. [Version of 6 Nov. 2003]
  • Errata

• Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005), 491--522.
  We give new general formulas for the asymptotics of the number of spanning trees of a large graph. A special case answers a question of McKay (1983) for regular graphs. The general answer involves a quantity for infinite graphs that we call ``tree entropy", which we show is a logarithm of a normalized determinant of the graph Laplacian for infinite graphs. Tree entropy is also expressed using random walks. We relate tree entropy to the metric entropy of the uniform spanning forest process on quasi-transitive amenable graphs, extending a result of Burton and Pemantle (1993). [Published version]
  • Errata

• Szegő limit theorems, Geom. Funct. Anal. 13 (2003), 574--590.
  The first Szegő limit theorem has been extended by Bump-Diaconis and Tracy-Widom to limits of other minors of Toeplitz matrices. We extend their results still further to allow more general measures and more general determinants. We also give a new extension to higher dimensions, which extends a theorem of Helson and Lowdenslager. [Version of 22 June 2024]
  • Errata

• (with Peter Paule and Axel Riese) A computer proof of a series evaluation in terms of harmonic numbers, Appl. Algebra Engrg. Comm. Comput. 13, no. 4 (2002), 327--333.
  A fruitful interaction between a new randomized WZ procedure and other computer algebra programs is illustrated by the computer proof of a series evaluation that originates from a definite integration problem. [Version of 16 July 2002]

• (with Jeffrey E. Steif) Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination, Duke Math. J. 120, no. 3 (2003), 515--575.
  We study a class of stationary processes indexed by $\Z^d$ that are defined via minors of $d$-dimensional (multilevel) Toeplitz matrices. We obtain necessary and sufficient conditions for phase multiplicity (the existence of a phase transition) analogous to that which occurs in statistical mechanics. Phase uniqueness is equivalent to the presence of a strong $K$ property, a particular strengthening of the usual $K$ (Kolmogorov) property. We show that all of these processes are Bernoulli shifts (isomorphic to i.i.d. processes in the sense of ergodic theory). We obtain estimates of their entropies and we relate these processes via stochastic domination to product measures. [Version of 15 Nov. 2019]

• Determinantal probability measures, Publ. Math. Inst. Hautes Études Sci. 98 (2003), 167--212.
  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. [Version of 10 Mar. 2004]
  
  • The unpublished original appendix, which proves the Matrix-Tree Theorem in a simple fashion, as well as a theorem of Maurer.
  • Errata

• (with Yuval Peres and Oded Schramm) Markov chain intersections and the loop-erased walk, Ann. Inst. H. Poincaré Probab. Statist. 39, no. 5, (2003), 779--791.
  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. [Version of 7 Feb. 2005]

• (with Deborah Heicklen) Change intolerance in spanning forests, J. Theor. Probab. 16 (2003), 47--58.
  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. [Version of 11 Dec. 2002]

• (with Olle Häggström and Johan Jonasson) Explicit isoperimetric constants and phase transitions in the random-cluster model, Ann. Probab. 30 (2002), 443--473.   (or gzipped version)
  The random-cluster model is a dependent percolation model that has applications in the study of Ising and Potts models. In this paper, several new results are obtained for the random-cluster model on nonamenable graphs with cluster parameter $q\geq 1$. Among these, the main ones are the absence of percolation for the free random-cluster measure at the critical value, and examples of planar regular graphs with regular dual where $\pc^\f (q) > \pu^\w (q)$ for $q$ large enough. The latter follows from considerations of isoperimetric constants, and we give the first nontrivial explicit calculations of such constants. Such considerations are also used to prove non-robust phase transition for the Potts model on nonamenable regular graphs. [Version of 6 Feb. 2002]

• (with Olle Häggström and Johan Jonasson) Coupling and Bernoullicity in random-cluster and Potts models, Bernoulli 8 (2002), no. 3, 275--294.   (or gzipped version)
  An explicit coupling construction of random-cluster measures is presented. As one of the applications of the construction, the Potts model on amenable Cayley graphs is shown to exhibit at every temperature the mixing property known as Bernoullicity. [Version of 12 Oct. 2001]

• Phase transitions on nonamenable graphs, J. Math. Phys. 41 (2000), 1099--1126.
  We survey known results about phase transitions in various models of statistical physics when the underlying space is a nonamenable graph. Most attention is devoted to transitive graphs and trees. [Version of 30 March 2000]
  • Errata

• (with Oded Schramm) Stationary measures for random walks in a random environment with random scenery, New York J. Math. 5 (1999), 107--113.
  Let $\Gamma$ act on a countable set $V$ with only finitely many orbits. Given a $\Gamma$-invariant random environment for a Markov chain on $V$ and a random scenery, we exhibit, under certain conditions, an equivalent stationary measure for the environment and scenery from the viewpoint of the random walker. Such theorems have been very useful in investigations of percolation on quasi-transitive graphs. [Published version]
  • Errata

• (with Oded Schramm) Indistinguishability of percolation clusters, Ann. Probab. 27 (1999), 1809--1836.
  We show that when percolation produces infinitely many infinite clusters on a Cayley graph, one cannot distinguish the clusters from each other by any invariantly defined property. This implies that uniqueness of the infinite cluster is equivalent to non-decay of connectivity (a.k.a. long-range order). We then derive applications concerning uniqueness in Kazhdan groups and in wreath products, and inequalities for $p_u$. [Published version]
  • Errata

• (with Alano Ancona and Yuval Peres) Crossing estimates and convergence of Dirichlet functions along random walk and diffusion paths, Ann. Probab., 27 (1999), 970--989.   (or gzipped version)
  Let $\{X_n\}$ be a transient reversible Markov chain and let $f$ be a function on the state space with finite Dirichlet energy. We prove crossing inequalities for the process $\{f(X_n)\}_{n \ge 1}$ and show that it converges almost surely and in $L^2$. Analogous results are also established for reversible diffusions on Riemannian manifolds. [Version of 22 March 1999]

• Singularity of some random continued fractions, J. Theoret. Probab., 13 (2000), 535--545.   (or gzipped version)
  We prove singularity of some distributions of random continued fractions that correspond to iterated function systems with overlap and a parabolic point. These arose while studying the conductance of Galton-Watson trees. [Version of 7 August 1999]

• (with Itai Benjamini and Oded Schramm) Percolation perturbations in potential theory and random walks, in Random Walks and Discrete Potential Theory (Cortona, 1997), Sympos. Math., M. Picardello and W. Woess (eds.), Cambridge Univ. Press, Cambridge, 1999, pp. 56--84.
  We show that on a Cayley graph of a nonamenable group, a.s. the infinite clusters of Bernoulli percolation are transient for simple random walk, that simple random walk on these clusters has positive speed, and that these clusters admit bounded harmonic functions. A principal new finding on which these results are based is that such clusters admit invariant random subgraphs with positive isoperimetric constant.

  We also show that percolation clusters in any amenable Cayley graph a.s. admit no nonconstant harmonic Dirichlet functions. Conversely, on a Cayley graph admitting nonconstant harmonic Dirichlet functions, a.s. the infinite clusters of $p$-Bernoulli percolation also have nonconstant harmonic Dirichlet functions when $p$ is sufficiently close to 1. Many conjectures and questions are presented. [Version of 13 April 1999]

• (with Itai Benjamini, Yuval Peres, and Oded Schramm) Uniform spanning forests, Ann. Probab. 29 (2001), 1--65.
  We study uniform spanning forest measures in infinite graphs, which are weak limits of uniform spanning tree measures from finite subgraphs. These limits can be taken with free or wired boundary conditions. Pemantle (1991) proved that the free and wired spanning forests coincide in $\Z^d$ and that they give a single tree iff $d<5$. In the present work, we extend Pemantle's alternative to general graphs and exhibit further connections of uniform spanning forests to random walks, potential theory, invariant percolation, and amenability. The uniform spanning forest model is related to random cluster models in statistical physics, but, because of the preceding connections, its analysis can be carried further. Among our results are the following:
  • The free spanning forest and wired spanning forest in a graph $G$ coincide iff all harmonic Dirichlet functions on $G$ are constant.
  • The tail $\sigma$-field of the wired spanning forest and the free spanning forest is trivial on any graph.
  • In any Cayley graph which is not a finite extension of $\Z$, all component trees of the wired spanning forest have one end; this is new in $\Z^d$ for $d>4$.
  • In any tree, and in any graph with spectral radius less than $1$, a.s. all components of the wired spanning forest are recurrent.
  • The basic topology of the free and the wired uniform spanning forest measures on lattices in hyperbolic space is determined.
  • A Cayley graph is amenable iff for all $\epsilon>0$, the union of the wired spanning forest and Bernoulli percolation with parameter $\epsilon$ is connected.
  • Harmonic measure from infinity is shown to exist on any recurrent proper planar graph with finite co-degrees.
  We also present fourteen open problems and conjectures. [Version of 27 Jan. 2009]
  • Errata

• A bird's-eye view of uniform spanning trees and forests, in Microsurveys in Discrete Probability, D. Aldous and J. Propp (eds.), Amer. Math. Soc., Providence, RI, 1998, pp. 135--162.   (or gzipped version)
  We survey the field of uniform spanning forest measures on infinite graphs, which are weak limits of uniform spanning tree measures from finite subgraphs. These limits can be taken with free or wired boundary conditions. Among other results, Pemantle (1991) proved that in $\Z^d$, the free and wired spanning forests coincide and that they give a single tree iff $d \le 4$. The theory has developed considerably since then and found further connections to random walks, potential theory, harmonic Dirichlet functions, invariant percolation and amenability. A crucial new tool is an algorithm invented by Wilson (1996) to generate random spanning trees. Uniform spanning forests also yield insights into loop-erased walks and harmonic measure from infinity.

• (with Robin Pemantle and Yuval Peres) Resistance bounds for first-passage percolation and maximum flow, J. Combin. Theory Ser. A 86 (1999), 158--168.   (or gzipped version)
  Suppose that each edge $e$ of a network is assigned a random exponential passage time with mean $r_e$. Then the expected first-passage time between two vertices is at least the effective resistance between them for the edge resistances $\langle r_e \rangle$. Similarly, suppose each edge is assigned a random exponential edge capacity with mean $c_e$. Then the expected maximum flow between two vertices is at least the effective conductance between them for the edge conductances $\langle c_e \rangle$. These inequalities are dual to each other for planar graphs and the second is tight up to a factor of 2 for trees; this has implications for a herd of gnus crossing a river delta.

• (with Itai Benjamini, Yuval Peres, and Oded Schramm) Group-invariant percolation on graphs, Geom. Funct. Anal. 9 (1999), 29--66.
  Let $G$ be a closed group of automorphisms of a graph $X$. We relate geometric properties of $G$ and $X$, such as amenability and unimodularity, to properties of $G$-invariant percolation processes on $X$, such as the number of infinite components, the expected degree, and the topology of the components. Our fundamental tool is a new mass-transport technique: this was invented by Häggström for the special case of automorphisms of regular trees and is developed further here.

  Perhaps surprisingly, these investigations of group-invariant percolation produce results that are new in the Bernoulli setting. Most notably, we prove that critical Bernoulli percolation on any nonamenable Cayley graph has no infinite clusters. More generally, the same is true for any nonamenable graph with a unimodular transitive automorphism group.

  We show that $G$ is amenable iff for all $\alpha<1$, there is a $G$-invariant site percolation $\omega$ on $X$ with $\P[x\in\omega]>\alpha$ for all vertices $x$ and with no infinite components. When $G$ is not amenable, a threshold $\alpha<1$ appears. An inequality for the threshold in terms of the isoperimetric constant is obtained, extending an inequality of Häggström for regular trees.

  If $G$ acts transitively on $X$, we show that $G$ is unimodular iff the expected degree is at least $2$ in any $G$-invariant bond percolation on $X$ with all components infinite.

  The investigation of dependent percolation also yields some results on automorphism groups of graphs that do not involve percolation. [Version of 14 July 2000]

  • Errata

• (with Itai Benjamini, Yuval Peres, and Oded Schramm) Critical percolation on any nonamenable group has no infinite clusters, Ann. Probab. 27 (1999), 1347--1356.   (or gzipped version)
  We show that independent percolation on any Cayley graph of a nonamenable group has no infinite components at the critical parameter. This result was obtained in the preceding paper as a corollary of a general study of group-invariant percolation. The goal here is to present a simpler self-contained proof that easily extends to quasi-transitive graphs with a unimodular automorphism group. The key tool is a ``mass-transport'' method, which is a technique of averaging in nonamenable settings. [Version of 14 Dec. 1999]

• (with Michael Larsen) Coalescing particles on an interval, J. Theoret. Probab. 12 (1999), 201--205.   (or gzipped version)
  At time 0, we begin with a particle at each integer in $[0, n]$. At each positive integer time, one of the particles remaining in $[1, n]$ is chosen at random and moved one to the left, coalescing with any particle that might already be there. How long does it take until all particles coalesce (at $0$)?
  • Errata

• (with Kevin Zumbrun) Normality of tree-growing search strategies, Ann. Applied Probab. 8 (1998), 112--130.   (or gzipped version)
  We study the class of tree-growing search strategies introduced by Lent and Mahmoud. Specifically, we study the conditions under which the number of comparisons needed to sort a sequence of randomly ordered numbers is asymptotically normal. Our main result is a sufficient condition for normality in terms of the growth rate of tree height alone; this condition is easily computed and satisfied by all standard deterministic search strategies. We also give some examples of normal search strategies with surprisingly small variance, in particular, much smaller than possible for the class of consistent strategies that are the focus of the work by Lent and Mahmoud.

• Probabilistic aspects of infinite trees and some applications, in Trees, B. Chauvin, S. Cohen, A. Rouault (editors), Birkhauser, Basel, 1996, pp. 81--94.   (or gzipped version)
  This is a talk giving an overview of some recent work on trees, especially my own. We begin by using flows to assign a positive real number, called the branching number, to an arbitrary (irregular) infinite locally finite tree. The branching number represents the ``average'' number of branches per vertex and is the exponential of the dimension of (the boundary of) the tree, as introduced by Furstenberg. There are many senses in which this branching number is an average. We discuss some based variously on electrical networks, random walks, percolation, or tree-indexed (branching) random walks. A refinement of the notion of branching number uses ideas of potential theory. This creates quite precise connections among probabilistic processes on trees.

  For applications, we consider the structure of the family tree of branching processes, the Hausdorff dimension and capacities of possibly random fractals, and random walks on Cayley graphs of infinite but finitely generated groups.

• (with Robin Pemantle and Yuval Peres) Random walks on the Lamplighter Group, Ann. Probab. 24 (1996), 1993--2006.
  Kaimanovich and Vershik described certain finitely generated groups of exponential growth such that simple random walk on their Cayley graph escapes from the identity at a sublinear rate, or equivalently, all bounded harmonic functions on the Cayley graph are constant. Here we focus on a key example, called $G_1$ by Kaimanovich and Vershik, and show that inward-biased random walks on $G_1$ move outward faster than simple random walk. Indeed, they escape from the identity at a linear rate provided that the bias parameter is smaller than the growth rate of $G_1$. These walks can be viewed as random walks interacting with a dynamical environment on $\Z$. The proof uses potential theory to analyze a stationary environment as seen from the moving particle. [Published version]

• (with Robin Pemantle and Yuval Peres) Biased random walks on Galton-Watson trees, Probab. Theory Relat. Fields 106 (1996), 249--264.
  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.

• (with Robin Pemantle and Yuval Peres) Unsolved problems concerning random walks on trees, in Classical and Modern Branching Processes, K. Athreya and P. Jagers (editors), Springer, New York, 1997, pp. 223--238.
  We state some unsolved problems and describe relevant examples concerning random walks on trees. Most of the problems involve the behavior of random walks with drift: e.g., is the speed on Galton-Watson trees monotonic in the drift parameter? These random walks have been used in Monte-Carlo algorithms for sampling from the vertices of a tree; in general, their behavior reflects the size and regularity of the underlying tree. Random walks are related to conductance. The distribution function for the conductance of Galton-Watson trees satisfies an interesting functional equation; is this distribution function absolutely continuous? [Version of 12 Aug. 2005]
  • Errata

• Diffusions and random shadows on negatively-curved manifolds, J. Functional Anal. 138 (1996), 426--448.   (or published version)
  Let $M$ be a $d$-dimensional complete simply-connected negatively-curved manifold. There is a natural notion of Hausdorff dimension for its boundary at infinity. This is shown to provide a notion of global curvature or average rate of growth in two probabilistic senses: First, on surfaces ($d = 2$), it is twice the critical drift separating transie from recurrence for Brownian motion with constant-length radial drift. Equivalently, it is twice the critical $\beta$ for the existence of a Green function for the operator $\Delta/2 - \beta \partial_r$. Second, for any $d$, it is the critical intensity for almost sure coverage of the boundary by random shadows cast by balls, appropriately scaled, produced from a constant-intensity Poisson point process. [Version of 1 Nov. 1996]
  • Erratum

• (with Thomas G. Kurtz, Robin Pemantle, and Yuval Peres) A conceptual proof of the Kesten-Stigum theorem for multi-type branching processes, in Classical and Modern Branching Processes, K. Athreya and P. Jagers (editors), Springer, New York, 1997, pp. 181--186.
  We give complete proofs of the theorem of convergence of types and the Kesten-Stigum theorem for multi-type branching processes. Very little analysis is used beyond the strong law of large numbers and some basic measure theory. [Version of 7 Sep. 2009]
  • Errata

• A simple path to Biggins' martingale convergence for branching random walk, in Classical and Modern Branching Processes, K. Athreya and P. Jagers (editors), Springer, New York, 1997, pp. 217--222.
  We give a simple non-analytic proof of Biggins' theorem on martingale convergence for branching random walks. [Version of 20 April 2012]
  • Errata

• How fast and where does a random walker move in a random tree?, in Random Discrete Structures, D. Aldous and R. Pemantle (editors), Springer, New York, 1996, pp. 185--198.   (or gzipped version)
  This is a talk describing the paper (written with Robin Pemantle and Yuval Peres) Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure, Ergodic Theory Dynamical Systems 15 (1995), 593--619.

• (with Robin Pemantle and Yuval Peres) Conceptual proofs of L log L criteria for mean behavior of branching processes, Ann. Probab. 23 (1995), 1125--1138.
  The Kesten-Stigum Theorem is a fundamental criterion for the rate of growth of a supercritical branching process, showing that an $L \log L$ condition is decisive. In critical and subcritical cases, results of Kolmogorov and later authors give the rate of decay of the probability that the process survives at least $n$ generations. We give conceptual proofs of these theorems based on comparisons of Galton-Watson measure to another measure on the space of trees. This approach also explains Yaglom's exponential limit law for conditioned critical branching processes via a simple characterization of the exponential distribution. [Published version]
  • Errata

• Seventy years of Rajchman measures, J. Fourier Anal. Appl., Kahane Special Issue (1995), 363--377.
  Rajchman measures are those Borel measures on the circle (say) whose Fourier transform vanishes at infinity. Their study proper began with Rajchman, but attention to them can be said to have begun with Riemann's theorem on Fourier coefficients, later extended by Lebesgue. Most of the impetus for the study of Rajchman measures has been due to their importance for the question of uniqueness of trigonometric series. This motivation continues to the present day with the introduction of descriptive set theory into harmonic analysis. The last ten years have seen the resolution of several old questions, some from Rajchman himself. We give a historical survey of the relationship between Rajchman measures and their common null sets with a few of the most interesting proofs.

• Random walks and the growth of groups, C. R. Acad. Sci. Paris 320 (1995), 1361--1366.   (or gzipped version)
  The critical value separating transience from recurrence for the amount of radial drift of a random walk on a Cayley graph of any finitely generated group is shown to equal the exponential growth rate of the group.

• (with Robin Pemantle and Yuval Peres) Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure, Ergodic Theory Dynamical Systems 15 (1995), 593--619.
  We consider simple random walk on the family tree $T$ of a nondegenerate supercritical Galton-Watson branching process and show that the resulting harmonic measure has a.s. strictly smaller Hausdorff dimension than that of the whole boundary of $T$. Concretely, this implies that an exponentially small fraction of the $n$th level of $T$ carries most of the harmonic measure. First order asymptotics for the rate of escape, Green function and the Avez entropy of the random walk are also determined. Ergodic theory of the shift on the space of random walk paths on trees is the main tool; the key observation is that iterating the transformation induced from this shift to the subset of ``exit points'' yields a nonintersecting path sampled from harmonic measure.
  • Errata

• (with Kevin Zumbrun) Homogeneous partial derivatives of radial functions, Proc. Amer. Math. Soc. 121 (1994), 315--316.   (or gzipped version)
  We prove the following surprising identity for differentiation of radial functions by homogeneous partial differential operators, which appears to be new.

  For a polynomial $P(x_1, \ldots, x_n)$, write, as usual, $P(D) := P(\partial/\partial x_1, \ldots, \partial/\partial x_n)$. Write $r := (x_1^2 + \cdots + x_n^2)^{1/2}$.

  Theorem. Let $P$ be a polynomial of $n$ variables homogeneous of degree $h$. Let $f$ be a function of one variable. Then $$ P(D)f(r) = \sum_{k=0}^{\lfloor h/2 \rfloor} {1 \over 2^k k!} \Delta^k P(x) \cdot \left({1 \over r}{\partial \over \partial r}\right)^{h-k} f(r). $$

• Random walks, capacity, and percolation on trees, Ann. Probab. 20 (1992), 2043--2088.
  A collection of several different probabilistic processes involving trees is shown to have an unexpected unity. This makes possible a fruitful interplay of these probabilistic processes. The processes are allowed to have arbitrary parameters and the trees are allowed to be arbitrary as well. Our work has five specific aims: First, an exact correspondence between random walks and percolation on trees is proved, extending and sharpening previous work of the author. This is achieved by establishing surprisingly close inequalities between the crossing probabilities of the two processes. Second, we give an equivalent formulation of these inequalities which uses a capacity with respect to a kernel defined by the percolation. This capacitary formulation extends and sharpens work of Fan on random interval coverings. Third, we show how this formulation also applies to generalize work of Evans on random labelling of trees. Fourth, the correspondence between random walks and percolation is used to decide whether certain random walks on random trees are transient or recurrent a.s. In particular, we resolve a conjecture of Griffeath on the necessity of the Nash-Williams criterion. Fifth, for this last purpose, we establish several new basic results on branching processes in varying environments. [Published version]
  • Errata

• (with Robin Pemantle) Random walk in a random environment and first-passage percolation on trees, Ann. Probab. 20, No. 1 (1992), 125--136.
  We show that the transience or recurrence of a random walk in certain random environments on an arbitrary infinite locally finite tree is determined by the branching number of the tree, which is a measure of the average number of branches per vertex. This generalizes and unifies previous work of the authors. It also shows that the point of phase transition for edge-reinforced random walk is likewise determined by the branching number of the tree. Finally, we show that the branching number determines the rate of first-passage percolation on trees, also known as the first-birth problem. Our techniques depend on quasi-Bernoulli percolation and large deviation results.
  • Published errata, Ann. Probab. 31 (2003), 528--529. Note: one more correction is that we mistakenly omitted the assumption that the environments at the vertices are independent.

• The local structure of some measure-algebra homomorphisms, Pacific J. Math. 148 No. 1 (1991), 89--106. Extending classical theorems, we obtain representations for bounded linear transformations from L-spaces to Banach spaces with a separable predual. In the case of homomorphisms from a convolution measure algebra to a Banach algebra, we obtain a generalization of Sreider's representation of the Gelfand spectrum via generalized characters. The homomorphisms from the measure algebra on a LCA group, $G$, to that on the circle are analyzed in detail. If the torsion subgroup of $G$ is denumerable, one consequence is the following necessary and sufficient condition that a positive finite Borel measure on $G$ be continuous: $\exists \gamma_\alpha \to\infty$ in $G$ such that $\forall n \ne 0$ $\hat\mu(\gamma_\alpha^n) \to 0$. [Published version]

• Random walks and percolation on trees, Ann. Probab. 18, No. 3 (1990), 931--958.
  There is a way to define an average number of branches per vertex for an arbitrary infinite locally finite tree. It equals the exponential of the Hausdorff dimension of the boundary in an appropriate metric. Its importance for probabilistic processes on a tree is shown in several ways, including random walk and percolation, where it provides points of phase transition. [Published version]
  • Errata

• The Ising model and percolation on trees and tree-like graphs, Commun. Math. Phys. 125, No. 2 (1989), 337--353.
  We calculate the exact temperature of phase transition for the Ising model on an arbitrary infinite tree with arbitrary interaction strengths and no external field. In the same setting, we calculate the critical temperature for spin percolation. The same problems are solved for the diluted models and for more general random interaction strengths. In the case of no interaction, we generalize to percolation on certain tree-like graphs. This last calculation supports a general conjecture on the coincidence of two critical probabilities in percolation theory. [Project Euclid link]

• Topologies on measure spaces and the Radon-Nikodým theorem, Studia Math. 91, No. 2 (1988), 125--129.
  Let $M(X)$ be the space of complex Borel measures on a compact metric space $X$. If $\sigma \in M(X)$, the Radon-Nikodym theorem identifies $L^1(\sigma)$ with $L(\sigma)$, the measures that vanish on those sets where $\sigma$ vanishes. Let $T$ be a topology on $M(X)$ and $L^T(\sigma)$ the $T$-closure of $L(\sigma)$. Analogously to the Radon-Nikodym theorem, we show that for certain $T$, $L^T(\sigma)$ is characterized by its common null sets. This unifies previous work of the author. [Publisher link]

• Strong laws of large numbers for weakly correlated random variables, Mich. Math. J. 35, No. 3 (1988), 353--359.
  We gather and refine known strong laws based on second-order conditions. For example, if $\E[|X_n|^2]\le 1,$ $\Re \E[X_n\bar X_m]\le\Phi_1(|n-m|)$, $\Phi_1\ge 0$, and $\sum_{n\ge 1} \Phi_1(n)/n$ is finite, then $(1/N)\sum_{n\le N} X_n \to 0$ a.s. Note that we do not assume that $\Phi_1$ is decreasing, nor even that it tend to 0 at $\infty$. New tools include some lemmas related to the principle of Cauchy condensation. [Project Euclid link]
  • Errata

• A new type of sets of uniqueness, Duke Math. J. 57, No. 2 (1988), 431--458.
  Recently many old questions in the theory of sets of uniqueness for trigonometric series have been answered using new techniques from Banach-space theory and descriptive set theory. For example, Kechris and Louveau and then Debs and Saint Raymond each gave a Borel basis for the class $U_0$ of sets of uniqueness in the wide sense. This fact has several important consequences. We shall show that the two bases are in fact the same, give a simpler proof that $U_0'$ is indeed a basis, and unify the theory with that for $U$-sets and $U_1$-sets. This will involve some simple extensions of theorems of Banach-Dixmier and Kechris-Louveau from subspaces to convex cones in Banach spaces. Further, less obvious, extensions of these same theorems to maps between two Banach spaces will be given to develop the theory of a new class of sets, $U_2$, which lies strictly between the $U_1$-sets and the $U_0$-sets. They too can be written as countable unions of special $U_2$-sets called $U_2'$-sets. The class $U'$ is very natural and was briefly considered by Piateckii-Shapiro and, as it turns out, by the present author in another form. Here we establish the equivalence of the two definitions of $U'$ and clarify their relations to the other types of sets of uniqueness. While this allows us to answer some previously open questions, others remain and are put into sharper relief. The theorem of Kechris and Louveau has a further generalization to polar sets and even to conjugate convex functions. [Project Euclid link]
  • Errata

• (with Alexander S. Kechris) Ordinal rankings on measures annihilating thin sets, Trans. Amer. Math. Soc. 310, No. 2 (1988), 747--758.
  We assign a countable ordinal number to each probability measure which annihilates all H-sets. The descriptive-set theoretic structure of this assignment allows us to show that this class of measures is coanalytic non-Borel. In addition, it allows us to quantify the failure of Rajchman's conjecture. Similar results are obtained for measures annihilating Dirichlet sets.

• Singular measures with spectral gaps, Proc. Amer. Math. Soc. 104, No. 1 (1988), 86--88.
  We show that every Borel measure on the circle whose Fourier spectrum has lacunary-type gaps annihilates every H-set.

• Mixing and asymptotic distribution modulo 1, Ergodic Theory Dynamical Systems 8 (1988), 597--619.
  If $\mu$ is a probability measure which is invariant and ergodic with respect to the transformation $x\mapsto qx$ on the circle $\mathbb{R}/\mathbb{Z}$, then according to the ergodic theorem, $\{q^n x\}$ has the asymptotic distribution $\mu$ for $\mu$-a.e. x. On the other hand, Weyl showed that when $\mu$ is Lebesgue measure, $\lambda$, and $\{m_j\}$ is an arbitrary sequence of integers increasing strictly to $\infty$, the asymptotic distribution of $\{m_j x\}$ is $\lambda$ for $\lambda$-a.e. $x$. Here, we investigate the asymptotic distributions of $\{m_j x\}$ $\mu$-a.e. for fairly arbitrary $\{m_j\}$ under some strong mixing conditions on $\mu$. The result is a kind of stable ergodicity: the distributions are obtained from simple operations applied to $\mu$. The ideas extend to the situation of a sequence of transformations $x\mapsto q_n x$ where invariance is not present. This gives us information about many Riesz products and Bernoulli convolutions. Finally, we apply the theory to resolve some questions about $H$-sets. [Publisher link]

• The size of some classes of thin sets, Studia Math. 86, No. 1 (1987), 59--78.
  The size of a class of subsets of the circle is reflected by the family of measures that annihilate all the sets belonging to the given class. For subclasses of U₀, the sets of uniqueness in the wide sense, the corresponding family of annihilating measures always includes M₀(T). We investigate when there are no other annihilating measures, in which case the class of sets is ``large". For example, Helson sets are shown not to form a large class, while a closely related natural class does. The fact that another class of sets, the H-sets, is ``small" disproves a conjecture of Rajchman. The class of sets of uniqueness (in the strict sense) is investigated in detail. Tools used include Riesz products and asymptotic distribution. [Publisher link]

• On the structure of sets of uniqueness, Proc. Amer. Math. Soc. 101, No. 4 (1987), 644--646.
  We show that every U₀-set is almost a W-set.

• Wiener's theorem, the Radon-Nikodym theorem, and M₀(T), Arkiv för Mat. 24 (1986), 277--282; Errata, ibid. 26 (1988), 165--166.

• Fourier-Stieltjes coefficients and asymptotic distribution modulo 1, Ann. Math. 2nd Ser., 122, No. 1 (1985), 155--170.
  Let R denote the class of complex Borel measures on the circle T whose Fourier-Stieltjes coefficients $\hat\mu(n)$ tend to 0 as $n \to\infty$. Ju. A. Sreider has defined a class of subsets of T, called W-sets, using the notion of asymptotic distribution. We establish Sreider's unproved claim that a measure $\mu$ lies in R if and only if $\mu E$ = 0 for all W-sets E. This depends on a remarkable lemma about asymptotic distribution. This lemma is, in turn, a special case of a theorem which allows us to extract from any weakly convergent sequence of functions a subsequence whose Cesàro means converge pointwise almost everywhere. [JSTOR link]

• Characterizations of measures whose Fourier-Stieltjes transforms vanish at infinity, Bull. Amer. Math. Soc. 10 (1984), 93--96.
  We announce the theorem that a measure on the circle is a Rajchman measure iff it annihilates all W-sets. We also announce the disproof of similar statements regarding W*-sets and H-sets.

• Characterizations of measures whose Fourier-Stieltjes transforms vanish at infinity, Ph.D. thesis (1983), University of Michigan.
  We prove that a measure on the circle is a Rajchman measure iff it annihilates all W-sets. We also disprove similar statements regarding W*-sets and H-sets. [Scan kindly provided by Fritz Gesztesy]

• Measure-theoretic quantifiers and Haar measure, Proc. Amer. Math. Soc. 86, No. 1 (1982), 67--70.
  Measure-theoretic quantifiers are introduced as convenient notation and to facilitate certain applications of Fubini's theorem. They are used to prove the uniqueness of Haar measure and to give some conditions involving translation which imply absolute continuity of another measure.
  • Erratum to "Measure-Theoretic Quantifiers and Haar Measure", Proc. Amer. Math. Soc. 91 No. 2, (1984), 329--330.

• A lower bound on the Cesàro operator, Proc. Amer. Math. Soc. 86, No. 4 (1982), 694.
  We confirm a conjecture of Allen Shields and Sheldon Axler.

• (with H. Mieras and C.L. Bennett) Time domain integral equation approach to EM scattering by dielectric solids, Antennas and Propagation Society International Symposium 18 (1980), 416--418, IEEE.

• (with H. Mieras and C.L. Bennett) Space-time integral equation approach to dielectric targets, Oct. 1979, SRC-CR-79-81 (for public release), Sperry Research Center, Sudbury, MA.

• E2691, Amer. Math. Monthly 86, No. 3 (1979), 224--225.
  [JSTOR link]

• E2573, Amer. Math. Monthly 84, No. 4 (1977), 298--299.
  [JSTOR link]

List of Papers Not Available Electronically:

• La mesure des ensembles non-normaux, Séminaire de Théorie des Nombres de Bordeaux, 1983--84, pp. 13--01 to 13--08 (Université de Bordeaux, France).
• La taille de certaines classes d'ensembles minces, Séminaire d'Analyse Harmonique, 1984--85, pp. IV--1 to IV--8 (Université de Paris-Sud, France).
• The measure of non-normal sets, Invent. Math. 83 (1986), 605--616. Publisher link.
• On measures simultaneously 2- and 3-invariant, Israel J. Math. 61 (1988), 219--224. Publisher link.
• (with Scot Adams) Amenability, Kazhdan's property and percolation for trees, groups and equivalence relations, Israel J. Math. 75 (1991), 341--370. Publisher link.
• Equivalence of boundary measures on covering trees of finite graphs, Ergodic Theory Dynamical Systems 14 (1994), 575--597. Publisher link.
• Sur l'histoire de M₀(T), appendix to J.-P. Kahane and R. Salem, Ensembles parfaits et séries trigonométriques, 2nd ed., Hermann, Paris, 1994.
• Biased random walks and harmonic functions on the Lamplighter Group, in Harmonic Functions on Trees and Buildings: Workshop on Harmonic Functions on Graphs, A. Korányi (ed.), American Mathematical Society, Providence, RI, 1997, pp. 137--139.

Some Talks:

• Lower bounds for trace reconstruction
• Comparing return probabilities
• Random walks on groups and the Kaimanovich-Vershik conjecture
• Random orderings and unique ergodicity of automorphism groups
• Determinantal probability: surprising relations
• Spectral embedding bounds random walk eigenvalues and return probabilities
• Determinantal probability measures
• Uniform spanning forests, the first $\ell^2$-Betti number, and uniform isoperimetric inequalities
• Random complexes via topologically-inspired determinants
• Stationary determinantal processes (fermionic lattice gases)
• Spanning trees, random graphs, and random walks
• Random trees and surfaces
• Unimodularity and stochastic processes

Typos/Errata (as PostScript or PDF Files) to Published Papers:

• (with Nina Holden) Erratum to "Lower bounds for trace reconstruction", Ann. Appl. Probab. 32, no. 4 (2022), 3201--3203.
• (with Yuval Peres, Xin Sun, and Tianyi Zheng) Occupation measure of random walks and wired spanning forests in balls of Cayley graphs, Ann. Fac. Sci. Toulouse Math., Ser. 6, 29, no. 1 (2020), 97--109.
• (with Alex Zhai) Zero sets for spaces of analytic functions, Ann. Inst. Fourier 68, no. 6 (2018), 2311--2328.
• (with Shayan Oveis Gharan) Sharp bounds on random walk eigenvalues via spectral embedding, Int. Math. Res. Not. IMRN 2018, no. 24 (2018), 7555--7605.
• Monotonicity of average return probabilities for random walks in random environments, Contemp. Math. 719 (2018), 1--9.
• Determinantal probability: basic properties and conjectures, Proc. International Congress of Mathematicians 2014, Seoul, Korea, vol. IV, 137--161.
• Errata to "Distance covariance in metric spaces", Ann. Probab. 46, no. 4 (2018), 2400--2405.
• Second errata to "Distance covariance in metric spaces", Ann. Probab. 49, No. 5 (2021), 2668--2670.
• (with Kevin Zumbrun) A calculus proof of the Cramér-Wold theorem, Proc. Amer. Math. Soc. 146, no. 3 (2018), 1331--1334.
• Errata to "Factors of IID on trees", Combin. Probab. Comput. 26, no. 2 (2017), 285--300.
• Hyperbolic space has strong negative type, Illinois J. Math. 58, no. 4 (2014), 1009--1013.
• (with Fedor Nazarov) Perfect matchings as IID factors on non-amenable groups, Europ. J. Combin. 32 (2011), 1115--1125.
• Identities and inequalities for tree entropy, Combin. Probab. Comput. 19, no. 2 (2010), 303--313.
• Random complexes and l²-Betti numbers, J. Topology Anal. 1, no. 2 (2009), 153--175.
• (with Mikaël Pichot and Stéphane Vassout) Uniform non-amenability, cost, and the first l²-Betti number, Geometry, Groups, and Dynamics 2 (2008), 595--617.
• (with Benjamin J. Morris and Oded Schramm) Ends in uniform spanning forests, Electr. J. Probab. 13, Paper 58 (2008), 1701--1725.
• (with David Aldous) Errata to "Processes on unimodular random networks", Electron. J. Probab. 22 (2017), paper no. 51, 4 pp.
• (with David Aldous) Second errata to "Processes on unimodular random networks", Electron. J. Probab. 24 (2019), paper no. 25, 1--2.
• (with Yuval Peres and Oded Schramm) Minimal spanning forests, Ann. Probab. 34, no. 5 (2006), 1665--1692.
• Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005), 491--522.
• Szegő limit theorems, Geom. Funct. Anal. 13 (2003), 574--590.
• (with Jessica L. Felker) High-precision entropy values for spanning trees in lattices, J. Phys. A. 36 (2003), 8361--8365.
• Determinantal probability measures, Publ. Math. Inst. Hautes Études Sci. 98 (2003), 167--212.
• (with Itai Benjamini, Yuval Peres and Oded Schramm) Uniform spanning forests, Ann. Probab. 29, no. 1 (2001), 1--65.
• Phase transitions on nonamenable graphs, J. Math. Phys. 41 (2000), 1099--1126.
• (with Oded Schramm) Indistinguishability of percolation clusters, Ann. Probab. 27 (1999), 1809--1836.
• (with Oded Schramm) Stationary measures for random walks in a random environment with random scenery, New York J. Math. 5 (1999), 107--113.
• (with Itai Benjamini, Yuval Peres, and Oded Schramm) Group-invariant percolation on graphs, Geom. Funct. Anal. 9 (1999), 29--66.
• (with Michael Larsen) Coalescing particles on an interval, J. Theoret. Probab. 12 (1999), 201--205.
• A simple path to Biggins' martingale convergence for branching random walk, in Classical and Modern Branching Processes, K. Athreya and P. Jagers (editors), Springer, New York, 1997, pp. 217--222.
• (with Thomas G. Kurtz, Robin Pemantle, and Yuval Peres) A conceptual proof of the Kesten-Stigum theorem for multi-type branching processes in Classical and Modern Branching Processes, K. Athreya and P. Jagers (editors), Springer, New York, 1997, pp. 181--186.
• (with Robin Pemantle and Yuval Peres) Unsolved problems concerning random walks on trees, Classical and Modern Branching Processes, K. Athreya and P. Jagers (editors), Springer, New York, 1997, pp. 223--238.
• Diffusions and random shadows on negatively-curved manifolds, J. Functional Anal. 138 (1996), 426--448.
• (with Robin Pemantle and Yuval Peres) Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure, Ergodic Theory Dynamical Systems 15 (1995), 593--619.
• (with Robin Pemantle and Yuval Peres) Conceptual proofs of $L \log L$ criteria for mean behavior of branching processes, Ann. Probab. 23 (1995), 1125--1138.
• Random walks, capacity, and percolation on trees, Ann. Probab. 20 (1992), 2043--2088.
• (with Robin Pemantle) Correction to: Random walk in a random environment and first-passage percolation on trees, Ann. Probab. 20 (1992), 125--136, published as Ann. Probab. 31 (2003), 528--529. Note: one more correction is that we mistakenly omitted the assumption that the environments at the vertices are independent.
• Amenability, Kazhdan's property and percolation for trees, groups and equivalence relations, Israel J. Math. 75 (1991), 341--370.
• Random walks and percolation on trees, Ann. Probab. 18 (1990), 931--958.
• Strong laws of large numbers for weakly correlated random variables, Mich. Math. J. 35 (1988), 353--359.
• A new type of sets of uniqueness, Duke Math. J. 57 (1988), 431--458.
• Errata to "Wiener's theorem, the Radon-Nikodym theorem, and M₀(T)", Arkiv för Mat. 26 (1988), 165--166.
• Erratum to "Measure-Theoretic Quantifiers and Haar Measure", Proc. Amer. Math. Soc. 91 No. 2, (1984), 329--330.

Coauthors:

Matteo D'Achille, Scot Adams, David Aldous, Alano Ancona, Omer Angel, Itai Benjamini, Lewis Bowen, Nicolas Curien, Nathanael Enriquëz, Jessica Felker, Damien Gaboriau, Ori Gurel-Gurevich, Olle Häggström, Deborah Heicklen, Nina Holden, Ander Holroyd, Yiping Hu, Nicholas James, Antal A. Járai, Johan Jonasson, Chris Judge, Alexander S. Kechris, Thomas G. Kurtz, Michael Larsen, Avinoam Mann, Benjamin J. Morris, Fedja Nazarov, Shayan Oveis Gharan, Peter Paule, Ron Peled, Robin Pemantle, Yuval Peres, Mikaël Pichot, Charles Radin, Axel Riese, Oded Schramm, Terry Soo, Jeff Steif, Xin Sun, Pengfei Tang, Romain Tessera, Andreas Thom, Matthew Tointon, Meltem Ünel, Stéphane Vassout, Graham White, Peter Winkler, Alex Zhai, Tianyi Zheng, Kevin Zumbrun.

Journal Prices:

Some journals are too expensive; see Kirby's article for detailed information. I support his suggested boycott of the most expensive journals, meaning that I will not submit to them, referee for them, nor be an editor for them. I hope that you will boycott them too. For somewhat old price information, see the spreadsheet by Ulf Rehmann. For similar efforts and discussion, see Gower's blog on Elsevier and a list to sign to indicate your support for Gower's boycott of Elsevier. I also boycott open access journals with high charges for article publishing. For information about this, see here for fair charges and the "AMS Primer on Open Access" for an interesting discussion of the issues.

Address:

Department of Mathematics
Indiana University
831 East 3rd St.
Bloomington, IN 47405-7106
USA
Tel.: 812-855-1645
Fax: 812-855-0046

Email Address:

rdlyons@iu.edu (My old address, rdlyons@indiana.edu, will no longer work after 31 Dec. 2025.)

Another photo album of the IUB campus, taken by me.