Random Markov matrices with heavy-tailed weights and no density: smallest singular values and spectra

Let W be an N×N matrix whose entries are independent copies of a nonnegative random variable w that is not constant and has E w^κ < ∞ for some κ > 0, and let P be the row-normalised random Markov matrix. For every z ≠ 1 there is b > 0 such that, almost surely, the smallest singular value of P − z is at least N^(−b) for all large N. An elementary argument based on the Kolmogorov–Rogozin inequality also gives P(s_N(P − z) ≤ N^(−b)) ≤ C (log N)^3 N^(−1/2). No density and no second moment enter. The almost sure bound rests on the inverse Littlewood–Offord theorem of Tao and Vu, whose proof is shown to need only a polynomial tail in place of a second moment. As consequences:(i) for weights with t^α P(w ≥ t) → c > 0, α ∈ (0,1), the empirical spectral measure of P converges almost surely to the limit μ_α of Bordenave, Caputo, Chafaï and Piras, whose theorem assumed in addition a bounded density;(ii) for matrices with independent heavy-tailed entries in the domain of attraction of an α-stable law, the almost sure convergence of the spectral measure proved by Bordenave, Caputo and Chafaï under a bounded density holds without it, which settles the almost sure upgrade expected in the survey of Bordenave and Chafaï. The intermediate singular values are controlled through the factorisation P − z = D^(−1)(W − zD) and Horn’s inequality. Along the way, a second-moment computation in the distance estimate of Bordenave, Caputo and Chafaï (2011, Proposition 3.7) is corrected, and the arguments use the corrected bound. The deterministic lemmas are verified in Lean 4 with Mathlib: 17 declarations, with no sorry, depending only on the standard axioms.