We consider the sorted top-$k$ problem whose goal is to recover the top-$k$ items with the correct order out of $n$ items using pairwise comparisons. In many applications, multiple rounds of interaction can be costly. We restrict our attention to alg
orithms with a constant number of rounds $r$ and try to minimize the sample complexity, i.e. the number of comparisons. When the comparisons are noiseless, we characterize how the optimal sample complexity depends on the number of rounds (up to a polylogarithmic factor for general $r$ and up to a constant factor for $r=1$ or 2). In particular, the sample complexity is $Theta(n^2)$ for $r=1$, $Theta(nsqrt{k} + n^{4/3})$ for $r=2$ and $tilde{Theta}left(n^{2/r} k^{(r-1)/r} + nright)$ for $r geq 3$. We extend our results of sorted top-$k$ to the noisy case where each comparison is correct with probability $2/3$. When $r=1$ or 2, we show that the sample complexity gets an extra $Theta(log(k))$ factor when we transition from the noiseless case to the noisy case. We also prove new results for top-$k$ and sorting in the noisy case. We believe our techniques can be generally useful for understanding the trade-off between round complexities and sample complexities of rank aggregation problems.
We prove the quantitative equivalence of two important geometrical conditions, pertaining to the regularity of a domain $Omegasubsetmathbb{R}^N$. These are: (i) the uniform two-sided supporting sphere condition, and (ii) the Lipschitz continuity of t
he outward unit normal vector. In particular, the answer to the question posed in our title is: Those domains, whose unit normal is well defined and has Lipschitz constant one. We also offer an extension to infinitely dimensional spaces $L^p$, $pin (1,infty)$.
We prove new results on lazy random walks on finite graphs. To start, we obtain new estimates on return probabilities $P^t(x,x)$ and the maximum expected hitting time $t_{rm hit}$, both in terms of the relaxation time. We also prove a discrete-time v
ersion of the first-named authors ``Meeting time lemma~ that bounds the probability of random walk hitting a deterministic trajectory in terms of hitting times of static vertices. The meeting time result is then used to bound the expected full coalescence time of multiple random walks over a graph. This last theorem is a discrete-time version of a result by the first-named author, which had been previously conjectured by Aldous and Fill. Our bounds improve on recent results by Lyons and Oveis-Gharan; Kanade et al; and (in certain regimes) Cooper et al.
We consider dynamical percolation on the $d$-dimensional discrete torus of side length $n$, $mathbb{Z}_n^d$, where each edge refreshes its status at rate $mu=mu_nle 1/2$ to be open with probability $p$. We study random walk on the torus, where the wa
lker moves at rate $1/(2d)$ along each open edge. In earlier work of two of the authors with A. Stauffer, it was shown that in the subcritical case $p<p_c(mathbb{Z}^d)$, the (annealed) mixing time of the walk is $Theta(n^2/mu)$, and it was conjectured that in the supercritical case $p>p_c(mathbb{Z}^d)$, the mixing time is $Theta(n^2+1/mu)$; here the implied constants depend only on $d$ and $p$. We prove a quenched (and hence annealed) version of this conjecture up to a poly-logarithmic factor under the assumption $theta(p)>1/2$. Our proof is based on percolation results (e.g., the Grimmett-Marstrand Theorem) and an analysis of the volume-biased evolving set process; the key point is that typically, the evolving set has a substantial intersection with the giant percolation cluster at many times. This allows us to use precise isoperimetric properties of the cluster (due to G. Pete) to infer rapid growth of the evolving set, which in turn yields the upper bound on the mixing time.
We consider random walk on dynamical percolation on the discrete torus $mathbb{Z}_n^d$. In previous work, mixing times of this process for $p<p_c(mathbb{Z}^d)$ were obtained in the annealed setting where one averages over the dynamical percolation en
vironment. Here we study exit times in the quenched setting, where we condition on a typical dynamical percolation environment. We obtain an upper bound for all $p$ which for $p<p_c$ matches the known lower bound.
We first study a model, introduced recently in cite{ES}, of a critical branching random walk in an IID random environment on the $d$-dimensional integer lattice. The walker performs critical (0-2) branching at a lattice point if and only if there is
no `obstacle placed there. The obstacles appear at each site with probability $pin [0,1)$ independently of each other. We also consider a similar model, where the offspring distribution is subcritical. Let $S_n$ be the event of survival up to time $n$. We show that on a set of full $mathbb P_p$-measure, as $ntoinfty$, (i) Critical case: P^{omega}(S_n)simfrac{2}{qn}; (ii) Subcritical case: P^{omega}(S_n)= expleft[left( -C_{d,q}cdot frac{n}{(log n)^{2/d}} right)(1+o(1))right], where $C_{d,q}>0$ does not depend on the branching law. Hence, the model exhibits `self-averaging in the critical case but not in the subcritical one. I.e., in (i) the asymptotic tail behavior is the same as in a toy model where space is removed, while in (ii) the spatial survival probability is larger than in the corresponding toy model, suggesting spatial strategies. We utilize a spine decomposition of the branching process as well as some known results on random walks.
The spectral gap $gamma$ 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$ m
ay be observed. Hsu, Kontorovich, and Szepesvari (2015) considered the problem of estimating $gamma$ from this data. Let $pi$ be the stationary distribution of $P$, and $pi_star = min_x pi(x)$. They showed that, if $t = tilde{O}bigl(frac{1}{gamma^3 pi_star}bigr)$, then $gamma$ can be estimated to within multiplicative constants with high probability. They also proved that $tilde{Omega}bigl(frac{n}{gamma}bigr)$ steps are required for precise estimation of $gamma$. We show that $tilde{O}bigl(frac{1}{gamma pi_star}bigr)$ steps of the chain suffice to estimate $gamma$ up to multiplicative constants with high probability. When $pi$ is uniform, this matches (up to logarithmic corrections) the lower bound of Hsu, Kontorovich, and Szepesvari.
We analyze the mixing behavior of the biased exclusion process on a path of length $n$ as the bias $beta_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 pr
ocess with constant bias. As the bias increases, the mixing time undergoes two phase transitions: one when $beta_n$ is of order $1/n$, and the other when $beta_n$ is order $log n/n$.
We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Ko
zma 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 $( u {bf d})^{-1}log n pm (log n)^{1/2+o(1)}$, where $ u$ and ${bf d}$ are the speed of random walk and dimension of harmonic measure on a ${rm Poisson}(lambda)$-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.
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.
