# Limit law for the number of local maxima in a square lattice of IID random variables

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.

-

This is an archetypical example where classical Bernstein's method of "sections" or "blocks" works. Among popular probability books, Kai Lai Chung's "A Course in Probability Theory" contains a complete proof of CLT for m-dependent r.v.'s indexed by $\mathbb{N}$. Here the indexation is 2-dimensional, but the idea is absolutely the same: divide the $N\times N$ array of r.v.'s into independent blocks of size that grows with $N$, with small "corridors" separating them. The corridors are needed to make the sums over blocks independent.