Source author record

Yuval Peres

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

125works

29topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A basic homogenization problem for the $p$ -Laplacian in ${\mathbb R}^d$ perforated along a sphere: $L^\infty$ estimates

We consider a boundary value problem for the $p$ -Laplacian, posed in the exterior of small cavities that all have the same $p$ -capacity and are anchored to the unit sphere in $\mathbb{R}^d$ , where $1<p<d.$ We assume that the distance between anchoring points is at least $\varepsilon$ and the characteristic diameter of cavities is $α\varepsilon$ , where $α=α(\varepsilon)$ tends to 0 with $\varepsilon$ . We also assume that anchoring points are asymptotically uniformly distributed as $\varepsilon \downarrow 0$ , and their number is asymptotic to a positive constant times $\varepsilon^{1-d}$ . The solution $u=u^\varepsilon$ is required to be 1 on all cavities and decay to 0 at infinity. Our goal is to describe the behavior of solutions for small $\varepsilon>0$ . We show that the problem possesses a critical window characterized by $τ:=\lim_{\varepsilon \downarrow 0}α/α_c \in (0,\infty)$ , where $α_c=\varepsilon^{1/γ}$ and $γ= \frac{d-p}{p-1}.$ We prove that outside the unit sphere, as $\varepsilon\downarrow 0$ , the solution converges to $A_*U$ for some constant $A_*$ , where $U(x)=\min\{1,|x|^{-γ}\}$ is the radial $p$ -harmonic function outside the unit ball. Here the constant $A_*$ equals 0 if $τ=0$ , while $A_*=1$ if $τ=\infty$ . In the critical window where $τ$ is positive and finite, $A_*\in(0,1)$ is explicitly computed in terms of the parameters of the problem. We also evaluate the limiting $p$ -capacity in all three cases mentioned above. Our key new tool is the construction of an explicit ansatz function $u_{A_*}^\varepsilon$ that approximates the solution $u^\varepsilon$ in $L^{\infty}(\mathbb{R}^d)$ and satisfies $\|\nabla u^\varepsilon-\nabla u_{A_*}^\varepsilon \|_{L^{p}(\mathbb{R}^d)} \to 0$ as $\varepsilon \downarrow 0$ .

preprint2022arXiv

No cutoff in Spherically symmetric trees

We show that for lazy simple random walks on finite spherically symmetric trees, the ratio of the mixing time and the relaxation time is bounded by a universal constant. Consequently, lazy simple random walks on any sequence of finite spherically symmetric trees do not exhibit pre-cutoff; this conclusion also holds for continuous-time simple random walks. This answers a question recently proposed by Gantert, Nestoridi, and Schmid. We also show that for lazy simple random walks on finite spherically symmetric trees, hitting times of vertices are (uniformly) non concentrated. Finally, we study the stability of our results under rough isometries.

preprint2022arXiv

Recurrence and windings of two revolving random walks

We study the winding behavior of random walks on two oriented square lattices. One common feature of these walks is that they are bound to revolve clockwise. We also obtain quantitative results of transience/recurrence for each walk.

preprint2020arXiv

Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements

Recall the classical hypothesis testing setting with two convex sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p in P or from a distribution q in Q and wants to decide from which set the points were sampled. It is known that the optimal exponential rate at which errors decrease can be achieved by a simple maximum-likelihood ratio test which does not depend on p or q, but only on the sets P and Q. We consider an adaptive generalization of this model where the choice of p in P and q in Q can change in each sample in some way that depends arbitrarily on the previous samples. In other words, in the k'th round, an adversary, having observed all the previous samples in rounds 1,...,k-1, chooses p_k in P and q_k in Q, with the goal of confusing the hypothesis test. We prove that even in this case, the optimal exponential error rate can be achieved by a simple maximum-likelihood test that depends only on P and Q. We then show that the adversarial model has applications in hypothesis testing for quantum states using restricted measurements. For example, it can be used to study the problem of distinguishing entangled states from the set of all separable states using only measurements that can be implemented with local operations and classical communication (LOCC). The basic idea is that in our setup, the deleterious effects of entanglement can be simulated by an adaptive classical adversary. We prove a quantum Stein's Lemma in this setting: In many circumstances, the optimal hypothesis testing rate is equal to an appropriate notion of quantum relative entropy between two states. In particular, our arguments yield an alternate proof of Li and Winter's recent strengthening of strong subadditivity for quantum relative entropy.

preprint2020arXiv

Consensus with Bounded Space and Minimal Communication

Population protocols are a fundamental model in distributed computing, where many nodes with bounded memory and computational power have random pairwise interactions over time. This model has been studied in a rich body of literature aiming to understand the tradeoffs between the memory and time needed to perform computational tasks. We study the population protocol model focusing on the communication complexity needed to achieve consensus with high probability. When the number of memory states is $s = O(\log \log{n})$ , the best upper bound known was given by a protocol with $O(n \log{n})$ communication, while the best lower bound was $Ω(n \log(n)/s)$ communication. We design a protocol that shows the lower bound is sharp. When each agent has $s=O(\log{n}^θ)$ states of memory, with $θ\in (0,1/2)$ , consensus can be reached in time $O(\log(n))$ with $O(n \log{(n)}/s)$ communications with high probability.

preprint2020arXiv

Induced graphs of uniform spanning forests

Given a subgraph $H$ of a graph $G$ , the induced graph of $H$ is the largest subgraph of $G$ whose vertex set is the same as that of $H$ . Our paper concerns the induced graphs of the components of $\operatorname{WSF}(G)$ , the wired spanning forest on $G$ , and, to a lesser extent, $\operatorname{FSF}(G)$ , the free uniform spanning forest. We show that the induced graph of each component of $\operatorname{WSF}(\mathbb Z^d$ ) is almost surely recurrent when $d\ge 8$ . Moreover, the effective resistance between two points on the ray of the tree to infinity within a component grows linearly when $d\ge9$ . For any vertex-transitive graph $G$ , we establish the following resampling property: Given a vertex $o$ in $G$ , let $\mathcal T_o$ be the component of $\operatorname{WSF}(G)$ containing $o$ and $\overline{\mathcal{T}_o}$ be its induced graph. Conditioned on $\overline{\mathcal{T}_o}$ , the tree $\mathcal T_o$ is distributed as $\operatorname{WSF}(\overline{\mathcal{T}_o})$ . For any graph $G$ , we also show that if $\mathcal T_o$ is the component of $\operatorname{FSF}(G)$ containing $o$ and $\overline{\mathcal{T}_o}$ is its induced graph, then conditioned on $\overline{\mathcal{T}_o}$ , the tree $\mathcal T_o$ is distributed as $\operatorname{FSF}(\overline{\mathcal{T}_o})$ .

preprint2020arXiv

Poisson Boundaries of Lamplighter Groups: Proof of the Kaimanovich-Vershik Conjecture

