For $i, j \in \{ 1, \ldots, n \}$, let $X\_{i,j}$ be a real-valued random variable uniformly distributed on the interval $[0,1]$. The $X\_{i,j}$ are independent.


Let $A\_{i,j}$ be the indicator random variable of the event that $X\_{i,j}$ is a local maximum, i. e. it is the largest of the five random variables $X\_{i,j}, X\_{i,j+1}, X\_{i,j-1}, X\_{i-1,j}, X\_{i+1, j}$. For the sake of not having to think about boundary conditions, interpret all coordinates modulo $n$.


Then it's clear that $E A\_{i,j} = 1/5$, by symmetry. It's also not hard to see that:


* $E (A\_{i,j} A\_{i,j+1}) = 0$, since we can't have local maxima both at $(i,j)$ and at $(i,j+1)$. (The case where $X\_{i,j} = X\_{i,j+1}$ can be ignored since it occurs with probability zero.
* I believe $E (A\_{i,j} A\_{i,j+2}) = 2/45$ and $E(A\_{i,j} A\_{i+1,j+1}) = 1/20$. (In any case, these are clearly constants, and their exact values don't matter.)
* $E(A\_{i,j} A\_{k,l}) = 1/25$ for all choices of $i, j, k, l$ other than the ones I already listed and those that clearly are related to them by symmetry. That is, $A\_{i,j}$ and $A\_{k,l}$ are independent unless the rook-neighborhoods of $(i,j)$ and $(k,l)$ overlap.


From this we can compute the mean and variance of $M\_n = \sum\_{i=1}^n \sum\_{j=1}^n A\_{i,j}$, the total number of maxima. Of course $EM = n^2/5$. The variance is a bit harder to compute and I haven't actually written out the computation, but it ought to be asymptotic to $c^2 n^2$ for some positive $c$. (It is the sum of $\Theta(n^2)$ covariances each of order 1.)


Let $\tilde{M}\_n = (M\_n-n^2/5)/(cn)$. Then $\tilde{M}\_n$ has mean $0$ and variance $1$. Is it true that the sequence $\{ \tilde{M\_n} \}\_{n=1}^\infty$ converges in distribution to the standard normal? Intuitively this seems like it should be true -- we're adding up a bunch of small, almost-independent contributions. If it's true, how can this be proven?


This problem came from last year's qualifying exam in probability at Penn; it's been making the rounds around here over the past few days but nobody seems to remember how to do it.



Limit law for the number of local maxima in a square lattice of IID random variables
There are quite a few extensions of the Central Limit Theorem to dependent random variables whose dependence is controlled. This includes the case of a sequence of sums of identically distributed random variables whose dependency graphs have uniformly bounded degrees. ["On Normal Approximations of Distributions in Terms of Dependency Graphs"](https://projecteuclid.org/journals/annals-of-probability/volume-17/issue-4/On-Normal-Approximations-of-Distributions-in-Terms-of-Dependency-Graphs/10.1214/aop/1176991178.full) is overkill, but it includes a sort of Berry-Esseen result bounding the error of the normal approximation.


My guess is that the expected answer on the qualifying exam was not a proof of that extension of the CLT, but was instead, "Recall this locally dependent version of the Central Limit Theorem from class. See that the indicator variables are only locally dependent." I'd be happy to be wrong about that, though.


