Return to Answer

Since the weight of $A$ in the statistical average can be arbitrarily small, we might as well replace $\mathbb{E}(A)$ by an arbitrary PSD matrix $B$ with $\lambda_2(B)>0$. The statement in the OP

If $\|A-B\|<\lambda_2(B)$, then $\lambda_2(A)>0,$

is a consequence of the "eigenvalue stability" inequality $$|\lambda_i(A)-\lambda_i(B)|\leq \|A-B\|,$$ which is proven, for example, in Tao's notes (equation 13).

The random-matrix connection is a bit of a red herring: Since the weight of $A$ in the statistical average can be arbitrarily small, we might as well replace $\mathbb{E}(A)$ by an arbitrary PSD matrix $B$ with $\lambda_2(B)>0$.
The statement in the OP

If $\|A-B\|<\lambda_2(B)$, then $\lambda_2(A)>0,$

is a consequence of the "eigenvalue stability" inequality $$|\lambda_i(A)-\lambda_i(B)|\leq \|A-B\|,$$ which is proven, for example, in Tao's notes (equation 13).

Since the weight of $A$ in the statistical average can be arbitrarily small, we might as well replace $\mathbb{E}(A)$ by an arbitrary PSD matrix $B$ with $\lambda_2(B)>0$. The problem in the OP then amounts to the "eigenvalue stability" inequality $$|\lambda_2(A)-\lambda_2(B)|\leq \|A-B\|,$$ which is proven, for example, in Tao's notes (equation 13).

Since the weight of $A$ in the statistical average can be arbitrarily small, we might as well replace $\mathbb{E}(A)$ by an arbitrary PSD matrix $B$ with $\lambda_2(B)>0$. The statement in the OP

If $\|A-B\|<\lambda_2(B)$, then $\lambda_2(A)>0,$

is a consequence of the "eigenvalue stability" inequality $$|\lambda_i(A)-\lambda_i(B)|\leq \|A-B\|,$$ which is proven, for example, in Tao's notes (equation 13).

A reformulation of the problem, not yet an answer: Since the weight of $A$ in the statistical average can be arbitrarily small, we might as well replace $\mathbb{E}(A)$ by an arbitrary PSD matrix $B$ with $\lambda_2(B)>0$. The problem in the OP then amounts to the inequality $$|\lambda_2(A)-\lambda_2(B)|\leq \|A-B\|,$$ which remains to be proved.

Since the weight of $A$ in the statistical average can be arbitrarily small, we might as well replace $\mathbb{E}(A)$ by an arbitrary PSD matrix $B$ with $\lambda_2(B)>0$. The problem in the OP then amounts to the "eigenvalue stability" inequality $$|\lambda_2(A)-\lambda_2(B)|\leq \|A-B\|,$$ which is proven, for example, in Tao's notes (equation 13).