Exercises

$\Lambda(\theta) = \log\frac{\lambda}{\lambda - \theta} = -\log(1 - \theta/\lambda)$ for $\theta < \lambda$.

$I(x) = \sup_{\theta < \lambda}\{\theta x + \log(1 - \theta/\lambda)\}$. Setting the derivative to zero: $x - 1/(\lambda - \theta) = 0 \Rightarrow \theta^* = \lambda - 1/x$. Substituting: $I(x) = \lambda x - 1 - \log(\lambda x)$ for $x > 0$. Note $I(1/\lambda) = 0$, confirming the rate function vanishes at the mean.

$\Lambda(\theta) = \mu(e^\theta - 1)$, defined for all $\theta$.

$I(x) = \sup_\theta\{\theta x - \mu(e^\theta - 1)\}$. Setting derivative to zero: $x = \mu e^{\theta^*}$, so $\theta^* = \log(x/\mu)$. $$I(x) = x\log\frac{x}{\mu} - x + \mu$$ for $x \geq 0$, with $I(\mu) = 0$.

With $p = 1/2$: $$I(3/4) = \frac{3}{4}\log\frac{3/4}{1/2} + \frac{1}{4}\log\frac{1/4}{1/2} = \frac{3}{4}\log\frac{3}{2} + \frac{1}{4}\log\frac{1}{2}.$$

Using natural log: $I(3/4) = \frac{3}{4}\ln\frac{3}{2} + \frac{1}{4}\ln\frac{1}{2} = \frac{3}{4}(0.405) + \frac{1}{4}(-0.693) \approx 0.131$ nats. So $\mathbb{P}(\bar{X}_n \geq 3/4) \doteq e^{-0.131n}$.

$I(x) = \sup_\theta\{\theta x - \Lambda(\theta)\}$ is a supremum of affine (hence convex) functions of $x$, so $I$ is convex.

$I(x) = \sup_\theta\{\theta x - \Lambda(\theta)\} \geq [\theta x - \Lambda(\theta)]_{\theta=0} = 0 - \Lambda(0) = 0$.

At $x = \mu$: $I(\mu) = \sup_\theta\{\theta\mu - \Lambda(\theta)\}$. Since $\Lambda$ is convex and $\Lambda'(0) = \mu$, the supremum is attained at $\theta = 0$: $I(\mu) = 0 \cdot \mu - \Lambda(0) = 0$. $\blacksquare$

For any $s > 0$: $\mathbb{P}(X \geq t) \leq e^{-st}\mathbb{E}[e^{sX}] \leq e^{-st + s^2\sigma^2/2}$.

Minimize over $s$: $d/ds[-st + s^2\sigma^2/2] = 0 \Rightarrow s^* = t/\sigma^2$. Substituting: $\mathbb{P}(X \geq t) \leq e^{-t^2/(2\sigma^2)}$. $\blacksquare$

$\mathbb{E}[e^{t(X+Y)}] = \mathbb{E}[e^{tX}]\mathbb{E}[e^{tY}] \leq e^{\sigma_1^2 t^2/2} \cdot e^{\sigma_2^2 t^2/2} = e^{(\sigma_1^2 + \sigma_2^2)t^2/2}$.

$X + Y$ is $\sqrt{\sigma_1^2 + \sigma_2^2}$-sub-Gaussian. Sub-Gaussian parameters add (like variances), and the effective parameter is the square root of the sum. $\blacksquare$

$\mathbb{E}[e^{tX^2}] = \int_{-\infty}^{\infty} \frac{1}{\sqrt{2\pi}}e^{tx^2 - x^2/2}dx = (1 - 2t)^{-1/2}$ for $t < 1/2$.

A sub-Gaussian MGF bound $e^{\sigma^2 t^2/2}$ is finite for all $t$, but $\mathbb{E}[e^{tX^2}] = \infty$ for $t \geq 1/2$. So $X^2$ is not sub-Gaussian.

For $|t| < 1/4$: $(1-2t)^{-1/2} \leq e^{2t^2}$ (by $-\frac{1}{2}\log(1-2t) \leq 2t^2$ for $|t| < 1/4$). So $X^2 - 1$ is sub-exponential with parameters $(\nu^2, \alpha) = (4, 4)$. $\blacksquare$

For $x \in [a, b]$: $e^{tx} \leq \frac{b-x}{b-a}e^{ta} + \frac{x-a}{b-a}e^{tb}$. Taking expectation with $\mathbb{E}[X] = 0$: $\mathbb{E}[e^{tX}] \leq \frac{b}{b-a}e^{ta} - \frac{a}{b-a}e^{tb}$.

Let $p = -a/(b-a) \in [0,1]$, $u = t(b-a)$. Then $\mathbb{E}[e^{tX}] \leq (1-p)e^{-pu} + pe^{(1-p)u} = e^{g(u)}$ where $g(u) = -pu + \log(1-p+pe^u)$.

$g(0) = 0$, $g'(0) = 0$ (using the reparametrization), and $g''(u) = \frac{pe^u(1-p+pe^u) - (pe^u)^2}{(1-p+pe^u)^2} = \frac{pe^u(1-p)}{(1-p+pe^u)^2} \leq \frac{1}{4}$. The last step uses $ab/(a+b)^2 \leq 1/4$. By Taylor: $g(u) \leq u^2/8$. $\blacksquare$

$\mathbb{P}(\bar{X}_n \geq 0.8) \leq 0.5/0.8 = 0.625$. (Useless.)

$\mathbb{P}(|\bar{X}_n - 0.5| \geq 0.3) \leq \frac{0.25}{100 \cdot 0.09} = 0.0278$.

$\mathbb{P}(\bar{X}_n \geq 0.8) \leq e^{-2 \cdot 100 \cdot 0.3^2} = e^{-18} \approx 1.5 \times 10^{-8}$.

$I(0.8) = 0.8\ln(0.8/0.5) + 0.2\ln(0.2/0.5) = 0.8(0.470) + 0.2(-0.916) = 0.193$ nats. $e^{-100 \cdot 0.193} = e^{-19.3} \approx 4.1 \times 10^{-9}$. The Cramér bound is about 3.7x tighter than Hoeffding in the exponent.

$\mathbb{P}(\hat{P}_n \in \mathcal{E}) = \sum_{Q \in \mathcal{P}_n : Q(1) \geq a} \mathbb{P}(\hat{P}_n = Q) \leq (n+1) \max_{Q(1) \geq a} e^{-nD(Q \| P)} = (n+1)e^{-nD(\text{Ber}(a) \| \text{Ber}(p))}$.

$\mathbb{P}(\hat{P}_n \in \mathcal{E}) \geq \mathbb{P}(\hat{P}_n = \text{Ber}(a_n))$ where $a_n = \lceil na \rceil / n \to a$. Using the lower type probability bound: $\geq \frac{1}{(n+1)^2}e^{-nD(\text{Ber}(a_n) \| \text{Ber}(p))} \to e^{-nD(\text{Ber}(a) \| \text{Ber}(p))}$ in the exponent.

Both bounds give rate $D(\text{Ber}(a) \| \text{Ber}(p))$. $\blacksquare$

$D(P_0 \| P_1) = \mathbb{E}_0[\log(f_0(X)/f_1(X))] = \mathbb{E}_0[\mu X - \mu^2/2] = -\mu^2/2 + \mu^2/2 = \mu^2/2$. Wait — more carefully: $\log(f_0/f_1) = -\mu X + \mu^2/2$, so $D(P_0 \| P_1) = \mathbb{E}_0[-\mu X + \mu^2/2] = 0 + \mu^2/2 = \mu^2/2$.

The NP test rejects $H_0$ when $\sum_i X_i > \gamma$. Under $H_1$, $\sum_i X_i \sim \mathcal{N}(n\mu, n)$. $\beta_n = \mathbb{P}_1(\sum X_i \leq \gamma) = \Phi((\gamma - n\mu)/\sqrt{n})$. Choosing $\gamma = c\sqrt{n}$ (to fix $\alpha$): $\beta_n \approx \Phi(-\sqrt{n}\mu + c) \approx e^{-n\mu^2/2}$ for large $n$, confirming the exponent $\mu^2/2$. $\blacksquare$

$C_\lambda = -\log[p^\lambda q^{1-\lambda} + (1-p)^\lambda(1-q)^{1-\lambda}]$.

Take the derivative with respect to $\lambda$ and set to zero. This yields a transcendental equation that generally requires numerical solution. For $p = 0.3$, $q = 0.7$: numerical optimization gives $\lambda^* \approx 0.5$ and $C \approx -\log[0.3^{0.5} \cdot 0.7^{0.5} + 0.7^{0.5} \cdot 0.3^{0.5}] = -\log[2\sqrt{0.21}] \approx 0.082$ nats.

Define $\mathbf{P}_\theta$ with entries $(P_\theta)_{ij} = P_{ij}e^{\theta j}$: $\mathbf{P}_\theta = \begin{pmatrix}1-\alpha & \alpha e^\theta \\ \beta & (1-\beta)e^\theta\end{pmatrix}$.