We answer positively a question of Kaimanovich and Vershik from 1979, showing that the final configuration of lamps for simple random walk on the lamplighter group over ${\Bbb Z}^d$ ( $d \ge 3$ ) is the Poisson boundary. For $d \ge 5$ , this had been shown earlier by Erschler (2011). We extend this to walks of more general types on more general groups.

preprint2020arXiv

Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

The insertion-deletion channel takes as input a bit string ${\bf x}\in\{0,1\}^{n}$ , and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover $\bf x$ from many independent outputs (called "traces") of the insertion-deletion channel applied to $\bf x$ . We show that if $\bf x$ is chosen uniformly at random, then $\exp(O(\log^{1/3} n))$ traces suffice to reconstruct $\bf x$ with high probability. For the deletion channel with deletion probability $q < 1/2$ the earlier upper bound was $\exp(O(\log^{1/2} n))$ . The case of $q\geq 1/2$ or the case where insertions are allowed has not been previously analyzed, and therefore the earlier upper bound was as for worst-case strings, i.e., $\exp(O( n^{1/3}))$ . We also show that our reconstruction algorithm runs in $n^{1+o(1)}$ time. A key ingredient in our proof is a delicate two-step alignment procedure where we estimate the location in each trace corresponding to a given bit of $\bf x$ . The alignment is done by viewing the strings as random walks and comparing the increments in the walk associated with the input string and the trace, respectively.

preprint2019arXiv

Biased infinity Laplacian Boundary Problem on finite graphs

We provide an algorithm, running in polynomial time in the number of vertices, computing the unique solution to the biased infinity Laplacian Boundary Problem on finite graphs. The algorithm is based on the general outline and approach taken in the corresponding algorithm for the unbiased case provided by Lazarus et al. The new ingredient is an adjusted (biased) notion of a slope of a function on a path in a graph. The algorithm can be used to determine efficiently numerical approximations to the viscosity solutions of biased infinity Laplacian PDEs.

preprint2019arXiv

Communication cost of consensus for nodes with limited memory

Motivated by applications in blockchains and sensor networks, we consider a model of $n$ nodes trying to reach consensus on their majority bit. Each node $i$ is assigned a bit at time zero, and is a finite automaton with $m$ bits of memory (i.e., $2^m$ states) and a Poisson clock. When the clock of $i$ rings, $i$ can choose to communicate, and is then matched to a uniformly chosen node $j$ . The nodes $j$ and $i$ may update their states based on the state of the other node. Previous work has focused on minimizing the time to consensus and the probability of error, while our goal is minimizing the number of communications. We show that when $m>3 \log\log\log(n)$ , consensus can be reached at linear communication cost, but this is impossible if $m<\log\log\log(n)$ . We also study a synchronous variant of the model, where our upper and lower bounds on $m$ for achieving linear communication cost are $2\log\log\log(n)$ and $\log\log\log(n)$ , respectively. A key step is to distinguish when nodes can become aware of knowing the majority bit and stop communicating. We show that this is impossible if their memory is too low.

preprint2017arXiv

The string of diamonds is nearly tight for rumour spreading

For a rumour spreading protocol, the spread time is defined as the first time that everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with its asynchronous variant, and show that for any $n$ -vertex graph and any starting vertex, the ratio between their expected spread times is bounded by $O \left({n}^{1/3}{\log^{2/3} n}\right)$ . This improves the $O(\sqrt n)$ upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of $O(\log n)$ , as illustrated by the string of diamonds graph. We also show that if for a pair $α,β$ of real numbers, there exists infinitely many graphs for which the two spread times are $n^α$ and $n^β$ in expectation, then $0\leqα\leq 1$ and $α\leq β\leq \frac13 + \frac23 α$ ; and we show each such pair $α,β$ is achievable.

preprint2016arXiv

Cutoff for the noisy voter model

Given a continuous time Markov Chain $\{q(x,y)\}$ on a finite set $S$ , the associated noisy voter model is the continuous time Markov chain on $\{0,1\}^S$ , which evolves in the following way: (1) for each two sites $x$ and $y$ in $S$ , the state at site $x$ changes to the value of the state at site $y$ at rate $q(x,y)$ ; (2) each site rerandomizes its state at rate 1. We show that if there is a uniform bound on the rates $\{q(x,y)\}$ and the corresponding stationary distributions are almost uniform, then the mixing time has a sharp cutoff at time $\log|S|/2$ with a window of order 1. Lubetzky and Sly proved cutoff with a window of order 1 for the stochastic Ising model on toroids; we obtain the special case of their result for the cycle as a consequence of our result. Finally, we consider the model on a star and demonstrate the surprising phenomenon that the time it takes for the chain started at all ones to become close in total variation to the chain started at all zeros is of smaller order than the mixing time.

preprint2016arXiv

Cutoff on all Ramanujan graphs

We show that on every Ramanujan graph $G$ , the simple random walk exhibits cutoff: when $G$ has $n$ vertices and degree $d$ , the total-variation distance of the walk from the uniform distribution at time $t=\frac{d}{d-2}\log_{d-1} n + s\sqrt{\log n}$ is asymptotically $\mathbb{P}(Z > c\, s)$ where $Z$ is a standard normal variable and $c=c(d)$ is an explicit constant. Furthermore, for all $1 \leq p \leq \infty$ , $d$ -regular Ramanujan graphs minimize the asymptotic $L^p$ -mixing time for SRW among all $d$ -regular graphs. Our proof also shows that, for every vertex $x$ in $G$ as above, its distance from $n-o(n)$ of the vertices is asymptotically $\log_{d-1} n$ .

preprint2016arXiv

Diffusive estimates for random walks on stationary random graphs of polynomial growth

Let $(G,ρ)$ be a stationary random graph, and use $B^G_ρ(r)$ to denote the ball of radius $r$ about $ρ$ in $G$ . Suppose that $(G,ρ)$ has annealed polynomial growth, in the sense that $\mathbb{E}[|B^G_ρ(r)|] \leq O(r^k)$ for some $k > 0$ and every $r \geq 1$ . Then there is an infinite sequence of times $\{t_n\}$ at which the random walk $\{X_t\}$ on $(G,ρ)$ is at most diffusive: Almost surely (over the choice of $(G,ρ)$ ), there is a number $C > 0$ such that $\mathbb{E} \left[\mathrm{dist}_G(X_0, X_{t_n})^2 \mid X_0 = ρ, (G,ρ)\right]\leq C t_n\qquad \forall n \geq 1\,.$ This result is new even in the case when $G$ is a stationary random subgraph of $\mathbb{Z}^d$ . Combined with the work of Benjamini, Duminil-Copin, Kozma, and Yadin (2015), it implies that $G$ almost surely does not admit a non-constant harmonic function of sublinear growth. To complement this, we argue that passing to a subsequence of times $\{t_n\}$ is necessary, as there are stationary random graphs of (almost sure) polynomial growth where the random walk is almost surely superdiffusive at an infinite subset of times.

