Fast Bidirectional Probability Estimation in Markov Models

Abstract

We develop a new bidirectional algorithm for estimating Markov chain multi-step transition probabilities: given a Markov chain, we want to estimate the probability of hitting a given target state in $\ell$ steps after starting from a given source distribution. Given the target state $t$, we use a (reverse) local power iteration to construct an `expanded target distribution', which has the same mean as the quantity we want to estimate, but a smaller variance -- this can then be sampled efficiently by a Monte Carlo algorithm. Our method extends to any Markov chain on a discrete (finite or countable) state-space, and can be extended to compute functions of multi-step transition probabilities such as PageRank, graph diffusions, hitting/return times, etc. Our main result is that in `sparse' Markov Chains -- wherein the number of transitions between states is comparable to the number of states -- the running time of our algorithm for a uniform-random target node is order-wise smaller than Monte Carlo and power iteration based algorithms; in particular, our method can estimate a probability $p$ using only $O(1/\sqrt{p})$ running time.

NIPS 2015

References in corpus (1)

• Learning Fast-Mixing Models for Structured Prediction

Cited by in corpus (6)

• Personalized PageRank Estimation and Search: A Bidirectional Approach
• Scalable Graph Neural Networks via Bidirectional Propagation
• Efficient Estimation of Heat Kernel PageRank for Local Clustering
• Efficient Algorithms for Personalized PageRank
• Efficient Estimation of Pairwise Effective Resistance
• Bidirectional PageRank Estimation: From Average-Case to Worst-Case