Catalog footprint

What is connected

125works
29topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

125 published item(s)

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.

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

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.

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

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

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

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.

preprint2012arXiv

Anatomy of the giant component: The strictly supercritical regime

In a recent work of the authors and Kim, we derived a complete description of the largest component of the Erdős-Rényi random graph $G(n,p)$ as it emerges from the critical window, i.e. for $p = (1+ε)/n$ where $ε^3 n \to\infty$ and $ε=o(1)$, in terms of a tractable contiguous model. Here we provide the analogous description for the supercritical giant component, i.e., the largest component of $G(n,p)$ for $p = λ/n$ where $λ>1$ is fixed. The contiguous model is roughly as follows: Take a random degree sequence and sample a random multigraph with these degrees to arrive at the kernel; Replace the edges by paths whose lengths are i.i.d. geometric variables to arrive at the 2-core; Attach i.i.d. Poisson Galton-Watson trees to the vertices for the final giant component. As in the case of the emerging giant, we obtain this result via a sequence of contiguity arguments at the heart of which are Kim's Poisson-cloning method and the Pittel-Wormald local limit theorems.

preprint2012arXiv

Continuum Percolation for Gaussian zeroes and Ginibre eigenvalues

We study continuum percolation on certain negatively dependent point processes on \R^2. Specifically, we study the Ginibre ensemble and the planar Gaussian zero process, which are the two main natural models of translation invariant point processes on the plane exhibiting local repulsion. For the Ginibre ensemble, we establish the uniqueness of infinite cluster in the supercritical phase. For the Gaussian zero process, we establish that a non-trivial critical radius exists, and we prove the uniqueness of infinite cluster in the supercritical regime.

preprint2012arXiv

Decayed MCMC Filtering

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 statistics. Exact computation of the posterior distribution is generally intractable for large discrete systems and for nonlinear continuous systems, so a good deal of effort has gone into developing robust approximation algorithms. This paper describes a simple stochastic approximation algorithm for filtering called {em decayed MCMC}. The algorithm applies Markov chain Monte Carlo sampling to the space of state trajectories using a proposal distribution that favours flips of more recent state variables. The formal analysis of the algorithm involves a generalization of standard coupling arguments for MCMC convergence. We prove that for any ergodic underlying Markov process, the convergence time of decayed MCMC with inverse-polynomial decay remains bounded as the length of the observation sequence grows. We show experimentally that decayed MCMC is at least competitive with other approximation algorithms such as particle filtering.

preprint2012arXiv

Detecting the trail of a random walker in a random scenery

Suppose that the vertices of the Euclidean lattice Z^d are endowed with a random scenery, obtained by tossing a fair coin at each vertex. A random walker, starting from the origin, replaces the coins along its path by i.i.d. biased coins. For which walks and dimensions can the resulting scenery be distinguished from the original scenery? We find the answer for simple random walk, where it does not depend on dimension, and for walks with a nonzero mean, where a transition occurs between dimensions three and four. We also answer this question for other types of graphs and walks, and raise several new questions.

preprint2012arXiv

Glauber Dynamics for the mean-field Potts Model

We study Glauber dynamics for the mean-field (Curie-Weiss) Potts model with $q\geq 3$ states and show that it undergoes a critical slowdown at an inverse-temperature $β_s(q)$ strictly lower than the critical $β_c(q)$ for uniqueness of the thermodynamic limit. The dynamical critical $β_s(q)$ is the spinodal point marking the onset of metastability. We prove that when $β<β_s(q)$ the mixing time is asymptotically $C(β, q) n \log n$ and the dynamics exhibits the cutoff phenomena, a sharp transition in mixing, with a window of order $n$. At $β=β_s(q)$ the dynamics no longer exhibits cutoff and its mixing obeys a power-law of order $n^{4/3}$. For $β>β_s(q)$ the mixing time is exponentially large in $n$. Furthermore, as $β\uparrow β_s$ with $n$, the mixing time interpolates smoothly from subcritical to critical behavior, with the latter reached at a scaling window of $O(n^{-2/3})$ around $β_s$. These results form the first complete analysis of mixing around the critical dynamical temperature --- including the critical power law --- for a model with a first order phase transition.

preprint2012arXiv

Hunter, Cauchy Rabbit, and Optimal Kakeya Sets

A planar set that contains a unit segment in every direction is called a Kakeya set. We relate these sets to a game of pursuit on a cycle $\Z_n$. A hunter and a rabbit move on the nodes of $\Z_n$ without seeing each other. At each step, the hunter moves to a neighbouring vertex or stays in place, while the rabbit is free to jump to any node. Adler et al (2003) provide strategies for hunter and rabbit that are optimal up to constant factors and achieve probability of capture in the first $n$ steps of order $1/\log n$. We show these strategies yield a Kakeya set consisting of $4n$ triangles with minimal area, (up to constant), namely $Θ(1/\log n)$. As far as we know, this is the first non-iterative construction of a boundary-optimal Kakeya set. Considering the continuum analog of the game yields a construction of a random Kakeya set from two independent standard Brownian motions $\{B(s): s \ge 0\}$ and $\{W(s): s \ge 0\}$. Let $τ_t:=\min\{s \ge 0: B(s)=t\}$. Then $X_t=W(τ_t)$ is a Cauchy process, and $K:=\{(a,X_t+at) : a,t \in [0,1]\}$ is a Kakeya set of zero area. The area of the $ε$-neighborhood of $K$ is as small as possible, i.e., almost surely of order $Θ(1/|\log ε|)$.

