Let $A_1,\ldots,A_k$ be a given sequence of $N$-by-$N$ Hermitian matrices. Assume all have spectrum contained in $[-1,-\delta] \cup [+\delta,+1]$ for some $\delta>0$. Let $$A=\frac{1}{\sqrt{k}} \sum\limits_{i=1}^k \sigma_i A_i,$$ where the $\sigma_i$ are independent random variables, each chosen to equal $+1$ with probability $1/2$ and $-1$ with probability $1/2$.
Can you prove "For every $\epsilon'>0$ and $p>0$, there is a $\delta'>0$ and a $k_0$ such that for all $k \geq k_0$, with probability at least $1-p$ the matrix $A$ has at most $\epsilon' N$ of its eigenvalues smaller than $\delta'$ in absolute value"? The quantities $k_0,\delta'$ should not depend on the particular sequence of matrices $A_i$, and should not depend on $N$. The quantities $k_0,\delta'$ may depend on $\delta$. Stated colloquially, I am asking: "Each $A_i$ has no small eigenvalues; can you prove that it is unlikely that $A$ has more than a few small eigenvalues?"
A few remarks: if the $A_i$ all commute, then this can be handled by a central limit theorem. Work in a simultaneous eigenbasis of the $A_i$, then each diagonal entry has variance at least $\delta^2$, so the diagonal entries of $A_i$ also have variance at least $\delta^2$.
Another remark: I believe that one can show that we can instead consider the $\sigma_i$ to be independent random variables drawn from a Gaussian distribution with variance $1$. Sketch of proof: to study the expected number of small eigenvalues of $A$, one can consider the expectation value of moments of $A$. Then, up to $O(1/k)$ corrections, these two ensembles have the same moments.