preprint2016arXiv

Estimating the Spectral Gap of a Reversible Markov Chain from a Short Trajectory

The spectral gap $γ$ of an ergodic and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix $P$ may be unknown, yet one sample of the chain up to a fixed time $t$ may be observed. Hsu, Kontorovich, and Szepesvari (2015) considered the problem of estimating $γ$ from this data. Let $π$ be the stationary distribution of $P$ , and $π_\star = \min_x π(x)$ . They showed that, if $t = \tilde{O}\bigl(\frac{1}{γ^3 π_\star}\bigr)$ , then $γ$ can be estimated to within multiplicative constants with high probability. They also proved that $\tildeΩ\bigl(\frac{n}γ\bigr)$ steps are required for precise estimation of $γ$ . We show that $\tilde{O}\bigl(\frac{1}{γπ_\star}\bigr)$ steps of the chain suffice to estimate $γ$ up to multiplicative constants with high probability. When $π$ is uniform, this matches (up to logarithmic corrections) the lower bound of Hsu, Kontorovich, and Szepesvari.

preprint2016arXiv

How many matrices can be spectrally balanced simultaneously?

We prove that any $\ell$ positive definite $d \times d$ matrices, $M_1,\ldots,M_\ell$ , of full rank, can be simultaneously spectrally balanced in the following sense: for any $k < d$ such that $\ell \leq \lfloor \frac{d-1}{k-1} \rfloor$ , there exists a matrix $A$ satisfying $\frac{λ_1(A^T M_i A) }{ \mathrm{Tr}( A^T M_i A ) } < \frac{1}{k}$ for all $i$ , where $λ_1(M)$ denotes the largest eigenvalue of a matrix $M$ . This answers a question posed by Peres, Popov and Sousi and completes the picture described in that paper regarding sufficient conditions for transience of self-interacting random walks. Furthermore, in some cases we give quantitative bounds on the transience of such walks.

preprint2016arXiv

Increasing subsequences of random walks

Given a sequence of $n$ real numbers $\{S_i\}_{i\leq n}$ , we consider the longest weakly increasing subsequence, namely $i_1<i_2<\dots <i_L$ with $S_{i_k} \leq S_{i_{k+1}}$ and $L$ maximal. When the elements $S_i$ are i.i.d. uniform random variables, Vershik and Kerov, and Logan and Shepp proved that $\mathbb{E} L=(2+o(1)) \sqrt{n}$ . We consider the case when $\{S_i\}_{i\leq n}$ is a random walk on $\mathbb{R}$ with increments of mean zero and finite (positive) variance. In this case, it is well known (e.g., using record times) that the length of the longest increasing subsequence satisfies $\mathbb{E} L\geq c\sqrt{n}$ . Our main result is an upper bound $\mathbb{E} L\leq n^{1/2 + o(1)}$ , establishing the leading asymptotic behavior. If $\{S_i\}_{i\leq n}$ is a simple random walk on $\mathbb{Z}$ , we improve the lower bound by showing that $\mathbb{E} L \geq c\sqrt{n} \log{n}$ . We also show that if $\{\mathbf{S}_i\}$ is a simple random walk in $\mathbb{Z}^2$ , then there is a subsequence of $\{\mathbf{S}_i\}_{i\leq n}$ of expected length at least $cn^{1/3}$ that is increasing in each coordinate. The above one-dimensional result yields an upper bound of $n^{1/2 + o(1)}$ . The problem of determining the correct exponent remains open.

preprint2016arXiv

Laplacian growth, sandpiles and scaling limits

Laplacian growth is the study of interfaces that move in proportion to harmonic measure. Physically, it arises in fluid flow and electrical problems involving a moving boundary. We survey progress over the last decade on discrete models of (internal) Laplacian growth, including the abelian sandpile, internal DLA, rotor aggregation, and the scaling limits of these models on the lattice Z^d as the mesh size goes to zero. These models provide a window into the tools of discrete potential theory: harmonic functions, martingales, obstacle problems, quadrature domains, Green functions, smoothing. We also present one new result: rotor aggregation in Z^d has O(log r) fluctuations around a Euclidean ball, improving a previous power-law bound. We highlight several open questions, including whether these fluctuations are O(1).

preprint2016arXiv

Mixing of the exclusion process with small bias

We analyze the mixing behavior of the biased exclusion process on a path of length $n$ as the bias $β_n$ tends to $0$ as $n \to \infty$ . We show that the sequence of chains has a pre-cutoff, and interpolates between the unbiased exclusion and the process with constant bias. As the bias increases, the mixing time undergoes two phase transitions: one when $β_n$ is of order $1/n$ , and the other when $β_n$ is order $\log n/n$ .

preprint2016arXiv

Non-universality for longest increasing subsequence of a random walk

The longest increasing subsequence of a random walk with mean zero and finite variance is known to be $n^{1/2 + o(1)}$ . We show that this is not universal for symmetric random walks. In particular, the symmetric Ultra-fat tailed random walk has a longest increasing subsequence that is asymptotically at least $n^{0.690}$ and at most $n^{0.815}$ . An exponent strictly greater than $1/2$ is also shown for the symmetric stable- $α$ distribution when $α$ is sufficiently small.

preprint2016arXiv

Random walks on the random graph

We study random walks on the giant component of the Erdős-Rényi random graph ${\cal G}(n,p)$ where $p=λ/n$ for $λ>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $\log^2 n$ . We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(\log n)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $(ν{\bf d})^{-1}\log n \pm (\log n)^{1/2+o(1)}$ , where $ν$ and ${\bf d}$ are the speed of random walk and dimension of harmonic measure on a ${\rm Poisson}(λ)$ -Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.

preprint2016arXiv

Restrictions of Hölder continuous functions

For $0<α<1$ let $V(α)$ denote the supremum of the numbers $v$ such that every $α$ -Hölder continuous function is of bounded variation on a set of Hausdorff dimension $v$ . Kahane and Katznelson (2009) proved the estimate $1/2 \leq V(α)\leq 1/(2-α)$ and asked whether the upper bound is sharp. We show that in fact $V(α)=\max\{1/2,α\}$ . Let $\dim_{H}$ and $\overline{\dim}_{M}$ denote the Hausdorff and upper Minkowski dimension, respectively. The upper bound on $V(α)$ is a consequence of the following theorem. Let $\{B(t): t\in [0,1]\}$ be a fractional Brownian motion of Hurst index $α$ . Then, almost surely, there exists no set $A\subset [0,1]$ such that $\overline{\dim}_{M} A>\max\{1-α,α\}$ and $B\colon A\to \mathbb{R}$ is of bounded variation. Furthermore, almost surely, there exists no set $A\subset [0,1]$ such that $\overline{\dim}_{M} A>1-α$ and $B\colon A\to \mathbb{R}$ is $β$ -Hölder continuous for some $β>α$ . The zero set and the set of record times of $B$ witness that the above theorems give the optimal dimensions. We also prove similar restriction theorems for deterministic self-affine functions and generic $α$ -Hölder continuous functions. Finally, let $\{\mathbf{B}(t): t\in [0,1]\}$ be a two-dimensional Brownian motion. We prove that, almost surely, there is a compact set $D\subset [0,1]$ such that $\dim_{H} D\geq 1/3$ and $\mathbf{B}\colon D\to \mathbb{R}^2$ is non-decreasing in each coordinate. It remains open whether $1/3$ is best possible.