preprint2012arXiv

Mechanisms for Risk Averse Agents, Without Loss

Auctions in which agents' payoffs are random variables have received increased attention in recent years. In particular, recent work in algorithmic mechanism design has produced mechanisms employing internal randomization, partly in response to limitations on deterministic mechanisms imposed by computational complexity. For many of these mechanisms, which are often referred to as truthful-in-expectation, incentive compatibility is contingent on the assumption that agents are risk-neutral. These mechanisms have been criticized on the grounds that this assumption is too strong, because "real" agents are typically risk averse, and moreover their precise attitude towards risk is typically unknown a-priori. In response, researchers in algorithmic mechanism design have sought the design of universally-truthful mechanisms --- mechanisms for which incentive-compatibility makes no assumptions regarding agents' attitudes towards risk. We show that any truthful-in-expectation mechanism can be generically transformed into a mechanism that is incentive compatible even when agents are risk averse, without modifying the mechanism's allocation rule. The transformed mechanism does not require reporting of agents' risk profiles. Equivalently, our result can be stated as follows: Every (randomized) allocation rule that is implementable in dominant strategies when players are risk neutral is also implementable when players are endowed with an arbitrary and unknown concave utility function for money.

preprint2012arXiv

Minkowski dimension of Brownian motion with drift

We study fractal properties of the image and the graph of Brownian motion in $\R^d$ with an arbitrary c{à}dl{à}g drift $f$. We prove that the Minkowski (box) dimension of both the image and the graph of $B+f$ over $A\subseteq [0,1]$ are a.s.\ constants. We then show that for all $d\geq 1$ the Minkowski dimension of $(B+f)(A)$ is at least the maximum of the Minkowski dimension of $f(A)$ and that of $B(A)$. We also prove analogous results for the graph. For linear Brownian motion, if the drift $f$ is continuous and $A=[0,1]$, then the corresponding inequality for the graph is actually an equality.

preprint2012arXiv

Mixing and relaxation time for Random Walk on Wreath Product Graphs

Suppose that G and H are finite, connected graphs, G regular, X is a lazy random walk on G and Z is a reversible ergodic Markov chain on H. The generalized lamplighter chain X* associated with X and Z is the random walk on the wreath product H\wr G, the graph whose vertices consist of pairs (f,x) where f=(f_v)_{v\in V(G)} is a labeling of the vertices of G by elements of H and x is a vertex in G. In each step, X* moves from a configuration (f,x) by updating x to y using the transition rule of X and then independently updating both f_x and f_y according to the transition probabilities on H; f_z for z different of x,y remains unchanged. We estimate the mixing time of X* in terms of the parameters of H and G. Further, we show that the relaxation time of X* is the same order as the maximal expected hitting time of G plus |G| times the relaxation time of the chain on H.

preprint2012arXiv

Mixing time of near-critical random graphs

Let $\mathcal{C}_1$ be the largest component of the Erdős--Rényi random graph $\mathcal{G}(n,p)$. The mixing time of random walk on $\mathcal {C}_1$ in the strictly supercritical regime, $p=c/n$ with fixed $c>1$, was shown to have order $\log^2n$ by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, $p=(1+\varepsilon)/n$ where $λ=\varepsilon^3n$ is bounded, Nachmias and Peres proved that the mixing time on $\mathcal{C}_1$ is of order $n$. However, it was unclear how to interpolate between these results, and estimate the mixing time as the giant component emerges from the critical window. Indeed, even the asymptotics of the diameter of $\mathcal{C}_1$ in this regime were only recently obtained by Riordan and Wormald, as well as the present authors and Kim. In this paper, we show that for $p=(1+\varepsilon)/n$ with $λ=\varepsilon^3n\to\infty$ and $λ=o(n)$, the mixing time on $\mathcal{C}_1$ is with high probability of order $(n/λ)\log^2λ$. In addition, we show that this is the order of the largest mixing time over all components, both in the slightly supercritical and in the slightly subcritical regime [i.e., $p=(1-\varepsilon)/n$ with $λ$ as above].

preprint2012arXiv

Self-interacting random walks

Let $μ_1,... μ_k$ be $d$-dimensional probability measures in $\R^d$ with mean 0. At each step we choose one of the measures based on the history of the process and take a step according to that measure. We give conditions for transience of such processes and also construct examples of recurrent processes of this type. In particular, in dimension 3 we give the complete picture: every walk generated by two measures is transient and there exists a recurrent walk generated by three measures.

preprint2012arXiv

Shortest-weight paths in random regular graphs

Consider a random regular graph with degree $d$ and of size $n$. Assign to each edge an i.i.d. exponential random variable with mean one. In this paper we establish a precise asymptotic expression for the maximum number of edges on the shortest-weight paths between a fixed vertex and all the other vertices, as well as between any pair of vertices. Namely, for any fixed $d \geq 3$, we show that the longest of these shortest-weight paths has about $\hatα\log n$ edges where $\hatα$ is the unique solution of the equation $α\log(\frac{d-2}{d-1}α) - α= \frac{d-3}{d-2}$, for $α> \frac{d-1}{d-2}$.

preprint2012arXiv

The Isolation Time of Poisson Brownian Motions

Let the nodes of a Poisson point process move independently in $\R^d$ according to Brownian motions. We study the isolation time for a target particle that is placed at the origin, namely how long it takes until there is no node of the Poisson point process within distance $r$ of it. In the case when the target particle does not move, we obtain asymptotics for the tail {probability} which are tight up to constants in the exponent in dimension $d\geq 3$ and tight up to logarithmic factors in the exponent for dimensions $d=1,2$. In the case when the target particle is allowed to move independently of the Poisson point process, we show that the best strategy for the target to avoid isolation is to stay put.

