I am looking for the tail bound of spectral norm for certain type of random matrix.

Let's say we have a $n\times n$ symmetric random matrix $R$, and for each entry $R_{ij}$, we have that $$ E[R_{ij}]=0 $$ $$ Var[R_{ij}]\leq C $$ $$ |Cov[R_{ij},R_{lm}]|\leq C/n,\quad if\quad (ij\neq lm) \cup (ij\neq ml) $$

And I need a tail bound on the spectral norm of $R$.

Our current approach does not utilize the bound on $|Cov[R_{ij},R_{lm}]|$. Our approach is as follows,

By Gershgorin circle theorem, we have that $$ ||R||_2 \leq \max_i \sum_{j=1}^n |R_{ij}| $$

Assume that $Var[R_{ij}]\leq C,\forall i,j$, we also have the following

$$ E[R_{ij}]=0 $$

$$ Var[|R_{ij}|]=E[|R_{ij}|^2]-E^2[|R_{ij}|]=Var[R_{ij}]-E^2[|R_{ij}|] \leq Var[R_{ij}] $$ and $$ C \geq Var[R_{ij}]\geq E^2[|R_{ij}|] $$

So we have

$$ E[\sum_{j=1}^n |R_{ij}|] =\sum_{j=1}^n E[ |R_{ij}|] \leq n\sqrt{C} $$ and $$ Var[\sum_{j=1}^n |R_{ij}|] \leq n^2 Var[R_{ij}] \leq n^2 C $$

By Chebyshev's inequality, we have $$ {Pr}(\sum_{j=1}^n |R_{ij}| \geq n\sqrt{C} + k n\sqrt{C} ) \leq \frac{1}{k^2} $$

And by union bound, we have that $$ {Pr}(\max_i \sum_{j=1}^n |R_{ij}| \geq n\sqrt{C} + k n\sqrt{C} ) \leq n\frac{1}{k^2} $$ By setting $k = \sqrt{\frac{n}{\delta }}$, we have that with probability $1-\delta$ $$ ||R||_2 \leq \max_i \sum_{j=1}^n |R_{ij}| \leq (1+ \sqrt{\frac{n}{\delta }} ) n\sqrt{C} $$

**Our goal is to remove the extra $\sqrt{n}$ in the coefficient**

In our approach, we obtained the tail bound on $\sum_{j=1}^n |R_{ij}|$ by assuming that they are fully correlated (corr=1).

**If we can prove that $|Cov(|R_{ij}|,|R_{ik}|)|\leq \theta C/n$ for some constant $\theta$, we can remove the extra $\sqrt{n}$ directly. But we don't know how to prove it or whether it's true or not.**

Or is there are better way to obtain the tail bound? Is there any result in random matrices literature that can be applied to this type of problem?