Russell Lyons
Course notes on stochastic calculus (following Jean-François Le Gall's
textbook, Brownian Motion, Martingales, and Stochastic
Calculus).
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:
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 l2-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 l2-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
M0(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 19 May 2024]
-
(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]
-
(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]
-
(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]
-
(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]
-
(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]
-
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]
-
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]
-
(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]
-
(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]
-
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:
-
(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]
-
(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 l2-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 P2 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]
-
(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]
-
(with Mikaël Pichot and Stéphane Vassout) Uniform
non-amenability, cost,
and the first l2-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]
-
(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]
-
(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]
-
(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]
-
(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]
-
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]
-
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]
-
(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]
-
(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]
-
(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]
-
(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]
-
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]
-
(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$)?
-
(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]
-
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]
-
(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]
-
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]
-
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]
-
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.
-
(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]
-
(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.
-
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]
-
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]
-
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]
-
(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 U0, the sets of uniqueness in the wide
sense, the corresponding family of annihilating measures always includes
M0(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 U0-set is almost a W-set.
-
Wiener's theorem, the Radon-Nikodym theorem, and
M0(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.
-
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]
- 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
M0(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.
-
(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 l2-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 l2-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
M0(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.
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.
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.
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.)
Photos:
A
photo album, with photos courtesy of Indiana University.
Use the slide show available under the three-dots menu on the top right,
which will go full screen.
Another photo album
of the IUB campus, taken by me.