@article{BCL-Coverage-Processes-On-Spheres-And-Condition-Numbers-For-Linear-Programming,
Title = {Coverage Processes on Spheres and Condition Numbers for Linear Programming},
Author = {Peter Bürgisser and Felipe Cucker and Martin Lotz},
Pages = {570-604},
Year = {2010},
Issn = {0091-1798},
Doi = {10.1214/09-AOP489},
Journal = {The Annals of Probability},
Volume = {38},
Number = {2},
Abstract = {This paper has two agendas. Firstly, we exhibit new results for coverage processes. Let $p(n,m,a)$ be the probability that n spherical caps of angular radius $a$ in $S^m$ do not cover the whole sphere $S^m$. We give an exact formula for $p(n,m,a)$ in the case $a\in [\frac\pi2,\pi]$ and an upper bound for $p(n,m,a)$ in the case $a\in [0,\frac\pi2]$, which tends to $p(n,m,\frac\pi2)$ when $a\to\frac\pi2$. In the case $a\in [0,\frac\pi2]$ 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 $CC(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 $CC(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 CC(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.},
Url = {http://www3.math.tu-berlin.de/algebra/work/AOP489-published.pdf},
Url2 = {http://dx.doi.org/10.1214/09-AOP489}
}