Coverage processes on spheres and condition numbers for linear programming (Q964778): Difference between revisions

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.