Parity, Balls and Boxes

2009-12-03T15:39:50Z

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

Some side comments:

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.

Answer by Alekk for Parity, Balls and Boxes

2009-12-04T03:48:50Z

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

Parity, Balls and Boxes - MathOverflow

Parity, Balls and Boxes

Answer by Alekk for Parity, Balls and Boxes