**Local limit theorem for large deviations and statistical box-tests **

*Igor Semaev*

**Abstract: **Let $n$ particles be independently allocated into $N$ boxes, where the $l$-th box appears with the probability $a_l$. Let $\mu_r$ be the number of boxes with exactly $r$ particles and $\mu=[ \mu_{r_1},\ldots, \mu_{r_m}]$. Asymptotical behavior of such random variables as $N$ tends to infinity was studied by many authors. It was previously known that if $Na_l$ are all upper bounded and $n/N$ is upper and lower bounded by positive constants, then $\mu$ tends in distribution to a multivariate normal low. A stronger statement, namely
a large deviation local limit theorem for $\mu$ under the same condition, is here proved. Also all cumulants of $\mu$ are proved to be $O(N)$.

Then we study the hypothesis testing that the box distribution is uniform, denoted $h$, with a recently introduced box-test. Its statistic is a quadratic form in variables $\mu-\mathbf{E}\mu(h)$. For a wide area of non-uniform $a_l$, an asymptotical relation for the power of the quadratic and linear box-tests, the statistics of the latter are linear functions of $\mu$, is proved. In particular, the quadratic test asymptotically is at least as powerful as any of the linear box-tests, including the well-known empty-box test if $\mu_0$ is in $\mu$.

**Category / Keywords: **secret-key cryptography / hash functions

**Date: **received 6 Jun 2011

**Contact author: **igor at ii uib no

**Available format(s): **PDF | BibTeX Citation

**Version: **20110608:113525 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]