## Coverage processes on spheres and condition numbers for linear programming.(English)Zbl 1205.60027

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.

### MSC:

 60D05 Geometric probability and stochastic geometry 52A22 Random convex sets and integral geometry (aspects of convex geometry) 90C05 Linear programming
Full Text:

### References:

  Agmon, S. (1954). The relaxation method for linear inequalities. Canad. J. Math. 6 382-392. · Zbl 0055.35001  Bürgisser, P. and Amelunxen, D. (2008). Uniform smoothed analysis of a condition number for linear programming. Accepted for Math. Program. A. Available at · Zbl 1242.90098  Cheung, D. and Cucker, F. (2001). A new condition number for linear programming. Math. Program. 91 163-174. · Zbl 1072.90564  Cheung, D. and Cucker, F. (2002). Probabilistic analysis of condition numbers for linear programming. J. Optim. Theory Appl. 114 55-67. · Zbl 1041.90028  Cheung, D., Cucker, F. and Hauser, R. (2005). Tail decay and moment estimates of a condition number for random linear conic systems. SIAM J. Optim. 15 1237-1261. · Zbl 1097.90057  Cucker, F. and Peña, J. (2002). A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine. SIAM J. Optim. 12 522-554. · Zbl 0996.90052  Cucker, F. and Wschebor, M. (2002). On the expected condition number of linear programming problems. Numer. Math. 94 419-478. · Zbl 1030.65039  Dunagan, J., Spielman, D. A. and Teng, S.-H. (2009). Smoothed analysis of condition numbers and complexity implications for linear programming. Math. Programming . To appear. Available at http://arxiv.org/abs/cs/0302011v2. · Zbl 1218.90109  Dvoretzky, A. (1956). On covering a circle by randomly placed arcs. Proc. Natl. Acad. Sci. USA 42 199-203. JSTOR: · Zbl 0074.12301  Gilbert, E. N. (1965). The probability of covering a sphere with N circular caps. Biometrika 52 323-330. JSTOR: · Zbl 0137.36202  Goffin, J.-L. (1980). The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5 388-414. JSTOR: · Zbl 0442.90051  Hall, P. (1985). On the coverage of k -dimensional space by k -dimensional spheres. Ann. Probab. 13 991-1002. · Zbl 0582.60015  Hall, P. (1988). Introduction to the Theory of Coverage Processes . Wiley, New York. · Zbl 0659.60024  Hauser, R. and Müller, T. (2009). Conditioning of random conic systems under a general family of input distributions. Found. Comput. Math. 9 335-358. · Zbl 1193.90199  Janson, S. (1986). Random coverings in several dimensions. Acta Math. 156 83-118. · Zbl 0597.60014  Kahane, J.-P. (1959). Sur le recouvrement d’un cercle par des arcs disposés au hasard. C. R. Math. Acad. Sci. Paris 248 184-186. · Zbl 0090.35801  Miles, R. E. (1968). Random caps on a sphere. Ann. Math. Statist. 39 1371. · Zbl 0165.58001  Miles, R. E. (1969). The asymptotic values of certain coverage probabilities. Biometrika 56 661-680. JSTOR: · Zbl 0184.41501  Miles, R. E. (1971). Isotropic random simplices. Adv. in Appl. Probab. 3 353-382. JSTOR: · Zbl 0237.60006  Moran, P. A. P. and Fazekas de St. Groth, S. (1962). Random circles on a sphere. Biometrika 49 389-396. JSTOR: · Zbl 0108.31602  Motzkin, T. S. and Schoenberg, I. J. (1954). The relaxation method for linear inequalities. Canad. J. Math. 6 393-404. · Zbl 0055.35002  Reitzner, M. (2002). Random points on the boundary of smooth convex bodies. Trans. Amer. Math. Soc. 354 2243-2278. JSTOR: · Zbl 0993.60012  Rosenblatt, F. (1962). Principles of Neurodynamics. Perceptrons and the Theory of Brain Mechanisms . Spartan Books, Washington, DC. · Zbl 0143.43504  Santaló, L. A. (1976). Integral Geometry and Geometric Probability . Addison-Wesley, Reading, MA. · Zbl 0342.53049  Siegel, A. F. (1979). Asymptotic coverage distributions on the circle. Ann. Probab. 7 651-661. · Zbl 0412.60014  Siegel, A. F. and Holst, L. (1982). Covering the circle with random arcs of random sizes. J. Appl. Probab. 19 373-381. JSTOR: · Zbl 0489.60017  Solomon, H. (1978). Geometric Probability . SIAM, Philadelphia, PA. · Zbl 0382.60016  Stevens, W. L. (1939). Solution to a geometrical problem in probability. Ann. Eugenics 9 315-320. · Zbl 0023.05603  Wendel, J. G. (1962). A problem in geometric probability. Math. Scand. 11 109-111. · Zbl 0108.31603  Whitworth, W. A. (1965). DCC Exercises in Choice and Chance . Dover, New York. · JFM 28.0212.14  Zähle, M. (1990). A kinematic formula and moment measures of random sets. Math. Nachr. 149 325-340. · Zbl 0725.60014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.