Spectra of random Markov generators with heavy-tailed rates

Let X be an N×N matrix with independent nonnegative entries distributed as x. Let D be the diagonal matrix of its row sums, and L = X − D the generator of the continuous-time random walk with rates X_ij. Suppose t^α P(x > t) → c > 0 for some α ∈ (0,2). Then the empirical spectral measure of a_N^{-1}(L + b_N), with a_N = (cN)^{1/α} and b_N = N E[x 1(x ≤ a_N)], converges almost surely to a deterministic probability measure μ_α that depends only on α. No density is assumed. For weights with finite variance, the corresponding limit is due to Bordenave, Caputo and Chafaï, who in 2012 set the heavy-tailed generator aside as a different model outside their results. The measure μ_α has finite moments of every order below α. For α ∈ (1,2) its mean is −α/(α−1), the limit of −(N E x − b_N)/a_N, so the limit for the centring N E x has mean 0. For rates e^{θG} with G Gumbel (the unnormalised weights of a Gumbel-softmax attention matrix), the limit is μ_{1/θ} for θ > 1/2, while for θ < 1/2 the rates have finite variance. The measure μ_α is described through an operator on the Poisson weighted infinite tree with a compensated diagonal, whose bipartization is again a tree. The second ingredient is a smallest-singular-value bound for any nonnegative, non-constant rates with a polynomial tail: for every K there is b with Σ_N sup_{N^{-K} ≤ |ζ| ≤ N^K} P(s_N(L − ζ) ≤ N^{-b}) < ∞. Its proof uses the inverse Littlewood–Offord theorem of Tao and Vu under a polynomial tail, and the identity L𝟏 = 0 to control vectors close to constants. The arithmetic inequalities of the proofs, the deterministic lemmas on vectors near constants and on large entries, and the tree property of the bipartized graph are verified in Lean 4 with Mathlib.