Coverage processes on spheres and condition numbers for linear programming

Abstract

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 \in [\pi /2,\pi ]$ and an upper bound for $p(n,m,\alpha )$ in the case $\alpha \in [0,\pi /2]$ which tends to $p(n,m,\pi /2)$ when $\alpha \to \pi /2$. In the case $\alpha \in [0,\pi /2]$ this yields upper bounds for the expected number of spherical caps of radius $\alpha$ that are needed to cover $S^m$. Secondly, we study the condition number $\mathcal{C}(A)$ of the linear programming feasibility problem $\exists x\in {\mathbb{R}}^{m+1}Ax\le 0,x\ne 0$ where $A\in {\mathbb{R}}^{n\times (m+1)}$ is randomly chosen according to the standard normal distribution. We exactly determine the distribution of $\mathcal{C}(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 $\mathbf{E}(\ln \mathcal{C}(A))\le 2\ln (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.

Published in at http://dx.doi.org/10.1214/09-AOP489 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (1)

• From Steiner Formulas for Cones to Concentration of Intrinsic Volumes