preprint2016arXiv

Sensitivity of mixing times in Eulerian digraphs

Let $X$ be a lazy random walk on a graph $G$ . If $G$ is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains, as the biased random walk on the cycle $\mathbb{Z}_n$ shows. However, we establish that for Eulerian digraphs, the mixing time is $O(mn)$ , where $m$ is the number of edges and $n$ is the number of vertices. In the reversible case, the mixing time is robust to the change of the laziness parameter. Surprisingly, in the directed setting the mixing time can be sensitive to such changes. We also study exploration and cover times for random walks on Eulerian digraphs and prove universal upper bounds in analogy to the undirected case.

preprint2016arXiv

Tight Lower Bounds for Multiplicative Weights Algorithmic Families

We study the fundamental problem of prediction with expert advice and develop regret lower bounds for a large family of algorithms for this problem. We develop simple adversarial primitives, that lend themselves to various combinations leading to sharp lower bounds for many algorithmic families. We use these primitives to show that the classic Multiplicative Weights Algorithm (MWA) has a regret of $\sqrt{\frac{T \ln k}{2}}$ , there by completely closing the gap between upper and lower bounds. We further show a regret lower bound of $\frac{2}{3}\sqrt{\frac{T\ln k}{2}}$ for a much more general family of algorithms than MWA, where the learning rate can be arbitrarily varied over time, or even picked from arbitrary distributions over time. We also use our primitives to construct adversaries in the geometric horizon setting for MWA to precisely characterize the regret at $\frac{0.391}{\sqrtδ}$ for the case of $2$ experts and a lower bound of $\frac{1}{2}\sqrt{\frac{\ln k}{2δ}}$ for the case of arbitrary number of experts $k$ .

preprint2016arXiv

Towards Optimal Algorithms for Prediction with Expert Advice

We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. In 1965, Cover gave the optimal algorithm for the case of 2 experts. In this paper, we design the optimal algorithm, adversary and regret for the case of 3 experts. Further, we show that the optimal algorithm for $2$ and $3$ experts is a probability matching algorithm (analogous to Thompson sampling) against a particular randomized adversary. Remarkably, our proof shows that the probability matching algorithm is not only optimal against this particular randomized adversary, but also minimax optimal. Our analysis develops upper and lower bounds simultaneously, analogous to the primal-dual method. Our analysis of the optimal adversary goes through delicate asymptotics of the random walk of a particle between multiple walls. We use the connection we develop to random walks to derive an improved algorithm and regret bound for the case of $4$ experts, and, provide a general framework for designing the optimal algorithm and adversary for an arbitrary number of experts.

preprint2016arXiv

Trace reconstruction with $\exp( O( n^{1/3} ) )$ samples

In the trace reconstruction problem, an unknown bit string $x \in \{0,1\}^n$ is observed through the deletion channel, which deletes each bit of $x$ with some constant probability $q$ , yielding a contracted string $\widetilde{x}$ . How many independent copies of $\widetilde{x}$ are needed to reconstruct $x$ with high probability? Prior to this work, the best upper bound, due to Holenstein, Mitzenmacher, Panigrahy, and Wieder (2008), was $\exp(\widetilde{O}(n^{1/2}))$ . We improve this bound to $\exp(O(n^{1/3}))$ using statistics of individual bits in the output and show that this bound is sharp in the restricted model where this is the only information used. Our method, that uses elementary complex analysis, can also handle insertions.

preprint2016arXiv

Transience in growing subgraphs via evolving sets

We extend the use of random evolving sets to time-varying conductance models and utilize it to provide tight heat kernel upper bounds. It yields the transience of any uniformly lazy random walk, on Z^d, d>=3, equipped with uniformly bounded above and below, independently time-varying edge conductances, of (effectively) non-decreasing in time vertex conductances (i.e. reversing measure), thereby affirming part of [ABGK, Conj. 7.1].

preprint2016arXiv

Weighted sampling without replacement

Comparing concentration properties of uniform sampling with and without replacement has a long history which can be traced back to the pioneer work of Hoeffding (1963). The goal of this short note is to extend this comparison to the case of non-uniform weights, using a coupling between the two samples. When the items' weights are arranged in the same order as their values, we show that the induced coupling for the cumulative values is a submartingale coupling. As a consequence, the powerful Chernoff-type upper-tail estimates known for sampling with replacement automatically transfer to the case of sampling without replacement. For general weights, we use the same coupling to establish a sub-Gaussian concentration inequality. We also construct another martingale coupling which allows us to answer a question raised by Luh and Pippenger (2014) on sampling in Polya urns with different replacement numbers.

preprint2016arXiv

When multiplicative noise stymies control

We consider the stabilization of an unstable discrete-time linear system that is observed over a channel corrupted by continuous multiplicative noise. Our main result shows that if the system growth is large enough, then the system cannot be stabilized in a second-moment sense. This is done by showing that the probability that the state magnitude remains bounded must go to zero with time. Our proof technique recursively bounds the conditional density of the system state (instead of focusing on the second moment) to bound the progress the controller can make. This sidesteps the difficulty encountered in using the standard data-rate theorem style approach; that approach does not work because the mutual information per round between the system state and the observation is potentially unbounded. It was known that a system with multiplicative observation noise can be stabilized using a simple memoryless linear strategy if the system growth is suitably bounded. In this paper, we show that while memory cannot improve the performance of a linear scheme, a simple non-linear scheme that uses one-step memory can do better than the best linear scheme.

preprint2015arXiv

A Gaussian upper bound for martingale small-ball probabilities

Consider a discrete-time martingale $\{X_t\}$ taking values in a Hilbert space $\mathcal H$ . We show that if for some $L \geq 1$ , the bounds $\mathbb{E} \left[\|X_{t+1}-X_t\|_{\mathcal H}^2 \mid X_t\right]=1$ and $\|X_{t+1}-X_t\|_{\mathcal H} \leq L$ are satisfied for all times $t \geq 0$ , then there is a constant $c = c(L)$ such that for $1 \leq R \leq \sqrt{t}$ , $\mathbb{P}(\|X_t\|_{\mathcal H} \leq R \mid X_0 = x_0) \leq c \frac{R}{\sqrt{t}} e^{-\|x_0\|_{\mathcal H}^2/(6 L^2 t)}\,.$ Following [Lee-Peres, Ann. Probab. 2013], this has applications to diffusive estimates for random walks on vertex-transitive graphs.

