# Fast Bidirectional Probability Estimation in Markov Models

arXiv: https://arxiv.org/abs/1507.05998 · HTML: https://mlsanity.com/paper/1507.05998/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2015.

## Built on by (most cited first, 4 of 4)

- [GRAND+: Scalable Graph Random Neural Networks](https://mlsanity.com/paper/2203.06389/) (2022)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model](https://mlsanity.com/paper/2509.13112/) (2025)

## Abstract (arXiv)

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 ℓ 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/√p) running time.