Consider $n$ points generated randomly and uniformly on a unit square. What is the expected value of the area (as a function of $n$) enclosed by the convex hull of the set of points?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
Update: By a result of Buchta (Zufallspolygone in konvexen Vielecken, Crelle, 1984; available on digizeitschriften.de) there is a general formula for this expected value, it is $$1 -\frac{8}{3(n+1)} \bigl( \sum_{k=1}^{n+1} \frac{1}{k} (1 - \frac{1}{2^k}) - \frac{1}{(n+1)2^{n+1}} \bigr) $$ yielding (starting with $n=3$): $11/144$, $11/72$, $79/360$, $199/720$, and so on.
The paper contains in fact a more general result, where the problem is solved for any convex $m$-gon; not just the square.
For asymtotics see other answer(s).
--
Old version (highly incomplete and wrong guess)
For $n=3$ the expected value is $11/144$ and for $n=4$ it is $11/72$.
This information is taken from a somewhat recent paper (2004) by Johan Philip where the respective distribution functions are studied in detail. I did not see any mention of exact values for other small values of $n$ there (the asymptocic result given already is mentioned though), so they might be unknown.
-
2$\begingroup$ Some additional information not directly related: the analog result for 4 points in a cube is rather recent (Zinani; 2003) where the solution is 3977/216000 - pi^2 / 2160 . So, I really guess explicit values for most n could well be unknown. $\endgroup$– user9072Commented Apr 4, 2012 at 13:05
-
2$\begingroup$ Do you know if in the $2$-dimensional case the expected values continue to be rational? If so, is there any easy way to see it? $\endgroup$ Commented Apr 5, 2012 at 3:37
-
1$\begingroup$ @Daniel Litt: thanks for the question; turns out my guess was wrong. The edit to appear soon, should clarify things. $\endgroup$– user9072Commented Apr 5, 2012 at 16:35
-
$\begingroup$ @quid: Thanks! That does indeed clarify things :). $\endgroup$ Commented Apr 6, 2012 at 16:53
$\begingroup$
$\endgroup$
1
Let $A$ be the expected area. Then: $$\lim_{n \rightarrow \infty} \frac{n}{\ln n} (1 - A) = \frac{8}{3} \;.$$ This can be found in many places, e.g., this MathWorld article.
[Updated with comparisons between the above formula (Asymp) and the exact formula (Exact) found by quid.] $$ \begin{array}{lcccc} n & & \mathrm{Asymp} & &\mathrm{Exact} \\ n=10 & : & A = 0.39 & : & 0.44 \\ n=100 & : & A = 0.89 & : & 0.88 \\ n=1000 & : & A = 0.98 & : & 0.98 \end{array} $$
answered Apr 4, 2012 at 12:25
-
$\begingroup$ Thanks, it's a start. Can we say anything about relatively small values of $n$ (i.e. not in the limit behavior)? $\endgroup$ Commented Apr 4, 2012 at 12:33
$\begingroup$
$\endgroup$
1
For any convex set $K$ in dimension $d$ with volume $V(K)$, it is aymptotically $$V(K)-\frac{T(K)}{(d+1)^{d-1}(d-1)!}n^{-1}ln(n)^{d-1}+O(n^{-1}ln(n)^{d-2}ln(ln(n)))$$ (see {New perspectives in stochastic geometry} by W. Kendall and I. Molchanov, p. 49) where $T(K)$ is the number of "flags", i.e. of sequences $f_0\subset f_1 \subset ... \subset f_{d-1}$ where $f_i$ is an $i$-dimensional facet. There is an abundant literature for random convex hulls and if you're interested there might be an exact closed formula for the square.
-
$\begingroup$ Is there perhaps a factor of V(K) missing from the second term? Compare the formula for $E_{n}(V)$ on p. 2 of this: link.springer.com/article/10.1007/BF02574691 $\endgroup$ Commented Feb 18, 2021 at 15:13