"birds on wire" type problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T01:16:41Z http://mathoverflow.net/feeds/question/93427 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93427/birds-on-wire-type-problem "birds on wire" type problem Alekk 2012-04-07T15:10:54Z 2012-04-08T01:56:20Z <p>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$?</p> <p>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. </p> <p>What about the case where the random variables $X_{i,j}$ are independent and exponentially distributed, say? Has it been studied in the literature?</p> http://mathoverflow.net/questions/93427/birds-on-wire-type-problem/93473#93473 Answer by Omer for "birds on wire" type problem Omer 2012-04-08T01:56:20Z 2012-04-08T01:56:20Z <p>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.</p> <p>The oriented version, where dependence is even weaker is just the range of a random function, which is quite simple to analyze.</p>