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

-
Thanks for the response! Two comments: 1) This answers a slightly different question, since number of balls may not be exactly m (assuming you want to retain independence). Presumably that is ok, since we can then take out/add the necessary order of root-m balls, which are negligible. 2) Thinking about this a little more, if I have a measure that is at least epsilon times the uniform measure, this gives me about order of n matchings by the standard split-into-good-and-bad-parts trick. So, maybe this is pretty general. – user2282 Dec 4 '09 at 20:13
I don't know if anybody else is following this, but after a little bit of thought, you are certainly correct that the constant's dependence on alpha is computable fairly easily, as is an up-to-constants rate of convergence, for this problem... which of course is very close to mine. Out of curiosity, can a good rate be obtained using the Kingsman's theorem approach? I have never seen a 'quantitative' version, but surely somebody must have written one down. – user2282 Dec 5 '09 at 5:27
a Martingale approach (Azuma for example) says that the probability that |M_n/n - E(M_n)/n| is greater that T decreases like 2.exp(-C.T^2.n) so that Borel-Cantelli shows that almost surely: M_n/n - E(M_n/n) = O(sqrt(log(n)/n)) But it does not seem easy to compute E(M_n/n), is it ? – Alekk Dec 5 '09 at 14:18