×

Cover times, blanket times, and majorizing measures. (English) Zbl 1250.05098

Summary: We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand’s theory of majorizing measures. In particular, we show that the cover time of any graph \(G\) is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on \(G\), scaled by the number of edges in \(G\).
This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an \(O(1)\) factor for any graph, answering a question of D. J. Aldous and J. Fill [“Reversible Markov chains and radom walks on graphs” (to appear)]. We also positively resolve the blanket time conjectures of P. Winkler and D. Zuckerman [Random Struct. Algorithms 9, No. 4, 403–411 (1996; Zbl 0872.60054)], showing that for any graph, the blanket and cover times are within an \(O(1)\) factor. The best previous approximation factor for both these problems was \(O((\log \log n)^2)\) for \(n\)-vertex graphs, due to J. D. Kahn, J. H. Kim, L. Lovász, and V. H. Vu [“The cover time, the blanket time, and the Matthews bound”, 41st Annual Symposium on Foundations of Computer Science, Redondo Beach: IEEE Comput. Soc. Press (2000)].

MSC:

05C81 Random walks on graphs
05C85 Graph algorithms (graph-theoretic aspects)
60J55 Local time and additive functionals
60G15 Gaussian processes

Citations:

Zbl 0872.60054
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. J. Aldous, Probability Approximations via the Poisson Clumping Heuristic, New York: Springer-Verlag, 1989, vol. 77. · Zbl 0679.60013
[2] D. J. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs. · Zbl 0684.60055
[3] D. J. Aldous, ”Markov chains with almost exponential hitting times,” Stochastic Process. Appl., vol. 13, iss. 3, pp. 305-310, 1982. · Zbl 0491.60077 · doi:10.1016/0304-4149(82)90016-3
[4] D. J. Aldous, ”Random walk covering of some special trees,” J. Math. Anal. Appl., vol. 157, iss. 1, pp. 271-283, 1991. · Zbl 0733.60092 · doi:10.1016/0022-247X(91)90149-T
[5] D. J. Aldous, ”Threshold limits for cover times,” J. Theoret. Probab., vol. 4, iss. 1, pp. 197-211, 1991. · Zbl 0717.60082 · doi:10.1007/BF01047002
[6] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff, ”Random walks, universal traversal sequences, and the complexity of maze problems,” in 20th Annual Symposium on Foundations of Computer Science, New York: IEEE, 1979, pp. 218-223.
[7] M. T. Barlow, J. Ding, A. Nachmias, and Y. Peres, ”The evolution of the cover time,” Combin. Probab. Comput., vol. 20, iss. 3, pp. 331-345, 2011. · Zbl 1226.05230 · doi:10.1017/S0963548310000489
[8] J. D. Biggins, ”Chernoff’s theorem in the branching random walk,” J. Appl. Probability, vol. 14, iss. 3, pp. 630-636, 1977. · Zbl 0373.60090 · doi:10.2307/3213469
[9] A. Z. Broder and A. R. Karlin, ”Bounds on the cover time,” J. Theoret. Probab., vol. 2, iss. 1, pp. 101-120, 1989. · Zbl 0681.60063 · doi:10.1007/BF01048273
[10] G. A. Campbell, ”Cisoidal oscillations,” Trans. Amer. Inst. Elec. Engrs., vol. 30, 1911.
[11] A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari, ”The electrical resistance of a graph captures its commute and cover times,” Comput. Complexity, vol. 6, iss. 4, pp. 312-340, 1996/97. · Zbl 0905.60049 · doi:10.1007/BF01270385
[12] C. Cooper and A. Frieze, ”The cover time of the giant component of a random graph,” Random Structures Algorithms, vol. 32, iss. 4, pp. 401-439, 2008. · Zbl 1157.05045 · doi:10.1002/rsa.20201
[13] D. Coppersmith and S. Winograd, ”Matrix multiplication via arithmetic progressions,” J. Symbolic Comput., vol. 9, iss. 3, pp. 251-280, 1990. · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[14] A. Dembo, Y. Peres, J. Rosen, and O. Zeitouni, ”Cover times for Brownian motion and random walks in two dimensions,” Ann. of Math., vol. 160, iss. 2, pp. 433-464, 2004. · Zbl 1068.60018 · doi:10.4007/annals.2004.160.433
[15] P. G. Doyle and L. J. Snell, Random Walks and Electric Networks, Washington, DC: Mathematical Association of America, 1984, vol. 22. · Zbl 0583.60065
[16] R. M. Dudley, ”The sizes of compact subsets of Hilbert space and continuity of Gaussian processes,” J. Functional Analysis, vol. 1, pp. 290-330, 1967. · Zbl 0188.20502 · doi:10.1016/0022-1236(67)90017-1
[17] E. B. Dynkin, ”Gaussian and non-Gaussian random fields associated with Markov processes,” J. Funct. Anal., vol. 55, iss. 3, pp. 344-376, 1984. · Zbl 0533.60061 · doi:10.1016/0022-1236(84)90004-1
[18] E. B. Dynkin, ”Local times and quantum fields,” in Seminar on Stochastic Processes, 1983, Boston, MA: Birkhäuser, 1984, vol. 7, pp. 69-83. · Zbl 0554.60058
[19] N. Eisenbaum, ”Une version sans conditionnement du théorème d’isomorphisms de Dynkin,” in Séminaire de Probabilités, XXIX, New York: Springer-Verlag, 1995, vol. 1613, pp. 266-289. · Zbl 0849.60075 · doi:10.1007/BFb0094219
[20] N. Eisenbaum, H. Kaspi, M. B. Marcus, J. Rosen, and Z. Shi, ”A Ray-Knight theorem for symmetric Markov processes,” Ann. Probab., vol. 28, iss. 4, pp. 1781-1796, 2000. · Zbl 1044.60064 · doi:10.1214/aop/1019160507
[21] U. Feige, ”A tight lower bound on the cover time for random walks on graphs,” Random Structures Algorithms, vol. 6, iss. 4, pp. 433-438, 1995. · Zbl 0832.60016 · doi:10.1002/rsa.3240060406
[22] U. Feige, ”A tight upper bound on the cover time for random walks on graphs,” Random Structures Algorithms, vol. 6, iss. 1, pp. 51-54, 1995. · Zbl 0811.60060 · doi:10.1002/rsa.3240060106
[23] U. Feige and O. Zeitouni, Deterministic approximation for the cover time of trees.
[24] X. Fernique, ”Régularité de processus gaussiens,” Invent. Math., vol. 12, pp. 304-320, 1971. · Zbl 0217.21104 · doi:10.1007/BF01403310
[25] X. Fernique, ”Régularité des trajectoires des fonctions aléatoires gaussiennes,” in École d’Été de Probabilités de Saint-Flour, IV-1974, New York: Springer-Verlag, 1975, vol. 480, pp. 1-96. · Zbl 0331.60025 · doi:10.1007/BFb0080190
[26] R. M. Foster, ”The average impedance of an electrical network,” in Reissner Anniversary Volume, Contributions to Applied Mechanics, J. W. Edwards, Ann Arbor, Michigan, 1948, pp. 333-340. · Zbl 0040.41801
[27] O. Guédon and A. Zvavitch, ”Supremum of a process in terms of trees,” in Geometric Aspects of Functional Analysis, New York: Springer-Verlag, 2003, vol. 1807, pp. 136-147. · Zbl 1038.60028 · doi:10.1007/978-3-540-36428-3_12
[28] S. Janson, Gaussian Hilbert Spaces, Cambridge: Cambridge Univ. Press, 1997, vol. 129. · Zbl 0887.60009 · doi:10.1017/CBO9780511526169
[29] J. Jonasson and O. Schramm, ”On the cover time of planar graphs,” Electron. Comm. Probab., vol. 5, pp. 85-90, 2000. · Zbl 0949.60083 · doi:10.1214/ECP.v5-1022
[30] J. D. Kahn, J. H. Kim, L. Lovász, and V. H. Vu, ”The cover time, the blanket time, and the Matthews bound,” in 41st Annual Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Comput. Soc. Press, 2000, pp. 467-475. · doi:10.1109/SFCS.2000.892134
[31] J. D. Kahn, N. Linial, N. Nisan, and M. E. Saks, ”On the cover time of random walks on graphs,” J. Theoret. Probab., vol. 2, iss. 1, pp. 121-128, 1989. · Zbl 0681.60064 · doi:10.1007/BF01048274
[32] D. J. Klein and M. Randić, ”Resistance distance,” J. Math. Chem., vol. 12, iss. 1-4, pp. 81-95, 1993. · doi:10.1007/BF01164627
[33] F. B. Knight, ”Random walks and a sojourn density process of Brownian motion,” Trans. Amer. Math. Soc., vol. 109, pp. 56-86, 1963. · Zbl 0119.14604 · doi:10.2307/1993647
[34] M. Ledoux, The Concentration of Measure Phenomenon, Providence, RI: Amer. Math. Soc., 2001. · Zbl 0995.60002
[35] M. Ledoux and M. Talagrand, Probability in Banach Spaces, New York: Springer-Verlag, 1991, vol. 23. · Zbl 0748.60004
[36] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing Times, Providence, RI: Amer. Math. Soc., 2009. · Zbl 1160.60001
[37] L. Lovász, ”Random walks on graphs: a survey,” in Combinatorics, Paul Erd\Hos is Eighty, Vol. 2, Budapest: János Bolyai Math. Soc., 1996, vol. 2, pp. 353-397. · Zbl 0854.60071
[38] R. Lyons, ”Random walks, capacity and percolation on trees,” Ann. Probab., vol. 20, iss. 4, pp. 2043-2088, 1992. · Zbl 0766.60091 · doi:10.1214/aop/1176989540
[39] R. Lyons and Y. Peres, Probability on Trees and Networks, 2009. · Zbl 1376.05002
[40] M. B. Marcus and J. Rosen, ”Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes,” Ann. Probab., vol. 20, iss. 4, pp. 1603-1684, 1992. · Zbl 0762.60068 · doi:10.1214/aop/1176989524
[41] M. B. Marcus and J. Rosen, ”Gaussian processes and local times of symmetric Lévy processes,” in Lévy Processes, Boston, MA: Birkhäuser, 2001, pp. 67-88. · Zbl 0988.60026
[42] M. B. Marcus and J. Rosen, Markov Processes, Gaussian Processes, and Local Times, Cambridge: Cambridge Univ. Press, 2006, vol. 100. · Zbl 1129.60002 · doi:10.1017/CBO9780511617997
[43] P. Matthews, ”Covering problems for Markov chains,” Ann. Probab., vol. 16, iss. 3, pp. 1215-1228, 1988. · Zbl 0712.60076 · doi:10.1214/aop/1176991686
[44] D. Ray, ”Sojourn times of diffusion processes,” Illinois J. Math., vol. 7, pp. 615-630, 1963. · Zbl 0118.13403
[45] D. A. Spielman, ”Algorithms, graph theory, and linear equations in Laplacian matrices,” in Proceedings of the International Congress of Mathematicians. Volume IV, New Delhi, 2010, pp. 2698-2722. · Zbl 1241.65033
[46] D. A. Spielman and N. Srivastava, ”Graph sparsification by effective resistances,” in STOC’08, New York: ACM, 2008, pp. 563-568. · Zbl 1231.68184 · doi:10.1145/1374376.1374456
[47] D. A. Spielman and S. -H. Teng, Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems, 2006. · Zbl 1311.65031 · doi:10.1137/090771430
[48] M. Talagrand, ”Regularity of gaussian processes,” Acta Math., vol. 159, iss. 1-2, pp. 99-149, 1987. · Zbl 0712.60044 · doi:10.1007/BF02392556
[49] M. Talagrand, ”Embedding subspaces of \(L_p\) in \(l^N_p\),” in Geometric Aspects of Functional Analysis, Basel: Birkhäuser, 1995, vol. 77, pp. 311-325. · Zbl 0828.46011
[50] M. Talagrand, ”Majorizing measures: the generic chaining,” Ann. Probab., vol. 24, iss. 3, pp. 1049-1103, 1996. · Zbl 0867.60017 · doi:10.1214/aop/1065725175
[51] M. Talagrand, ”Majorizing measures without measures,” Ann. Probab., vol. 29, iss. 1, pp. 411-417, 2001. · Zbl 1019.60033 · doi:10.1214/aop/1008956336
[52] M. Talagrand, The Generic Chaining. Upper and Lower Bounds of Stochastic Processes, New York: Springer-Verlag, 2005. · Zbl 1075.60001 · doi:10.1007/3-540-27499-5
[53] P. Tetali, ”Random walks and the effective resistance of networks,” J. Theoret. Probab., vol. 4, iss. 1, pp. 101-109, 1991. · Zbl 0722.60070 · doi:10.1007/BF01046996
[54] <a href=’http://dx.doi.org/10.1002/(SICI)1098-2418(199612)9:43.0.CO;2-0\(^{\prime}\) title=’Go to document’> P. Winkler and D. Zuckerman, ”Multiple cover time,” Random Structures Algorithms, vol. 9, iss. 4, pp. 403-411, 1996. · Zbl 0872.60054 · doi:10.1002/(SICI)1098-2418(199612)9:4<403::AID-RSA4>3.0.CO;2-0
[55] D. Zuckerman, ”A technique for lower bounding the cover time,” SIAM J. Discrete Math., vol. 5, iss. 1, pp. 81-87, 1992. · Zbl 0743.60068 · doi:10.1137/0405007
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.