preprint2012arXiv

The looping constant of Z^d

The looping constant $ξ(Z^d)$ is the expected number of neighbors of the origin that lie on the infinite loop-erased random walk in $Z^d$. Poghosyan, Priezzhev and Ruelle, and independently, Kenyon and Wilson, proved recently that $ξ(Z^2)=5/4$. We consider the infinite volume limits as $G \uparrow Z^d$ of three different statistics: (1) The expected length of the cycle in a uniform spanning unicycle of G; (2) The expected density of a uniform recurrent state of the abelian sandpile model on G; and (3) The ratio of the number of spanning unicycles of G to the number of rooted spanning trees of G. We show that all three limits are rational functions of the looping constant $ξ(Z^d)$. In the case of $Z^2$ their respective values are 8, 17/8 and 1/8.

preprint2012arXiv

The Multiplicative golden mean shift has infinite Hausdorff measure

In an earlier work, joint with R. Kenyon, we computed the Hausdorff dimension of the "multiplicative golden mean shift" defined as the set of all reals in [0,1] whose binary expansion (x_k) satisfies x_k x_{2k}=0 for all k=1,2... Here we show that this set has infinite Hausdorff measure in its dimension. A more precise result in terms of gauges in which the Hausdorff measure is infinite is also obtained.

preprint2012arXiv

Uniform mixing time for Random Walk on Lamplighter Graphs

Suppose that $\CG$ is a finite, connected graph and $X$ is a lazy random walk on $\CG$. The lamplighter chain $X^\diamond$ associated with $X$ is the random walk on the wreath product $\CG^\diamond = \Z_2 \wr \CG$, the graph whose vertices consist of pairs $(f,x)$ where $f$ is a labeling of the vertices of $\CG$ by elements of $\Z_2$ and $x$ is a vertex in $\CG$. There is an edge between $(f,x)$ and $(g,y)$ in $\CG^\diamond$ if and only if $x$ is adjacent to $y$ in $\CG$ and $f(z) = g(z)$ for all $z \neq x,y$. In each step, $X^\diamond$ moves from a configuration $(f,x)$ by updating $x$ to $y$ using the transition rule of $X$ and then sampling both $f(x)$ and $f(y)$ according to the uniform distribution on $\Z_2$; $f(z)$ for $z \neq x,y$ remains unchanged. We give matching upper and lower bounds on the uniform mixing time of $X^\diamond$ provided $\CG$ satisfies mild hypotheses. In particular, when $\CG$ is the hypercube $\Z_2^d$, we show that the uniform mixing time of $X^\diamond$ is $Θ(d 2^d)$. More generally, we show that when $\CG$ is a torus $\Z_n^d$ for $d \geq 3$, the uniform mixing time of $X^\diamond$ is $Θ(d n^d)$ uniformly in $n$ and $d$. A critical ingredient for our proof is a concentration estimate for the local time of random walk in a subset of vertices.

preprint2012arXiv

Uniformity of the uncovered set of random walk and cutoff for lamplighter chains

We show that the measure on markings of $\mathbf {Z}_n^d$, $d\geq3$, with elements of ${0,1}$ given by i.i.d. fair coin flips on the range $\mathcal {R}$ of a random walk $X$ run until time $T$ and 0 otherwise becomes indistinguishable from the uniform measure on such markings at the threshold $T=1/2T_{\mathrm {cov}}(\mathbf {Z}_n^d)$. As a consequence of our methods, we show that the total variation mixing time of the random walk on the lamplighter graph $\mathbf {Z}_2\wr \mathbf {Z}_n^d$, $d\geq3$, has a cutoff with threshold $1/2T_{\mathrm {cov}}(\mathbf {Z}_n^d)$. We give a general criterion under which both of these results hold; other examples for which this applies include bounded degree expander families, the intersection of an infinite supercritical percolation cluster with an increasing family of balls, the hypercube and the Caley graph of the symmetric group generated by transpositions. The proof also yields precise asymptotics for the decay of correlation in the uncovered set.

preprint2011arXiv

A power law of order 1/4 for critical mean-field Swendsen-Wang dynamics

The Swendsen-Wang dynamics is a Markov chain widely used by physicists to sample from the Boltzmann-Gibbs distribution of the Ising model. Cooper, Dyer, Frieze and Rue proved that on the complete graph K_n the mixing time of the chain is at most O(n^{1/2}) for all non-critical temperatures. In this paper we show that the mixing time is Theta(1) in high temperatures, Theta(log n) in low temperatures and Theta(n^{1/4}) at criticality. We also provide an upper bound of O(log n) for Swendsen-Wang dynamics for the q-state ferromagnetic Potts model on any tree with n vertices.

preprint2011arXiv

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

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on $n$ vertices whose edge weights are chosen independently and uniformly at random from $[0,1]$ is $O(n^2)$, in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of \emph{locally shortest paths} in such randomly weighted graphs is $O(n^2)$, in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in $O(\log^{2}n)$ expected time.

preprint2011arXiv

An isoperimetric inequality for the Wiener sausage

