MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider $n$ individuals {$1,2, \ldots, n$}. For each (unordered) pair of individuals $i \neq j$ we consider a random variable $X_{i,j}$ that can be thought of as the distance between $i$ and $j$. Each individual kills its closest neighbour (everything happens at the same time). Can we say anything about the distribution of the number of survivors in the limit $n \to \infty$?

The case $X_{i,j} = |Y_i-Y_j|$ where $Y_1, \ldots,Y_N$ are $n$ i.i.d random variables uniformly distributed on $[0,1]$ is the famous "birds on wire" problem.

What about the case where the random variables $X_{i,j}$ are independent and exponentially distributed, say? Has it been studied in the literature?

share|cite|improve this question
If the RVs are independent and non-atomic, then the distribution does not matter. – Ori Gurel-Gurevich Apr 7 '12 at 19:21
up vote 2 down vote accepted

The number of people who kill any given $i$ has asymptotically Poisson distribution (since the events that $j$ kills $i$ for different $j$s are almost independent). Thus the number of survivors $S$ is roughly $N/e$. Since different $i$s are also nearly independent, $S$ is roughly normal.

The oriented version, where dependence is even weaker is just the range of a random function, which is quite simple to analyze.

share|cite|improve this answer
thanks - this makes sense and is verified by a quick simulation. I guess that I have overestimated the dependence between the different individuals. This was motivated by the case where $X_{i,j} = d(Y_i,Y_j)$ where each $Y_i$ is uniformly distributed on the unit 2d square, as discussed on this blog post The dependence structure in this case seems more intricate. – Alekk Apr 8 '12 at 18:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.