Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 210 / 2

Because the scalar signal and the noise vector are independent random variables with normal distributions, their sum is a Gaussian random vector. Its expected value is zero, and the covariance matrix isThus this is a rank-one covariance spike. Each summand $X_i{X}_i^{\top }$ has expected value ${\Sigma }_S$, so $\mathbb{E}\hat{\Sigma }={\Sigma }_S$. Here the empirical matrix is an uncentered empirical second-moment matrix; because the population expected value is known to be zero, it is an unbiased estimator of the covariance matrix. The TeX's apparent factorial denominator is a transcription error.

Use the convention $\mathbb{E}{e}^{sX}\le e^{{\sigma }^2{s}^2/2}$ for the centered sub-Gaussian random variable. Applying the two-sided Chernoff bound to $X$ gives $\mathbb{P}(|X|>x)\le 2e^{-x^2/(2{\sigma }^2)}$. Since $\mathbb{E}{X}^2\ge 0$, this already supplies the requested bound:For averages of independent random variables, the stronger useful statement is that the centered square of a sub-Gaussian random variable is a sub-exponential random variable. The Bernstein bound for independent sub-exponential variables then give $\mathbb{P}(n^{-1}{\sum }_i(X_i^2-\mathbb{E}{X}_i^2)>t)\le 2\exp [-cn\min \{t^2/{\sigma }^4,t/{\sigma }^2\}]$ for a universal positive $c$. These are the concentration theorems used for quadratic scan statistics.

Put $\ell =\log (d/\delta )$ and $r=\sqrt{\ell /n}\le 1$. Use the quadratic scan statistic $\Lambda$ and reject when $\Lambda >1+4r$. Under the null hypothesis, each $nu(T{)}^{\top }\hat{\Sigma }u(T)$ has the chi-squared distribution with $n$ degrees of freedom. The chi-squared concentration inequality gives $P_0^{\otimes n}(\Lambda >1+2r+2r^2)\le d{e}^{-\ell }=\delta$, by the union bound. Since $2r+2r^2\le 4r$, the proposed Type I error is at most $\delta$.

For the true set $S$, $nu(S{)}^{\top }\hat{\Sigma }u(S)/(1+\theta )$ has the same chi-squared distribution. We need a lower-tail bound that remains positive even when $\ell /n$ is close to one. Set $a=e^{-4r}$. The chi-squared Chernoff lower-tail bound gives $P(V\le na)\le \exp [-n(a-1-\log a)/2]\le e^{-n{r}^2}=e^{-\ell }$: indeed $e^{-4r}-1+4r\ge 2r^2$ for $0\le r\le 1$. To verify this last inequality, its derivative is $4(1-r-e^{-4r})$; the expression in parentheses is strictly concave, starts at zero, and changes sign once, so the minimum occurs at an endpoint, where the inequality holds.

The function $g(r)=(1+4r)e^{4r}-1$ is convex with $g(0)=0$, so $g(r)\le rg(1)<300r$ on this interval. Consequently $\theta >300r$ implies $(1+\theta )e^{-4r}>1+4r$. Failure to reject then requires $V\le na$, giving Type II error at most $e^{-\ell }\le \delta$, uniformly in $S$. An explicit, deliberately conservative answer isThe sharp constant is unnecessary; the detection scale is $\sqrt{\log (d/\delta )/n}$.

Define $P_{\theta ,n}=d^{-1}{\sum }_{S\in \mathcal{S}}{P}_{\theta ,S}^{\otimes n}$. Expanding its chi-squared divergence by the second moment of a mixture likelihood ratio, and using the supplied one-observation cross moment and independence, givesHere $S,T$ are independent uniform members of the specified family of cyclic intervals. Their overlap $R=|S\cap T|$ does not have the hypergeometric distribution of arbitrary uniform $k$-subsets. The family's geometry must be retained.

Let $x={\theta }^2{R}^2/k^2<1/4$. Since $-\log (1-x)\le x/(1-x)\le 2x$ and $R^2/k^2\le R/k$, we obtain $(1-x{)}^{-n/2}\le e^{nx}\le e^{n{\theta }^{2}R/k}$. Taking the expected value proves the upper bound. The factor $n$ in the last exponent is present in the PDF and missing in the TeX aid.

Two independent cyclic intervals intersect with probability at most $\min \{1,(2k-1)/d\}\le 2k/d$. For $k\le d/2$, precisely the $2k-1$ starting-point offsets $-(k-1),\dots ,k-1$ can overlap; for larger $k$, the upper bound is automatic. The cyclic interval overlap bound and the preceding chi-squared divergence estimate therefore giveAs in 1(e), the square-root hypothesis is meaningful when $\alpha d\ge 1$. The chi-squared testing lower bound bounds the total variation distance by $\sqrt{2{\alpha }^{\epsilon }}/2$. The worst individual Type II error dominates the error under the uniform mixture model. ThusTaking $\alpha$ small makes this lower bound informative. This argument uses the actual cyclic-interval alternative, without substituting a different family of subsets.