Let $(ξ(s))_{s\geq 0}$ be a standard Brownian motion in $d\geq 1$ dimensions and let $(D_s)_{s \geq 0}$ be a collection of open sets in $\R^d$. For each $s$, let $B_s$ be a ball centered at 0 with $\vol(B_s) = \vol(D_s)$. We show that $\E[\vol(\cup_{s \leq t}(ξ(s) + D_s))] \geq \E[\vol(\cup_{s \leq t}(ξ(s) + B_s))]$, for all $t$. In particular, this implies that the expected volume of the Wiener sausage increases when a drift is added to the Brownian motion.

preprint2011arXiv

Can extra updates delay mixing?

We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance or the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a Hamming metric, single-site dynamics mixes in O(n log n) steps on an n-vertex graph. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of log n compared to updates at uniform random locations on an n-vertex graph. Our result is especially effective in comparing block and single-site dynamics; it has already been used in works of Martinelli, Sinclair, Mossel, Sly, Ding, Lubetzky, and Peres in various combinations.

preprint2011arXiv

Cover times, blanket times, and majorizing measures

We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph $G$ is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on $G$, scaled by the number of edges in $G$. This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an O(1) factor for any graph, answering a question of Aldous and Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph, the blanket and cover times are within an O(1) factor. The best previous approximation factor for both these problems was $O((\log \log n)^2)$ for $n$-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).

preprint2011arXiv

Isolated zeros for Brownian motion with variable drift

It is well known that standard one-dimensional Brownian motion B(t) has no isolated zeros almost surely. We show that for any alpha<1/2 there are alpha-Hölder continuous functions f for which the process B-f has isolated zeros with positive probability. We also prove that for any continuous function f, the zero set of B-f has Hausdorff dimension at least 1/2 with positive probability, and 1/2 is an upper bound if f is 1/2-Hölder continuous or of bounded variation.

preprint2011arXiv

Local central limit theorems in stochastic geometry

We give a general local central limit theorem for the sum of two independent random variables, one of which satisfies a central limit theorem while the other satisfies a local central limit theorem with the same order variance. We apply this result to various quantities arising in stochastic geometry, including: size of the largest component for percolation on a box; number of components, number of edges, or number of isolated points, for random geometric graphs; covered volume for germ-grain coverage models; number of accepted points for finite-input random sequential adsorption; sum of nearest-neighbour distances for a random sample from a continuous multidimensional distribution.

preprint2011arXiv

Mixing of the upper triangular matrix walk

We study a natural random walk over the upper triangular matrices, with entries in the field $\Z_2$, generated by steps which add row $i+1$ to row $i$. We show that the mixing time of the lazy random walk is $O(n^2)$ which is optimal up to constants. Our proof makes key use of the linear structure of the group and extends to walks on the upper triangular matrices over the fields $\Z_q$ for $q$ prime.

preprint2011arXiv

Random laminations and multitype branching processes

We consider multitype branching processes arising in the study of random laminations of the disk. We classify these processes according to their subcritical or supercritical behavior and provide Kolmogorov-type estimates in the critical case corresponding to the random recursive lamination process of [1]. The proofs use the infinite dimensional Perron-Frobenius theory and quasi-stationary distributions.

preprint2011arXiv

Stable Poisson Graphs in One Dimension

Let each point of a homogeneous Poisson process on $\RR$ independently be equipped with a random number of stubs (half-edges) according to a given probability distribution $μ$ on the positive integers. We consider schemes based on Gale-Shapley stable marriage for perfectly matching the stubs to obtain a simple graph with degree distribution $μ$. We prove results on the existence of an infinite component and on the length of the edges, with focus on the case $μ(\{2\})=1$. In this case, for the random direction stable matching scheme introduced by Deijfen and Meester we prove that there is no infinite component, while for the stable matching of Deijfen, Häggström and Holroyd we prove that existence of an infinite component follows from a certain statement involving a {\em finite} interval, which is overwhelmingly supported by simulation evidence.

preprint2011arXiv

Tug-of-war and infinity Laplace equation with vanishing Neumann boundary condition

We study a version of the stochastic "tug-of-war" game, played on graphs and smooth domains, with the empty set of terminal states. We prove that, when the running payoff function is shifted by an appropriate constant, the values of the game after n steps converge in the continuous case and the case of finite graphs with loops. Using this we prove the existence of solutions to the infinity Laplace equation with vanishing Neumann boundary condition.

preprint2010arXiv

A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm

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 cyclic group $G$ and find that if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in $Θ(\sqrt{|G|})$ steps. Moreover, for the parallelized distinguished points algorithm on $J$ processors we find that $Θ(\sqrt{|G|}/J)$ steps suffices. These are the first proofs of the correct order bounds which do not assume that every step of the algorithm produces an i.i.d. sample from $G$.

preprint2010arXiv

Brownian motion with variable drift: 0-1 laws, hitting probabilities and Hausdorff dimension

By the Cameron--Martin theorem, if a function $f$ is in the Dirichlet space $D$, then $B+f$ has the same a.s. properties as standard Brownian motion, $B$. In this paper we examine properties of $B+f$ when $f \notin D$. We start by establishing a general 0-1 law, which in particular implies that for any fixed $f$, the Hausdorff dimension of the image and the graph of $B+f$ are constants a.s. (This 0-1 law applies to any Lévy process.) Then we show that if the function $f$ is Hölder$(1/2)$, then $B+f$ is intersection equivalent to $B$. Moreover, $B+f$ has double points a.s. in dimensions $d\le 3$, while in $d\ge 4$ it does not. We also give examples of functions which are Hölder with exponent less than $1/2$, that yield double points in dimensions greater than 4. Finally, we show that for $d \ge 2$, the Hausdorff dimension of the image of $B+f$ is a.s. at least the maximum of 2 and the dimension of the image of $f$.

