Russell Lyons

Contents of This Site:

This video is best listened to on headphones. For more information on it, visit Random Walk Demonstrations.

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

Course Notes

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

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:

Note that often the electronic versions of papers here fix errors that are noted after publication. Those errors are listed separately in the errata section.

Titles:

(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
The size of some classes of thin sets
On the structure of sets of uniqueness
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
E2691
E2573

Abstracts and Links:

(with Itai Benjamini and Oded Schramm) Unimodular random trees, Ergodic Theory Dynamical Systems, to appear.
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. [Version of 13 May 2013]
(with Omer Angel and Alexander S. Kechris) Random orderings and unique ergodicity of automorphism groups, J. Europ. Math. Soc., to appear.
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. [Version of 19 Nov. 2012]
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., to appear.
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. [Version of 21 Feb. 2013]
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
(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 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 11 July 2011] Click here for a sample of the matroidal measure P₂ in a 3x3x3 cube.
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]
- 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]
(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 2 Aug. 2012; 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 9 June 2003]
(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 17 Nov. 2003]
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.
(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. (or gzipped version)
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$. [Version of 4 Nov. 1999]
(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. (or gzipped version)
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. (or gzipped version)
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. (or gzipped version)
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.
(with Robin Pemantle and Yuval Peres) Biased random walks on Galton-Watson trees, Probab. Theory Relat. Fields 106 (1996), 249--264. (or gzipped version)
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 gzipped 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.
(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. (or gzipped version)
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.
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. (or gzipped version)
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. (or gzipped version)
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.
(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$. [Project Euclid link]
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.
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₀ 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₀' is indeed a basis, and unify the theory with that for U-sets and U₁-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₂, which lies strictly between the U₁-sets and the U₀-sets. They too can be written as countable unions of special U₂-sets called U₂'-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.
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.
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.
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.
Wiener's theorem, the Radon-Nikodym theorem, and M₀(T), Arkiv för Mat. 24 (1986), 277--282; Errata, ibid. 26 (1988), 165--166. Publisher link and publisher link.
On measures simultaneously 2- and 3-invariant, Israel J. Math. 61 (1988), 219--224. Publisher link.
Mixing and asymptotic distribution modulo 1, Ergodic Theory Dynamical Systems 8 (1988), 597--619. 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.

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

Coauthors:

Scot Adams, David Aldous, Alano Ancona, Omer Angel, Itai Benjamini, Lewis Bowen, Damien Gaboriau, Ori Gurel-Gurevich, Olle Häggström, Deborah Heicklen, Ander Holroyd, Nicholas James, Antal A. Járai, Johan Jonasson, Alexander S. Kechris, Thomas G. Kurtz, Michael Larsen, Benjamin J. Morris, Fedja Nazarov, Peter Paule, Ron Peled, Robin Pemantle, Yuval Peres, Mikaël Pichot, Charles Radin, Axel Riese, Oded Schramm, Terry Soo, Jeff Steif, Stéphane Vassout, Peter Winkler, 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 more recent price information, see the AMS survey. This data is nicely organized by Ulf Rehmann. One can also search at http://www.journalprices.com/. 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.

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@indiana.edu

Photos:

Click on the ones for Campus and Bloomington at this link.

IUB virtual tour

Amazing Factoids:

A 2001 survey of U.S. American adults says that 14% of men and 34% of women believe that the sun goes around the earth and not v.v.; and that 34% of men and 58% of women do not know that it takes one year for the earth to go around the sun. Is this reliable? It was done for the National Science Foundation, so one hopes so. The method was random-digit dialing by telephone, which sounds good. But the response rate was only 39% with the highly educated overrepresented. See footnote 1 for this. It is not stated whether any corrections to the data were done to compensate. The wordings were: "Does the Earth go around the Sun, or does the Sun go around the Earth?" "How long does it take for the Earth to go around the Sun: one day, one month, or one year?"
Actual quote: "We want to increase the value of academic excellence people are paying for," said Neil Theobald, vice chancellor for budget and administration at Indiana University, concerning the new $1000 fee for undergraduates. (See Indiana Daily Student, p. 1, Sep. 4, 2002, also at http://idsnews.com.)
On 12 Aug. 2005, there were many stories about the haze in Malaysia. Since 1997, the actual air quality figures have been a state secret for fear of keeping away tourists.
There have been many stories about bird flu recently. In The Washington Post on 20 Oct. 2005 in an article entitled "Indonesia Neglected Bird Flu Until Too Late, Experts Say", we read that "In an interview with The Washington Post this spring, Tri Satya Putri Naipospos, Indonesia's national director of animal health, first disclosed that officials had known chickens were dying from bird flu since the middle of 2003 but kept this secret until last year because of lobbying by the poultry industry. ... the owners of major poultry companies, who have personal ties to senior Agriculture Ministry officials, insisted that any containment efforts be done secretly, Naipospos recalled. These eight farming conglomerates, which handle 60 percent of the country's poultry, feared that publicity would harm sales of chicken and eggs."
A recent survey of US adults found that 42% believe that "living things have existed in their present form since the beginning of time". The question was asked after questions on religious belief. The wording was "Some people think that humans and other living things [have evolved over time]. Others think that humans and other living things [have existed in their present form since the beginning of time]. Which of these comes closest to your view?", with the two possibilities in brackets given in each order to half the respondents. The margin of error was 2.5% and the polling was done in July 2005.
Scott Hensley and Barbara Martinez of the Wall Street Journal reported on 15 July 2005 that "In 2004, 237,000 meetings and talks sponsored by pharmaceutical companies featured doctors as speakers, compared with 134,000 meetings led by company sales representatives, according to market researcher Verispan LLC of Yardley, Pa." Also, "[t]he industry [has] nearly 100,000 salespeople in the U.S." A copy of the article can be found here.
U.S. military trainers at Guantánamo Bay based an entire interrogation class in December 2002 on a chart from a 1957 article entitled "Communist Attempts to Elicit False Confessions From Air Force Prisoners of War". The trainers did not disclose their source and may not have known it. See The New York Times, 2 July 2008. For more information on how these techniques came to be used by the CIA without knowing their origin, see The New York Times, 22 April 2009.
"Determining how often, if ever, blood supplied by the Red Cross has been responsible for serious health problems is difficult. F.D.A. documents rarely spell out the consequences of the failures they catalogue, a reflection, to some degree, of the agency's concern about alarming the public. But often they simply do not know. 'Patients who get blood transfusions tend to be pretty sick,' Dr. Healy said. 'If they spike a fever post-transfusion, no one is likely to suspect that the blood caused it.'" See The New York Times, 17 July 2008.
When Christopher Columbus landed in the Bahama Islands, the native Arawak people came to greet him and his sailors. Columbus wrote (somewhat contradictorily): "They ... brought us parrots and balls of cotton and spears and many other things, which they exchanged for the glass beads and hawks' bells. They willingly traded everything they owned .... They were well-built, with good bodies and handsome features .... They do not bear arms, and do not know them, for I showed them a sword, they took it by the edge and cut themselves out of ignorance. They have no iron. Their spears are made of cane .... They would make fine servants .... With fifty men we could subjugate them all and make them do whatever we want." This is quoted at the beginning of Howard Zinn's book, "A People's History of the United States", but I don't know the source or the translator of Columbus' log.
At the top of the page of a UN report, it says "The livestock sector emerges as one of the top two or three most significant contributors to the most serious environmental problems, at every scale from local to global. The findings of this report suggest that it should be a major policy focus when dealing with problems of land degradation, climate change and air pollution, water shortage and water pollution, and loss of biodiversity. Livestock's contribution to environmental problems is on a massive scale and its potential contribution to their solution is equally large. The impact is so significant that it needs to be addressed with urgency." What amazes me is that the UN wrote this. It does not amaze me that it is pretty much ignored. Recently, however, to my surprise, Sweden has begun to pay attention: see The New York Times, To Cut Global Warming, Swedes Study Their Plates, 23 Oct. 2009. For a more recent estimate of greenhouse gases attributable to livestock (at least 51%---a rather amazing figure), see Livestock and Climate Change by the Worldwatch Institute, written by Goodland and Anhang. Who are they? "Robert Goodland retired as lead environmental adviser at the World Bank Group after serving there for 23 years. In 2008 he was awarded the first Coolidge Memorial Medal by the IUCN for outstanding contributions to environmental conservation. Jeff Anhang is a research officer and environmental specialist at the World Bank Group's International Finance Corporation, which provides private-sector financing and advice in developing countries." It is also amazing that this latter study was cited by Bill Gates.
Fresh water will soon run out in the country of Yemen. It turns out that "[a]t least two-thirds of Yemen's water consumption" is for growing khat, a mild narcotic. In addition, the population growth rate is 4.5% a year and "[t]he government subsidizes the exploitation of water for khat and other agriculture". "The country's first water minister was removed a couple of years ago from his post for trying to outlaw wildcatters drilling for water wherever they pleased." See The Los Angeles Times, 3 August 2008. More on the sad history is at The New York Times, 1 Nov. 2009, where one of the causes of the problem is identified as "cheap foreign grain" in the 1960s.
"The F.B.I. director, Robert S. Mueller III, in his first public comments since the presentation of the evidence against Dr. Ivins on Wednesday, said Friday that he was proud of the inquiry [about the anthrax mailings]. 'I do not apologize for any aspect of the investigation,' he told reporters. It is erroneous, he added, 'to say there were mistakes.'" See The New York Times, 10 Aug. 2008.
It turns out that manufacturers of seeds that produce genetically modified crops require purchasers to agree not to perform any research on those seeds without prior permission. For example, according to The New York Times, 19 Feb. 2009, "The growers' agreement from Syngenta not only prohibits research in general but specifically says a seed buyer cannot compare Syngenta's product with any rival crop." Such problems led 26 corn-insect specialists to complain to the EPA that " no truly independent research can be legally conducted on many critical questions". At the same time, some believe that genetically modified crop production has actually caused an increase in pesticide use (see also the UCS report, "Failure to Yield"). In 2008, 96% of Indiana's soybeans were genetically modified. Most genetically-modified soybeans are resistant to the herbicide glyphosate, marketed as Roundup by Monsanto. If a farmer uses Monsanto's seeds, he is required to use Monsanto's glyphosate, not a generic version of it (see p. 14 of Behind the Bean by the Cornucopia Institute). For an update on the spread of glyphosate-resistant weeds, see U.S. Farmers Cope With Roundup-Resistant Weeds in The New York Times, 4 May 2010.
The EPA and the Ad Council created an "award winning public service announcement (PSA), `I Feel Like a Fish With No Water.'" (EPA) They covered the country with billboards, print ads, and radio and TV ads. You can see a print version at noattacks.org and the video at metacafe.com or noattacks.org. The PSA had some success: "What does an asthma attack feel like? After doing a lot research and finding explanation after explanation I finally heard the perfect description. Asthma feels like a fish out of water. Now use your imagination a little and you'll be able to identify with both the terror and physical pain associated with asthma attacks." (Owen Walcher) Amazingly, according to the creators, "No fish were harmed during the making of this public service announcement. Fish handlers were present at all times during the shoot to manage the care and well being of the fish on hand." I wonder what they had for dinner.
"The Federal Aviation Administration is proposing to keep secret from travelers its vast records on where and how often commercial planes are damaged by hitting flying birds. The government agency argued that some carriers and airports would stop reporting incidents for fear the public would misinterpret the data and hold it against them. The reporting is voluntary because the FAA rejected a National Transportation Safety Board recommendation 10 years ago to make it mandatory." This is from an AP story of 28 March 2009.
In May 2008, JAMA published a study in which the authors failed to disclose all conflicts of financial interest. When an outsider, Dr. Leo, told JAMA about it, he heard nothing for 5 months, whereupon he published a letter about it (as well as other statistical problems with the study and its media coverage) online at the British Medical Journal. This upset JAMA greatly, who called Leo to inform him "that, if his actions represented his apparent lack of confidence in and regard for JAMA, he certainly should not plan to submit future manuscripts or letters for publication." JAMA even "felt an obligation to notify the dean of his institution about our concerns of how Leo's actions were potentially damaging to JAMA's reputation." According to this dean, the JAMA editor said "she would 'ruin the reputation of our medical school' if he didn't force Dr. Leo to retract the BMJ letter and stop talking to the media."
For a time, JAMA required future whistle blowers "not [to] reveal this information to third parties or the media while the investigation is under way", but they mollified this in response to criticism and removed all traces of their original editorial, some of which can still be found here. For Leo's story, see the WSJ. JAMA maintains that it "did not threaten Leo or anyone at the school."
"Having a family had been an elusive goal for Jeff and Kerry Mastera, a blur of more than two years, dozens of doctor visits and four tries with a procedure called intrauterine insemination, all failures. In one year, the Masteras spent 23 percent of their income on fertility treatments.
"The couple had nearly given up, but last year they decided to try once more, this time through in-vitro fertilization. Pregnancy quickly followed, as did the Mastera boys, who arrived at the Swedish Medical Center in Denver on Feb. 16 at 3 pounds, 1 ounce apiece. Kept alive in a neonatal intensive care unit, Max remained in the hospital 43 days; Wes came home in 51.
"By the time it was over, medical bills for the boys exceeded $1.2 million.
"Eight months later, the extraordinary effort seems worth it to the Masteras, who live in Aurora, Colo."
The Masteras are a middle-class family. This story is from The New York Times, 11 Oct. 2009.
The US "intercepted phone calls of Al Haramain, a now-defunct Islamic charity in Oregon, and of two lawyers representing it in 2004." The charity sued, but the US said that "the charity's lawsuit should be dismissed without a ruling on the merits because allowing it to go forward could reveal state secrets." The charity knew of the illegal surveillance because "the government inadvertently disclosed a classified document that made clear that the charity had been subjected to surveillance without warrants.
"Although the plaintiffs in the Haramain case were not allowed to use the document to prove that they had standing, Mr. Eisenberg and six other lawyers working on the case were able to use public information ... to prove it had been wiretapped." The judge ruled in favor of the charity. See The New York Times, 1 April 2010.
On the other hand, on 8 Sep. 2010, "A federal appeals court ... ruled that former prisoners of the C.I.A. could not sue over their alleged torture in overseas prisons because such a lawsuit might expose secret government information." The plaintiffs had sued "Jeppesen Dataplan Inc., a Boeing subsidiary" for "arranging flights for the Central Intelligence Agency to transfer prisoners to other countries for imprisonment and interrogation." See The New York Times, 9 Sep. 2010 for this. The judges cited precedent going back to an 1876 Supreme Court case, Totten v. United States, "where the estate of a Civil War spy sued the United States for breaching an alleged agreement to compensate the spy for his wartime espionage services. ... [T]he Court held that the action was barred because it was premised on the existence of a 'contract for secret services with the government,' which was 'a fact not to be disclosed'." See this for the ruling.
People "harvest" a lot of shrimp in the Gulf of Mexico. In order to avoid catching and drowning a lot of sea turtles (critically endangered in part because of this industry), the federal government passed laws requiring nets to have devices that allow turtles to escape. "The devices are so contentious that Louisiana law has long forbidden its wildlife and fisheries agents to enforce federal regulations on the devices," according to The New York Times, 15 July 2010. "By contrast, Mississippi officials strengthened turtle protections by decreasing the allowable tow time for skimmers, posting observers on boats, and sending out pamphlets on turtle resuscitation."
In 2009, the Pew Research Center conducted a poll in the US asking adults, "Do you believe in astrology, or that the position of the stars and planets can affect people's lives?" The percent of Republicans who answered yes was 14, of Independents was 26, and of Democrats was 31. The margin of error was not reported for these subgroups of the sample, but seems to be around 4%.
As the U.S. government prepares for shutting down, The New York Times reports on 6 April 2011: "The chairman of the Committee on House Administration, Representative Dan Lungren, Republican of California, sent detailed guidance on Tuesday to all House members and offices on what they could and could not do during a government shutdown.
"A sample letter he provided warned: `Working in any way during a period of furlough, even as a volunteer, is grounds for disciplinary action, up to and including termination of employment. To avoid violating this prohibition, we strongly recommend that you turn your BlackBerries off for the duration of the furlough.'"
The American Society of Hypertension, Inc. (ASH) does not want to disclose the financial ties its board members have to industry. If you want to find out, you must be a current member of the Society and it is subject to these rules: "(a) a representation in writing is made that any such requests are in good faith and not made for a purpose which is in the interest of a business or object other than the business or object of the Society, or for any purpose to harm the Society or the person(s) whose disclosure(s) are requested, and (b) submission of a signed confidentiality statement". The disclosure form (the object of such a request) asks the respondent to agree or disagree with various statements, such as "Activity content, including presentation of therapeutic options, will be well balanced, evidence-based and unbiased" and "The recommendations that I provide involving clinical medicine will be based on evidence that is accepted within the profession of medicine as adequate justification for their indications and contraindications in the care of patients."
"I never dreamed that my discovery four decades ago would lead to such a profit-driven public health disaster." So wrote the discoverer of prostate-specific antigen (basis of the P.S.A. test).
Marion Nestle, the editor of The Surgeon General's Report on Nutrition and Health (1998), wrote in her book Food Politics that "My first day on the job, I was given the rules: No matter what the research indicated, the report could not recommend `eat less meat' as a way to reduce intake of saturated fat, nor could it suggest restrictions on intake of any other category of food. In the industry-friendly climate of the Reagan administration, the producers of foods that might be affected by such advice would complain to their beneficiaries in Congress, and the report would never be published."
"At least 15 drug and medical-device companies have paid $6.5 billion since 2008 to settle accusations of marketing fraud or kickbacks. However, none of the more than 75 doctors named as participants were sanctioned, despite allegations of fraud or of conduct that put patients at risk", according to Pro Publica, 16 Sep. 2011.
It is hard to shock me now with accounts of misdeeds among doctors, pharmaceutical companies, or medical journals, but the tales of Peter Wilmshurst have so many shocking aspects that I won't even summarize them here. Fortunately, he won an award for his efforts. See also this article for even more sordid details, and this account of being sued.
On 13 Jan. 2012, the Republican National Committee (RNC) passed some resolutions. One commends Israel, stating, e.g., "Israel has been granted her lands under and through the oldest recorded deed as reported in the Old Testament, a tome of scripture held sacred and reverenced by Jew and Christian, alike, as the acts and words of God" and "God has never rescinded his grant of said lands". Another resolution "exposed" United Nations Agenda 21, a non-binding plan for "sustainable development" signed by Pres. George H.W. Bush in 1992. Now, the RNC says that it is "a comprehensive plan of extreme environmentalism, social engineering, and global political control" which "views the American way of life of private property ownership, single family homes, private car ownership and individual travel choices, and privately owned farms; all as destructive to the environment".
On 2 Oct. 2011, France required that all school meals be based on animal products. It defined the protein component of a meal as one based on meat, fish, eggs, offal, or cheese ("plat principal à base de viandes, poissons, oeufs, abats ou fromages"), requiring a certain number of meals to be based on meat or fish. Apparently this is to support French agriculture against the likes of Paul McCartney, who called for one day a week without meat.
The following 3 paragraphs come from the 29 Oct. 2012 New York Times:
"It's about sustainability, and I've been a vegetarian for three years, but I'm excited to eat Bill and Lou," said Lisa Wilson, a senior. "I eat meat when I know where it comes from."
Andrew Kohler, a senior, took a course in which he learned how to drive the oxen team.
"They start listening to you, and they become your friend," Mr. Kohler said. "I feel honored to eat them."
"State and federal authorities decided against indicting HSBC in a money-laundering case over concerns that criminal charges could jeopardize one of the world's largest banks and ultimately destabilize the global financial system." For details, see the 10 Dec. 2012 New York Times.
Dairy farmers are compelled to pay for federal advertising of milk and milk products. This fee is known as the "dairy checkoff". As the dairy checkoff organization says, the purpose is to "drive increased sales of and demand for dairy products and ingredients." Among the ways they do this is to work "to unite the industry in communicating about dairy-related topics that may affect consumer confidence in U.S. dairy: animal care, environmental stewardship, innovation, food safety, value to the community, and health and wellness." In order to "protect and promote the image of dairy products, producers and the industry[, ...] [t]hey also develop and deploy crisis communications planning, including regional crisis drills that engage many sectors of the dairy industry." Some independent farmers objected to the fee, but they lost their lawsuit. There are many other checkoffs; the one for beef is being contested.

"A single cigarette butt in a liter of water containing minnows is toxic enough to kill half of the fish within 96 hours, a standard toxicity test", according to a summary in the New York Times on 9 April 2013 concerning cigarette-butt litter.