Largest eigenvalue of finite band random matrices Let $\mathbf{M}_n$ be an $n \times n$ symmetric matrix
$$
\mathbf{M}_n = \begin{cases}
X_{j-i,i}\ &\text{if }i\leq j\leq r+i\\
0\ &\text{if }r+i< j\leq n\end{cases}
$$
for some fixed $r>0$, and the random variables $\{X_{i,j}\}$ are assumed real, positive, i.i.d., and have finite mean and variance.
As an example, for $r=1$ and $n=4$ we have,
$$\mathbf{M}_4 = 
\begin{pmatrix}
X_{0,1} & X_{1,1} & 0 & 0\\
X_{1,1} & X_{0,2} & X_{1,2} & 0 \\
0 & X_{1,2} & X_{0,3} & X_{1,3} \\
0 & 0 & X_{1,3} & X_{0,4} 
\end{pmatrix}$$
I was wondering if something is known about the asymptotic of $\lambda_1(\mathbf{M}_n)$, i.e., the largest eigenvalue of $\mathbf{M}_n$, in the limit $n \to \infty$. In particular, is something is known about the deviation of $\lambda_1(\mathbf{M}_n)$ from its mean, i.e.,
$$
\Pr\left[|\lambda_1(\mathbf{M}_n)-\mathbb{E}\lambda_1(\mathbf{M}_n)|\geq t\right]\leq ?
$$
I was wondering whether there is a general concentration bound, e.g., for non-identical matrices, which subsumes the above case.
 A: I start with this simple remark: the tridiagonal matrix $$A_k=\begin{pmatrix}0 & 1 &  & & \\ 1 & 0 & 1 &  & \\  & 1 & 0 & \ddots & \\ &  & \ddots & & 1 \\ & & & 1 & 0\end{pmatrix}$$, $A_k\in \mathbb{R}^{(k+1)\times (k+1)}$ have largest eigenvalue $\lambda_\max (A_k) =2\cos{\frac{\pi}{k+2}}$.
We will focus on the submatrices with large entries of $M_n$. When there are $k$ consecutive large entries :$ \forall i\leq k$ $X_{a+i}\geq C $ for some $a$, we will assume that $X_{a+i} = C$ for all $i$ and write $CA_k$. This is obiously not true but it is just to simplify the discussion.
We then have $$ M_n = \begin{pmatrix}\ddots & \\ & C_1A_{k_1}  \\ & & \ddots  \\ & & & C_2 A_{k_2} \\ & & & & \ddots \\ & & & & & . \end{pmatrix} $$
where  $\ddots$  have small entries  (let say $\mathcal{O}(1)$) and $C_i\gg 1$. The largest eigenvalue will come from these submatrices
$$\lambda_\max (M_n) \approx \max_j \lambda_{\max}(C_j A_{k_j})=\max_j 2 C_j\cos(\frac{\pi}{k_j+2})$$
For large $n$ the behaviour will depend on the tail of the random variable $X_1$.
We first consider the case of polynomial tail : $\mathbb{P}(X \geq K)\sim \frac{1}{K^\alpha}$.
For any $k$, $\lambda_{\max}(C A_{k})\geq K\Leftrightarrow C \geq \frac{K}{2\cos(\frac{\pi}{k+2})}$ and we estimate $$\mathbb{P}(\forall i\leq k, X_k \geq \frac{K}{2\cos(\frac{\pi}{k+2})}) = \Big(\frac{2\cos(\frac{\pi}{k+2})}{K} \Big)^k$$ For $K\rightarrow \infty$, one can see that the case $k=1$ have the much larger probability and we deduce that in this situation it is enougth to consider only $k=1$ submatrices.
Conclusion for polynomial tail we have
$$\lambda_\max (M_n) \approx \max_j X_j \sim n^{1/\alpha}$$ (Because there are $n$ iid $X_j$, we set $K=n^{1/\alpha}$ such that $\mathbb{P}(X_1 \geq K)=\frac{1}{n}$).
We now consider the case of exponential tail : $\mathbb{P}(X \geq K)\sim \exp(-\gamma K)$.
We estimate $$\mathbb{P}\Big(\forall i\leq k, X_k \geq \frac{K}{2\cos(\frac{\pi}{k+2})}\Big) = \exp\Big(-\frac{\gamma k K}{2 \cos(\frac{\pi}{k+2})} \Big)$$ Still here for $K\rightarrow \infty$, the case $k=1$ have the much larger probability.
Conclusion for exponential tail we have
$$\lambda_\max (M_n) \approx \max_j X_j \sim \frac{\log(n)}{\gamma}$$ (we set $K$ such that $\mathbb{P}(X_1 \geq K)=\frac{1}{n}$).
We continue with the case of sup-exponential tail : $\mathbb{P}(X \geq K)\sim \exp(-K^\gamma)$.
We have $$\mathbb{P}\Big(\forall i\leq k, X_k \geq \frac{K}{2\cos(\frac{\pi}{k+2})}\Big) = \exp\Big(-\frac{ k }{2^\gamma \cos(\frac{\pi}{k+2})^\gamma}K^\gamma \Big)$$ Here there is a $k^*$ that maximize $\frac{k}{\cos(\frac{\pi}{k+2})^\gamma}$ which have the much larger probability for $K\rightarrow \infty$.
We also set $K$ such that this event is of order $1/n$ and then for sup-exponential tail we have
$$\lambda_\max (M_n) \sim \frac{2\cos(\frac{\pi}{k^*+2})}{(k^*)^\frac{1}{\gamma}}\log(n)^{\frac{1}{\gamma}}$$
Finally in case of bounded $X$, for any $\epsilon>0$, and $k$, we can find $a$ such that $\forall i\leq k, X_{a+i}\geq \|X\|_\infty-\epsilon$ with probability that goes to $1$ as $n\rightarrow \infty$. Then $$2 \|X\|_\infty \geq \lambda_\max (M_n) \geq 2 (\|X\|_\infty-\epsilon) \cos(\frac{\pi}{k+2}) $$ and we get $\lambda_\max (M_n) \rightarrow 2 \|X\|_\infty$.
