A sharp estimate for cover times on binary trees. (English) Zbl 1255.05179
The paper deals with a cover time of a random walk on a graph. The cover time of a random walk on a graph, which is the time it takes the walk to visit every vertex in the graph is a basic parameter. The authors compute the second order correction for cover time of the binary tre of depth \(n\) (continuous time) random walk and show that the second order correction differs from corresponding one for the maximum of the Gaussian free field on the tree.
Reviewer: Nicko G. Gamkrelidze (Moskva)
References:
| [1] | Handbook of Mathematical Functions, with Formulas, Graphs, and Mathematical Tables, (Abramowitz, Milton; Stegun, Irene A., National Bureau of Standards Applied Mathematics Series, vol. 55 (1965), Superintendent of Documents, US Government Printing Office: Superintendent of Documents, US Government Printing Office Washington, DC), Third printing, with corrections · Zbl 0171.38503 |
| [2] | Addario-Berry, L.; Reed, B., Minima in branching random walks, Ann. Probab., 37, 3, 1044-1079 (2009) · Zbl 1196.60142 |
| [3] | E. Aidekon, Convergence in law of the minimum of a branching random walk. Preprint, available athttp://arxiv.org/abs/1101.1810; E. Aidekon, Convergence in law of the minimum of a branching random walk. Preprint, available athttp://arxiv.org/abs/1101.1810 · Zbl 1285.60086 |
| [4] | Aldous, D. J., Random walk covering of some special trees, J. Math. Anal. Appl., 157, 1, 271-283 (1991) · Zbl 0733.60092 |
| [5] | D. Aldous, J. Fill, Reversible Markov chains and random walks on graphs, available athttp://www.stat.berkeley.edu/aldous/RWG/book.html; D. Aldous, J. Fill, Reversible Markov chains and random walks on graphs, available athttp://www.stat.berkeley.edu/aldous/RWG/book.html |
| [6] | Bolthausen, E.; Deuschel, J.-D.; Giacomin, G., Entropic repulsion and the maximum of the two-dimensional harmonic crystal, Ann. Probab., 29, 4, 1670-1692 (2001) · Zbl 1034.82018 |
| [7] | Bramson, M. D., Maximal displacement of branching Brownian motion, Commun. Pure Appl. Math., 31, 5, 531-581 (1978) · Zbl 0361.60052 |
| [8] | Bramson, M.; Zeitouni, O., Tightness for a family of recursion equations, Ann. Probab., 37, 2, 615-653 (2009) · Zbl 1169.60020 |
| [9] | M. Bramson, O. Zeitouni, Tightness of the recentered maximum of the two-dimensional discrete gaussian free field. Preprint, available at http://arxiv.org/abs/1009.3443; M. Bramson, O. Zeitouni, Tightness of the recentered maximum of the two-dimensional discrete gaussian free field. Preprint, available at http://arxiv.org/abs/1009.3443 · Zbl 1237.60041 |
| [10] | Dembo, A.; Peres, Y.; Rosen, J.; Zeitouni, O., Cover times for Brownian motion and random walks in two dimensions, Ann. of Math. (2), 160, 2, 433-464 (2004) · Zbl 1068.60018 |
| [11] | J. Ding, Asymptotics of cover times via gaussian free fields: bounded-degree graphs and general trees. Preprint, available at http://arxiv.org/abs/1103.4402; J. Ding, Asymptotics of cover times via gaussian free fields: bounded-degree graphs and general trees. Preprint, available at http://arxiv.org/abs/1103.4402 · Zbl 1316.60064 |
| [12] | J. Ding, J. Lee, Y. Peres, Cover times, blanket times, and majorizing measures. Ann. of Math. (in press).; J. Ding, J. Lee, Y. Peres, Cover times, blanket times, and majorizing measures. Ann. of Math. (in press). · Zbl 1288.05252 |
| [13] | Kahn, J.; Kim, J. H.; Lovász, L.; Vu, V. H., The cover time, the blanket time, and the Matthews bound, (41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, 2000 (2000), IEEE Comput. Soc. Press: IEEE Comput. Soc. Press Los Alamitos, CA), 467-475 |
| [14] | Levin, D. A.; Peres, Y.; Wilmer, E. L., Markov Chains and Mixing Times (2009), American Mathematical Society: American Mathematical Society Providence, RI, With a chapter by James G. Propp and David B. Wilson · Zbl 1160.60001 |
| [15] | R. Lyons, with Y. Peres, Probability on Trees and Networks, Cambridge University Press, 2012. Current version available at http://mypage.iu.edu/ rdlyons/; R. Lyons, with Y. Peres, Probability on Trees and Networks, Cambridge University Press, 2012. Current version available at http://mypage.iu.edu/ rdlyons/ |
| [16] | Shorack, G. R.; Wellner, J. A., (Empirical Processes with Applications to Statistics. Empirical Processes with Applications to Statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics (1986), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York) · Zbl 1170.62365 |
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.
