COVERAGE PROCESSES ON SPHERES AND CONDITION NUMBERS FOR LINEAR PROGRAMMING

• 成果类型: Article
• 署名作者: Buergisser, Peter; Cucker, Felipe; Lotz, Martin
• 署名单位: University of Paderborn; City University of Hong Kong; University of Oxford
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/09-AOP489
• 发表日期: 2010
• 页码: 570-604
• 关键词: conic systems; circle; arcs; distributions; probability

摘要

This paper has two agendas. Firstly, we exhibit new results for coverage processes. Let p(n, m, alpha) be the probability that n spherical caps of angular radius alpha in S-m do not cover the whole sphere S-m. We give an exact formula for p (n, m, alpha) in the case alpha is an element of [pi/2, pi] and an upper bound for p(n, m, alpha) in the case alpha is an element of [0, pi/2] which tends to p(n, m, pi/2) when alpha -> pi/2. In the case alpha is an element of [0, pi/2] this yields upper bounds for the expected number of spherical caps of radius a that are needed to cover S-m. Secondly, we study the condition number b(A) of the linear programming feasibility problem there exists x is an element of Rm+1 Ax <= 0, x not equal 0 where A is an element of Rnx(m+1) is randomly chosen according to the standard normal distribution. We exactly determine the distribution of b(A) conditioned to A being feasible and provide an upper bound on the distribution function in the infeasible case. Using these results, we show that E(In b(A)) <= 2 In(m + 1) + 3.31 for all n > m, the sharpest bound for this expectancy as of today. Both agendas are related through a result which translates between coverage and condition.