Take the 2-minute tour ×

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

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.

  • share|improve this question
    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

    1 Answer 1

    up vote 2 down vote accepted

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

    share|improve this answer
    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

    Your Answer


