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?

  • 2
    $\begingroup$ If the RVs are independent and non-atomic, then the distribution does not matter. $\endgroup$ Apr 7 '12 at 19:21

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.

  • $\begingroup$ 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 goo.gl/ECGLV. The dependence structure in this case seems more intricate. $\endgroup$
    – Alekk
    Apr 8 '12 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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