Description

Seeds randomly disperse on the wind, take root, germinate, and bloom: What is the minimal length of fencing required to enclose the resulting garden? How many corners will the fence have? What is the probability that it encloses a particular landmark? These questions, and many questions of a similar flavour, arise in the probabilistic analysis of spatial models and statistical inference for spatial data.

The simplest probabilistic setting for these questions goes as follows. Consider a fixed number of independent random vectors, distributed according to a particular two-dimensional Gaussian (normal) distribution in the plane. For the given (random) set of points that results, construct the convex hull, that is, the smallest convex set that contains all the points. This gives a (random) convex polygon, known as a Gaussian polygon (since it is generated by a Gaussian distribution).

A simulated Gaussian polygon, using R.

We can understand the random polygon by asking about some of its associated statistics such as its area, perimeter length, number of faces, and so on, all of which are random variables. What can one say about their means, variances, or distribution? For a fixed, small number of points such problems in geometrical probability go back many years and include the famous Sylvester's problem; one question in this domain is to find the probability that if four points are thrown randomly in space, one of the points lies inside the triangle formed by the other three. Statistics of random convex hulls for large numbers of points were studied in the early 1960s by Rényi and Sulanki, and statistician Efron. In statistics, convex hulls give natural geometric approaches to multivariate extremes and outliers. A different, but related, set or work looks at the convex hull generated by the path of a stochastic process in the plane; already in the 1940s Paul Léevy started investigating the many deep and curious properties of the convex hull of Brownian motion, for example.

This project will investigate some probabilistic aspects of convex hull generated by random points in space, with potential applications to statistics, applied sciences, or other areas.

There will scope for simulation.

• Look at some of the recommended literature or other literature you find to see which look most interesting/helpful.
• In particular, look at the extensive survey papers by Bárány and Majumdar et al. and the article by Peyerimhoff (listed below).
• Do a web search for "Gaussian polytope", "random convex hull" or some of the other key words in the above description.
• Investigate $\LaTeX$.
• Try to simulate a Gaussian polygon in R, or Python. The built-in function chull in R can be used to find the convex hull of a point set.
• Look at Projects resources on Blackboard.

Prerequisites

Probability II is essential.

If you have encountered the multivariate normal distribution before (e.g. in one of the Statistics modules) that would speed things up a bit, but it is not essential.

Certain directions for this project will benefit significantly from programming skills, such as using R, python, MATLAB.

Mode of operation and evidence of learning

• We will need some basic properties of the multivariate normal distribution, such as can be found in many books called "Multivariate Analysis" or similar.
• The first results towards understanding the behaviour of the polygon can be explored by the concept of support function from convex geometry, which turns certain multidimensional problems into one-dimensional problems.
• We can then answer, for example, the question of what is the shape of the random polygon as the number of points increases?
• This may lead us into exploring extreme value theory for the Gaussian distribution.
• Roughly 5-6 weeks into term it is expected that students will have chosen their own focus for the project.

Some potential topics

• What is the probability that the random convex hull has a particular property, such as it has exactly $k$ faces, or contains a given point?
• What are some statistics of the random covex hull, e.g., the expected number of faces, the expected volume, perimeter, etc.?
• What if the point set comes from a different distribution, or from some stochastic process?
• What links are their to other problems? E.g., random arcs on a circle?
• What applications are there?

Resources

Reading list. Here are some references that cover some generalities and some of the potential specific directions for further investigation.

• I. Bárány, Sylvester’s question: The probability that n points are in convex position. Ann. Probab. 27 (1999) 2020–2034.
• I. Bárány, Random polytopes, convex bodies, and approximation. pp. 77–118 in Stochastic Geometry, Lecture Notes in Math., 1892, Springer, Berlin, 2007.
• V. Barnett, The ordering of multivariate data. J. Royal Statist. Soc. A 139 (1976) 318–355.
• M. Cranston, P. Hsu, and P. March, Smoothness of the convex hull of planar Brownian motion. Ann. Probab. 17 (1989) 144–150.
• T.M. Cover, The probability that a random game is unfair. Ann. Math. Statist. 37 (1966) 1796–1799.
• B. Efron, The convex hull of a random set of points. Biometrika 52 (1965) 331–343.
• N.P. Jewell and J.P. Romano, Coverage problems and random convex hulls. J. Appl. Probab. 19 (1982) 546–561.
• S.N. Majumdar, A. Comtet, and J. Randon-Furling, Random convex hulls and extreme value statistics. J. Stat. Phys. 138 (2010) 955–1009.
• J. Mycielski, On random convex hulls. Colloq. Math. 51 (1987) 263–265.
• N. Peyerimhoff, Areas and intersections in convex domains. Amer. Math. Monthly 104 (1997) 697–704.
• A. Rényi and R. Sulanke, Über die konvexe Hülle von $n$ zufällig gewählten Punkten. (German) Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1963) 75–84.
• A. Rényi and R. Sulanke, Über die konvexe Hülle von $n$ zufällig gewählten Punkten II. (German) Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 3 (1964) 138–147.
• T.L. Snyder and J.M. Steele, Convex hulls of random walks. Proc. Amer. Math. Soc. 117 (1993) 1165–1173.
• H. Solomon, Geometric Probability. SIAM, 1978.
• F. Spitzer and H. Widom, The circumference of a convex polygon. Proc. Amer. Math. Soc. 12 (1961) 506–509.
• M. Tsao, Bounds on coverage probabilities of the empirical likelihood ratio confidence regions. Ann. Statist. 32 (2004) 1215–1221.
• U. Wagner and E. Welzl, Origin-embracing distributions or a continuous analogue of the upper bound theorem. SCG ’00: Proceedings of the sixteenth annual symposium on computational geometry, ACM, 2000, pp. 50–56.
• J.G. Wendel, A problem in geometric probability. Math. Scand. 11 (1962) 109–111.

Get in touch if you would be interested in doing some simulations and/or have any questions!