Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling
Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling
复制标题
抽象管、改进的包含排除恒等式和不平等以及重要性抽样
DOI：
10.1214/aos/1069362380
复制
发表时间：
1997
影响因子：
4.5
通讯作者：
H. Wynn
中科院分区：
文献类型：
--
作者：
D. Naiman;H. Wynn
许多统计应用需要评估凸多面体的概率含量。在身份中，大多数d的术语都由多面体的各个方面确定，可以使用线性编程来找到。或上限。此外，导致的不平等导致了评估概率含量的重要性，这些方法往往比幼稚的hit-hit-hit-miss monte carlo更有效。我们介绍一个管子由一对（a，s）组成，其中a =（a1，...，a n）是一组集合，S是一个简单的复合物，每个子复合物s（x）= { f∈S：x∈I∈ f a i）每当x∈Ui n = 1 a i时，都比naiman和wynn提出的概念更强。 R D中的空间通过Voronoi分解产生抽象的管子及其相关的Delauney双重复合物。 n i-1 a i，上限和下限是通过在偶数或奇数深度截断的身份来获得的。案例引入了抽象子管的概念，并显示（a，s 1）是（a，s 2）的子管至少是因此，与（a，s 2）相应的不等式。
Numerous statistical applications require the evaluation of the probability content of a convex polyhedron. We demonstrate for a given polyhedron in R d that there is a depth d inclusion-exclusion identity for its indicator function, which is a linear combination of indicator functions of intersections of at most d half-spaces. Terms in the identity are determined by the incidence of the facets of the polyhedron, which can be found using linear programming. This identity can be truncated at any depth to give a lower or upper bound. In addition, the resulting inequalities lead to importance sampling schemes for evaluating the probability content, and these methods tend to be more efficient than the naive hit-or-miss Monte Carlo method. These results arise in a more general setting which we introduce. An tube consists of a pair (A, S) where A = (A1,..., A n ) is a collection of sets, S is a simplicial complex, and where each subcomplex S(x) = {F ∈ S:x ∈ ∩ i ∈ F A i ) is contractible whenever x ∈ U i n =1 A i . The notion presented here is stronger than the one introduced earlier by Naiman and Wynn. Several examples are given and key consequences are demonstrated. In particular, arrangements of points and half-spaces in R d give rise to abstract tubes via Voronoi decompositions and their associated Delauney dual complexes. Every abstract tube is shown to give rise to an inclusion-exclusion identity for I U n i-1 A i , and upper and lower bounds are obtained by truncating the identity at an even or an odd depth. This property is analogous to the truncation inequality property of the classical inclusion-exclusion identity, which may be viewed as a special case. The notion of an abstract subtube is introduced, and it is shown that if (A, S 1 ) is a subtube of (A, S 2 ) then the truncation inequality gotten from the depth m truncation for (A, S 1 ) is at least as sharp as the corresponding inequality from (A, S 2 ). As a consequence, the generalized inclusion-exclusion inequalities are always at least as sharp as their classical counterparts.