Homework

Homework 3

Truncation in the CLT. We are given an iid sequence $\{X_i\}_{i \in \Z}$. Suppose $X_{n,\leq N} = X_n 1_{X_n \leq N}$. Define $X_{i,> N}$ similarly. Let $\mu_{i,\cdot}$ and $\sigma_{i,\cdot}$ be the corresponding mean and variance, and let the corresponding sums be $S_{n,\leq N}$ and $S_{n,>N}$. Then the moment method shows

$\frac{S_{n,\leq N} - n E[X_{n,\leq N}]}{\sigma_{\leq N} \sqrt{N}} \overset{d}{=} N(0,1)$

Show that
1. There is a sequence $N_n \to \infty$ such that $S_{n,\leq N_n} \overset{d}{=} N(0,1)$ and $\sigma_{1,\leq N_n} \to 1$, and
2. $S_{n,> N_n} \overset{d}{=} 0$.
3. If $A_n \overset{d}{=} A$ and $B_n \overset{d}{=} B$ where $B$ is a degenerate (almost surely deterministic) random variable, then $A_n + B_n \overset{d}{=} A + B$. Conclude the CLT from this.
1. Recall the $\epsilon$-net $\Sigma$ considered in class. Show that $\vert \Sigma\vert \geq C^n/\e^{n-1}$.
2. Consider a matrix with iid bounded entries $\{\xi\}_{ij}$. Recall the inequality $\Prob( \| M \| _{op} > A \sqrt{n} ) \leq C \exp( -c A n)$ we proved using the $\epsilon$-net method in class. Using the $\epsilon$-net method, prove the same inequality for symmetric or Hermitian matrices whose entries are bounded and iid in the upper triangular part of the matrix ($i \geq j$).
Let $\{\xi\}_{ij}$ have bounded iid entries. Show, using Talagrand’s inequality, that

$\E \vert \| M \|_{op} - \operatorname{Med}(\| M\|_{op}) \vert^k = O(1)$ for any fixed $k$.
A tree is a connected acyclic graph.
1. Show that a connected graph of $n$ vertices and $n-1$ edges is a tree.
2. Show that a cycle of length $2n$ is non-crossing iff there is a tree $n$ of edges and $n+1$ vertices, such that the cycle lies in the tree and traverses each edge exactly twice.
1. Consider the integer nearest-neighbor lattice $\Z^2$. An up-right or staircase walk from $(0,0)$ to $(n,n)$ is a lattice path with $2n$ edges that can only take steps in $\{e_1,e_2\}$. A Dyck path from $(0,0)$ to $(n,n)$ is a staircase walk that stays strictly below the diagonal $y=x$. Show that the number of Dyck paths is given by the Catalan number $C_{n}$.
2. Do Exercise 2.3.12. Is there some connection between this and the reflection principle for random walks and Brownian motion?
1. A partition of $[n]$ is a collection of disjoint subsets of $[n]$ whose union is $[n]$. Arrange the integers $1,\ldots,n$ around a circle. We consider a partition to be noncrossing if no two blocks cross each other in the cyclic arrangement; i.e., if $a$, $b$ are in one block and $x$, $y$ are in another, then they are not arranged in the order $a$,$x$,$b$,$y$. In other words, if you draw a line between $a$ and $b$ and $x$ and $y$, they do not cross. Show that the number of partitions of $[n]$ are also counted by the Catalan numbers!
2. Show the recursion
  
  $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$
  
  and deduce
  
  $C_{n} = \frac{1}{n+1} \binom{2n}{n}$
1. Do Exercise 2.3.5 (Talagrand’s inequality for symmetric/Hermitian matrices)
2. Do Exercise 2.3.14. By combining the result of the lower Bai-Yin theorem and Talagrand’s inequality, show that with $\xi$ bounded one has
  
  $\lim_{n \to \infty} \frac{1}{\sqrt{n}} \| M \|_{op} = 2$

Homework 2

Let $X_1,\ldots$ be iid random variables such that $\E[X_1^4] < \infty$. Prove the strong law of large numbers using the method of moments.
Prove Hoeffding’s inequality with the optimal constant. The step to complete is the following. Let

$\psi(y,\theta) = -y \theta + \log ( 1 - y + y \exp(\theta))$

where $y \in (0,1)$ and $\theta \geq 0$. Show that $\psi(y,\theta) \leq \theta^2/8$.
Show that

$1 + \frac{t^2 \Var(X)}{2} e^{t(b-a)} \leq \exp( 3 t^2 (b-a)^2)$