preprint2010arXiv

Collisions of Random Walks

A recurrent graph $G$ has the infinite collision property if two independent random walks on $G$, started at the same point, collide infinitely often a.s. We give a simple criterion in terms of Green functions for a graph to have this property, and use it to prove that a critical Galton-Watson tree with finite variance conditioned to survive, the incipient infinite cluster in $\Z^d$ with $d \ge 19$ and the uniform spanning tree in $\Z^2$ all have the infinite collision property. For power-law combs and spherically symmetric trees, we determine precisely the phase boundary for the infinite collision property.

preprint2010arXiv

Diameters in supercritical random graphs via first passage percolation

We study the diameter of $C_1$, the largest component of the Erdős-Rényi random graph $G(n,p)$ in the emerging supercritical phase, i.e., for $p = \frac{1+ε}n$ where $ε^3 n \to \infty$ and $ε=o(1)$. This parameter was extensively studied for fixed $ε> 0$, yet results for $ε=o(1)$ outside the critical window were only obtained very recently. Prior to this work, Riordan and Wormald gave precise estimates on the diameter, however these did not cover the entire supercritical regime (namely, when $ε^3 n\to\infty$ arbitrarily slowly). Łuczak and Seierstad estimated its order throughout this regime, yet their upper and lower bounds differed by a factor of $1000/7$. We show that throughout the emerging supercritical phase, i.e. for any $ε=o(1)$ with $ε^3 n \to \infty$, the diameter of $C_1$ is with high probability asymptotic to $D(ε,n)=(3/ε)\log(ε^3 n)$. This constitutes the first proof of the asymptotics of the diameter valid throughout this phase. The proof relies on a recent structure result for the supercritical giant component, which reduces the problem of estimating distances between its vertices to the study of passage times in first-passage percolation. The main advantage of our method is its flexibility. It also implies that in the emerging supercritical phase the diameter of the 2-core of $C_1$ is w.h.p. asymptotic to $(2/3)D(ε,n)$, and the maximal distance in $C_1$ between any pair of kernel vertices is w.h.p. asymptotic to $(5/9)D(ε,n)$.

preprint2010arXiv

Finding Hidden Cliques in Linear Time with High Probability

We are given a graph $G$ with $n$ vertices, where a random subset of $k$ vertices has been made into a clique, and the remaining edges are chosen independently with probability $\tfrac12$. This random graph model is denoted $G(n,\tfrac12,k)$. The hidden clique problem is to design an algorithm that finds the $k$-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov uses spectral techniques to find the hidden clique with high probability when $k = c \sqrt{n}$ for a sufficiently large constant $c > 0$. Recently, an algorithm that solves the same problem was proposed by Feige and Ron. It has the advantages of being simpler and more intuitive, and of an improved running time of $O(n^2)$. However, the analysis in the paper gives success probability of only $2/3$. In this paper we present a new algorithm for finding hidden cliques that both runs in time $O(n^2)$, and has a failure probability that is less than polynomially small.

preprint2010arXiv

Hitting times for random walks with restarts

The time it takes a random walker in a lattice to reach the origin from another vertex $x$, has infinite mean. If the walker can restart the walk at $x$ at will, then the minimum expected hitting time $T(x,0)$ (minimized over restarting strategies) is finite; it was called the ``grade'' of $x$ by Dumitriu, Tetali and Winkler. They showed that, in a more general setting, the grade (a variant of the ``Gittins index'') plays a crucial role in control problems involving several Markov chains. Here we establish several conjectures of Dumitriu et al on the asymptotics of the grade in Euclidean lattices. In particular, we show that in the planar square lattice, $T(x,0)$ is asymptotic to $2|x|^2\log|x|$ as $|x| \to \infty$. The proof hinges on the local variance of the potential kernel $h$ being almost constant on the level sets of $h$. We also show how the same method yields precise second order asymptotics for hitting times of a random walk (without restarts) in a lattice disk.

preprint2010arXiv

Mobile Geometric Graphs: Detection, Coverage and Percolation

We consider the following dynamic Boolean model introduced by van den Berg, Meester and White (1997). At time 0, let the nodes of the graph be a Poisson point process in R^d with constant intensity and let each node move independently according to Brownian motion. At any time t, we put an edge between every pair of nodes if their distance is at most r. We study three features in this model: detection (the time until a target point---fixed or moving---is within distance r from some node of the graph), coverage (the time until all points inside a finite box are detected by the graph), and percolation (the time until a given node belongs to the infinite connected component of the graph). We obtain precise asymptotics for these features by combining ideas from stochastic geometry, coupling and multi-scale analysis.

preprint2010arXiv

New coins from old, smoothly

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 coin, $N$ times each, where $N$ may be random. The work of Keane and O'Brien (1994) implies that such a simulation scheme with the probability $¶_p(N<\infty)$ equal to 1 exists iff $f$ is continuous. Nacu and Peres (2005) proved that $f$ is real analytic in an open set $S \subset (0,1)$ iff such a simulation scheme exists with the probability $¶_p(N>n)$ decaying exponentially in $n$ for every $p \in S$. We prove that for $α>0$ non-integer, $f$ is in the space $C^α[0,1]$ if and only if a simulation scheme as above exists with $¶_p(N>n) \le C (Δ_n(p))^α$, where $Δ_n(x)\eqbd \max \{\sqrt{x(1-x)/n},1/n \}$. The key to the proof is a new result in approximation theory: Let $\B_n$ be the cone of univariate polynomials with nonnegative Bernstein coefficients of degree $n$. We show that a function $f:[0,1] \to (0,1)$ is in $C^α[0,1]$ if and only if $f$ has a series representation $\sum_{n=1}^\infty F_n$ with $F_n \in \B_n$ and $\sum_{k>n} F_k(x) \le C(Δ_n(x))^α$ for all $ x \in [0,1]$ and $n \ge 1$. We also provide a counterexample to a theorem stated without proof by Lorentz (1963), who claimed that if some $ϕ_n \in \B_n$ satisfy $|f(x)-ϕ_n(x)| \le C (Δ_n(x))^α$ for all $ x \in [0,1]$ and $n \ge 1$, then $f \in C^α[0,1]$.

