TEXT SIZE

search for



CrossRef (0)
A New Integral Representation of the Coverage Probability of a Random Convex Hull
Commun. Stat. Appl. Methods 2015;22:69-80
Published online January 31, 2015
© 2015 Korean Statistical Society.

Won Sona, Chi Tim Ng1,b, and Johan Lima

aDepartment of Statistics, Seoul National University, Korea, bDepartment of Statistics, Chonnam National University, Korea
Correspondence to: Chi Tim Ng
Department of Statistics, Chonnam National University, 77 Yongbong-ro, Buk-gu, Gwangju 500-757, Korea. E-mail: easterlyng@gmail.com
Received November 25, 2014; Revised December 30, 2014; Accepted December 30, 2014.
 Abstract

In this paper, the probability that a given point is covered by a random convex hull generated by independent and identically-distributed random points in a plane is studied. It is shown that such probability can be expressed in terms of an integral that can be approximated numerically by function-evaluations over the grid-points in a 2-dimensional space. The new integral representation allows such probability be computed efficiently. The computational burdens under the proposed integral representation and those in the existing literature are compared. The proposed method is illustrated through numerical examples where the random points are drawn from (i) uniform distribution over a square and (ii) bivariate normal distribution over the two-dimensional Euclidean space. The applications of the proposed method in statistics are are discussed.

Keywords : Coverage probability, integral representation, random convex hull, random points, stochastic geometry
1. Introduction

Since the work of Renyi and Sulanke (1963a, b), the convex hull generated by independent and identically-distributed random points (random convex hull in short) has attracted a considerable attention in the literatures of stochastic geometry and has been employed in a variety of statistical procedures. For example, Barnett (1976) defines an ordering of the multivariate data based on the notion of convex hull peeling depth. In Cook (1979), the random convex hull generated by the data points is used to identify the influential observations in linear regression. In the data envelopment analysis, the random convex hull is an important tool for estimating the frontier function (Jeong, 2004; Jeong and Park, 2006) and finding the optimal classifiers (Fawcett and Niculescu-Mizil, 2007; Lim and Won, 2012). Recently, Ng et al. (2014) develops a test of independence of two random variables based on the area of the random convex hull.

Though there are endeavors of establishing the probabilistic properties of the random convex hull, most existing works focus on the situations of either (i) the sample size goes to infinity or (ii) the random points are generated from the uniform distribution. The classical results in Renyi and Sulanke (1963a, b) of the expected number of vertexes, the perimeter, and the area of the random convex hull are applicable only if the sample size goes to infinity. Subsequent studies in Hueter (1994, 1999) andHsing (1994) also focus on the asymptotic behaviors of the random convex hull. Exact formulas of the functionals of the random convex hull are studied in for example, Buchta (2005, 2006). However, the results are obtained only under the assumption that the random points are drawn from the uniform distribution over certain bounded regions.

In order to obtain the probabilistic properties of the random convex hull in the finite-sample cases, Efron (1965) considers the probability that a given point p = (x, y) is not covered by the convex hull of n independent points {pi = (xi, yi), i = 1, 2, . . . , n} from a general distribution F(x, y) on ?2. Let q(p, n) be such a probability. By providing an integral representation of q(p, n), Efron (1965) further obtains a formula of the expected area of the random convex hull. This integral representation is derived under the coordinate system proposed by Santalo (1953) that is rather complicated to use in practice. As we will indicate in Section 2.3, evaluating q(p, n) under this integral representation requires function-evaluations over the grid-points in a 3-dimensional space.

The main contribution of this paper is to establish a new integral representation that allows q(p, n) be evaluated numerically by function-evaluations over the grid-points in a 2-dimensional space.

This short note is organized as follows. In Section 2, a new integral representation of q(p, n) is given and the numerical algorithm of evaluating q(p, n) is proposed. The results are applicable to a general distribution F(x, y) under finite-sample cases. In Section 3, we show that q(p, n) can further be simplified in the special cases when the random points are drawn from the uniform distribution on a square and from the bivariate normal distribution with an arbitrarily given covariance matrix. Numerical examples are also provided. In the concluding section, the applications to certain statistical problems are discussed.

2. Probability