preprint2015arXiv

Approval Voting and Incentives in Crowdsourcing

The growing need for labeled training data has made crowdsourcing an important part of machine learning. The quality of crowdsourced labels is, however, adversely affected by three factors: (1) the workers are not experts; (2) the incentives of the workers are not aligned with those of the requesters; and (3) the interface does not allow workers to convey their knowledge accurately, by forcing them to make a single choice among a set of options. In this paper, we address these issues by introducing approval voting to utilize the expertise of workers who have partial knowledge of the true answer, and coupling it with a ("strictly proper") incentive-compatible compensation mechanism. We show rigorous theoretical guarantees of optimality of our mechanism together with a simple axiomatic characterization. We also conduct preliminary empirical studies on Amazon Mechanical Turk which validate our approach.

preprint2015arXiv

Bandit Convex Optimization: sqrt{T} Regret in One Dimension

We analyze the minimax regret of the adversarial bandit convex optimization problem. Focusing on the one-dimensional case, we prove that the minimax regret is $\widetildeΘ(\sqrt{T})$ and partially resolve a decade-old open problem. Our analysis is non-constructive, as we do not present a concrete algorithm that attains this regret rate. Instead, we use minimax duality to reduce the problem to a Bayesian setting, where the convex loss functions are drawn from a worst-case distribution, and then we solve the Bayesian version of the problem with a variant of Thompson Sampling. Our analysis features a novel use of convexity, formalized as a "local-to-global" property of convex functions, that may be of independent interest.

preprint2015arXiv

Convergence of discrete Green functions with Neumann boundary conditions

In this note we prove convergence of Green functions with Neumann boundary conditions for the random walk to their continuous counterparts. Also a few Beurling type hitting estimates are obtained for the random walk on discretizations of smooth domains. These have been used recently in the study of a two dimensional competing aggregation system known as $Competitive\, Erosion$ . Some of the statements appearing in this note are classical for ${\mathbb{Z}}^2$ . However additional arguments are needed for the proofs in the bounded geometry setting.

preprint2015arXiv

Formation of an interface by competitive erosion

In 2006, the fourth author proposed a graph-theoretic model of interface dynamics called competitive erosion. Each vertex of the graph is occupied by a particle that can be either red or blue. New red and blue particles alternately get emitted from their respective bases and perform random walk. On encountering a particle of the opposite color they kill it and occupy its position. We prove that on the cylinder graph (the product of a path and a cycle) an interface spontaneously forms between red and blue and is maintained in a predictable position with high probability.

preprint2015arXiv

Heat diffusion with frozen boundary

Consider "Frozen Random Walk" on $\mathbb{Z}$ : $n$ particles start at the origin. At any discrete time, the leftmost and rightmost $\lfloor{\frac{n}{4}}\rfloor$ particles are "frozen" and do not move. The rest of the particles in the "bulk" independently jump to the left and right uniformly. The goal of this note is to understand the limit of this process under scaling of mass and time. To this end we study the following deterministic mass splitting process: start with mass $1$ at the origin. At each step the extreme quarter mass on each side is "frozen". The remaining "free" mass in the center evolves according to the discrete heat equation. We establish diffusive behavior of this mass evolution and identify the scaling limit under the assumption of its existence. It is natural to expect the limit to be a truncated Gaussian. A naive guess for the truncation point might be the $1/4$ quantile points on either side of the origin. We show that this is not the case and it is in fact determined by the evolution of the second moment of the mass distribution.

preprint2015arXiv

Random Dirichlet series arising from records

We study the distributions of the random Dirichlet series with parameters $(s, β)$ defined by $S=\sum_{n=1}^{\infty}\frac{I_n}{n^s},$ where $(I_n)$ is a sequence of independent Bernoulli random variables, $I_n$ taking value $1$ with probability $1/n^β$ and value $0$ otherwise. Random series of this type are motivated by the record indicator sequences which have been studied in extreme value theory in statistics. We show that when $s>0$ and $0< β\le 1$ with $s+β>1$ the distribution of $S$ has a density; otherwise it is purely atomic or not defined because of divergence. In particular, in the case when $s>0$ and $β=1$ , we prove that for every $0<s<1$ the density is bounded and continuous, whereas for every $s>1$ it is unbounded. In the case when $s>0$ and $0<β<1$ with $s+β>1$ , the density is smooth. To show the absolute continuity, we obtain estimates of the Fourier transforms, employing van der Corput's method to deal with number-theoretic problems. We also give further regularity results of the densities, and present an example of non atomic singular distribution which is induced by the series restricted to the primes.

preprint2015arXiv

Random walks colliding before getting trapped

Let $P$ be the transition matrix of a finite, irreducible and reversible Markov chain. We say the continuous time Markov chain $X$ has transition matrix $P$ and speed $λ$ if it jumps at rate $λ$ according to the matrix $P$ . Fix $λ_X,λ_Y,λ_Z\geq 0$ , then let $X,Y$ and $Z$ be independent Markov chains with transition matrix $P$ and speeds $λ_X,λ_Y$ and $λ_Z$ respectively, all started from the stationary distribution. What is the chance that $X$ and $Y$ meet before either of them collides with $Z$ ? For each choice of $λ_X,λ_Y$ and $λ_Z$ with $\max(λ_X,λ_Y)>0$ , we prove a lower bound for this probability which is uniform over all transitive, irreducible and reversible chains. In the case that $λ_X=λ_Y=1$ and $λ_Z=0$ we prove a strengthening of our main theorem using a martingale argument. We provide an example showing the transitivity assumption cannot be removed for general $λ_X,λ_Y$ and $λ_Z$ .

preprint2015arXiv

The divisible sandpile at critical density

The divisible sandpile starts with i.i.d. random variables ("masses") at the vertices of an infinite, vertex-transitive graph, and redistributes mass by a local toppling rule in an attempt to make all masses at most 1. The process stabilizes almost surely if m<1 and it almost surely does not stabilize if m>1, where $m$ is the mean mass per vertex. The main result of this paper is that in the critical case m=1, if the initial masses have finite variance, then the process almost surely does not stabilize. To give quantitative estimates on a finite graph, we relate the number of topplings to a discrete biLaplacian Gaussian field.

preprint2015arXiv

Topics in Markov chains: mixing and escape rate

These are the notes for the minicourse on Markov chains delivered at the Saint Petersburg Summer School, June 2012. The main emphasis is on methods for estimating mixing times (for finite chains) and escape rates (for infinite chains). Lamplighter groups are key examples in both topics and the Varopolous-Carne long range estimate is useful in both settings.

preprint2014arXiv