and complete the proof of a weaker Hoeffding inequality.
Show that McDiarmid’s inequality implies Hoeffding’s inequality: let $\vert X_i\vert \leq c_i$ for $i=1,\ldots,n$. Let $S_n$ be the sum of the $X_i$. Then

$\Prob( |S_n - E S_n| \geq \lambda \sum_i c_i^2 ) \leq C \exp( - c \lambda^2).$
Show that there are iid random variables $\{X_i\}$ (even those with finite variance) for which their sum $S_n$ cannot have a subGaussian tail behavior on all scales. In particular we cannot have

$\Prob( S_n \leq \lambda \sqrt{n}) \leq C \exp( - c \lambda^2 )$

for all $\lambda > 0$.

Consider $X_i \sim \Exponential(1)$. Show

$M(t) = \frac{1}{1 - t} \quad |t| < 1$

Let $I(t)$ be the Legendre transform of $M(t)$. Then,

$I(t) = \sup_{s > 0} \left( s t - \log M(t) \right) = t - 1 - \log \left( \frac{t}{t+1} \right).$

Conclude using Cram'er’s theorem that $S_n$ does not have a Gaussian tail as specified above.
We say that a random variable is sub-Gaussian if

$\Prob( |X| > t ) \leq 2 \exp \left( - t^2/2C^2 \right)$

Use Cramer’s theorem to conclude that for sub-Gaussian random variables

$\Prob ( S_n > \lambda n) \leq 2 \exp( - \lambda^2/4C n )$

For some constant $C$. Hint: Compute the moment generating function of $X$.
Show that the following are equivalent. Let $X \in \R^n$ be an iid vector of standard Gaussians.
1. For all 1-Lipschitz functions $F \colon \R^d \to \R$, there exist constants $C_1,C_2$ such that
$\Prob( | F(X) - \E F(X) | > \lambda ) \leq C_1 \exp( - C_2 \lambda^2)$
1. Let $A$ be a measurable set and $A_r = \{ y \colon d(y,A) \leq r\}$ be its $r$-neighborhood. Then,
$\Prob(X \in A) \Prob( X \not\in A) \leq C_1 \exp( - C_2 \lambda^2)$
Fill in the details in Talagrand’s concentration inequality:
1. Define the sets $A_{X_n}$ and $B$:
  
  $\begin{align*} A_{X_n} & := \{ z \in \W^{n-1} \colon (z',X_n) \in A \} \\ B & := \{ x \in \W^{n-1} \colon \exists |t| \leq K s.t. (z',t) \in A \} \\ \end{align*}$
  
  $d_c(X,A) \leq (1-\lambda)^2 + \lambda d_c(X',A_{X_n})^2 + (1-\lambda) d_c(X',B)^2$
2. Show
  
  $\inf_{0 \leq \lambda \leq 1} e^{c(1-\lambda)^2} r^{-\lambda} \leq 2 - r$
3. Show that we can choose $c > 0$ small enough such that
  
  $(1-p) e^c + p \leq p^{-1}.$
4. Show
  
  $\E[ \Prob(X' \in A_{X_n} | X_n ) ] = P(X \in A)$

Homework 1

Let $A$ be a complex Hermitian matrix. Show that $A$ can be diagonalized by a unitary matrix $U$; i.e., $\exists U$ such that

$\Lambda = U^* A U$

Show that $U$ can be chosen to be orthogonal matrix when $A$ is a real symmetric matrix.
Let $U$ and $V$ be subspaces. Is $U \cap V$ a subspace? Is $U \cup V$ a subspace? How about $U + V := \{ u + v \colon u \in U \AND v \in V\}$?

Show the formula

$dim(U) + dim(V) - dim(U \cap V) = dim(U + V)$

When $U \cap V = \{0\}$, then we write $U + V = U \oplus V$, the direct sum.
Let $H$ be a Hilbert space, and let $V$ be a closed subspace. Show the decomposition

$H = V \oplus V^\bot$
Show the permutahedron property in Tao, Exercise 1.3.2.
Wielandt minimax formula (Exercise 1.3.3)
If $A$ is a Hermitian matrix, show that $\Vert A\Vert_{op} = \max(\vert \lambda_1(A)\vert ,\vert \lambda_N(A)\vert$. Also show that $\Vert A\Vert_{op}$ is a bonafide norm on the space of matrices.
Ex 1.3.6 from Tao about using Lidskii’s inequality to get the p-Weilandt-Hoffman inequality.
Ex 1.3.7 Show the Schatten p-norms are actually norms on the space of Hermitian matrices. Is it a a norm on the space of all matrices?
Ex. 1.3.9 non-commutative Holder inequality.
Ex. 1.3.10 Do the Hermitian part of this problem for me.