---
breaks: False
---

{%hackmd theme-dark %}

# Notes on: Random Matrices @ HSE 2019

## Structure of the lectures I missed, based on problem sets

### Problemset 3

- Bernstein-type bounds
- $|\mathbb{E}[(X-\mu)^k]|\leq \frac{k!}{2}\sigma^2 b^{k-2},~k\geq3$
- Equiv: MGF bound, $\mathbb{E} e^{\lambda(X-\mu)} \leq \frac{\lambda^2\sigma^2}{2(1-|\lambda|b)},~|\lambda|\leq\frac1b$

### Problemset 4

- $\varepsilon$-net argument

### Problemset 5

- http://iosipoi.ru/rmt/PS5.pdf
- $X_1, \ldots, X_n\in\mathbb{R}^d$ highdim, sampled from unknown distrib
- $\Sigma = \mathbb{E} X_iX_i^\top,~i=1,\ldots,n$ cov mat
- $\hat\Sigma= \frac1n \sum_i X_iX_i^\top$, $d\times d$
- Unbiased
- Law of large numbers: converges a.s.
- Comparison method
- Gaussian comparison ineqs
- Bound on the expected value of operator norm of $X$ (with Gaussian columns?)

### Problemset 6

- http://iosipoi.ru/rmt/PS6.pdf
- Catalan Numbers
- Equivalent combinatorics problems leading to Catalan numbers:
- Balanced paranthesis
- Dyck paths of $n$ up-steps and $n$ down-steps
- Rooted binary trees of $n$ internal nodes
- Rooted trees on $n$ edges
- Recursive def: $C_{n+1} = \sum_{j=0}^n C_j C_{n-j}$
- Solution: $C_n = \frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}$
- Derivation hints:
- $f$ -- generating function of $C$
- $f(z) = C_0 + z(f(z))^2$
- $(1+x)^\alpha = \sum_{n=0}^\infty x^n = \sum_{n=0}^\infty \frac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}x^n$
- Wigner's semicircular law
- $W_n = (w_{ij})_{1\leq i,j \leq n}$ an rmatrix
- $W_n$ symmetric
- Conditioned on symmetricity, $w_{ij}$ are independent
- $\mathbb{E}w_{ij}=0$
- $w_{ii}$ iid with $\mathbb{E}w_{ii}^2 <\infty$
- $w_{ij},~i<j$ iid with $\mathbb{E}w_{ij} = 1$
- Also assume moments exist and are bounded
- Gaussian Orthogonal Ensemble
- Scaled matrix: $\overline{W}_n = \frac{1}{\sqrt{n}}W_n$.
- Empircal spectral distribution (ESD) of $\overline{W}_n$
- $\lambda_1(\overline{W}_n) \leq \cdots \leq \lambda_n(\overline{W}_n)$
- $\mu_{\overline{W}_n}(x) = \frac1n \sum_{j=1}^n\delta_{\lambda_j(\overline{W}_n)}(x)$
- Atomic measure
- Limit may be cont
- Measure is random, as is the matrix and its eigenvalues
- Expected ESD of normalized Wigner mat tends to semicircular law
- $\mu_{\mathrm{sc}}(x) = \frac{1}{2\pi}\sqrt{4 - x^2}1_{|x|\leq 2}(x)$
- Method of moments
- Families of distributions that are defined
by their sets of moments
- Convergences
- Weak: $P_n\to P$ in distribution, if $\lim_n F_n(x) \to F(x)$ for every $x$ at which $F$ is cont
- In prob: $P_n \implies P$ if $\lim_n \int f \mathrm{d}P_n = \int f\mathrm{d}P$
- Compact support and conv in moments $\implies$ weak convergence
- Moments of semicircular law
- Odd: $0$
- Even: Catalan numbers
- Hints:
- Beta function: $B(x, y) = \int_0^1 t^{x-1}(1-t)^{y-1}\mathrm{d}t = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$
- $\Gamma(x+1)=x\Gamma(x)$
- $\Gamma(n+\frac12)=\frac{(2n)!}{4^n n!}\sqrt{\pi}$
- Wigner type

* * *

Lecture notes are of bigger interest
"Modern RMT 3-4.pdf" contains ent tensorization topic

Define
$$\operatorname{Ent}[Z]= \mathbb{E}[Z\log Z] - \mathbb{E}[Z]\log\mathbb{E}[Z]$$

Assume
$$\operatorname{Ent}[e^{\lambda X}]\leq \frac{\lambda^2\sigma^2}{2} \mathbb{E}[e^{\lambda X}]~\text{for}~\lambda\geq0$$
Then
$$\psi(\lambda) \equiv \log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq \lambda^2\sigma^2/2$$

### Tensorization of Entropy

Let $X_1, \ldots, X_n$ be indep,
then $$\operatorname{Ent}[f(X_1, \ldots, X_n)]
\leq \operatorname{\mathbb{E}}\left[
\sum_{i=1}^n \operatorname{Ent}_i f(X_1, \ldots, X_n)
\right]$$

**Lemma 6**
$$\operatorname{Ent}[Z] = \sup_{X:~\mathbb{E}[e^X]=1} \mathbb{E}[ZX]$$