Competing first passage percolation on random regular graphs

We consider two competing first passage percolation processes started from uniformly chosen subsets of a random regular graph on $N$ vertices. The processes are allowed to spread with different rates, start from vertex subsets of different sizes or at different times. We obtain tight results regarding the sizes of the vertex sets occupied by each process, showing that in the generic situation one process will occupy $Θ(1)N^α$ vertices, for some $0 < α< 1$ . The value of $α$ is calculated in terms of the relative rates of the processes, as well as the sizes of the initial vertex sets and the possible time advantage of one process. The motivation for this work comes from the study of viral marketing on social networks. The described processes can be viewed as two competing products spreading through a social network (random regular graph). Considering the processes which grow at different rates (corresponding to different attraction levels of the two products) or starting at different times (the first to market advantage) allows to model aspects of real competition. The results obtained can be interpreted as one of the two products taking the lion share of the market. We compare these results to the same process run on $d$ dimensional grids where we show that in the generic situation the two products will have a linear fraction of the market each.

preprint2014arXiv

Four Random Permutations Conjugated by an Adversary Generate $S_n$ with High Probability

We prove a conjecture dating back to a 1978 paper of D.R.\ Musser~\cite{musserirred}, namely that four random permutations in the symmetric group $\mathcal{S}_n$ generate a transitive subgroup with probability $p_n > ε$ for some $ε> 0$ independent of $n$ , even when an adversary is allowed to conjugate each of the four by a possibly different element of $§_n$ (in other words, the cycle types already guarantee generation of $\mathcal{S}_n$ ). This is closely related to the following random set model. A random set $M \subseteq \mathbb{Z}^+$ is generated by including each $n \geq 1$ independently with probability $1/n$ . The sumset $\text{sumset}(M)$ is formed. Then at most four independent copies of $\text{sumset}(M)$ are needed before their mutual intersection is no longer infinite.

preprint2014arXiv

Intersection and mixing times for reversible chains

Suppose X and Y are two independent irreducible Markov chains on n states. We consider the intersection time, which is the first time their trajectories intersect. We show for reversible and lazy chains that the total variation mixing time is always upper bounded by the expected intersection time taken over the worst starting states. For random walks on trees we show the two quantities are equivalent. We obtain an expression for the expected intersection time in terms of the eigenvalues for reversible and transitive chains. For such chains we also show that it is up to constants the geometric mean of n and E[I], where I is the number of intersections up to the uniform mixing time. Finally for random walks on regular graphs we obtain sharp inequalities that relate the expected intersection time to maximum hitting time and mixing time.

preprint2014arXiv

Martingale defocusing and transience of a self-interacting random walk

Suppose that $(X,Y,Z)$ is a random walk in $\mathbb{Z}^3$ that moves in the following way: on the first visit to a vertex only $Z$ changes by $\pm 1$ equally likely, while on later visits to the same vertex $(X,Y)$ performs a two-dimensional random walk step. We show that this walk is transient thus answering a question of Benjamini, Kozma and Schapira. One important ingredient of the proof is a dispersion result for martingales.

preprint2014arXiv

Online Learning with Composite Loss Functions

We study a new class of online learning problems where each of the online algorithm's actions is assigned an adversarial value, and the loss of the algorithm at each step is a known and deterministic function of the values assigned to its recent actions. This class includes problems where the algorithm's loss is the minimum over the recent adversarial values, the maximum over the recent values, or a linear combination of the recent values. We analyze the minimax regret of this class of problems when the algorithm receives bandit feedback, and prove that when the minimum or maximum functions are used, the minimax regret is $\tilde Ω(T^{2/3})$ (so called hard online learning problems), and when a linear function is used, the minimax regret is $\tilde O(\sqrt{T})$ (so called easy learning problems). Previously, the only online learning problem that was known to be provably hard was the multi-armed bandit with switching costs.

preprint2014arXiv

Permuted Random Walk Exits Typically in Linear Time

Given a permutation sigma of the integers {-n,-n+1,...,n} we consider the Markov chain X_{sigma}, which jumps from k to sigma (k\pm 1) equally likely if k\neq -n,n. We prove that the expected hitting time of {-n,n} starting from any point is Theta(n) with high probability when sigma is a uniformly chosen permutation. We prove this by showing that with high probability, the digraph of allowed transitions is an Eulerian expander; we then utilize general estimates of hitting times in directed Eulerian expanders.

preprint2014arXiv

Projections of the natural measure for percolation fractals

We prove that, with probability 1, all orthogonal projections of the natural measure on a percolation fractal are absolutely continuous and (except for the horizontal and vertical projection) have Hölder continuous density.

preprint2014arXiv

Restrictions of Brownian motion

Let $\{ B(t) \colon 0\leq t\leq 1\}$ be a linear Brownian motion and let $\dim$ denote the Hausdorff dimension. Let $α>\frac12$ and $1\leq β\leq 2$ . We prove that, almost surely, there exists no set $A\subset[0,1]$ such that $\dim A>\frac12$ and $B\colon A\to\mathbb{R}$ is $α$ -Hölder continuous. The proof is an application of Kaufman's dimension doubling theorem. As a corollary of the above theorem, we show that, almost surely, there exists no set $A\subset[0,1]$ such that $\dim A>\fracβ{2}$ and $B\colon A\to\mathbb{R}$ has finite $β$ -variation. The zero set of $B$ and a deterministic construction witness that the above theorems give the optimal dimensions.

preprint2014arXiv

Rigidity and tolerance for perturbed lattices

A perturbed lattice is a point process $Π=\{x+Y_x:x\in \mathbb{Z}^d\}$ where the lattice points in $\mathbb{Z}^d$ are perturbed by i.i.d.\ random variables $\{Y_x\}_{x\in \mathbb{Z}^d}$ . A random point process $Π$ is said to be rigid if $|Π\cap B_0(1)|$ , the number of points in a ball, can be exactly determined given $Π\setminus B_0(1)$ , the points outside the ball. The process $Π$ is called deletion tolerant if removing one point of $Π$ yields a process with distribution indistinguishable from that of $Π$ . Suppose that $Y_x\sim N_d(0,σ^2 I)$ are Gaussian vectors with with $d$ independent components of variance $σ^2$ . Holroyd and Soo showed that in dimensions $d=1,2$ the resulting Gaussian perturbed lattice $Π$ is rigid and deletion intolerant. We show that in dimension $d\geq 3$ there exists a critical parameter $σ_r(d)$ such that $Π$ is rigid if $σ<σ_r$ and deletion tolerant (hence non-rigid) if $σ>σ_r$ .

preprint2014arXiv

Surprise probabilities in Markov chains

