4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ If the RVs are independent and non-atomic, then the distribution does not matter. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Apr 7, 2012 at 19:21

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Apr 8, 2012 at 18:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .