(with Fedor Nazarov)
Perfect matchings as IID factors on non-amenable groups,
preprint.
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 20 Aug. 2009]
(with Alexander E. Holroyd and Terry Soo)
Poisson splitting by factors,
preprint.
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 {\em 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 {\em 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.
[Version of 21 Aug. 2009]
Random complexes and $\ell^2$-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 17 May 2009]
Identities and inequalities for tree entropy,
Combin. Probab. Comput., to appear.
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.
[Version of 15 Aug. 2009]
(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]
(with Mikaël Pichot and Stéphane Vassout) Uniform
non-amenability, cost,
and the first l2-Betti number,
Geometry, Groups, and
Dynamics2 (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 Antal A. Járai) Ladder sandpiles,
Markov Proc. Rel. Fields13 (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 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 7 Oct. 2009; note that Proposition 4.9 was inadvertently
changed by the publisher to Theorem 4.9]
(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]
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 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]
(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 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]
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. A86 (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 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 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.
(or gzipped version)
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.
(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.
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.
[JSTOR link]
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.
[JSTOR link]
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\'ym 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]
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_0, the sets of uniqueness in the wide sense, the
corresponding family of annihilating measures always includes M_0(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]
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]
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.
[JSTOR link]
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.
To sign a statement, visit the Banff Protocol page.
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."
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."
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).
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."
And the fish on the dinner plate?
"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."
Now they require future whistle blowers "not [to]
reveal this information to third parties
or the media while the investigation is under way". 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.