In a Markov chain started at a state $x$ , the hitting time $τ(y)$ is the first time that the chain reaches another state $y$ . We study the probability $\mathbf{P}_x(τ(y) = t)$ that the first visit to $y$ occurs precisely at a given time $t$ . Informally speaking, the event that a new state is visited at a large time $t$ may be considered a "surprise". We prove the following three bounds: 1) In any Markov chain with $n$ states, $\mathbf{P}_x(τ(y) = t) \le \frac{n}{t}$ . 2) In a reversible chain with $n$ states, $\mathbf{P}_x(τ(y) = t) \le \frac{\sqrt{2n}}{t}$ for $t \ge 4n + 4$ . 3) For random walk on a simple graph with $n \ge 2$ vertices, $\mathbf{P}_x(τ(y) = t) \le \frac{4e \log n}{t}$ . We construct examples showing that these bounds are close to optimal. The main feature of our bounds is that they require very little knowledge of the structure of the Markov chain. To prove the bound for random walk on graphs, we establish the following estimate conjectured by Aldous, Ding and Oveis-Gharan (private communication): For random walk on an $n$ -vertex graph, for every initial vertex $x$ , $\sum_y \left( \sup_{t \ge 0} p^t(x, y) \right) = O(\log n).$

preprint2014arXiv

Wald for non-stopping times: The rewards of impatient prophets

Let $X_1,X_2,\ldots$ be independent identically distributed nonnegative random variables. Wald's identity states that the random sum $S_T:=X_1+\cdots+X_T$ has expectation $E(T)) E(X_1)$ provided $T$ is a stopping time. We prove here that for any $1<α\leq 2$ , if $T$ is an arbitrary nonnegative random variable, then $S_T$ has finite expectation provided that $X_1$ has finite $α$ -moment and $T$ has finite $1/(α-1)$ -moment. We also prove a variant in which $T$ is assumed to have a finite exponential moment. These moment conditions are sharp in the sense that for any i.i.d.\ sequence $X_i$ violating them, there is a $T$ satisfying the given condition for which $S_T$ (and, in fact, $X_T$ ) has infinite expectation. An interpretation of this is given in terms of a prophet being more rewarded than a gambler when a certain impatience restriction is imposed.

preprint2013arXiv

Bandits with Switching Costs: T^{2/3} Regret

We study the adversarial multi-armed bandit problem in a setting where the player incurs a unit cost each time he switches actions. We prove that the player's $T$ -round minimax regret in this setting is $\widetildeΘ(T^{2/3})$ , thereby closing a fundamental gap in our understanding of learning with bandit feedback. In the corresponding full-information version of the problem, the minimax regret is known to grow at a much slower rate of $Θ(\sqrt{T})$ . The difference between these two rates provides the \emph{first} indication that learning with bandit feedback can be significantly harder than learning with full-information feedback (previous results only showed a different dependence on the number of actions, but not on $T$ .) In addition to characterizing the inherent difficulty of the multi-armed bandit problem with switching costs, our results also resolve several other open problems in online learning. One direct implication is that learning with bandit feedback against bounded-memory adaptive adversaries has a minimax regret of $\widetildeΘ(T^{2/3})$ . Another implication is that the minimax regret of online learning in adversarial Markov decision processes (MDPs) is $\widetildeΘ(T^{2/3})$ . The key to all of our results is a new randomized construction of a multi-scale random walk, which is of independent interest and likely to prove useful in additional settings.

preprint2013arXiv

Chip-Firing and Rotor-Routing on Directed Graphs

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 open problems.

preprint2013arXiv

Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures

Let X_1 ,..., X_n be a collection of binary valued random variables and let f : {0,1}^n -> R be a Lipschitz function. Under a negative dependence hypothesis known as the {\em strong Rayleigh} condition, we show that f - E f satisfies a concentration inequality generalizing the classical Gaussian concentration inequality for sums of independent Bernoullis: P (S_n - E S_n > a) < exp (-2 a^2 / n). The class of strong Rayleigh measures includes determinantal measures, weighted uniform matroids and exclusion measures; some familiar examples from these classes are generalized negative binomials and spanning tree measures. For instance, the number of vertices of odd degree in a uniform random spanning tree of a graph satisfies a Gaussian concentration inequality with n replaced by |V|, the number of vertices. We also prove a continuous version for concentration of Lipschitz functionals of a determinantal point process.

preprint2013arXiv

Dimension of Fractional Brownian motion with variable drift

Let $X$ be a fractional Brownian motion in $\mathbb{R}^d$ . For any Borel function $f:[0,1] \to \mathbb{R}^d$ , we express the Hausdorff dimension of the image and the graph of $X+f$ in terms of $f$ . This is new even for the case of Brownian motion and continuous $f$ , where it was known that this dimension is almost surely constant. The expression involves an adaptation of the parabolic dimension previously used by Taylor and Watson to characterize polarity for the heat equation. In the case when the graph of $f$ is a self-affine McMullen-Bedford carpet, we obtain an explicit formula for the dimension of the graph of $X+f$ in terms of the generating pattern. In particular, we show that it can be strictly bigger than the maximum of the Hausdorff dimension of the graph of $f$ and that of $X$ . Despite the random perturbation, the Minkowski and Hausdorff dimension of the graph of $X+f$ can disagree.

preprint2013arXiv

Escape rates for rotor walk in Z^d

Rotor walk is a deterministic analogue of random walk. We study its recurrence and transience properties on Z^d for the initial configuration of all rotors aligned. If n particles in turn perform rotor walks starting from the origin, we show that the number that escape (i.e., never return to the origin) is of order n in dimensions d>=3, and of order n/log(n) in dimension 2.

preprint2013arXiv

Harmonic maps on amenable groups and a diffusive lower bound for random walks

We prove diffusive lower bounds on the rate of escape of the random walk on infinite transitive graphs. Similar estimates hold for finite graphs, up to the relaxation time of the walk. Our approach uses nonconstant equivariant harmonic mappings taking values in a Hilbert space. For the special case of discrete, amenable groups, we present a more explicit proof of the Mok-Korevaar-Schoen theorem on the existence of such harmonic maps by constructing them from the heat flow on a Følner set.

preprint2013arXiv

Localization for controlled random walks and martingales

We consider controlled random walks that are martingales with uniformly bounded increments and nontrivial jump probabilities and show that such walks can be constructed so that P(S_n^u=0) decays at polynomial rate n^{-α} where α>0 can be arbitrarily small. We also show, by means of a general delocalization lemma for martingales, which is of independent interest, that slower than polynomial decay is not possible.

preprint2013arXiv

Markov type and threshold embeddings

