Why are concentration inequalities for random matrices with bounded entries not trivial?

I just read this blog entry, and it is unclear to me why the tail bound results are not trivial for all bounded random matrices.

For instance, Corollary 4 states that for an $$n\times n$$ random matrix $$M$$ with i.i.d. mean-zero entries absolutely bounded by $$1$$, $$P(\|M\|_{op} > A \sqrt{n}) \leq C \exp(-c A n)$$ for all $$A \geq C$$, where $$\|\|_{op}$$ is the operator norm and $$C, c > 0$$ are constants.

Since $$\|M\|_{op}$$ is bounded due to the boundedness of $$M$$'s entries, we can simply choose $$C$$ high enough so that $$A \sqrt{n}$$ necessarily surpasses this bound. The probability $$P(\|M\|_{op} > A \sqrt{n})$$ is then $$0$$, and the tail bound holds trivially for all choices of $$c$$.

Given there are no further qualifications on the $$c$$ and $$C$$, why is the result not trivial?

• I didn't check the link, so this might be a stupid question. Are the constants are allowed to depend on $n$? If not, notice that $\| M \|_{op}$ is not bounded as $n$ varies, so this bound is nontrivial if it holds for infinitely many $n$ for the same values of the constants.
– Ian
Aug 14, 2020 at 14:56
• I don't really follow the conclusion that you can choose arbitrary positive constants $c$ and $C$, after all the bound is supposed to hold for all $A \geq C$. (So you don't have to freedom to choose $A$.) But I agree that choosing $C$ high enough such that $\mathbb{P}[||M|| > C\sqrt{n}] = 0$ seals the deal. I think that the power of such results comes from the specific constants involved. Aug 14, 2020 at 15:01
• @infinite_monkey Yes, thanks for the correction; that was sloppy. Aug 14, 2020 at 15:04
• @Ian I suspect you are right. The text seems vague as it says $c$ and $C$ are absolute constants''. I am not too familiar with math terminology, but this may indicate they cannot depend on $n$. Aug 14, 2020 at 15:28
• Yes, absolute constants do not depend on $n$. The power of these sorts of concentration inequalities is that they hold for all $n$ (meaning the constant $C$ works for all $n$ too). To gain some intuition on concentration inequalities, I suggest working through the proof of Hoeffding's and/or Bernstein's inequality. Aug 14, 2020 at 15:50