Lovász, László; Simonovits, M. Random walks in a convex body and an improved volume algorithm. (English) Zbl 0788.60087 Random Struct. Algorithms 4, No. 4, 359-412 (1993). Summary: We give a randomized algorithm using \(O(n^ 7\log^ 2 n)\) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is \(O(n^ 6\log^ 4 n)\) for centrally symmetric bodies and for polytopes with a polynomial number of facets, and \(O(n^ 5\log^ 4 n)\) for centrally symmetric polytopes with a polynomial number of facets. We also give an \(O(n^ 6\log n)\) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of A. Sinclair and M. Jerrum [Proc. 20th ACM STOC, 235-244 (1988)] and the authors [Proc. 31st Ann. Symp. Found. Comput. Sci., IEEE Computer Soc., 346-355 (1990)] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. Cited in 4 ReviewsCited in 106 Documents MSC: 60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) 60D05 Geometric probability and stochastic geometry Keywords:randomized algorithm; polytopes; convex body; Markov chains; mixing rate PDFBibTeX XMLCite \textit{L. Lovász} and \textit{M. Simonovits}, Random Struct. Algorithms 4, No. 4, 359--412 (1993; Zbl 0788.60087) Full Text: DOI References: [1] Alon, Combinatorica 6 pp 83– (1986) [2] and , Eigenvalues, expanders, and superconcentrators, Proc. 25th Ann. Symp. on Found. of Comput. Sci., 1984, pp. 320–322. [3] Alon, J. Combinat. Theory B 38 pp 73– (1985) [4] and , Sampling and integration of near log-concave functions, Proc. 23th ACM STOC, 1990, pp. 156–163. [5] and , Computing the volume is difficult, Proc. 18th Ann. ACM Symp. Theory of Comput. 1986, pp. 442–447. [6] Berbie, Math. Program. 37 pp 184– (1987) [7] Random Graphs, Academic Press, London, 1985. [8] and , Theorie der konvexen Körper, Springer, Berlin, 1934. · Zbl 0008.07708 [9] and , Counting linear extenstions is # P-complete, Bellcore preprint, 1990. [10] How hard is it to marry at random? (On the approximation of the permanent), Proc. 18th Ann. ACM Symp. on Theory of Comput., 1986, pp. 50–58. [11] Chernoff, Ann. Math. Stat. 23 pp 493– (1952) [12] Danzer, Arch. Math. 8 pp 214– (1957) [13] Dinghas, Math. Z. 68 pp 111– (1957) [14] and , Combinatorial Laplacians and isoperimetric inequality, in From Local Times to Global Geometry Control and Physics, Ed., Pitman Res. Notes in Math. Series 150, pp. 68–74, 1986. [15] Dyer, SIAM J. Comput. 17 pp 967– (1988) [16] and , Computing the volume of convex bodies: a case where randomness provably helps, preprint, 1991. · Zbl 0754.68052 [17] and , Computing the volume of convex bodies: a case where randomness provably helps, in Probabilistic Combatorics and Its Applications, Béla Bollobás, Ed., Proceedings of Symposia in Applied Mathematics, Vol. 44, 1992, 123–170. [18] Elekes, Discrete Comput. Geom. 1 pp 289– (1986) [19] , and , preprint, 1992. [20] Introduction to the Theory of Probability and Its Applications, I–II, Wiley, New York, 1968. [21] and , Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. [22] , and , Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988. · Zbl 0634.05001 [23] Measure Theory, Springer-Verlag, Berlin, 1974. [24] Jerrum, Theor. Comput. Sci. 43 pp 169– (1986) [25] Karzanov, Order 8 pp 7– (1991) [26] Khachiyan, Izv. Akad. Nauk SSSR, Eng. Cybern. 3 pp 216– (1988) [27] Khachiyan, Usp. Mat. Nauk. 44 pp 199– (1989) [28] Complexity of polytope volume computation, in New Trends in Discrete and Computational Geometry, Ed., Springer, Berlin, pp. 91–101, 1993. [29] Khachiyan, Math. Program. [30] Polytope volume computation, Preprint NISTIR 89-4123, US Dept. of Commerce, Natl. Inst. of Stand. Tech., Gaithersburg, MD. · Zbl 0734.52009 [31] Lenstra, Oper. Res. 8 pp 538– (1983) [32] Geometric algorithms and algorithmic geometry, Proc. of Int. Congress of Math. Kyoto, 1990, Springer-Verlag, Berlin, 1991, pp. 139–154. · Zbl 0742.52013 [33] How to compute the volume? Jber. d. Dt. Math.-Verein, Jubiläumstagung 1990, B. G. Teubner, Stuttgart, pp. 138–151, 1992. [34] and , Mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, Proc. 31st Ann. Symp. on Found. of Comput. Sci., IEEE Computer Soc., 1990, pp. 346–355. [35] and , On the randomized complexity of volume and diameter, Proc. 33rd IEEE FOCS, 1992, pp. 482–491. [36] and , Extensions of the hit-and-run algorithm for random point generation (1990) (extended abstract). [37] Metropolis, J. Chem. Phys. 21 pp 1087– (1953) [38] and , Self-concordant Functions and Polynomial-Time Methods in Convex Programming (Russian), Centr. Econ. and Math. Inst., Acad. Nauk SSR, Chap. 7, 1989. [39] Payne, Arch. Ration Mech. Anal. 5 pp 286– (1960) [40] Prékopa, Acta Sci. Math. Szeged. 32 pp 301– (1971) [41] Prékopa, Acta Sci. Math. Szeged. 34 pp 335– (1973) [42] Functional Analysis, London, Blackie, 1956. [43] Smith, Oper. Res. 32 pp 1296– (1984) [44] and , Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved, Proc. 20th ACM STOC, 1988, pp. 235–244. [45] Yudin, Ekon. Mat. Metody 12 pp 357– [46] Matekon 13 pp 25– (1976) 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.