  We study the Lanczos algorithm where the initial vector is sampled uniformly
from $\mathbb{S}^{n-1}$. Let $A$ be an $n \times n$ Hermitian matrix. We show
that when run for few iterations, the output of Lanczos on $A$ is almost
deterministic. More precisely, we show that for any $ \varepsilon \in (0, 1)$
there exists $c >0$ depending only on $\varepsilon$ and a certain global
property of the spectrum of $A$ (in particular, not depending on $n$) such that
when Lanczos is run for at most $c \log n$ iterations, the output Jacobi
coefficients deviate from their medians by $t$ with probability at most
$\exp(-n^\varepsilon t^2)$ for $t<\Vert A \Vert$. We directly obtain a similar
result for the Ritz values and vectors. Our techniques also yield asymptotic
results: Suppose one runs Lanczos on a sequence of Hermitian matrices $A_n \in
M_n(\mathbb{C})$ whose spectral distributions converge in Kolmogorov distance
with rate $O(n^{-\varepsilon})$ to a density $\mu$ for some $\varepsilon > 0$.
Then we show that for large enough $n$, and for $k=O(\sqrt{\log n})$, the
Jacobi coefficients output after $k$ iterations concentrate around those for
$\mu$. The asymptotic setting is relevant since Lanczos is often used to
approximate the spectral density of an infinite-dimensional operator by way of
the Jacobi coefficients; our result provides some theoretical justification for
this approach.
  In a different direction, we show that Lanczos fails with high probability to
identify outliers of the spectrum when run for at most $c' \log n$ iterations,
where again $c'$ depends only on the same global property of the spectrum of
$A$. Classical results imply that the bound $c' \log n$ is tight up to a
constant factor.
