The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties

Finite sample properties of random covariance-type matrices have been the subject of much research. In this paper we focus on the lower tail of such a matrix, and prove that it is subgaussian under a simple fourth moment assumption on the one-dimensional marginals of the random vectors. A similar result holds for more general sums of random positive semidefinite matrices, and the (relatively simple) proof uses a variant of the so-called PAC-Bayesian method for bounding empirical processes. We give two applications of the main result. In the first one we obtain a new finite-sample bound for ordinary least squares estimator in linear regression with random design. Our result is model-free, requires fairly weak moment assumptions and is almost optimal. Our second application is to bounding restricted eigenvalue constants of certain random ensembles with heavy tails. These constants are important in the analysis of problems in Compressed Sensing and High Dimensional Statistics, where one recovers a sparse vector from a small umber of linear measurements. Our result implies that heavy tails still allow for the fast recovery rates found in efficient methods such as the LASSO and the Dantzig selector. Along the way we strengthen, with a fairly short argument, a recent result of Rudelson and Zhou on the restricted eigenvalue property.

Stochastic processes with random contexts: a characterization, and adaptive estimators for the transition probabilities

This paper introduces the concept of random context representations for the transition probabilities of a finite-alphabet stochastic process. Processes with these representations generalize context tree processes (a.k.a. variable length Markov chains), and are proven to coincide with processes whose transition probabilities are almost surely continuous functions of the (infinite) past. This is similar to a classical result by Kalikow about continuous transition probabilities. Existence and uniqueness of a minimal random context representation are proven, and an estimator of the transition probabilities based on this representation is shown to have very good pastwise adaptativity properties. In particular, it achieves minimax performance, up to logarithmic factors, for binary renewal processes with bounded $2+gamma$ moments.

Mean field conditions for coalescing random walks

The main results in this paper are about the full coalescence time $mathsf{C}$ of a system of coalescing random walks over a finite graph $G$. Letting $mathsf{m}(G)$ denote the mean meeting time of two such walkers, we give sufficient conditions under which $mathbf{E}[mathsf{C}]approx 2mathsf{m}(G)$ and $mathsf{C}/mathsf{m}(G)$ has approximately the same law as in the mean field setting of a large complete graph. One of our theorems is that mean field behavior occurs over all vertex-transitive graphs whose mixing times are much smaller than $mathsf{m}(G)$; this nearly solves an open problem of Aldous and Fill and also generalizes results of Cox for discrete tori in $dgeq2$ dimensions. Other results apply to nonreversible walks and also generalize previous theorems of Durrett and Cooper et al. Slight extensions of these results apply to voter model consensus times, which are related to coalescing random walks via duality. Our main proof ideas are a strengthening of the usual approximation of hitting times by exponential random variables, which give results for nonstationary initial states; and a new general set of conditions under which we can prove that the hitting time of a union of sets behaves like a minimum of independent exponentials. In particular, this will show that the first meeting time among $k$ random walkers has mean $approxmathsf{m}(G)/bigl({matrix{k 2}}bigr)$.

Mixing and hitting times for finite Markov chains

Let 0<alpha<1/2. We show that the mixing time of a continuous-time reversible Markov chain on a finite state space is about as large as the largest expected hitting time of a subset of stationary measure at least alpha of the state space. Suitably modified results hold in discrete time and/or without the reversibility assumption. The key technical tool is a construction of a random set A such that the hitting time of A is both light-tailed and a stationary time for the chain. We note that essentially the same results were obtained independently by Peres and Sousi [arXiv:1108.0133].

On the coalescence time of reversible random walks

Consider a system of coalescing random walks where each individual performs random walk over a finite graph G, or (more generally) evolves according to some reversible Markov chain generator Q. Let C be the first time at which all walkers have coalesced into a single cluster. C is closely related to the consensus time of the voter model for this G or Q. We prove that the expected value of C is at most a constant multiple of the largest hitting time of an element in the state space. This solves a problem posed by Aldous and Fill and gives sharp bounds in many examples, including all vertex-transitive graphs. We also obtain results on the expected time until only k>1 clusters remain. Our proof tools include a new exponential inequality for the meeting time of a reversible Markov chain and a deterministic trajectory, which we believe to be of independent interest.