Parity, Balls and Boxes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T06:05:24Z http://mathoverflow.net/feeds/question/7677 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7677/parity-balls-and-boxes Parity, Balls and Boxes smalldeviations 2009-12-03T15:39:50Z 2009-12-04T16:31:54Z <p>Start with a distribution $\mu$ on [n], and drop m balls into these n+1 slots independently and according to the distribution &amp;mu. That is, we have iid random variables x <sub> 1 </sub> through x <sub> m </sub> distributed according to &amp;mu. Assume that m is close to the same size as n.</p> <p>I call a collection of tuples (a(i), b (i)), with all a(i), b(i) between 1 and m, a partial matching if no number is repeated, and for all i, x <sub> b(i) </sub> = x <sub> a(i) </sub> + 1.</p> <p>My (purposefully vague) question is: Is there, with high probability, a partial matching that includes many of the balls?</p> <p>Of course, for some distributions this obviously doesn't happen. I would be happy if somebody had a 'standard argument' for this type of question in nice cases, and maybe we could get some understanding of what makes it run (and so in what cases it doesn't).</p> <p>Some side comments: <li>We need that m be not much smaller than n, as otherwise most points will be fairly far apart. <li>For nice distributions, such as the uniform or binomial, one can do calculations much like the birthday paradox, and get some semi-plausible answers. I don't know if these are best possible, and would love to hear it if somebody out there has a nice clearly-tight argument for nice distributions. I was thinking of just asking about the uniform distribution, as I guess somebody out there must have a beautiful argument.</p> http://mathoverflow.net/questions/7677/parity-balls-and-boxes/7745#7745 Answer by Alekk for Parity, Balls and Boxes Alekk 2009-12-04T03:48:50Z 2009-12-04T16:31:54Z <p>if $m=\alpha n$ and $\mu$ is uniform, it seems like a basic sub-additivity argument shows that $\frac{M_n}{n}$ converges almost surely to a constant $C_{\alpha}$, where $M_n$ is the cardinal of a maximal partial match of $[n]$. To see that, put a Poisson process $P$ on the real line with intensity $\alpha$ and say that there are $P((k;k+1)) = Poisson(\alpha)$ balls in the slot $k$. Then, if $M_{m,n}$ is the cardinal of a maximal partial match of ${m,m+1, \ldots,n-1}$ (with your notations), then $M_{p,r} \geq M_{p,q} + M_{q,r}$ so that a Kingsman-like sub-additive theorem holds and give the conclusion.</p> <p>Notice also that the number of missed slots is very concentrated around $n e^{-\alpha}$ (concentration of order $\sqrt{n}$) so that I would not be surprised if one could compute this constant $C_{\alpha}$ . </p>