Limit law for the number of local maxima in a square lattice of IID random variables - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T14:06:18Z http://mathoverflow.net/feeds/question/19454 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19454/limit-law-for-the-number-of-local-maxima-in-a-square-lattice-of-iid-random-variab Limit law for the number of local maxima in a square lattice of IID random variables Michael Lugo 2010-03-26T18:56:06Z 2010-03-29T20:57:42Z <p>For <code>$i, j \in \{ 1, \ldots, n \}$</code>, let $X_{i,j}$ be a real-valued random variable uniformly distributed on the interval $[0,1]$. The $X_{i,j}$ are independent.</p> <p>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$.</p> <p>Then it's clear that $E A_{i,j} = 1/5$, by symmetry. It's also not hard to see that:</p> <ul> <li><p>$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.</p></li> <li><p>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.)</p></li> <li><p>$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.</p></li> </ul> <p>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.)</p> <p>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 <code>$\{ \tilde{M_n} \}_{n=1}^\infty$</code> 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?</p> <p>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.</p> http://mathoverflow.net/questions/19454/limit-law-for-the-number-of-local-maxima-in-a-square-lattice-of-iid-random-variab/19516#19516 Answer by Douglas Zare for Limit law for the number of local maxima in a square lattice of IID random variables Douglas Zare 2010-03-27T14:26:29Z 2010-03-27T14:26:29Z <p>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. <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aop/1176991178" rel="nofollow">"On Normal Approximations of Distributions in Terms of Dependency Graphs"</a> is overkill, but it includes a sort of Berry-Esseen result bounding the error of the normal approximation. </p> <p>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. </p> http://mathoverflow.net/questions/19454/limit-law-for-the-number-of-local-maxima-in-a-square-lattice-of-iid-random-variab/19767#19767 Answer by Yuri Bakhtin for Limit law for the number of local maxima in a square lattice of IID random variables Yuri Bakhtin 2010-03-29T20:57:42Z 2010-03-29T20:57:42Z <p>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. </p> <p>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. </p>