Coverage Processes on Spheres and Condition Numbers for Linear Programming

Dr Martin Lotz ( Oxford University and City University of Hong Kong )

This talk is concerned with the probabilistic behaviour of a condition number C(A) for the problem of deciding whether a system of n homogeneous linear inequalities in m unknowns has a non-zero solution. In the case where the input system is feasible, the exact probability distribution of the condition number for random inputs is determined, and a sharp bound for the general case. In particular, for the expected value of the logarithm log C(A), an upper bound of order O(log m) (m the number of variables) is presented which does not depend on the number of inequalities.

The probability distribution of the condition number C(A) is closely related to the probability of covering the m-sphere with n spherical caps of a given radius. As a corollary, we obtain bounds on the probability of covering the sphere with random caps.