The wreath product of Z with Z has Hilbert compression exponent 2 3 (2009)
Tim Austin, Assaf Naor, Yuval Peres
Let G be a finitely generated group, equipped with the word metric d associated with some finite set of generators. The Hilbert compression exponent of G is the supremum over all α ≥ 0 such that...
Random-turn Hex and other selection games (2009)
Yuval Peres, Oded Schramm, Scott Sheffield, David B. Wilson
Overview. The game of Hex, invented independently by Piet Hein in 1942 and John Nash in 1948 [9], has two players who take turns placing stones of their respective colors on the hexagons of a...
Harmonic maps on amenable groups and a diffusive lower bound for random walks (2009)
We prove that on any infinite, connected, locally finite, transitive graph G, the probability of the random walk being within $\eps \sqrt{t}$ of the origin after t steps is at most $O(\eps)$. A...
Convolutions of Cantor measures without resonance (2009)
Nazarov, Fedor, Peres, Yuval, Shmerkin, Pablo
Denote by $\mu_a$ the distribution of the random sum $(1-a) \sum_{j=0}^\infty \omega_j a^j$, where $P(\omega_j=0)=P(\omega_j=1)=1/2$ and all the choices are independent. For $0
Mixing time for the Ising model: a uniform lower bound for all graphs (2009)
Consider Glauber dynamics for the Ising model on a graph of $n$ vertices. Hayes and Sinclair showed that the mixing time for this dynamics is at least $n\log n/f(\Delta)$, where $\Delta$ is the...
Mixing time of near-critical random graphs (2009)
Ding, Jian, Lubetzky, Eyal, Peres, Yuval
Let $C_1$ be the largest component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$. The mixing time of random walk on $C_1$ in the strictly supercritical regime, $p=c/n$ with fixed $c>1$, was shown to...
A transient Markov chain with finitely many cutpoints (2009)
Nicholas James, Russell Lyons, Yuval Peres
Dedicated to David Freedman with admiration Abstract: We give an example of a transient reversible Markov chain that almost surely has only a finite number of cutpoints. We explain how this is...
Reconstruction on Trees: Exponential Moment Bounds for Linear Estimators (2009)
Consider a Markov chain $(\xi_v)_{v \in V} \in [k]^V$ on the infinite $b$-ary tree $T = (V,E)$ with irreducible edge transition matrix $M$, where $b \geq 2$, $k \geq 2$ and $[k] = \{1,...,k\}$. We...
Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks (2009)
Azar, Yossi, Birnbaum, Benjamin, Celis, L. Elisa, Devanur, Nikhil R., Peres, Yuval
Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and...
Heaviness in Toral Rotations (2009)
We investigate the dimension of the set of points in the d-torus which have the property that their orbit under rotation by some alpha hits a fixed closed target A more often than expected for all...
Anatomy of a young giant component in the random graph (2009)
Ding, Jian, Kim, Jeong Han, Lubetzky, Eyal, Peres, Yuval
We provide a complete description of the giant component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3...
Diameters in supercritical random graphs via first passage percolation (2009)
Ding, Jian, Kim, Jeong Han, Lubetzky, Eyal, Peres, Yuval
We study the diameter of $C_1$, the largest component of the Erd\H{o}s-R\'enyi random graph $\cG(n,p)$ emerging from the critical window, i.e., for $p = \frac{1+\epsilon}n$ where $\epsilon^3 n \to...
Convolutions of Cantor measures without resonance (2009)
Nazarov, Fedor, Peres, Yuval, Shmerkin, Pablo
Denote by $\mu_a$ the distribution of the random sum $(1-a) \sum_{j=0}^\infty \omega_j a^j$, where $P(\omega_j=0)=P(\omega_j=1)=1/2$ and all the choices are independent. For $0
Han, Guangyue, Marcus, Brian, Peres, Yuval
In this note, we show that small complex perturbations of positive matrices are contractions, with respect to a complex version of the Hilbert metric, on the standard complex simplex. We show that...
$L_p$ compression, traveling salesmen, and stable walks (2009)
We show that if $H$ is a group of polynomial growth whose growth rate is at least quadratic then the $L_p$ compression of the wreath product $\Z\bwr H$ equals $\max{\frac{1}{p},{1/2}}$. We also show...
ABSOLUTE CONTINUITY FOR RANDOM ITERATED FUNCTION SYSTEMS WITH OVERLAPS (2009)
Yuval Peres, Károly Simon, Boris Solomyak
Abstract. We consider linear iterated function systems with a random mul-tiplicative error on the real line. Our system is {x ↦ → di + λiY x} m i=1, where di ∈ R and λi> 0 are fixed and...
Fractals with Positive Length and Zero Buffon Needle Probability (2009)
Yuval Peres, Károly Simon, Boris Solomyak
polygonal approximation, is not useful for measuring the “length ” of more complicated sets. For a Borel (e.g., closed or open) subset F of R, the Lebesgue measure |F | of F,
Noise Tolerance of Expanders and Sublinear Expander Reconstruction (2009)
We consider the problem of online sublinear expander reconstruction and its relation to random walks in “noisy” expanders. Given access to an adjacency list representation of a bounded-degree...
Phase Transitions in Gravitational Allocation (2009)
Chatterjee, Sourav, Peled, Ron, Peres, Yuval, Romik, Dan
Given a Poisson point process of unit masses (``stars'') in dimension d>=3, Newtonian gravity partitions space into domains of attraction (cells) of equal volume. In earlier work, we showed the...
Thick Points of the Gaussian Free Field (2009)
Hu, Xiaoyu, Miller, Jason, Peres, Yuval
Let $U \subseteq \C$ be a bounded domain with smooth boundary and let $F$ be an instance of the continuum Gaussian free field on $U$ with respect to the Dirichlet inner product $\int_U \nabla f(x)...
Yuval Peres, For Scribing, Yun Long
revisions; Yelena Shvets for pictures and editing; Ranjit Samra of rojaysoriginalart.com for the lemon figure. Thanks also to Itamar Landau and Sithparran Vanniasegaram for corrections to an earlier...
Is the critical percolation probability local? (2009)
Benjamini, Itai, Nachmias, Asaf, Peres, Yuval
We show that the critical probability for percolation on a d-regular non-amenable graph of large girth is close to the critical probability for percolation on an infinite d-regular tree. This is a...
Mixing time of critical Ising model on trees is polynomial in the height (2009)
Ding, Jian, Lubetzky, Eyal, Peres, Yuval
In the heat-bath Glauber dynamics for the Ising model on the lattice, physicists believe that the spectral gap of the continuous-time chain exhibits the following behavior. For some critical...
Growth Rates and Explosions in Sandpiles (2009)
Fey, Anne, Levine, Lionel, Peres, Yuval
We study the abelian sandpile growth model, where n particles are added at the origin on a stable background configuration in Z^d. Any site with at least 2d particles then topples by sending one...
PROBABILITY THEORY AND EXAMPLES. 2nd edition (2008)
Eric Blair, Zhen-qing Chen, Ted Cox, Jan Hannig, Andrew Hayen, ...
spell checking I have found many more misspelled words. These and other small points of grammar have not been added to the list.
Bootstrap percolation on infinite trees and non-amenable groups (2008)
József Balogh, Yuval Peres, Gábor Pete
Abstract. Bootstrap percolation on an arbitrary graph has a random initial configu-ration, where each vertex is occupied with probability p, independently of each other, and a deterministic spreading...
A love and respect of trees has been characteristic of mankind since the beginning of human evolution. Instinctively, we understood the importance of trees to our lives before we were able to ascribe...
Censored Glauber Dynamics for the mean field Ising Model (2008)
Ding, Jian, Lubetzky, Eyal, Peres, Yuval
We study Glauber dynamics for the Ising model on the complete graph on $n$ vertices, known as the Curie-Weiss Model. It is well known that at high temperature ($\beta < 1$) the mixing time is...
Markov chain intersections and the loop-erased walk (2008)
Russell Lyons, Yuval Peres, Oded Schramm
Abstract. 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...
Abstract Maximum Overhang (extended abstract) ∗ (2008)
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
Finding Sparse Cuts Locally Using Evolving Sets (2008)
A {\em local graph partitioning algorithm} finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring part of a large graph $G$, starting from a specified vertex. For...
Biased tug-of-war, the biased infinity Laplacian, and comparison with exponential cones (2008)
Peres, Yuval, Pete, Gábor, Somersille, Stephanie
We prove that if U\subset\R^n is an open domain whose closure \overline{U} is compact in the path metric, and F is a Lipschitz function on \partial{U}, then for each \beta\in\R there exists a unique...
New coins from old, smoothly (2008)
Holtz, Olga, Nazarov, Fedor, Peres, Yuval
Given a (known) function $f:[0,1] \to (0,1)$, we consider the problem of simulating a coin with probability of heads $f(p)$ by tossing a coin with unknown heads probability $p$, as well as a fair...
The mixing time evolution of Glauber dynamics for the mean-field Ising model (2008)
Ding, Jian, Lubetzky, Eyal, Peres, Yuval
We consider Glauber dynamics for the Ising model on the complete graph on $n$ vertices, known as the Curie-Weiss model. It is well-known that the mixing-time in the high temperature regime ($\beta <...
doi:10.1112/plms/pdl018 UNIVERSAL FINITARY CODES WITH EXPONENTIAL TAILS (2008)
Nate Harvey, Alexander E. Holroyd, Yuval Peres, Dan Romik
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite-alphabet Bernoulli process to any other finite-alphabet Bernoulli process of strictly lower entropy. In...
Benjamini, Lyons and Schramm (1999) considered properties of an infinite graph G, and the simple random walk on it, that are preserved by random perturbations. To address problems raised by those...
Cover times for Brownian motion and (2008)
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
random walks in two dimensions
Let n be a positive integer, and 0 ≤ p ≤ 1. The Random Graph G(n, p) is a probability edges appear with space over the set of graphs on n vertices in which each of the possible � n 2...
Chip-Firing and Rotor-Routing on Directed Graphs (2008)
Holroyd, Alexander E., Levine, Lionel, Meszaros, Karola, Peres, Yuval, Propp, James, Wilson, David B.
We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several intriguing...
The power law for the Buffon needle probability of the four-corner Cantor set (2008)
Nazarov, Fedor, Peres, Yuval, Volberg, Alexander
Let $C_n$ be the $n$-th generation in the construction of the middle-half Cantor set. The Cartesian square $K_n$ of $C_n$ consists of $4^n$ squares of side-length $4^{-n}$. The chance that a long...
Total-variation cutoff in birth-and-death chains (2008)
Ding, Jian, Lubetzky, Eyal, Peres, Yuval
The cutoff phenomenon describes a case where a Markov chain exhibits a sharp transition in its convergence to stationarity. In 1996, Diaconis surveyed this phenomenon, and asked how one could...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2008)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Embeddings of Discrete Groups and the Speed of Random Walks (2008)
Let G be a group generated by a finite set S and equipped with the associated left-invariant word metric dG. For a Banach space X, let α*X(G) (respectively, α/#X(G)) be the supremum over all α ≥...
TUG-OF-WAR AND THE INFINITY LAPLACIAN (2008)
Yuval Peres, Oded Schramm, Scott Sheffield, B. Wilson
1.1. Overview. We consider a class of zero-sum two-player stochastic games called tug-of-war and use them to prove that every bounded real-valued Lipschitz function F on a subset Y of a length space...
Scaling Limits for Internal Aggregation Models with Multiple Sources (2007)
We study the scaling limits of three different aggregation models on Z^d: internal DLA, in which particles perform random walks until reaching an unoccupied site; the rotor-router model, in which...
Holroyd, Alexander E., Pemantle, Robin, Peres, Yuval, Schramm, Oded
Suppose that red and blue points occur as independent homogeneous Poisson processes in R^d. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For...
Levin, David A., Luczak, Malwina J., Peres, Yuval
We study the Glauber dynamics for the Ising model on the complete graph, also known as the Curie-Weiss Model. For beta < 1, we prove that the dynamics exhibits a cut-off: the distance to stationarity...
Kim, Jeong Han, Montenegro, Ravi, Peres, Yuval, Tetali, Prasad
We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a...
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let (x; r) denote the occupation measure of the ball of radius r centered at x for Brownian motion fW t g 0t1 in IR d; d 2. We prove that for any analytic set E in [0; 1], we have inf t2E lim inf r!0...
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm
Abstract. We study 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 (FSF) or...
Abstract. The distribution of the random series P (2007)
Yuval Peres, Wilhelm Schlag, Boris Solomyak
is the infinite convolution product
Elon Lindenstrauss, David Meiri, Yuval Peres, P N \gamma
Abstract. Given ergodic p-invariant measures f i g on the 1-torus T = R=Z, we give a sharp condition on their entropies, guaranteeing that the entropy of the convolution 1 \Delta \Delta \Delta n...
HOW LIKELY IS BUFFON'S NEEDLE TO FALL NEAR A PLANAR CANTOR SET? (2007)
Dedicated to the memory of Thomas H. Wol Abstract. Let be a compact planar set of positive nite one-dimensional Hausdor measure. Suppose that the intersection of with any rectiable curve has zero...
A Phase Transition in Random Coin Tossing (2007)
David A. Levin, Robin Pemantle, Yuval Peres, Are Singular, While If
this paper is organized as follows. In Section 2, we provide definitions and introduce notation. In Section 3, we prove a useful general zero-one law, to show that singularity and absolute continuity...
Yuval Peres, Jay Rosen, Ofer Zeitouni
this paper, log 2 stands for the logarithm to the base 2.
Dimitris Achlioptas, Yuval Peres
Let Fk (n, m) be a random k-SAT formula with n variables and m clauses selected uniformly and independently among all 2 k
Claire Kenyon, Elchanan Mossel, Yuval Peres
We study discrete time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show...
Path properties of Brownian Motion (2007)
and wrote the rst draft of the notes: Diego Garcia, Yoram Gat, Diogo A. Gomes, Charles
A phase transition in random coin tossing (2007)
A. Levin, Robin Pemantle, Yuval Peres
Suppose that a coin with bias θ is tossed at renewal times of a renewal process, and a fair coin is tossed at all other times. Let µθ be the distribution of the observed sequence of coin tosses,...
An Invitation to Sample Paths of Brownian Motion (2007)
and wrote the rst draft of the notes: Diego Garcia, Yoram Gat, Diogo A. Gomes, Charles
Abstract Draw planes in IR (2007)
Johan Jonasson, Elchanan Mossel, Yuval Peres
that are orthogonal to the x axis, and intersect the x axis at the points of a Poisson process with intensity ; similarly, draw planes orthogonal to the y and z axes using independent Poisson...
Where Did The Brownian Particle Go? (2007)
Robin Pemantle, Yuval Peres, Jim Pitman, Marc Yor
Consider the radial projection onto the unit sphere of the path a d-dimensional Brownian motion W, started at the center of the sphere and run for unit time. Given the occupation measure of this...
Amir Dembo, Yuval Peres, Ofer Zeitouni
Suppose that the integers are assigned i.i.d. random variables f! x g (taking values in the unit interval), which serve as an environment. This environment defines a random walk fX k g (called a...
Which properties of a random sequence are dynamically sensitive? (2007)
Itai Benjamini, Olle Haggstrom, Yuval Peres, Jeffrey E. Steif
Consider a sequence of i.i.d. random variables, where each variable is refreshed (i.e., replaced by an independent variable with the same law) independently, according to a Poisson clock. At any...
Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x; r) denote the total occupation measure of the ball of radius r centered at x for Brownian motion in IR 3. We prove that sup jxj1 T (x; r)=(r 2 j log rj) ! 16= 2 a.s. as r! 0, thus solving a...
Equivalence of positive Hausdorff measure and the open set condition for self--conformal sets (2007)
Yuval Peres, Micha L Rams, K Aroly Simon, Boris Solomyak, Let V R
Abstract. A compact set K is self-conformal if it is a nite union of its images by conformal contractions. It is well known that if the conformal contractions satisfy the \open set condition...
Abstract Draw planes in IR (2007)
Johan Jonasson, Elchanan Mossel, Yuval Peres
that are orthogonal to the x axis, and intersect the x axis at the points of a Poisson process with intensity; similarly, draw planes orthogonal to the y and z axes using independent Poisson...
Where Did The Brownian Particle Go? (2007)
Robin Pemantle Yuval, Yuval Peres, Jim Pitman, Marc Yor
Consider the radial projection onto the unit sphere of the path a d-dimensional Brownian motion W , started at the center of the sphere and run for unit time.
An Invitation to Sample (2007)
Paths Of Brownian, Yuval Peres, Elchanan Mossel, Yimin Xiao, Frédéric Latrémolière, Wei Li, ...
Contents Chapter 1. Brownian Motion 1 1. Motivation -- Intersection of Brownian paths 1 2. Gaussian random variables 1 3. Levy's construction of Brownian motion 4 4. Basic properties of Brownian...
Dynamical sensitivity of the infinite cluster in critical percolation (2007)
Peres, Yuval, Schramm, Oded, Steif, Jeffrey E.
In dynamical percolation, the status of every bond is refreshed according to an independent Poisson clock. For graphs which do not percolate at criticality, the dynamical sensitivity of this property...
The infinite valley for a recurrent random walk in random environment (2007)
Gantert, Nina, Peres, Yuval, Shi, Zhan
We consider a one-dimensional recurrent random walk in random environment (RWRE). We show that the - suitably centered - empirical distributions of the RWRE converge weakly to a certain limit law...
Embeddings of discrete groups and the speed of random walks (2007)
For a finitely generated group G and a banach space X let \alpha^*_X(G) (respectively \alpha^#_X(G)) be the supremum over all \alpha\ge 0 such that there exists a Lipschitz mapping (respectively an...
Card shuffling and diophantine approximation (2007)
Angel, Omer, Peres, Yuval, Wilson, David B.
The ``overlapping-cycles shuffle'' mixes a deck of $n$ cards by moving either the $n$th card or the $(n-k)$th card to the top of the deck, with probability half each. We determine the spectral gap...
Critical percolation on random regular graphs (2007)
We describe the component sizes in critical independent p-bond percolation on a random d-regular graph on n vertices, where d \geq 3 is fixed and n grows. We prove mean-field behavior around the...
Paterson, Mike, Peres, Yuval, Thorup, Mikkel, Winkler, Peter, Zwick, Uri
How far can a stack of $n$ identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
The wreath product of Z with Z has Hilbert compression exponent 2/3 (2007)
Austin, Tim, Naor, Assaf, Peres, Yuval
Let G be a finitely generated group, equipped with the word metric d associated with some finite set of generators. The Hilbert compression exponent of G is the supremum over all $\alpha\ge 0$ such...
A transient Markov chain with finitely many cutpoints (2007)
James, Nicholas, Lyons, Russell, Peres, Yuval
We give an example of a transient reversible Markov chain that almost surely has only a finite number of cutpoints. We explain how this is relevant to a conjecture of Diaconis and Freedman and a...
Trees and Markov convexity (2007)
Lee, James R., Naor, Assaf, Peres, Yuval
We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion....
Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation (2007)
Let ${n_k}$ be an increasing lacunary sequence, i.e., $n_{k+1}/n_k>1+r$ for some $r>0$. In 1987, P. Erdos asked for the chromatic number of a graph $G$ on the integers, where two integers $a,b$ are...
Resonance between Cantor sets (2007)
Let $C_a$ be the central Cantor set obtained by removing a central interval of length $1-2a$ from the unit interval, and continuing this process inductively on each of the remaining two intervals. We...
Strong Spherical Asymptotics for Rotor-Router Aggregation and the Divisible Sandpile (2007)
The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We prove that the asymptotic shape of this model is...
Universal finitary codes with exponential tails (2007)
Harvey, Nate, Holroyd, Alexander E., Peres, Yuval, Romik, Dan
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite-alphabet Bernoulli process to any other finite-alphabet Bernoulli process of strictly lower entropy. In...
Critical random graphs: Diameter and mixing time (2007)
Let $\mathcal{C}_1$ denote the largest connected component of the critical Erd\H{o}s--R\'{e}nyi random graph $G(n,{\frac{1}{n}})$. We show that, typically, the diameter of $\mathcal{C}_1$ is of order...
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
Embeddings of discrete groups and the speed of random walks (2007)
Let G be a group generated by a finite set S and equipped with the associated left-invariant word metric dG. For a Banach space X let α ∗ X (G) (respectively α # X (G)) be the supremum over all...
Asymptotically Dense Dilations of Sets on the Circle (2006)
Given an infinite closed subset A of the circle group T, we consider sequences of integers {nj} such that njA → T in the Hausdorff metric. We prove the existence of a sequence of squares possessing...
A Combinatorial Application of the Maximal Ergodic Theorem (2006)
Let X be a compact space,μ a Borel probability measure on X, T: X → X a measure preserving continuous transformation and g: X → R a continuous function. Then for some y∈X, $$\forall N\ge...
Gravitational allocation to Poisson points (2006)
Chatterjee, Sourav, Peled, Ron, Peres, Yuval, Romik, Dan
For d>=3, we construct a non-randomized, fair and translation-equivariant allocation of Lebesgue measure to the points of a standard Poisson point process in R^d, defined by allocating to each of the...
Component sizes of the random graph outside the scaling window (2006)
We provide simple proofs describing the behavior of the largest component of the Erdos-Renyi random graph G(n,p) outside of the scaling window, p={1+\eps(n) \over n} where \eps(n) tends to 0, but...
Minimal spanning forests (2006)
Minimal spanning forests on infinite graphs are weak limits of minimal spanning trees from finite subgraphs. These limits can be taken with free or wired boundary conditions and are denoted FMSF...
Transience of percolation clusters on wedges (2006)
Berger, Noam; University Of California, Los Angeles; Berger@math.ucla.edu, Benjamini, Itai; The Weizmann Institute; Itai@wisdom.weizmann.ac.il, Angel, Omer; University Of British Columbia; Angel@math.ubc.ca, Peres, Yuval; The University Of California, Berkeley; Peres@stat.berkeley.edu
We study random walks on supercritical percolation clusters on wedges in $Z^3$, and show that the infinite percolation cluster is (a.s.) transient whenever the wedge is transient. This solves a...
Tug of war with noise: a game theoretic view of the p-Laplacian (2006)
Peres, Yuval, Sheffield, Scott
Fix a bounded domain Omega in R^d, a continuous function F on the boundary of Omega, and constants epsilon>0, p>1, and q>1 with p^{-1} + q^{-1} = 1. For each x in Omega, let u^epsilon(x) be the value...
Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces (2006)
Naor, Assaf, Peres, Yuval, Schramm, Oded, Sheffield, Scott
A metric space $X$ has Markov-type $2$ if for any reversible finite-state Markov chain $\{Z_t\}$ (with $Z_0$ chosen according to the stationary distribution) and any map $f$ from the state space to...
A stable marriage of Poisson and Lebesgue (2006)
Hoffman, Christopher, Holroyd, Alexander E., Peres, Yuval
Let Ξ be a discrete set in ℝd. Call the elements of Ξ centers. The well-known Voronoi tessellation partitions ℝd into polyhedral regions (of varying sizes) by allocating each site of ℝd to...
A Central Limit Theorem for biased random walks on Galton-Watson trees (2006)
Let ${\cal T}$ be a rooted Galton-Watson tree with offspring distribution $\{p_k\}$ that has $p_0=0$, mean $m=\sum kp_k>1$ and exponential tails. Consider the $\lambda$-biased random walk...
Tug-of-war and the infinity Laplacian (2006)
Peres, Yuval, Schramm, Oded, Sheffield, Scott, Wilson, David B.
We prove that every bounded Lipschitz function F on a subset Y of a length space X admits a tautest extension to X, i.e., a unique Lipschitz extension u for which Lip_U u = Lip_{boundary of U} u for...
Late points for random walks in two dimensions (2006)
Dembo, Amir, Peres, Yuval, Rosen, Jay, Zeitouni, Ofer
Let $\mathcal{T}_{n}(x)$ denote the time of first visit of a point x on the lattice torus ℤn2=ℤ2/nℤ2 by the simple random walk. The size of the set of α, n-late points $\mathcal{L}_{n}(\alpha...
Determinantal Processes and Independence (2006)
Hough, J. Ben, Krishnapur, Manjunath, Peres, Yuval, Virág, Bálint
We give a probabilistic introduction to determinantal and permanental point processes. Determinantal processes arise in physics (fermions, eigenvalues of random matrices) and in combinatorics...
Sh67] L.A. Shepp. A first passage problem for the Wiener process. Ann. Math. Statist. 38, 1912--1914. [Sh98] Z. Shi. Windings of Brownian motion and random walks in the plane. Ann. Probab. 26...
A Central Limit Theorem for biased random walks on Galton-Watson trees (2006)
Let T be a rooted Galton-Watson tree with offspring distribution {pk} that has p0 = 0, mean m = P kpk> 1 and exponential tails. Consider the λ-biased random walk {Xn}n≥0 on T; this is the...
A Central Limit Theorem for biased random walks on Galton-Watson trees (2006)
Let T be a rooted Galton-Watson tree with offspring distribution {pk} that has p0 = 0, mean m = P kpk> 1 and exponential tails. Consider the λ-biased random walk {Xn}n≥0 on T; this is the...
Universal finitary codes with exponential tails (2006)
Harvey, Nate, Holroyd, Alexander E., Peres, Yuval, Romik, Dan
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite-alphabet Bernoulli process to any other finite-alphabet Bernoulli process of strictly lower entropy. In...
The critical random graph, with martingales (2005)
We give a short proof that the largest component of the random graph $G(n, 1/n)$ is of size approximately $n^{2/3}$. The proof gives explicit bounds for the probability that the ratio is very large...
Valleys and the maximum local time for random walk in random environment (2005)
Dembo, Amir, Gantert, Nina, Peres, Yuval, Shi, Zhan
Let $\xi(n, x)$ be the local time at $x$ for a recurrent one-dimensional random walk in random environment after $n$ steps, and consider the maximum $\xi^*(n) = \max_x \xi(n,x)$. It is known that...
Random-Turn Hex and other selection games (2005)
Peres, Yuval, Schramm, Oded, Sheffield, Scott, Wilson, David B.
The game of Hex has two players who take turns placing stones of their respective colors on the hexagons of a rhombus-shaped hexagonal grid. Black wins by completing a crossing between two opposite...
Tail Bounds for the Stable Marriage of Poisson and Lebesgue (2005)
Hoffman, Christopher, Holroyd, Alexander E., Peres, Yuval
Let \Xi be a discrete set in R^d. Call the elements of \Xi centers. The well-known Voronoi tessellation partitions R^d into polyhedral regions (of varying volumes) by allocating each site of R^d to...
Two new Markov order estimators (2005)
We present two new methods for estimating the order (memory depth) of a finite alphabet Markov chain from observation of a sample path. One method is based on entropy estimation via recurrence times...
A stable marriage of Poisson and Lebesgue (2005)
Hoffman, Christopher, Holroyd, Alexander E., Peres, Yuval
Let $\Xi$ be a discrete set in ${\mathbb{R}}^d$. Call the elements of $\Xi$ centers. The well-known Voronoi tessellation partitions ${\mathbb{R}}^d$ into polyhedral regions (of varying sizes) by...
Spherical Asymptotics for the Rotor-Router Model in Z^d (2005)
The rotor-router model is a deterministic analogue of random walk invented by Jim Propp. It can be used to define a deterministic aggregation model analogous to internal diffusion limited...
The critical Ising model on trees, concave recursions and nonlinear capacity (2005)
We consider the Ising model on a general tree under various boundary conditions: all plus, free and spin-glass. In each case, we determine when the root is influenced by the boundary values in the...
How large a disc is covered by a random walk in n steps? (2005)
Dembo, Amir, Peres, Yuval, Rosen, Jay
We show that the largest disc covered by a simple random walk (SRW) on $\mathbb{Z}^2$ after n steps has radius n^{1/4+o(1)}, thus resolving an open problem of R\'{e}v\'{e}sz [Random Walk in Random...
Determinantal Processes and Independence (2005)
Hough, J. Ben, Krishnapur, Manjunath, Peres, Yuval, Virág, Bálint
We give a probabilistic introduction to determinantal and permanental point processes. Determinantal processes arise in physics (fermions, eigenvalues of random matrices) and in combinatorics...
Universal finitary codes with exponential tails (2005)
Harvey, Nate, Holroyd, Alexander E., Peres, Yuval, Romik, Dan
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite-alphabet Bernoulli process to any other finite-alphabet Bernoulli process of strictly lower entropy. In...
Absolute continuity for random iterated function systems with overlaps (2005)
Peres, Yuval, Simon, Károly, Solomyak, Boris
We consider linear iterated function systems with a random multiplicative error on the real line. Our system is $\{x\mapsto d_i + \lambda_i Y x\}_{i=1}^m$, where $d_i\in \R$ and $\lambda_i>0$ are...
Fast simulation of new coins from old (2005)
Let S⊂(0,1). Given a known function f:S→(0,1), we consider the problem of using independent tosses of a coin with probability of heads p (where p∈S is unknown) to simulate a coin with...
Critical percolation on certain non-unimodular graphs (2005)
Peres, Yuval, Pete, Gabor, Scolnicov, Ariel
An important conjecture in percolation theory is that almost surely no infinite cluster exists in critical percolation on any transitive graph for which the critical probability is less than 1....
Extra heads and invariant allocations (2005)
Holroyd, Alexander E., Peres, Yuval
Let Π be an ergodic simple point process on ℝd and let Π* be its Palm version. Thorisson [Ann. Probab. 24 (1996) 2057–2064] proved that there exists a shift coupling of Π and Π*; that is, one...
Thoughts on noise and quantum computing (2005)
Gil Kalai, Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2005)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Mixing for Markov Chains and Spin Systems (2005)
Yuval Peres, Ra Kliem, Lionel Levine, Yun Long, Asaf Nachmias, Alex Skorokhod, ...
for help preparing these notes. These notes have not been subjected to the usual scrutiny reserved for formal publications. –Yuval Lecture 1: Introduction and total variation distance
Noise Stability of Weighted Majority (2004)
Benjamini, Kalai and Schramm (2001) showed that weighted majority functions of $n$ independent unbiased bits are uniformly stable under noise: when each bit is flipped with probability $\epsilon$,...
Minimal spanning forests (2004)
Lyons, Russell, Peres, Yuval, Schramm, Oded
Minimal spanning forests on infinite graphs are weak limits of minimal spanning trees from finite subgraphs. These limits can be taken with free or wired boundary conditions and are denoted FMSF...
Fluctuation of planar Brownian loop capturing large area (2004)
We consider a planar Brownian loop $B$ that is run for a time $T$ and conditioned on the event that its range encloses the unusually high area of $\pi T^2$, with $T$ being large. We study the...
Mixing Times for Random Walks on Finite Lamplighter Groups (2004)
Peres, Yuval; University Of California; Peres@stat.berkeley.edu, Revelle, David; University Of California; Revelle@stat.berkeley.edu
Given a finite graph G, a vertex of the lamplighter graph consists of a zero-one labeling of the vertices of G, and a marked vertex of G. For transitive graphs G, we show that, up to constants, the...
Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces (2004)
Naor, Assaf, Peres, Yuval, Schramm, Oded, Sheffield, Scott
A metric space $X$ has {\em Markov type} 2, if for any reversible finite-state Markov chain $\{Z_t\}$ (with $Z_0$ chosen according to the stationary distribution) and any map $f$ from the state space...
Scaling limits of the uniform spanning tree and loop-erased random walk on finite graphs (2004)
Let x and y be chosen uniformly in a graph G. We find the limiting distribution of the length of a loop-erased random walk from x to y on a large class of graphs that include the discrete torus in...
Anchored expansion, percolation and speed (2004)
Chen, Dayue, Peres, Yuval, Pete, Gábor
Benjamini, Lyons and Schramm [Random Walks and Discrete Potential Theory (1999) 56–84] considered properties of an infinite graph G, and the simple random walk on it, that are preserved by random...
An LIL for cover times of disks by planar random walk and Wiener sausage (2004)
Let R_n be the radius of the largest disk covered after n steps of a simple random walk. We prove that almost surely limsup_{n \to \infty}(log R_n)^2/(log n log_3 n) = 1/4, where log_3 denotes 3...
Cover times for Brownian motion and random walks in two dimensions (2004)
Dembo, Amir, Peres, Yuval, Rosen, Jay, Zeitouni, Ofer
Let $\TT(x,\eps)$ denote the first hitting time of the disc of radius $\eps$ centered at $x$ for Brownian motion on the two dimensional torus $\Bbb{T}^2$. We prove that $\sup_{x\in \Bbb{T}^2}...
Geometry of the uniform spanning forest: Transitions in dimensions 4, 8, 12,... (2004)
Benjamini, Itai, Kesten, Harry, Peres, Yuval, Schramm, Oded
The uniform spanning forest (USF) in $\Zd$ is the weak limit of random, uniformly chosen, spanning trees in $[-n,n]^d$. Pemantle proved that the USF consists a.s. of a single tree if and only if $d...
Recurrent Graphs where Two Independent Random Walks Collide Finitely Often (2004)
Krishnapur, Manjunath; University Of California At Berkeley, USA; Manju@stat.berkeley.edu, Peres, Yuval; University Of California At Berkeley, USA; Peres@stat.berkeley.edu
We present a class of graphs where simple random walk is recurrent, yet two independent walkers meet only finitely many times almost surely. In particular, the comb lattice, obtained from $Z^2$ by...
Recurrent graphs where two independent random walks collide finitely often (2004)
Krishnapur, Manjunath, Peres, Yuval
We present a class of graphs where simple random walk is recurrent, yet two independent walkers meet only finitely many times almost surely. In particular, the comb lattice, obtained from Z^2 by...
The sharp Hausdorff measure condition for length of projections (2004)
In a recent paper, Pertti Mattila asked which gauge functions $\phi$ have the property that for any planar Borel set $A$ with positive Hausdorff measure in gauge $\phi$, the projection of $A$ to...
Shuffling by semi-random transpositions (2004)
Mossel, Elchanan, Peres, Yuval, Sinclair, Alistair
In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the k'th card along the circle with a uniformly chosen random card. The problem of determining the...
Mixing times for random walks on finite lamplighter groups (2004)
Given a finite graph G, a vertex of the lamplighter graph consists of a zero-one labeling of the vertices of G, and a marked vertex of G. For transitive graphs G, we show that, up to constants, the...
Conceptual Proofs of L log L Criteria (2004)
Lyons, Russell, Pemantle, Robin, Peres, Yuval
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,...
Random Walks in Varying Dimensions (2004)
Benjamini, Itai, Pemantle, Robin, Peres, Yuval
We establish recurrence criteria for sums of independent random variables which take values in Euclidean lattices of varying dimension. In particular, we describe transient inhomogenous random walks...
On which graphs are all random walks in random environments transient? (2004)
An infinite graph G has the property that a random walk in random environment on G defined by i.i.d. resistances with any common distribution is almost surely transient, if and only if for some p
The trace of spatial Brownian motion is capacity-equivalent to the unit square (2004)
Pemantle, Robin, Peres, Yuval, Shapiro, Jonathan W.
We show that with probability 1, the trace B[0,1] of Brownian motion in space, has positive capacity with respect to exactly the same kernels as the unit square. More precisely, the energy of...
Non-amenable products are not treeable (2004)
Let X and Y be infinite graphs, such that the automorphism group of X is nonamenable, and the automorphism group of Y has an infinite orbit. We prove that there is no automorphism-invariant measure...
Where did the Brownian particle go? (2004)
Pemantle, Robin, Peres, Yuval, Pitman, Jim, Yor, Marc
Consider the radial projection onto the unit sphere of the path a d-dimensional Brownian motion W, started at the center of the sphere and run for unit time. Given the occupation measure mu of this...
A phase transition in random coin tossing (2004)
Levin, David A., Pemantle, Robin, Peres, Yuval
Suppose that a coin with bias theta is tossed at renewal times of a renewal process, and a fair coin is tossed at all other times. Let mu_\theta be the distribution of the observed sequence of coin...
What is the probability of intersecting the set of Brownian double points? (2004)
We give potential theoretic estimates for the probability that a set $A$ contains a double point of planar Brownian motion run for unit time. Unlike the probability for $A$ to intersect the range of...
Critical RWRE on trees and tree-indexed random walks (2004)
We study the behavior of Random Walk in Random Environment (RWRE) on trees in the critical case left open in previous work. Representing the random walk by an electrical network, we assume that the...
Domination Between Trees and Application to an Explosion Problem (2004)
We define a notion of stochastic domination between trees, where one tree dominates another if when the vertices of each are labeled with independent, identically distributed random variables, one...
Planar first-passage percolation times are not tight (2004)
We consider first-passage percolation on the two-dimensional integer lattice Z^2 with passage times that are IID exponentials of mean one. It has been conjectured, based on numerical evidence, that...
Galton-Watson Trees with the Same Mean Have the Same Polar Sets (2004)
Evans defines a notion of what it means for a set B to be polar for a process indexed by a tree. The main result herein is that a tree picked from a Galton-Watson measure whose offspring distribution...
Martin Capacity for Markov Chains (2004)
Benjamini, Itai, Pemantle, Robin, Peres, Yuval
The probability that a transient Markov chain, or a Brownian path, will ever visit a given set Lambda, is classically estimated using the capacity of Lambda with respect to the Green kernel G(x,y)....
The Threshold for Random k-SAT is 2^k log 2 - O(k) (2004)
Dimitris Achlioptas, Yuval Peres
this paper. We also thank the referees for useful comments. Part of this work was done while the authors participated in the focused research group on discrete probability at BIRS, July 12-26, 2003
Bootstrap percolation on infinite trees and non-amenable groups (2003)
Balogh, Jozsef, Peres, Yuval, Pete, Gabor
Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability p, independently of each other, and a deterministic spreading rule with...
Zeros of the i.i.d. Gaussian power series: a conformally invariant determinantal process (2003)
Consider the zero set of the random power series f(z)=sum a_n z^n with i.i.d. complex Gaussian coefficients a_n. We show that these zeros form a determinantal process: more precisely, their joint...
Fast simulation of new coins from old (2003)
Let S\subset (0,1). Given a known function f:S\to (0,1), we consider the problem of using independent tosses of a coin with probability of heads p (where p\in S is unknown) to simulate a coin with...
An invariant of finitary codes with finite expected square root coding length (2003)
Let $p$ and $q$ be probability vectors with the same entropy $h$. Denote by $B(p)$ the Bernoulli shift indexed by $\Z$ with marginal distribution $p$. Suppose that $\phi$ is a measure preserving...
Glauber Dynamics on Trees and Hyperbolic Graphs (2003)
Berger, Noam, Kenyon, Claire, Mossel, Elchanan, Peres, Yuval
We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with $n$ vertices and of bounded degree. We...
Brownian Motion on Compact Manifolds: Cover Time and Late Points (2003)
Dembo, Amir; Stanford University; Amir@math.stanford.edu, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu, Rosen, Jay; College Of Staten Island, CUNY; Jrosen3@earthlink.net
Let $M$ be a smooth, compact, connected Riemannian manifold of dimension $d>2$ and without boundary. Denote by $T(x,r)$ the hitting time of the ball of radius $r$ centered at $x$ by Brownian motion...
Information flow on trees (2003)
Mossel, Elchanan, Peres, Yuval
Consider a tree network $T$, where each edge acts as an independent copy of a given channel $M$, and information is propagated from the root. For which $T$ and $M$ does the configuration obtained at...
Extra heads and invariant allocations (2003)
Holroyd, Alexander E., Peres, Yuval
Let \Pi be an ergodic simple point process on R^d and let \Pi^* be its Palm version. Thorisson [Ann. Probab. 24 (1996) 2057-2064] proved that there exists a shift coupling of \Pi and \Pi^*; that is,...
Evolving sets, mixing and heat kernel bounds (2003)
We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties...
The Threshold for Random k-SAT is 2^k ln2 - O(k) (2003)
Achlioptas, Dimitris, Peres, Yuval
Let F be a random k-SAT formula on n variables, formed by selecting uniformly and independently m = rn out of all possible k-clauses. It is well-known that if r>2^k ln 2, then the formula F is...
On the Maximum Satisfiability of Random Formulas (2003)
Achlioptas, Dimitris, Naor, Assaf, Peres, Yuval
Maximum satisfiability is a canonical NP-hard optimization problem that appears empirically hard for random instances. Let us say that a Conjunctive normal form (CNF) formula consisting of...
Brownian intersections, cover times and thick points via trees (2003)
There is a close connection between intersections of Brownian motion paths and percolation on trees. Recently, ideas from probability on trees were an important component of the multifractal analysis...
Identifying several biased coins encountered by a hidden random walk (2003)
Suppose that attached to each site z in Z is a coin with bias theta(z), and only finitely many of these coins have non-zero bias. Allow a simple random walker to generate observations by tossing, at...
New coins from old: computing with unknown bias (2003)
Mossel, Elchanan, Peres, Yuval
Suppose that we are given a function f : (0,1) -> (0,1) and, for some unknown p in (0,1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of ``heads''). For which...
Anchored expansion, percolation and speed (2003)
Chen, Dayue, Peres, Yuval, Pete, Gabor
Benjamini, Lyons and Schramm [Random Walks and Discrete Potential Theory (1999) 56-84] considered properties of an infinite graph G, and the simple random walk on it, that are preserved by random...
Late points for random walks in two dimensions (2003)
Dembo, Amir, Peres, Yuval, Rosen, Jay, Zeitouni, Ofer
Let $\mathcal{T}_n(x)$ denote the time of first visit of a point $x$ on the lattice torus $\mathbb {Z}_n^2=\mathbb{Z}^2/n\mathbb{Z}^2$ by the simple random walk. The size of the set of $\alpha$,...
Trees and Matchings from Point Processes (2003)
Holroyd, Alexander E.; University Of California, Berkeley; Holroyd@math.berkeley.edu, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu
A factor graph of a point process is a graph whose vertices are the points of the process, and which is constructed from the process in a deterministic isometry-invariant way. We prove that the...
Which properties of a random sequence are dynamically sensitive? (2003)
Benjamini, Itai, Häggström, Olle, Peres, Yuval, Steif, Jeffrey E.
Consider a sequence of i.i.d.\ random variables, where each variable is refreshed (i.e., replaced by an independent variable with the same law) independently, according to a Poisson clock. At any...
On the Fraction of Satisfiable Clauses in Typical Formulas (2003)
Dimitris Achlioptas, Assaf Naor, Yuval Peres
Given n Boolean variables x1,..., xn, a k-clause is a disjunction of k literals, where a literal is a variable or its negation. A k-CNF formula is a conjunction of a finite number of k-clauses. Call...
On the maximum satisfiability of random formulas (2003)
Dimitris Achlioptas, Assaf Naor, Yuval Peres
Say that a k-CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 − 2 −k + p2 −k of its clauses (note that every k-CNF formula is 0-satisfiable). Let Fk(n,...
Trees and matchings from point processes (2002)
Holroyd, Alexander E., Peres, Yuval
A factor graph of a point process is a graph whose vertices are the points of the process, and which is constructed from the process in a deterministic isometry-invariant way. We prove that the...
The speed of biased random walk on percolation clusters (2002)
Berger, Noam, Gantert, Nina, Peres, Yuval
We consider biased random walk on supercritical percolation clusters in $\Z^2$. We show that the random walk is transient and that there are two speed regimes: If the bias is large enough, the random...
Transience of percolation clusters on wedges (2002)
Angel, Omer, Benjamini, Itai, Berger, Noam, Peres, Yuval
We study random walks on supercritical percolation clusters on wedges in $\Z^3$, and show that the infinite percolation cluster is (a.s.) transient whenever the wedge is transient. This solves a...
Bhaskara Marthi, Hanna Pasula, Stuart Russell, Yuval Peres
Filtering---estimating the state of a partially observable Markov process from a sequence of observations---is one of the most widely studied problems in control theory, AI, and computational...
Suppose that we are given a function f: (0, 1) → (0, 1) and, for some unknown p ∈ (0, 1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of “heads”). For which...
Brownian Motion on Compact Manifolds: Cover Time and Late Points (2002)
Amir Dembo, Yuval Peres, Jay Rosen
Let M be a smooth, compact, connected Riemannian manifold of dimension d ≥ 3 and without boundary. Denote by T(x, ε) the hitting time of the ball of radius ε centered...
A Phase Transition in Random coin Tossing (2001)
Levin, David A., Pemantle, Robin, Peres, Yuval
Suppose that a coin with bias $\theta$ is tossed at renewal times of a renewal process, and a fair coin is tossed at all other times. Let $\mu_\theta$ be the distribution ofthe observed sequence of...
Cover Times for Brownian Motion and Random Walks in Two Dimensions (2001)
Dembo, Amir, Peres, Yuval, Rosen, Jay, Zeitouni, Ofer
Let T(x,r) denote the first hitting time of the disc of radius r centered at x for Brownian motion on the two dimensional torus. We prove that sup_{x} T(x,r)/|log r|^2 --> 2/pi as r --> 0. The same...
Geometry of the Uniform Spanning Forest: Transitions in Dimensions 4, 8, 12 (2001)
Benjamini, Itai, Kesten, Harry, Peres, Yuval, Schramm, Oded
The uniform spanning forest (USF) in Z^d is the weak limit of random, uniformly chosen, spanning trees in [-n,n]^d. Pemantle proved that the USF consists a.s. of a single tree if and only if d
Markov Chain Intersections and the Loop-Erased Walk (2001)
Lyons, Russell, Peres, Yuval, Schramm, Oded
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...
Information flow on trees (2001)
Mossel, Elchanan, Peres, Yuval
Consider a tree network $T$, where each edge acts as an independent copy of a given channel $M$, and information is propagated from the root. For which $T$ and $M$ does the configuration obtained at...
Thick points for intersections of planar sample paths (2001)
Dembo, Amir, Peres, Yuval, Rosen, Jay, Zeitouni, Ofer
Let $L_n^{X}(x)$ denote the number of visits to $x \in {\bf Z}^2$ of the simple planar random walk $X$, up till step $n$. Let $X'$ be another simple planar random walk independent of $X$. We show...
Uniform spanning forests (2001)
Benjamini, Itai, Lyons, Russell, Peres, Yuval, Schramm, Oded
We study 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 (FSF )or wired (WSF )...
Where Did the Brownian Particle Go? (2001)
Pemantle, Robin; Ohio State University; Pemantle@math.ohio_state.edu, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu, Pitman, Jim; University Of California, Berkeley; Pitman@stat.berkeley.edu, Yor, Marc; Université Pierre Et Marie Curie; Pitman@stat.berkeley.edu
Consider the radial projection onto the unit sphere of the path a $d$-dimensional Brownian motion $W$, started at the center of the sphere and run for unit time. Given the occupation measure $mu$ of...
Uniform spanning forests (2001)
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm
Abstract. We study 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 (FSF) or...
Cover times for Brownian motion and random walks in two dimensions (2001)
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x; ") denote the rst hitting time of the disc of radius " centered at x for Brownian motion on the two dimensional torus T 2 We prove that sup x2T 2 T (x; ")=j log...
A dimension gap for continued fractions with independent digits (2001)
Yuri Kifer, Yuval Peres, Benjamin Weiss
Abstract. Kinney and Pitcher (1966) determined the dimension of measures on [0; 1] which make the digits in the continued fraction expansion i.i.d. variables.>From their formula it is not clear...
Broadcasting on trees and the Ising model (2000)
Evans, William, Kenyon, Claire, Peres, Yuval, Schulman, Leonard J.
Consider a process in which information is transmitted from a given root node on a noisy tree network $T$.We start with an unbiased random bit $R$ at the root of the tree and send it down the edges...
A Large Wiener Sausage from Crumbs. (2000)
Angel, Omer; Weizmann Institute Of Science; Omer@wisdom.weizmann.ac.il, Benjamini, Itai; Weizmann Institute Of Science; Itai@wisdom.weizmann.ac.il, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu
Let $B(t)$ denote Brownian motion in $R^d$. It is a classical fact that for any Borel set $A$ in $R^d$, the volume $V_1(A)$ of the Wiener sausage $B[0,1]+A$ has nonzero expectation iff $A$ is...
Khoshnevisan, Davar; University Of Utah; Davar@math.utah.edu, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu, Xiao, Yimin; University Of Utah; Xiao@math.utah.edu
Orey and Taylor (1974) introduced sets of ``fast points'' where Brownian increments are exceptionally large, They proved that for $lambda in (0,1]$, the Hausdorff dimension of ${rm F}(lambda)$ is...
Thick points for spatial Brownian motion: multifractal analysis of occupation measure (2000)
Dembo, Amir, Peres, Yuval, Rosen, Jay, Zeitouni, Ofer
Let $\mathscr{T}(x,r)$ denote the total occupation measure of the ball of radius $r$ centered at $x$ for Brownian motion in $\mathbb{R}^3$. We prove that $\sup_{|x|\leq1}\mathscr{T}(x,r)/(r^{2}|\log...
Broadcasting on trees and the Ising model (2000)
William Evans, Claire Kenyon, Yuval Peres, Leonard J. Schulman
Consider a process in which information is transmitted from a given root node on a noisy tree network T. We start with an unbiased random bit R at the root of the tree, and send it down the edges of...
Broadcasting on trees and the Ising model (2000)
William Evans, Claire Kenyon, Yuval Peres, Leonard J. Schulman
Consider a process in which information is transmitted from a given root node on a noisy tree network T. We start with an unbiased random bit R at the root of the tree, and send it down the edges of...
Approximation By Polynomials With Coefficients (2000)
Yuval Peres And, Yuval Peres, Boris Solomyak
. In response to a question of R. Kenyon, we prove that the set of polynomials with coecients 1, evaluated at a xed real number , is dense in R for a.e. 2 ( p 2; 2). For 2 (1; p 2], a more complete...
Critical Percolation on Any Nonamenable Group has no Infinite Clusters (1999)
Benjamini, Itai, Lyons, Russell, Peres, Yuval, Schramm, Oded
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 by the present authors earlier as a...
Thick Points for Transient Symmetric Stable Processes (1999)
Dembo, Amir; Stanford University; Amir@stat.standford.edu, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu, Rosen, Jay; College Of Staten Island, CUNY; Jrosen3@idt.net, Zeitouni, Ofer; Technion; Zeitouni@ee.technion.ac.il
Let T(x,r) denote the total occupation measure of the ball of radius r centered at x for a transient symmetric stable processes of index $b<d$ in $R^d$ and K(b,d) denote the norm of the...
Entropy of convolutions on the circle (1999)
Lindenstrauss, Elon, Meiri, David, Peres, Yuval
Given ergodic p-invariant measures {\mu_i} on the 1-torus T=R/Z, we give a sharp condition on their entropies, guaranteeing that the entropy of the convolution \muon converges to \log p. We also...
Ancona, Alano, Lyons, Russell, Peres, Yuval
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\geq 1}$...
Thick points for transient symmetric stable processes, Elect (1999)
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x; r) denote the total occupation measure of the ball of radius r centered at x for a transient symmetric stable processes of index in IR d and ;d denote the norm of the convolution with its...
Probability on trees: an introductory climb (1999)
These notes are based on Lectures delivered at the Saint Flour Summer School in
Critical percolation on any nonamenable group has no infinite clusters (1999)
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm, In Z
Abstract. 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 Benjamini, Lyons, Peres,...
Thick Points for Planar Brownian Motion and the Erdös-Taylor Conjecture on Random Walk (1999)
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x; r) denote the occupation measure of the disc of radius r centered at x by planar Brownian motion run till time 1. We prove that sup jxj1 T (x; r)=(r 2 j log rj 2 ) ! 2 a.s. as r ! 0, thus...
Thick Points for Transient Symmetric Stable Processes (1999)
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x, r) denote the total occupation measure of the ball of radius r centered at x for a transient symmetric stable processes of index # < d in IR d and # #,d denote the norm of the...
Problems on self-similar sets, self-affine sets: an update (1999)
Self-similar sets that satisfy a certain separation condition (the open set condition) are quite well understood. However, self-similar sets with "overlap", and self-affine sets (with or...
Where Did The Brownian Particle Go? (1999)
Robin Pemantle, Yuval Peres, Jim Pitman, Marc Yor
Consider the radial projection onto the unit sphere of the path a d-dimensional Brownian motion W run for unit time. Given the occupation measure ¯ of this projected path, what can be said about the...
Group-Invariant Percolation on Graphs (1999)
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm
. 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 ,...
Unpredictable paths and percolation (1998)
Benjamini, Itai, Pemantle, Robin, Peres, Yuval
4 We construct a nearest-neighbor process ${S_n}$ on Z that is less predictable than simple random walk, in the sense that given the process until time $n$, the conditional probability that $S_{n+k}...
Eventual Intersection for Sequences of Lévy Processes (1998)
Evans, Steven N.; University Of California At Berkeley; Evans@stat.berkeley.edu, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu
Consider the events ${F_n cap bigcup_{k=1}^{n-1} F_k = emptyset}$, $n in N$, where $(F_n)_{n=1}^infty$ is an i.i.d. sequence of stationary random subsets of a compact group $G$. A plausible...
Yuval Peres, Roberto Schonmann
Consider i.i.d. percolation with retention parameter p on an infinite graph G. There is a well known critical parameter p c 2 [0; 1] for the existence of infinite open clusters. Recently, it has been...
Energy and cutsets in infinite percolation clusters (1998)
Grimmett, Kesten and Zhang (1993) showed that for d ≥ 3, simple random walk on the infinite cluster C∞(Zd,p) of supercritical percolation on Zd is a.s. transient. Their result is equivalent to...
Energy and Cutsets in Infinite Percolation Clusters (1998)
Grimmett, Kesten and Zhang (1993) showed that for d # 3, simple random walk on the infinite cluster C# (Z d , p) of supercritical percolation on Z d is a.s. transient. Their result is equivalent to...
Broadcasting on Trees and the Ising Model (1998)
William Evans, Claire Kenyon, Yuval Peres, Leonard J. Schulman
Consider a process in which information is transmitted from a given root node on a noisy tree network T . We start with an unbiased random bit R at the root of the tree, and send it down the edges of...
Energy and Cutsets in Infinite Percolation Clusters (1998)
Grimmett, Kesten and Zhang (1993) showed that for d 3, simple random walk on the infinite cluster C1 (Z d ; p) of supercritical percolation on Z d is a.s. transient. Their result is equivalent to the...
Uniform Spanning Forests (1998)
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm
. We study 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 (FSF) or wired (WSF)...
A Phase Transition in Random Coin Tossing (1998)
David Levin, Robin Pemantle, Yuval Peres
Suppose that a coin with bias ` is tossed at renewal times of a renewal process, and a fair coin is tossed at all other times. Let ` be the distribution of the observed sequence of coin tosses, and...
Thick Points for Spatial Brownian Motion: Multifractal Analysis of Occupation Measure (1998)
Amir Dembo Yuval, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x; r) denote the total occupation measure of the ball of radius r centered at x for Brownian motion in IR 3 . We prove that sup jxj1 T (x; r)=(r 2 j log rj) ! 16=ß 2 a.s. as r ! 0, thus...
Broadcasting on Trees and the Ising Model (1998)
William Evans, Claire Kenyon, Yuval Peres, Leonard J. Schulman
Consider a process in which information is transmitted from a given root node on a noisy tree network T . We start with an unbiased random bit R at the root of the tree, and send it down the edges of...
Eventual intersection of sequences of Lévy processes (1998)
Abstract: Consider the events fFn \ S n,1 k=1 Fk =;g, n 2 N, where (Fn) 1 n=1 is an i.i.d. sequence of stationary random subsets of a compact group G. A plausible conjecture is that these events will...
Ladder heights, Gaussian random walks and the Riemann zeta function (1997)
Chang, Joseph T., Peres, Yuval
Let $\{S_n: n \geq 0\}$ be a random walk having normally distributed increments with mean $\theta$ and variance 1, and let $\tau$ be the time at which the random walk first takes a positive value, so...
No directed fractal percolation in zero area (1997)
Chayes, Lincoln, Pemantle, Robin, Peres, Yuval
We show that fractal (or "Mandelbrot") percolation in two dimensions produces a set containing no directed paths, when the set produced has zero area. This improves a similar result by the first...
Paths with exponential intersection tails and oriented percolation (1997)
Benjamini, Itai, Pemantle, Robin, Peres, Yuval
We show that oriented percolation occurs whenever a condition is satisfied called "exponential intersection tails". This condition says that a measure on paths exists for which the probability of two...
Ladder heights, Gaussian random walks, and the Riemann zeta function (1997)
Let fS n: n 0g be a random walk having normally distributed increments with mean ` and variance 1, and let be the time at which the random walk first takes a positive value, so that S is the first...
Self-Similar Measures And Intersections Of Cantor Sets (1997)
. It is natural to expect that the arithmetic sum of two Cantor sets should have positive Lebesgue measure if the sum of their dimensions exceeds 1, but there are many known counterexamples, e.g....
Entropy Of Convolutions On The Circle (1997)
Elon Lindenstrauss, David Meiri, Yuval Peres, P N \gamma
. Given ergodic p-invariant measures f¯ i g on the 1-torus T = R=Z, we give a sharp condition on their entropies, guaranteeing that the entropy of the convolution ¯ 1 \Delta \Delta \Delta ¯n...
Ladder heights, Gaussian random walks, and the Riemann zeta function (1997)
Let �Sn � n ≥ 0 � be a random walk having normally distributed increments with mean θ and variance 1, and let τ be the time at which the random walk first takes a positive value, so that...
Random walks on the lamplighter group (1996)
Lyons, Russell, Pemantle, Robin, Peres, Yuval
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...
Packing Dimension and Cartesian Products (1996)
Christopher J. Bishop, Yuval Peres
We show that for any analytic set A in R d , its packing dimension dim P (A) can be represented as sup B fdim H (A B) dim H (B)g ; where the supremum is over all compact sets B in R d , and dim H...
Intersection-Equivalence of Brownian Paths and Certain Branching Processes (1996)
We show that sample paths of Brownian motion (and other stable processes) intersect the same sets as certain random Cantor sets constructed by a branching process. With this approach, the classical...
Absolute Continuity of Bernoulli Convolutions (1996)
. The distribution of the random series P \Sigma n has been studied by many authors since the two seminal papers by Erdos in 1939 and 1940. Works of Alexander and Yorke, Przytycki and Urba'nski,...
Bi-Invariant Sets And Measures Have Integer Hausdorff Dimension (1996)
. Let A; B be two diagonal endomorphisms of the d-dimensional torus with corresponding eigenvalues relatively prime. We show that for any A-invariant ergodic measure ¯, there exists a projection...
Tail Estimates for One-Dimensional Random Walk in Random Environment (1996)
Amir Dembo, Yuval Peres, Ofer Zeitouni
Suppose that the integers are assigned i.i.d. random variables f! x g (taking values in the unit interval), which serve as an environment. This environment defines a random walk fX k g (called a...
Tail Estimates for One-Dimensional Random Walk in Random Environment (1996)
Amir Dembo, Yuval Peres, Ofer Zeitouni
Suppose that the integers are assigned i.i.d. random variables f! x g (taking values in the unit interval), which serve as an environment. This environment defines a random walk fX k g (called a...
Olle Häggström, Yuval Peres, Jeffrey E. Steif
We study bond percolation evolving in time in such a way that the edges turn on and off independently according to a continuous time stationary 2-state Markov chain. Asking whether an infinite open...
Tail Estimates for One-Dimensional Random Walk in Random Environment (1996)
Amir Dembo, Yuval Peres, Ofer Zeitouni
Suppose that the integers are assigned i.i.d. random variables f! x g (taking values in the unit interval), which serve as an environment. This environment defines a random walk fX k g (called a...
Packing Dimension and Cartesian Products (1996)
Christopher J. Bishop, Yuval Peres
Abstract We show that for any analytic set A in Rd, its packing dimension dimP(A) can be represented as supBfdimH(A \Theta B) \Gamma dimH(B)g; where the supremum is over all compact sets B in Rd, and...
The dimension of the Brownian frontier is greater than 1 (1995)
Bishop, Christopher J., Jones, Peter, Pemantle, Robin, Peres, Yuval
Consider a planar Brownian motion run for finite time. The frontier or ``outer boundary'' of the path is the boundary of the unbounded component of the complement. Burdzy (1989) showed that the...
The Dimension of the Brownian Frontier is Greater Than 1 (1995)
Christopher J. Bishop, Peter W. Jones, Robin Pemantle, Yuval Peres
Consider a planar Brownian motion run for finite time. The frontier or "outer boundary" of the path is the boundary of the unbounded component of the complement. Burdzy (1989) showed that...
Martin Capacity For Markov Chains (1995)
Itai Benjamini, Robin Pemantle, Yuval Peres
The probability that a transient Markov chain, or a Brownian path, will ever visit a given set , is classically estimated using the capacity of with respect to the Green kernel G(x; y). We show that...
The Dimension of the Brownian Frontier is Greater Than 1. (1995)
Christopher J. Bishop, Peter W. Jones, Robin Pemantle, Yuval Peres
Consider a planar Brownian motion run for nite time. The frontier or \outer boundary" of the path is the boundary of the unbounded component of the complement. Burdzy (1989) showed that the...
Martin Capacity For Markov Chains And Random Walks In Varying Dimensions (1993)
Itai Benjamini, Robin Pemantle, Yuval Peres
this paper is organized as follows. Martin capacity for Markov chains is the focus of Section 2. Several examples are given, including an interesting relation between simple random walk in three...
When Does a Branching Process Grow Like its Mean? Conceptual Proofs of L log L Criteria (1993)
Russell Lyons, Robin Pemantle, Yuval Peres
. 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,...
When Does a Branching Process Grow Like its Mean? Conceptual Proofs of L log L Criteria (1993)
Russell Lyons, Robin Pemantle, Yuval Peres
Abstract. 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...
Thin Points for Brownian Motion
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x; r) denote the occupation measure of the ball of radius r centered at x for Brownian motion fW t g 0t1 in IR d ; d 2. We prove that for any analytic set E in [0; 1], we have inf t2E lim inf...
Thick Points for Transient Symmetric Stable Processes
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x; r) denote the total occupation measure of the ball of radius r centered at x for a transient symmetric stable processes of index fi ! d in IR d and fi;d denote the norm of the convolution...
Thick Points for Spatial Brownian Motion: Multifractal Analysis of Occupation Measure
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni
Let T (x; r) denote the total occupation measure of the ball of radius r centered at x for Brownian motion in IR 3 . We prove that sup jxj1 T (x; r)=(r 2 j log rj) ! 16=ß 2 a.s. as r ! 0, thus...
Galton-Watson Trees with the Same Mean have the Same Polar Sets
: Evans (1992) defines a notion of what it means for a set B to be polar for a process indexed by a tree, \Gamma. The main result herein is that a tree picked from a Galton-Watson measure whose...
Chip-Firing and Rotor-Routing on Directed Graphs
Er E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, David B. Wilson
Abstract. We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several...