The statement of Hoeffding's combinatorial central limit theorem is as follows: given for each $n$, an $n \times n$ matrix $A = (a_{ij})$, one can consider the random diagonal sum: $$\displaystyle f(\sigma) = \sum_{i=1}^n a_{i,\sigma(i)}$$ where $\sigma$ is a uniformly chosen element in $S_n$. Then after appropriate centering and linear scaling, $f(\sigma)$ converges to the standard normal random variable in distribution. The sharpest result in this direction is presumably given by Bolthausen. There has been an extension by Zhao, Bai, Chao, and Liang of this result to the case of doubly indexed matrix $A= (a_{ij,kl})$, and the associated random diagonal $f(\sigma) = \sum_{i \neq j} a_{ij, \sigma(i) \sigma(j)}$, which is also Gaussian in the limit after centering and scaling. But I only know this one extension. It seems that the statement is true for a wide variety of other group actions (the previous two examples correspond to $S_n$ acting on elements in a $n$-object set or on pairs of elements in that set). So for instance one surmises that the action of $GL(n,q)$ would give a q-analogue of combinatorial CLT, or even the action of $SO(n)$ on $S^{n-1}$. But I haven't been able to find any result in these directions. It would be supreme to even prove a result that establishes CLT under a general condition about the group action itself.

  • $\begingroup$ I don't know (in fact, I hadn't heard of this theorem until right now!), but I agree with your judgement that such theorems should exist. $\endgroup$ – Michael Lugo Mar 7 '11 at 3:56
  • $\begingroup$ I should mention that the conjecture in its most general form of group actions was first mentioned to me by Persi Diaconis. At the time I thought it had been well-studied. $\endgroup$ – John Jiang Mar 7 '11 at 3:59
  • $\begingroup$ What are the conditions on the $a_{ij}$? $\endgroup$ – Douglas Zare Mar 7 '11 at 7:46
  • $\begingroup$ The condition is given in Bolthausen's an estimate of the remainder of combinatorial CLT. It roughly translates to the following: if $f(\sigma)$ is centered, then we need $\sqrt{n} \E [f(\sigma)^3] / (\rm{var} f(\sigma))^{3/2}$ to go to zero, much like in the case of Berry-Esseen's theorem. $\endgroup$ – John Jiang Mar 7 '11 at 9:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.