{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T00:44:57Z","timestamp":1791074697858,"version":"4.1.0"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We consider a finite random walk on a weighted graph G; we show that the fraction of time spent in a set of vertices A converges to the stationary probability $\\pi (A)$ with error probability exponentially small in the length of the random walk and the square of the size of the deviation from $\\pi (A)$. The exponential bound is in terms of the expansion of G and improves previous results of [D. Aldous, Probab. Engrg. Inform. Sci., 1 (1987), pp. 33--46], [L. Lov\u00e1sz and M. Simonovits, {\\it Random Structures Algorithms}, 4 (1993), pp. 359--412], [M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di, Deterministic simulation of logspace, in Proc. 19th ACM Symp. on Theory of Computing, 1987].<\/jats:p>\n                  <jats:p>We show that taking the sample average from one trajectory gives a more efficient estimate of $\\pi (A)$ than the standard method of generating independent sample points from several trajectories. Using this more efficient sampling method, we improve the algorithms of Jerrum and Sinclair for approximating the number of perfect matchings in a dense graph and for approximating the partition function of a ferromagnetic Ising system, and we give an efficient algorithm to estimate the entropy of a random walk on an unweighted graph.<\/jats:p>","DOI":"10.1137\/s0097539794268765","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1203-1220","source":"Crossref","is-referenced-by-count":103,"title":["A Chernoff Bound for Random Walks on Expander Graphs"],"prefix":"10.1137","volume":"27","author":[{"given":"David","family":"Gillman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"MMM"},{"key":"R2","unstructured":"L. Ahlfors,\n                      Complex Analysis\n                      , 2nd ed., McGraw\u2010Hill, New York, 1966."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di,\n                      Deterministic simulation of logspace\n                      , in Proc. 19th ACM Symp. on Theory of Computing, 1987.","DOI":"10.1145\/28395.28410"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964800000267"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01848136"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/18.53762"},{"key":"R9","unstructured":"R. Ash,\n                      Information Theory\n                      , Interscience, New York, 1965."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Z. Broder,\n                      How hard is it to marry at random? (on the approximation of the permanent)\n                      , in Proc. 18th ACM Symp. on Theory of Computing, 1986, pp. 50\u201358.","DOI":"10.1145\/12130.12136"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"R12","volume":"736","author":"Cram\u00e9r H.","year":"1938","journal-title":"Actualit\u00e9s Scientifiques et Industrielles"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"A. Cohen and A. Wigderson,\n                      Dispersers, deterministic amplification, and weak random sources\n                      , in Proc.30th IEEE Symp. on Foundations of Computer Science, 1989.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004826"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/jmaa.1997.5850"},{"key":"R16","unstructured":"J. L. Doob,\n                      Stochastic Processes\n                      , Wiley, New York, 1953."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Martin Dyer, Alan Frieze, Computing the volume of convex bodies: a case where randomness provably helps, Proc. Sympos. Appl. Math., Vol. 44, Amer. Math. Soc., Providence, RI, 1991, 123\u201316993a:52004","DOI":"10.1090\/psapm\/044\/1141926"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Dyer, A. Frieze, and R. Kannan,\n                      A random polynomial time algorithm for approximating the volume of convex bodies\n                      , in Proc. 21st Annual ACM Symp. on Theory of Computing, 1989, pp. 375\u2013381.","DOI":"10.1145\/73007.73043"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005981"},{"key":"R20","unstructured":"D. Gillman,\n                      Hidden Markov Chains: Convergence Rates and the Complexity of Inference\n                      , Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1993."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"David Gillman, A Chernoff bound for random walks on expander graphs, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 680\u20136911328459","DOI":"10.1109\/SFCS.1993.366819"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, David Zuckerman, Security preserving amplification of hardness, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 318\u201332692k:94017","DOI":"10.1109\/FSCS.1990.89550"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF00532560"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and D. Zuckerman,\n                      How to Recycle Random Bits\n                      , in Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"R28","unstructured":"N. Kahale,\n                      Large Deviation Bounds for Markov Chains\n                      , DIMACS Technical Report, DIMACS, Rutgers University, New Brunswick, NJ, 1994, pp. 94\u201339."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. Karp and M. Luby,\n                      Monte Carlo algorithms for enumeration and reliablity problems\n                      , in Proc. 15th ACM Symp. on Theory of Computing, 1983.","DOI":"10.1109\/SFCS.1983.35"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5700-4"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"C. Kenyon, D. Randall, and A. Sinclair,\n                      Matchings in lattice graphs\n                      , in Proc. 25th ACM Symp. on Theory of Computing, 1993, pp. 738\u2013746.","DOI":"10.1145\/167088.167278"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177705671"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040402"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057036"},{"key":"R35","first-page":"67","volume":"6","author":"Nagaev S.","year":"1961","journal-title":"Teor. Verojatnost. i Primenen."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.25.353"},{"key":"R37","unstructured":"E. Seneta,\n                      Nonnegative Matrices\n                      , Wiley, New York, 1973."},{"key":"R38","unstructured":"A. Sinclair,\n                      Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow\n                      , Technical Report ECS\u2010LFCS\u201091\u2010178, Department of Computer Science, University of Edinburgh, Scotland, October 1991."},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"R40","volume-title":"Matrix perturbation theory","author":"Stewart G.","year":"1990"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"},{"key":"R42","unstructured":"J. H. Wilkinson,\n                      The Algebraic Eigenvalue Problem\n                      , Clarendon Press, Oxford, UK, 1965."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794268765","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:14Z","timestamp":1787335934000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794268765"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794268765"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794268765","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}