$\mathbb{E}[e^{\theta S_n}] \sim \rho(\mathbf{P}_\theta)^n$ where $\rho$ is the spectral radius (largest eigenvalue) of $\mathbf{P}_\theta$. Therefore: $\Lambda(\theta) = \log\rho(\mathbf{P}_\theta)$.

The characteristic polynomial of $\mathbf{P}_\theta$ is $\lambda^2 - [(1-\alpha) + (1-\beta)e^\theta]\lambda + [(1-\alpha)(1-\beta)e^\theta - \alpha\beta e^\theta] = 0$. The largest root $\rho(\mathbf{P}_\theta)$ gives $\Lambda(\theta)$ in closed form.

Let $\mathbf{X}_k = \mathbf{h}_k\mathbf{h}_k^H - \mathbf{R}$. For Gaussian vectors, $\|\mathbf{h}_k\|^2$ is sub-exponential, so with truncation at level $K = C\|\mathbf{R}\|\log(nd/\delta)$, the bounded matrix Bernstein inequality applies.

$\mathbb{P}(\|\hat{\mathbf{R}} - \mathbf{R}\| \geq t) \leq 2d\exp\left(-\frac{nt^2/2}{\|\mathbf{R}\|^2 + Kt/3}\right)$. Setting $t = \epsilon\|\mathbf{R}\|$ and requiring the RHS $\leq \delta$: $n \geq C\frac{d\log(d/\delta)}{\epsilon^2}$ suffices (with $C$ depending on the truncation level).

$\mathbb{E}[e^{tX}] = \frac{1}{2}(e^t + e^{-t}) = \cosh(t)$.

Using $\cosh(t) = \sum_{k=0}^\infty \frac{t^{2k}}{(2k)!} \leq \sum_{k=0}^\infty \frac{t^{2k}}{2^k k!} = e^{t^2/2}$ (since $(2k)! \geq 2^k k!$). Therefore $\mathbb{E}[e^{tX}] \leq e^{t^2/2}$, confirming $X$ is 1-sub-Gaussian. $\blacksquare$

$\mathbb{P}(\bar{X}_n \geq a) = \mathbb{E}_{\theta^*}[e^{-\theta^* S_n + n\Lambda(\theta^*)} \mathbf{1}\{\bar{X}_n \geq a\}]$.

$\geq e^{-n[\theta^*(a + \delta) - \Lambda(\theta^*)]} P_{\theta^*}(a \leq \bar{X}_n \leq a + \delta)$.

Under $P_{\theta^*}$, $\bar{X}_n$ has mean $a$ and variance $\Lambda''(\theta^*)/n \to 0$. So $P_{\theta^*}(a \leq \bar{X}_n \leq a + \delta) \to \Phi(\delta\sqrt{n/\Lambda''(\theta^*)}) - 1/2 > 0$. Taking $\frac{1}{n}\log$, the CLT term is $o(1)$, and letting $\delta \to 0$: $\liminf \frac{1}{n}\log\mathbb{P}(\bar{X}_n \geq a) \geq -[\theta^* a - \Lambda(\theta^*)] = -I(a)$. $\blacksquare$

The LLR is $\ell_n = \sum_i \log(P_0(X_i)/P_1(X_i)) = n\bar{X}_n\log(p/q) + n(1-\bar{X}_n)\log((1-p)/(1-q))$. This is a monotone function of $\bar{X}_n$ (decreasing since $p < q$), so the NP test reduces to $\bar{X}_n \leq \gamma$ for some threshold $\gamma$.

$\alpha_n = P_0(\bar{X}_n \leq \gamma)$. For $\gamma \in (p, q)$, this goes to zero. The exact value of $\gamma$ affects only the sub-exponential term.

$\beta_n = P_1(\bar{X}_n \leq \gamma)$. Under $P_1$, $\bar{X}_n$ has mean $q$ and we need $\bar{X}_n \leq \gamma < q$. By Cramér's theorem with the Bernoulli rate function: $\beta_n \doteq e^{-nI_1(\gamma)}$ where $I_1(x) = x\log(x/q) + (1-x)\log((1-x)/(1-q))$. As $\gamma \to p^+$ (optimal threshold): $I_1(p) = D(\text{Ber}(p) \| \text{Ber}(q)) = D(P_0 \| P_1)$. $\blacksquare$

$D(Q \| P) = -\sum_x Q(x)\log\frac{P(x)}{Q(x)} \geq -\log\sum_x Q(x)\frac{P(x)}{Q(x)} = -\log 1 = 0$.

Equality in Jensen's holds iff $P(x)/Q(x)$ is constant a.s. under $Q$, i.e., $P = Q$. $\blacksquare$