# Parity, Balls and Boxes

Start with a distribution $\mu$ on [n], and drop m balls into these n+1 slots independently and according to the distribution &mu. That is, we have iid random variables x 1 through x m distributed according to &mu. Assume that m is close to the same size as n.

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 b(i) = x a(i) + 1.

My (purposefully vague) question is: Is there, with high probability, a partial matching that includes many of the balls?

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

• We need that m be not much smaller than n, as otherwise most points will be fairly far apart.
• 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.

• I have a minor question regarding your notation. Is [n] the same as the set {0,1,…,n}? I am guessing it is. And if so, is your question really the following: If m balls are independently dropped in these n+1 positions, do many of them have at least one neighbour? – Harald Hanche-Olsen Dec 3 '09 at 16:05
• Thanks for the clarifications! Yes: In my notation, [n] ={0,1,...,n} No: if we drop 1 ball at 0, and 10000 balls at 1, all of them have at least one neighbour, but the best partial matching uses only 2 balls. Clarification: I agree that for 'reasonable' distributions, my question and the 'at-least-one-neighbour' question will have similar answers. – user2282 Dec 3 '09 at 16:36
• Ah; I missed the “no number is repeated” part. So you're looking for a large number of nonoverlapping pairs of neighbours, then. – Harald Hanche-Olsen Dec 3 '09 at 17:16

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.
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}$ .