Very nice clean reasoning! I've been using the language of expectations, but I think it's more accurate to say we seek the limit as n -> oo of the probability that a random point is a singleton. Or better, the heck with probability altogether -- we're just aiming for the limit as n -> oo of the fraction of singletons. Dan P.S. It seems plausible that the nonlinear recurrence relation Emma derives for s[n] would imply s[n] -> 1/e^2, but it would be nice to see a proof. Probably much harder: Can it be solved in closed form for s[n] as a function of n ? On 2012-11-29, at 6:16 PM, Emma Cohen wrote:
In the 1-D case for the sequential seating problem we can just calculate the expected number s[n] of singletons (out of n original points) recursively by conditioning on which of the n-1 possible locations we choose for the first pair. Since placing the first pair at position k separates the line into two unfilled lines, one of length k-1 and one of length n-k-1, we have \[s[n] = \frac{1}{n-1} \sum_{k=1}^{n-1} (s[k-1] + s[n-k-1]) = \frac{2}{n-1} \sum_{k=0}^{n-2} s[k] = \frac{n-2}{n-1} s[n-1] + \frac{2}{n-1} s[n-2]\] with s[0] = 0 and s[1] = 1. Mathematica confirms that s[n]/n -> 1/e^2.
The 2-D case does not seem to admit such an obvious recurrence.