nips nips2013 nips2013-66 nips2013-66-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Christina E. Lee, Asuman Ozdaglar, Devavrat Shah
Abstract: Computing the stationary distribution of a large finite or countably infinite state space Markov Chain (MC) has become central in many problems such as statistical inference and network analysis. Standard methods involve large matrix multiplications as in power iteration, or simulations of long random walks, as in Markov Chain Monte Carlo (MCMC). Power iteration is costly, as it involves computation at every state. For MCMC, it is difficult to determine whether the random walks are long enough to guarantee convergence. In this paper, we provide a novel algorithm that answers whether a chosen state in a MC has stationary probability larger than some ∆ ∈ (0, 1), and outputs an estimate of the stationary probability. Our algorithm is constant time, using information from a local neighborhood of the state on the graph induced by the MC, which has constant size relative to the state space. The multiplicative error of the estimate is upper bounded by a function of the mixing properties of the MC. Simulation results show MCs for which this method gives tight estimates. 1
[1] B. Cipra. The best of the 20th century: Editors name top 10 algorithms. SIAM News, 33(4):1, May 2000.
[2] T.M. Semkow, S. Pomm, S. Jerome, and D.J. Strom, editors. Applied Modeling and Computations in Nuclear Science. American Chemical Society, Washington, DC, 2006.
[3] L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical Report 1999-66, November 1999.
[4] S. Assmussen and P. Glynn. Stochastic Simulation: Algorithms and Analysis (Stochastic Modelling and Applied Probability). Springer, 2010.
[5] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21:1087, 1953.
[6] W.K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97–109, 1970.
[7] G.H. Golub and C.F. Van Loan. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 1996.
[8] D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs: Chapter 2 (General Markov chains). book in preparation. URL: http:// www.stat.berkeley.edu/ ∼aldous/ RWG/ Chap2.pdf , pages 7, 19–20, 1999.
[9] B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability, pages 502–525, 1982.
[10] P. Diaconis and L. Saloff-Coste. What do we know about the Metropolis algorithm? Journal of Computer and System Sciences, 57(1):20–36, 1998.
[11] P. Diaconis. The Markov chain Monte Carlo revolution. Bulletin of the American Mathematical Society, 46(2):179–205, 2009.
[12] D.A. Levin, Y. Peres, and E.L. Wilmer. Markov chains and mixing times. Amer Mathematical Society, 2009.
[13] G. Jeh and J. Widom. Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Web, pages 271–279, New York, NY, USA, 2003.
[14] D. Fogaras, B. Racz, K. Csalogany, and T. Sarlos. Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2(3):333–358, 2005.
[15] K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova. Monte Carlo methods in PageRank computation: When one iteration is sufficient. SIAM Journal on Numerical Analysis, 45(2):890–904, 2007.
[16] B. Bahmani, A. Chowdhury, and A. Goel. Fast incremental and personalized PageRank. Proc. VLDB Endow., 4(3):173–184, December 2010.
[17] C. Borgs, M. Brautbar, J. Chayes, and S.-H. Teng. Sublinear time algorithm for PageRank computations and related applications. CoRR, abs/1202.2771, 2012.
[18] SP. Meyn and RL. Tweedie. Markov chains and stochastic stability. Springer-Verlag, 1993.
[19] C.E. Lee, A. Ozdaglar, and D. Shah. Computing the stationary distribution locally. MIT LIDS Report 2914, Nov 2013. URL: http://www.mit.edu/∼celee/LocalStationaryDistribution.pdf.
[20] F.G. Foster. On the stochastic matrices associated with certain queuing processes. The Annals of Mathematical Statistics, 24(3):355–360, 1953. 9