preprint2010arXiv

The critical Ising model on trees, concave recursions and nonlinear capacity

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 limit as the boundary recedes to infinity. We obtain exact capacity criteria that govern behavior at critical temperatures. For plus boundary conditions, an $L^3$ capacity arises. In particular, on a spherically symmetric tree that has $n^αb^n$ vertices at level $n$ (up to bounded factors), we prove that there is a unique Gibbs measure for the ferromagnetic Ising model at the relevant critical temperature if and only if $α\le1/2$. Our proofs are based on a new link between nonlinear recursions on trees and $L^p$ capacities.

preprint2010arXiv

The evolution of the cover time

The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovasz and Vu yielded a (log log n)^2 polynomial time approximation. We refine this upper bound, and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdos-Renyi random graph G(n,c/n) in the supercritical regime with c>1 fixed, is asymptotic to f(c) n \log^2 n, where f(c) tends to 1 as c tends to 1. However, our new bound implies that the cover time for the critical Erdos-Renyi random graph G(n,1/n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube {0,1}^n, on high-girth expanders, and on tori Z_n^d for fixed large d. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman, is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4.

preprint2010arXiv

Thick points of the Gaussian free field

Let $U\subseteq\mathbf{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)\cdot \nabla g(x)\,dx$. The set $T(a;U)$ of $a$-thick points of $F$ consists of those $z\in U$ such that the average of $F$ on a disk of radius $r$ centered at $z$ has growth $\sqrt{a/π}\log\frac{1}{r}$ as $r\to 0$. We show that for each $0\leq a\leq2$ the Hausdorff dimension of $T(a;U)$ is almost surely $2-a$, that $ν_{2-a}(T(a;U))=\infty$ when $0<a\leq2$ and $ν_2(T(0;U))=ν_2(U)$ almost surely, where $ν_α$ is the Hausdorff-$α$ measure, and that $T(a;U)$ is almost surely empty when $a>2$. Furthermore, we prove that $T(a;U)$ is invariant under conformal transformations in an appropriate sense. The notion of a thick point is connected to the Liouville quantum gravity measure with parameter $γ$ given formally by $Γ(dz)=e^{\sqrt{2π}γF(z)}\,dz$ considered by Duplantier and Sheffield.

preprint2009arXiv

Biased tug-of-war, the biased infinity Laplacian, and comparison with exponential cones

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 β\in\R there exists a unique viscosity solution to the β-biased infinity Laplacian equation β|\nabla u| + Δ_\infty u=0 on U that extends F, where Δ_\infty u= |\nabla u|^{-2} \sum_{i,j} u_{x_i}u_{x_ix_j} u_{x_j}. In the proof, we extend the tug-of-war ideas of Peres, Schramm, Sheffield and Wilson, and define the β-biased \eps-game as follows. The starting position is x_0 \in U. At the k^\text{th} step the two players toss a suitably biased coin (in our key example, player I wins with odds of \exp(β\eps) to 1), and the winner chooses x_k with d(x_k,x_{k-1}) < \eps. The game ends when x_k \in \partial{U}, and player II pays the amount F(x_k) to player I. We prove that the value u^{\eps}(x_0) of this game exists, and that \|u^\eps - u\|_\infty \to 0 as \eps \to 0, where u is the unique extension of F to \overline{U} that satisfies comparison with β-exponential cones. Comparison with exponential cones is a notion that we introduce here, and generalizing a theorem of Crandall, Evans and Gariepy regarding comparison with linear cones, we show that a continuous function satisfies comparison with β-exponential cones if and only if it is a viscosity solution to the β-biased infinity Laplacian equation.

preprint2009arXiv

Convolutions of Cantor measures without resonance

Denote by $μ_a$ the distribution of the random sum $(1-a) \sum_{j=0}^\infty ω_j a^j$, where $P(ω_j=0)=P(ω_j=1)=1/2$ and all the choices are independent. For $0<a<1/2$, the measure $μ_a$ is supported on $C_a$, the central Cantor set obtained by starting with the closed united interval, removing an open central interval of length $(1-2a)$, and iterating this process inductively on each of the remaining intervals. We investigate the convolutions $μ_a * (μ_b \circ S_λ^{-1})$, where $S_λ(x)=λx$ is a rescaling map. We prove that if the ratio $\log b/\log a$ is irrational and $λ\neq 0$, then \[ D(μ_a *(μ_b\circ S_λ^{-1})) = \min(\dim_H(C_a)+\dim_H(C_b),1), \] where $D$ denotes any of correlation, Hausdorff or packing dimension of a measure. We also show that, perhaps surprisingly, for uncountably many values of $λ$ the convolution $μ_{1/4} *(μ_{1/3}\circ S_λ^{-1})$ is a singular measure, although $\dim_H(C_{1/4})+\dim_H(C_{1/3})>1$ and $\log (1/3) /\log (1/4)$ is irrational.

preprint2009arXiv

Growth Rates and Explosions in Sandpiles

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 particle to each neighbor. We find that with constant background height h <= 2d-2, the diameter of the set of sites that topple has order n^{1/d}. This was previously known only for h<d. Our proof uses a strong form of the least action principle for sandpiles, and a novel method of background modification. We can extend this diameter bound to certain backgrounds in which an arbitrarily high fraction of sites have height 2d-1. On the other hand, we show that if the background height 2d-2 is augmented by 1 at an arbitrarily small fraction of sites chosen independently at random, then adding finitely many particles creates an explosion (a sandpile that never stabilizes).

preprint2009arXiv

Mixing time of critical Ising model on trees is polynomial in the height

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 inverse-temperature $β_c$, the inverse-gap is bounded for $β< β_c$, polynomial in the surface area for $β= β_c$ and exponential in it for $β> β_c$. This has been proved for $\Z^2$ except at criticality. So far, the only underlying geometry where the critical behavior has been confirmed is the complete graph. Recently, the dynamics for the Ising model on a regular tree, also known as the Bethe lattice, has been intensively studied. The facts that the inverse-gap is bounded for $β< β_c$ and exponential for $β> β_c$ were established, where $β_c$ is the critical spin-glass parameter, and the tree-height $h$ plays the role of the surface area. In this work, we complete the picture for the inverse-gap of the Ising model on the $b$-ary tree, by showing that it is indeed polynomial in $h$ at criticality. The degree of our polynomial bound does not depend on $b$, and furthermore, this result holds under any boundary condition. We also obtain analogous bounds for the mixing-time of the chain. In addition, we study the near critical behavior, and show that for $β> β_c$, the inverse-gap and mixing-time are both $\exp[Θ((β-β_c) h)]$.

preprint2009arXiv

Reconstruction on Trees: Exponential Moment Bounds for Linear Estimators

Consider a Markov chain $(ξ_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 denote by $L_n$ the level-$n$ vertices of $T$. Assume $M$ has a real second-largest (in absolute value) eigenvalue $λ$ with corresponding real eigenvector $ν\neq 0$. Letting $σ_v = ν_{ξ_v}$, we consider the following root-state estimator, which was introduced by Mossel and Peres (2003) in the context of the "recontruction problem" on trees: \begin{equation*} S_n = (bλ)^{-n} \sum_{x\in L_n} σ_x. \end{equation*} As noted by Mossel and Peres, when $bλ^2 > 1$ (the so-called Kesten-Stigum reconstruction phase) the quantity $S_n$ has uniformly bounded variance. Here, we give bounds on the moment-generating functions of $S_n$ and $S_n^2$ when $bλ^2 > 1$. Our results have implications for the inference of evolutionary trees.

preprint2009arXiv

Scaling Limits for Internal Aggregation Models with Multiple Sources

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 particles perform deterministic analogues of random walks; and the divisible sandpile, in which each site distributes its excess mass equally among its neighbors. As the lattice spacing tends to zero, all three models are found to have the same scaling limit, which we describe as the solution to a certain PDE free boundary problem in R^d. In particular, internal DLA has a deterministic scaling limit. We find that the scaling limits are quadrature domains, which have arisen independently in many fields such as potential theory and fluid dynamics. Our results apply both to the case of multiple point sources and to the Diaconis-Fulton smash sum of domains.

preprint2008arXiv

Censored Glauber Dynamics for the mean field Ising Model

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 ($β< 1$) the mixing time is $Θ(n\log n)$, whereas at low temperature ($β> 1$) it is $\exp(Θ(n))$. Recently, Levin, Luczak and Peres considered a censored version of this dynamics, which is restricted to non-negative magnetization. They proved that for fixed $β> 1$, the mixing-time of this model is $Θ(n\log n)$, analogous to the high-temperature regime of the original dynamics. Furthermore, they showed \emph{cutoff} for the original dynamics for fixed $β<1$. The question whether the censored dynamics also exhibits cutoff remained unsettled. In a companion paper, we extended the results of Levin et al. into a complete characterization of the mixing-time for the Currie-Weiss model. Namely, we found a scaling window of order $1/\sqrt{n}$ around the critical temperature $β_c=1$, beyond which there is cutoff at high temperature. However, determining the behavior of the censored dynamics outside this critical window seemed significantly more challenging. In this work we answer the above question in the affirmative, and establish the cutoff point and its window for the censored dynamics beyond the critical window, thus completing its analogy to the original dynamics at high temperature. Namely, if $β= 1 + δ$ for some $δ> 0$ with $δ^2 n \to \infty$, then the mixing-time has order $(n / δ)\log(δ^2 n)$. The cutoff constant is $(1/2+[2(ζ^2 β/ δ- 1)]^{-1})$, where $ζ$ is the unique positive root of $g(x)=\tanh(βx)-x$, and the cutoff window has order $n / δ$.

preprint2008arXiv

Resonance between Cantor sets

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 prove that if $\log b/\log a$ is irrational, then \[ \dim(C_a+C_b) = \min(\dim(C_a) + \dim(C_b),1), \] where $\dim$ is Hausdorff dimension. More generally, given two self-similar sets $K,K'$ in $\RR$ and a scaling parameter $s>0$, if the dimension of the arithmetic sum $K+sK'$ is strictly smaller than $\dim(K)+\dim(K') \le 1$ (``geometric resonance''), then there exists $r<1$ such that all contraction ratios of the similitudes defining $K$ and $K'$ are powers of $r$ (``algebraic resonance''). Our method also yields a new result on the projections of planar self-similar sets generated by an iterated function system that includes a scaled irrational rotation.

preprint2008arXiv

Tug-of-war and the infinity Laplacian

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 all open subsets U of X that do not intersect Y. This was previously known only for bounded domains R^n, in which case u is infinity harmonic, that is, a viscosity solution to Delta_infty u = 0. We also prove the first general uniqueness results for Delta_infty u = g on bounded subsets of R^n (when g is uniformly continuous and bounded away from zero), and analogous results for bounded length spaces. The proofs rely on a new game-theoretic description of u. Let u^epsilon(x) be the value of the following two-player zero-sum game, called tug-of-war: fix x_0=x \in X minus Y. At the kth turn, the players toss a coin and the winner chooses an x_k with d(x_k, x_{k-1})< epsilon. The game ends when x_k is in Y, and player one's payoff is F(x_k) - (epsilon^2/2) sum_{i=0}^{k-1} g(x_i) We show that the u^εconverge uniformly to u as epsilon tends to zero. Even for bounded domains in R^n, the game theoretic description of infinity-harmonic functions yields new intuition and estimates; for instance, we prove power law bounds for infinity-harmonic functions in the unit disk with boundary values supported in a delta-neighborhood of a Cantor set on the unit circle.

preprint2007arXiv

Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation

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 connected by an edge iff their difference $|a-b|$ is in the sequence ${n_k}$. Y. Katznelson found a connection to a Diophantine approximation problem (also due to Erdos): the existence of $x$ in $(0,1)$ such that all the multiples $n_j x$ are at least distance $δ(x)>0$ from the set of integers. Katznelson bounded the chromatic number of $G$ by $Cr^{-2}|\log r|$. We apply the Lovász local lemma to establish that $δ(x)>cr|\log r|^{-1}$ for some $x$, which implies that the chromatic number of $G$ is at most $Cr^{-1} |\log r|$. This is sharp up to the logarithmic factor.

preprint2006arXiv

Determinantal Processes and Independence

We give a probabilistic introduction to determinantal and permanental point processes. Determinantal processes arise in physics (fermions, eigenvalues of random matrices) and in combinatorics (nonintersecting paths, random spanning trees). They have the striking property that the number of points in a region $D$ is a sum of independent Bernoulli random variables, with parameters which are eigenvalues of the relevant operator on $L^2(D)$. Moreover, any determinantal process can be represented as a mixture of determinantal projection processes. We give a simple explanation for these known facts, and establish analogous representations for permanental processes, with geometric variables replacing the Bernoulli variables. These representations lead to simple proofs of existence criteria and central limit theorems, and unify known results on the distribution of absolute values in certain processes with radially symmetric distributions.

preprint2005arXiv

Spherical Asymptotics for the Rotor-Router Model in Z^d

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 aggregation. We prove an isoperimetric inequality for the exit time of simple random walk from a finite region in Z^d, and use this to prove that the shape of the rotor-router aggregation model in Z^d, suitably rescaled, converges to a Euclidean ball in R^d.

preprint2005arXiv

Zeros of the i.i.d. Gaussian power series: a conformally invariant determinantal process

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 intensity can be written as a minor of the Bergman kernel. We show that the number of zeros of f in a disk of radius r about the origin has the same distribution as the sum of independent {0,1}-valued random variables X_k, where P(X_k=1)=r^{2k}. Moreover, the set of absolute values of the zeros of f has the same distribution as the set {U_k^{1/2k}} where the U_k are i.i.d. random variables uniform in [0,1]. The repulsion between zeros can be studied via a dynamic version where the coefficients perform Brownian motion; we show that this dynamics is conformally invariant.

preprint2004arXiv

Glauber Dynamics on Trees and Hyperbolic Graphs

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 show that the relaxation time (defined as the reciprocal of the spectral gap $|λ_1-λ_2|$) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in $n$. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time $τ_2$ satisfies $τ_2=O(1)$, then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.

preprint2004arXiv

Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces

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 to $X$, the distance $D_t$ from $f(Z_0)$ to $f(Z_t)$ satisfies $\E(D_t^2) \le K^2 t \E(D_1^2)$ for some $K=K(X)<\infty$. This notion is due to K. Ball (1992), who showed its importance for the Lipschitz extension problem. However until now, only Hilbert space (and its bi-Lipschitz equivalents) were known to have Markov type 2. We show that every Banach space with modulus of smoothness of power type 2 (in particular, $L_p$ for $p>2$) has Markov type 2; this proves a conjecture of Ball. We also show that trees, hyperbolic groups and simply connected Riemannian manifolds of pinched negative curvature have Markov type 2. Our results are applied to settle several conjectures on Lipschitz extensions and embeddings. In particular, we answer a question posed by Johnson and Lindenstrauss in 1982, by showing that for $1<q<2<p<\infty$, any Lipschitz mapping from a subset of $L_p$ to $L_q$ has a Lipschitz extension defined on all of $L_p$.

preprint2004arXiv

The sharp Hausdorff measure condition for length of projections

In a recent paper, Pertti Mattila asked which gauge functions $ϕ$ have the property that for any planar Borel set $A$ with positive Hausdorff measure in gauge $ϕ$, the projection of $A$ to almost every line has positive length. We show that integrability near zero of $ϕ(r)/(r^2)$, which is known to be sufficient for this property, is also necessary if $ϕ$ is regularly varying. Our proof is based on a random construction adapted to the gauge function.