UC Berkeley

In this dissertation we investigate three different problems related to (1) concentration inequalities using Stein's method of exchangeable pair, (2) first-passage percolation along thin lattice cylinders and (3) limiting spectral distribution of random linear combinations of projection matrices.

Stein's method is a semi-classical tool for establishing distributional convergence, particularly effective in problems involving dependent random variables. A version of Stein's method for concentration inequalities was introduced in the Ph.D.~thesis of Sourav Chatterjee to prove concentration of measure in problems involving complex dependencies such as random permutations and Gibbs measures.

In the first part of the dissertation we provide some extensions of the theory and three new applications: (1) We obtain a concentration inequality for the magnetization in the Curie-Weiss model at critical temperature (where it obeys a non-standard normalization and super-Gaussian concentration). (2) We derive exact large deviation asymptotics for the number of triangles in the Erd\H os-R enyi random graph $G(n,p)$ when $p \ge 0.31$. Similar results are derived also for general subgraph counts. (3) We obtain some interesting concentration inequalities for the Ising model on lattices that hold at all temperatures.

In the second part, we consider first-passage percolation across thin cylinders of the form $[0,n]\times [-h_n,h_n]^{d-1}$. We prove that the first-passage times obey Gaussian central limit theorems as long as $h_n$ grows slower than $n^{1/(d+1)}$. We obtain appropriate moment bounds and use decomposition of the first-passage time into an approximate sum of independent random variables and a renormalization type argument to prove the result. It is an open question as to what is the fastest that $h_n$ can grow so that a Gaussian CLT still holds. We conjecture that $n^{2/3}$ is the right answer for~$d= 2$ and provide some numerical evidence for that.

Finally, in the last part we consider limiting spectral distributions of random matrices of the form $\sum_{i=1}^{k}a_{i}X_{i}M_{i}$ where $X_{i}$'s are i.i.d.~mean zero and variance one random variables, $a_{i}$'s are some given sequence of real numbers with $\ell^{2}$ norm one and $M_{i}$'s are projection matrices with dimension growing to infinity. We provide sufficient conditions under which the limiting spectral distribution is Gaussian. We also provide examples from the theory of representations of symmetric group for which our results hold.