For two metric spaces X and Y, say that X {threshold-embeds} into Y if there exist a number K > 0 and a family of Lipschitz maps $f_τ : X \to Y : τ> 0 \}$ such that for every $x,y \in X$ , \[ d_X(x,y) \geq τ=> d_Y(f_τ(x),f_τ(y)) \geq \|φ_τ\|_{\Lip} τ/K \] where $\|f_τ\|_{\Lip}$ denotes the Lipschitz constant of $f_τ$ . We show that if a metric space X threshold-embeds into a Hilbert space, then X has Markov type 2. As a consequence, planar graph metrics and doubling metrics have Markov type 2, answering questions of Naor, Peres, Schramm, and Sheffield. More generally, if a metric space X threshold-embeds into a p-uniformly smooth Banach space, then X has Markov type p. This suggests some non-linear analogs of Kwapien's theorem. For instance, a subset $X \subseteq L_1$ threshold-embeds into Hilbert space if and only if X has Markov type 2.

preprint2013arXiv

Mixing time for the Ising model: a uniform lower bound for all graphs

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(Δ)$ , where $Δ$ is the maximum degree and $f(Δ) = Θ(Δ\log^2 Δ)$ . Their result applies to more general spin systems, and in that generality, they showed that some dependence on $Δ$ is necessary. In this paper, we focus on the ferromagnetic Ising model and prove that the mixing time of Glauber dynamics on any $n$ -vertex graph is at least $(1/4+o(1))n \log n$ .

preprint2013arXiv

Mixing times are hitting times of large sets

We consider irreducible reversible discrete time Markov chains on a finite state space. Mixing times and hitting times are fundamental parameters of the chain. We relate them by showing that the mixing time of the lazy chain is equivalent to the maximum over initial states x and large sets A of the hitting time of A starting from x. We also prove that the first time when averaging over two consecutive time steps is close to stationarity is equivalent to the mixing time of the lazy version of the chain.

preprint2013arXiv

Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times

We study the behavior of random walk on dynamical percolation. In this model, the edges of a graph G are either open or closed and refresh their status at rate μ while at the same time a random walker moves on G at rate 1 but only along edges which are open. On the d-dimensional torus with side length n, we prove that in the subcritical regime, the mixing times for both the full system and the random walker are n^2/μ up to constants. We also obtain results concerning mean squared displacement and hitting times. Finally, we show that the usual recurrence transience dichotomy for the lattice Z^d holds for this model as well.

preprint2013arXiv

Sensitivity of mixing times

In this note, we demonstrate an instance of bounded-degree graphs of size $n$ , for which the total variation mixing time for the random walk is decreased by a factor of $\log n/ \log\log n$ if we multiply the edge-conductances by bounded factors in a certain way.

preprint2013arXiv

Total variation cutoff in a tree

We construct a family of trees on which a lazy simple random walk exhibits total variation cutoff. The main idea behind the construction is that hitting times of large sets should be concentrated around their means. For this sequence of trees we compute the mixing time, the relaxation time and the cutoff window.

Yuval Peres

Research overview

Is this your work?

125 publications

A basic homogenization problem for the ppp-Laplacian in Rd{\mathbb R}^dRd perforated along a sphere: L∞L^\inftyL∞ estimates

No cutoff in Spherically symmetric trees

Recurrence and windings of two revolving random walks

Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements

Consensus with Bounded Space and Minimal Communication

Induced graphs of uniform spanning forests

Poisson Boundaries of Lamplighter Groups: Proof of the Kaimanovich-Vershik Conjecture

Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

Biased infinity Laplacian Boundary Problem on finite graphs

Communication cost of consensus for nodes with limited memory

The string of diamonds is nearly tight for rumour spreading

Cutoff for the noisy voter model

Cutoff on all Ramanujan graphs

Diffusive estimates for random walks on stationary random graphs of polynomial growth

Estimating the Spectral Gap of a Reversible Markov Chain from a Short Trajectory

How many matrices can be spectrally balanced simultaneously?

Increasing subsequences of random walks

Laplacian growth, sandpiles and scaling limits

Mixing of the exclusion process with small bias

Non-universality for longest increasing subsequence of a random walk

Random walks on the random graph

Restrictions of Hölder continuous functions

Sensitivity of mixing times in Eulerian digraphs

Tight Lower Bounds for Multiplicative Weights Algorithmic Families

Towards Optimal Algorithms for Prediction with Expert Advice

Trace reconstruction with exp⁡(O(n1/3))\exp( O( n^{1/3} ) )exp(O(n1/3)) samples

Transience in growing subgraphs via evolving sets

Weighted sampling without replacement

When multiplicative noise stymies control

A Gaussian upper bound for martingale small-ball probabilities

Approval Voting and Incentives in Crowdsourcing

Bandit Convex Optimization: sqrt{T} Regret in One Dimension

Convergence of discrete Green functions with Neumann boundary conditions

Formation of an interface by competitive erosion

Heat diffusion with frozen boundary

Random Dirichlet series arising from records

Random walks colliding before getting trapped

The divisible sandpile at critical density

Topics in Markov chains: mixing and escape rate

Competing first passage percolation on random regular graphs

Four Random Permutations Conjugated by an Adversary Generate SnS_nSn​ with High Probability

Intersection and mixing times for reversible chains

Martingale defocusing and transience of a self-interacting random walk

Online Learning with Composite Loss Functions

Permuted Random Walk Exits Typically in Linear Time

Projections of the natural measure for percolation fractals

Restrictions of Brownian motion

Rigidity and tolerance for perturbed lattices

Surprise probabilities in Markov chains

Wald for non-stopping times: The rewards of impatient prophets

Bandits with Switching Costs: T^{2/3} Regret

Chip-Firing and Rotor-Routing on Directed Graphs

Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures

Dimension of Fractional Brownian motion with variable drift

Escape rates for rotor walk in Z^d

Harmonic maps on amenable groups and a diffusive lower bound for random walks

Localization for controlled random walks and martingales

Markov type and threshold embeddings

Mixing time for the Ising model: a uniform lower bound for all graphs

Mixing times are hitting times of large sets

Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times

Sensitivity of mixing times

Total variation cutoff in a tree

Anatomy of the giant component: The strictly supercritical regime

Continuum Percolation for Gaussian zeroes and Ginibre eigenvalues

Decayed MCMC Filtering

Detecting the trail of a random walker in a random scenery

Glauber Dynamics for the mean-field Potts Model

Hunter, Cauchy Rabbit, and Optimal Kakeya Sets

Mechanisms for Risk Averse Agents, Without Loss

Minkowski dimension of Brownian motion with drift

Mixing and relaxation time for Random Walk on Wreath Product Graphs

Mixing time of near-critical random graphs

Mixing time of the Card-Cyclic-to-Random shuffle

Non-amenable Cayley graphs of high girth have p_c < p_u and mean-field exponents

Self-interacting random walks

A basic homogenization problem for the $p$ -Laplacian in ${\mathbb R}^d$ perforated along a sphere: $L^\infty$ estimates

Trace reconstruction with $\exp( O( n^{1/3} ) )$ samples

Four Random Permutations Conjugated by an Adversary Generate $S_n$ with High Probability

All-Pairs Shortest Paths in $O(n^2)$ time with high probability