Let convH(p1, p2, . . . , pn) be the smallest convex hull containing n independent sample points pi = (xi, yi)i=1,...,n distributed according to law F(x, y) over a convex but not necessarily bounded region D. Denote the joint density function corresponding to F by f (x, y). In this section, we derive a new integral representation of q(p, n), the probability that a given point p = (x, y) 늿 D does not belong to convH((p1, p2, . . . , pn). General results for arbitrarily given distribution F(쨌) and convex region D are given in this article. Special cases will be discussed in Section 3.

2.1. Toy example

Before presenting the new integral representation of q(p, n), let us consider the game described below. The sample space of this game is discrete. Later on, a continuous version of such game is used to obtain q(p, n).

Let us consider the following game of lucky wheel as shown in Figure 1. Assume that the lucky wheel is divided into 12 sectors. These sectors are denoted by (1, 2), (2, 3), (3, 4), . . . , (12, 1) respectively. The first and the second number in the brackets are the starting-points and the end-points of the sector anticlockwise. Each sector can either be occupied or not occupied. Here, the events that the sectors are occupied are not necessarily exclusive. The sample space for this problem is then the set of 12-dimensional ordered tuples with 0 (for non occupied) or 1 (for occupied) as the coordinate values. The probability mass function of this sample space is given. For simplicity, assume that the mass function at (0, 0, . . . , 0) is zero. If there are at least six (i.e., half of 12) consecutive sectors that are not occupied, you win, otherwise, you lose. What is the winning probability?

To answer the above question, rewrite the event E of getting win as the union of the following events.

E1=The?sector?(12,1)?is?occupied?while?(1,7)?is?not.E2=The?sector?(1,2)?is?occupied?while?(2,8)?is?not.???E11=The?sector?(10,11)?is?occupied?while?(11,5)?is?not.E12=The?sector?(11,12)?is?occupied?while?(12,6)?is?not.

In the above, note that 6 = 12/2 guarantees that these events E1, E2, . . . , E12 are mutually exclusive. The event E1 is equivalent to that (12, 7) is occupied while (1, 7) is not occupied. Therefore,

P(E1)=P((12,7)?is?occupied)-P((1,7)?is?occupied).

Similarly, the probabilities of events E2 to E12 can be obtained.

2.2. General case

Now we return to our original question, 쐗hat is the probability that a fixed point p = (x, y) 늿 D does not belong to the convex hull.

The following two statements are equivalent.

  • 1. p does not belong to the convex hull.

  • 2. There is a sector subtended by p and an angle greater than not occupied by any points pi, i = 1, 2, . . . , n.

Some analogies between the lucky wheel game and the random convex hull are as follows. The lucky wheel in the game has 12 sectors of 30 degrees. In the domain D has infinitely many sectors subtended by the point p and angles of infinitestimal sizes . To win the game, one needs to get at least six consecutive sectors that is not occupied. In order that p is outside the random convex hull, it requires the existence of a sector with subtended angle greater than or equal to that is not occupied by any random points.

For any given 2 > 1, the probability that (1, 2) is occupied is

1-{P(p1(2,1+2))}n.

Let us define G(s, t) = ?(p1 늿 (s, t)). It is not difficult to see by analogy that the required probability is

q(p,n)=limNk=1N{P?((k-,k+)?is?occupied)-P?((k,k+)?is?occupied)}=limNk=1N{[G(k+,k+2)]n-[G(k+,k-+2)]n}=02tG(s+,t)n|t=s+2ds=n02[G(s+,s+2)]n-1G(s+,t)t|t=s+2ds.

In the above, k = k 쨌 2/N for k = 1, 2, . . . , N and = 2/N. In addition,

G(s,t)=st0r()f(x+r?cos?,y+r?sin?)r?drd.

If D is bounded, r() can be defined as shown in Figure 2 and if D = ?2, r() can be replaced by 닞.

By differentiating G(s, t) with respect to t, we have

G(s,t)t=0r(t)f(x+r?cos?t,y+r?sin?t)r?dr.

Since the above partial derivative does not involve s, it is convenient to introduce the notation

h(t)=G(s,t)t.

Note that h(t) is a function of t only and does not depend on s. Then, the required probability can be written as

q(p,n)=P(p=(x,y)?convH(p1,,pn))=n02h(s+)[G(s,s+)]n-1?ds.

In the above, G(s, s + ) is a function of p = (x, y).

2.3. Computational issue

In this subsection, we show that the new integral representation given in Subsection 2.2 allows the probability be evaluated numerically by function-evaluations over the grid-points in a 2-dimensional space.

Note that Equation (2.1) can be rewritten as

q(p,n)=n02h(s+)?[ss+h()d]n-1?ds.
Algorithm
  • Step 1: Choose integers M and N. Set k = 2k/2N for k = 0, 1, 2, . . . , 2N ? 1.

  • Step 2: For k = 0, 1, 2, . . . , 2N ? 1, evaluate the integral

    h()=0r(k)f(x+r?cos?k,y+r?sin?k)r?dr

    using any appropriate numerical integration method with M function-evaluations.

  • Step 3: Compute I0=N-1k=0N-1h(k).

  • Step 4: For k = 1, 2, 3, , . . . , 2N ? 1, compute Ik = Ik?1 + N?1[h(k) ? h(k?N)].

  • Step 5: Obtain q(p,n)?nN-1k=02N-1h(k+N)Ikn-1.

This algorithm requires only MN function-evaluations and the computational burden of Step 3?5 is only O(N). If the domain is infinite, Gaussian quadrature method can be chosen in Step 2.

It is interesting to note that the integral representation of q(p, n) in Equation (5.13) of Efron (1965) is

q(p,n)=12n0-n+1((p,),)?-(p,)?f(x(,,),y(,,)),

where

(p,)=x?cos?+y?sin?,(p,)=y?cos?-x?sin?,x(,,)=?cos?-?sin?,y(,,)=?cos?+?sin?,n+1(,)=n-1(,)-(1-(,))n-1,(,)=-f(x(,,),y(,,))???dd.

The integral (, ) involves the three-dimensional function f (x(, , ), y(, , )). As such, the probability q(p, n) has to be approximated numerically with function-evaluations over the grid-points in a three-dimensional space.

3. Two Special Cases

The following two special cases will be discussed in this section. In the first example, F(쨌) is the uniform distribution function over a bounded convex set D. In the second example, F(쨌) is the bivariate Gaussian distribution function with mean zero and variance covariance matrix 닊.

3.1. Uniform distribution on [0, 1]2

Consider the case that the random points pi, i = 1, 2, . . . , n are drawn independently from the uniform distribution over [0, 1]2. Below, we only consider the case p = (x, y) with 0 돞 x, y 돞 1/2. The probabilities for other values of p can be obtained by symmetry. Under our uniform-distribution assumptions, the function G(s, t) can be written as

G(s,t)=12str2()?d

and thereby the required probability is

q(p,n)=n202r2(s+)Gn-1(s,s+)?ds.

Here, both r2() and G(s, t) depend on p = (x, y).

Let 0 < 1/2 돞 23 돞 3/2 돞 4 be the angles defined as follows ,

tan(2-4)=y1-x,tan(1)=1-y1-x,tan(-2)=1-yx,tan(3-)=yx.

In this case,

h(t)=120r(t)r?dr=12r2(t),

and r() is defined as:

r()={(1-x)1cos?,if???4-21,1-ysin?,if???12,1-ysin(-),if???22,xcos(-),if???2,xcos(-),if???3,ycos(32-),if???332.

Finally,

G(s,s+)=ss+12r()2d

and

q(p,n)=n02h(s+)[G(s,s+)]n-1?ds.

Next, numerical examples are presented. Here, we compute the probability q(p, n) for various p and n = 10, 100 and 1000. The points p is chosen as points in {(x, y)|x = i * 0.01, y = 0.01 * j, i, j = 1, 2, . . . , 99}. Figure 3 shows the probabilities q(p, n) for different p and n.

3.2. Bivariate normal distribution

Consider the case that the random points pi , i = 1, 2, . . . , n are drawn independently from the bivariate Normal distribution with mean zero and variance covariance matrix 닊.

To compute the probability q(p, n), we first compute G(s, s + ) and h(s). To find G(s, s + ) , it is beneficial to consider the rectangular coordinates rather than the polar coordinates. In this case, G(s, s + ) is the probability measure of the shaded region shown in Figure 5. Let (, ) be the coordinate of a random point. Consider the following rotation and translation,

()=UsT?(-x-y),

where

UsT=(cos?ssin?s-sin?scos?s).

With such transform, the required probability becomes P( > 0) . It can be verified that

()~N?(-UsT?(xy),?UsTUs).

Let

(p,s)=x?sin?s-y?cos?s

and

2(p,s)=(sin?s,-cos?s)(sin?s,-cos?s)T.

We have

G(s,s+)=1-?(-(p,s)(p,s)),

where 過(쨌) is the cumulative distribution function of the standard normal random variable.

Next, we find h(t). The integral

h(p,t)=0f(x+r?cos?t,y+r?sin?t)rdr

can be found explicitly. Let

E(p)=(x,y)-1(x,y)T,B(p,t)=(x,y)-1(cos?t,sin?t)T,C(p,t)=(cos?t,sin?t)-1(cos?t,sin?t)T.

We have

h(p,t)=(2)-12??-12C-1(t)?exp?{-12?(E-B2(t)C-1(t))}[?(B(t)C12(t))-B(t)C12(t)?{1-?(B(t)C12(t))}].

Again,

q(p,n)=n02h(s+)[G(s,s+)]n-1?ds.

Numerical examples are given in the following. The probability q(p, n) is computed for three bivariate normal distributions with mean (0, 0)T and covariance matrices

=(1001),(10.30.31),?????????and?????????(10.70.71)

respectively. For each 닊, q(p, n) are computed for n = 10, 100, and 1000 and p from the grid points over [?5, 5] 횞 [?5, 5]. The results are shown in Figure 6.

4. Conclusion

In this paper, a new integral representation is given for q(p, n), the probability that a random convex hull generated by independent and identically-distributed random points covers p. Under such new representation, q(p, n) can be approximated numerically by function-evaluations over the grid-points in a 2-dimensional space. On the contrary, the classical integral representation obtained in Efron (1965) requires function-evaluations over the grid-points in a 3-dimensional space. The new results allow even more efficient computation of q(p, n) in the finite-sample cases. Moreover, the proofs provided in the present paper is much simpler and intuitive than those in Efron (1965).

One of the future research directions is to apply the new integral representation and to further simplify the formulas of a number of functionals of the random convex hull, including the moments of area and perimeters etc. For example, the expected area of the random convex hull convH(p1, p2, . . . , pn), denoted by An, can be written as

An=q(p,n)?dxdy.

The probability that the n + 1th observation pn+1 = (xn+1, yn+1) does not belong to the random convex hull convH((p1, p2, . . . , pn) is

un+1=1-q(p,n)?dF(x,y).

Indeed, this is the probability that a new random point forms a new vertex of the convex hull. Therefore, un+1 can be useful in the simulation of the random convex hull.

In the data envelopment analysis, the probability q(p, n) can be used to obtain the required number of sample size n so that the given point p is within the random convex hull. Such sample size is an estimator of the frontier function (or the domain) of the bivariate distribution on a plane (Jeong, 2004; Jeong and Park, 2006).

It is also an interesting research direction of generalizing the results to the higher dimensional situations. The improved efficiency in the computation would facilitates many applications of random convex hull in the multivariate data analysis in the future.

Figures
Fig. 1. An illustration of lucky wheel
Fig. 2. Notations
Fig. 3. Uniform distribution
Fig. 4. Uniform distribution
Fig. 5. Bivariate normal distribution
Fig. 6. Normal Distribution
References
  1. Barnett, V (1976). The ordering of multivariate data. (with discussion). Journal of the Royal Statistical Society, Series A. 139, 318-339.
    CrossRef
  2. Buchta, C (2005). An identity relating moments of functionals of convex hulls. Discrete Computational Geometry. 33, 125-142.
    CrossRef
  3. Buchta, C (2006). The exact distribution of the number of vertices of a random convex chain. Mathematika. 53, 247-254.
    CrossRef
  4. Cook, RD (1979). Influential observations in linear regression. Journal of the American Statistical Association. 74, 169-174.
    CrossRef
  5. Efron, B (1965). The convex hull of random set of points. Biometrika. 52, 331-343.
    CrossRef
  6. Fawcett, T, and Niculescu-Mizil, A (2007). PAV and the ROC convex hull. Machine Learning. 68, 97-106.
    CrossRef
  7. Hsing, T (1994). On the asymptotic distribution of the area outside a random convex hull in a disk. Annals of Applied Probability. 4, 478-493.
    CrossRef
  8. Hueter, I (1994). The convex hull of normal samples. Journal of Applied Probability. 26, 855-875.
    CrossRef
  9. Hueter, I (1999). Limit theorems for the convex hull of random points in higher dimensions. Transactions of the American Mathematical Society. 351, 4337-4363.
    CrossRef
  10. Jeong, S (2004). Asymptotic distribution of DEA efficiency scores. Journal of Korean Statistical Society. 33, 449-458.
  11. Jeong, S, and Park, BU (2006). Large sample approximation of the distribution for convex hull estimators of boundaries. Scandinavian Journal of Statistics. 33, 139-151.
    CrossRef
  12. Lim, J, and Won, J (2012). ROC convex hull and nonparametric maximum likelihood estimation. Machine Learning. 88, 433-444.
    CrossRef
  13. Ng, CT, Lim, J, Lee, KE, Yu, D, and Choi, S (2014). A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square. Computational Statistics. 29, 1187-1205.
    CrossRef
  14. Renyi, A, and Sulanke, R (1963a). ?ber die knovexe H?lle von n zuf?llig gew?hlten Punkten. Zeitschrift f?r Wahrscheinlichkeitstheorie und verwandte Gebiete. 2, 75-84.
    CrossRef
  15. Renyi, A, and Sulanke, R (1963b). ?ber die knovexe H?lle von n zuf?llig gew?hlten Punkten. Zeitschrift f?r Wahrscheinlichkeitstheorie und verwandte Gebiete. 3, 138-147.
    CrossRef
  16. Santalo, LA (1953). Introduction to integral geometry. Actualities Scientifiques et Industrielles. Paris: Hermann.