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

Question

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.

Answer 1

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" 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.

Answer 2

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.

The sums over blocks are i.i.d. and satisfy CLT for arrays, and the correction from the "corridors" is relatively small and does not spoil the CLT.