Coverage processes on spheres and condition numbers for linear programming (Q964778)

Let \(p(n,m,\alpha)\) be the probability that \(n\) spherical caps of angular radius \(\alpha\) do not cover the whole sphere \(S^m\). The authors give an exact formula for this probability in the case \(\alpha\in[\pi/2,\pi]\) and an upper bound in the case \(\alpha\in[0,\pi/2]\), which tends to the exact value as \(\alpha\to\pi/2\). The obtained upper bound yields upper bounds for the expected number of caps that are needed to cover the whole sphere. Then the authors study the condition number \(\mathcal{C}(A)\) of the linear programming feasibility problem concerning the existence of a nonzero \(x\in\mathbb{R}^{m+1}\) such that \(Ax\leq 0\) componentwise, where a \(n\times(m+1)\) matrix \(A\) is randomly chosen according to the standard normal distribution. The relation to spherical caps is explained by the fact that \(\mathcal{C}(A)\) equals \(1/|\cos\rho(A)|\), where \(\rho(A)\) is the radius of a largest excluding cap for \(A=(a_1,\dots,a_n)\), i.e. the complement to the smallest cap that contains the points \(a_1,\dots,a_n\). The authors exactly determine the distribution of \(\mathcal{C}(A)\) conditioned on \(A\) being feasible and provide an upper bound on the distribution function in the infeasible case. From these results they show that \[ \mathbf{E} \ln\mathcal{C}(A)\leq 2 \ln(m+1)+3.31\,,\quad n>m\,, \] which is the sharpest known bound for this expectation.