Fast Bidirectional Probability Estimation in Markov Models
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 statesthe 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.
The paper introduces a new algorithm for estimating multi-step transition probabilities (MSTP) for (discrete) Markov chains, and also presents some analysis of the algorithm.The main theoretical results are (1) a bound on the relative error of the (unbiased) estimate -- this is based on concentration bounds, and (2) a bound on the runtime for sparse problems.For (2), the interesting result is that the runtime of O(sqrt(1/delta)), where delta is the threshold above which we'd like to estimate MSTPs. The dependence with respect to sparsity is on the average number of neighbors (rather than an upper bound on the number of neighbors). This work appears to build directly on the recent FAST-PPR algorithm (KDD 2014) -- which also achieves runtime O(sqrt(1/delta)) but was designed specifically for PageRank.            Section 3 devotes a page to a bulleted list of potential applications of MSTP estimation.It feels a bit slapped on, as if to flesh out the paper, but some readers may appreciate this section.It would be useful here to explicitly distinguish between applications where single MSTP values are of interest and those that call for many or all such values.This information would complement the experiments Section 4.            I wasn't a fan of the experiments section. The experiments focus exclusively on runtime, but this is not very interesting unless complemented by results for accuracy. It is great that you compare 3 algorithms on 4 real datasets, but you are missing critical experimental results here. I'm also on the fence about whether the comparisons are fair.As the authors note, the other algorithms "were designed for community detection, and return scores from the source to all targets, rather than just one target."So, it is indeed interesting that the proposed algorithm here beats the others on a single target (or more generally, a small number of targets).This suggests that to round out a fair comparison, you might also report how long the bidirectional algorithm would require on all targets.Alternatively or additionally, you might evaluate a parallel implementation of your algorithm (i.e., the dead-simple embarrassingly parallel thing).E.g., how many parallel cores would you need to beat the other algorithms on all targets?     - For reasons of interpretability, it would be useful to also report some basic stats for the various datasets in a table -- number of nodes, average degree.     - The bar graphs (Figure 2) on a log scale in units of ms are a bit difficult to interpret. I would consider a table in units of seconds.      Minor comments:     - "order-wise" might be more common     - Some hyphens unnecessary or incorrect:Monte-Carlo, transition-probabilities, bidirectional-MSTP     - No line break in the middle of "PageRank" (page 2)     - Some of the hyphens in Algorithms seem unnecessary:estimate-vectors, residual-vectors, sample-path(s)     - Define c as an input to Algorithm 2 (?)     - Avoid using red + green in figures, and it would be nice if figures worked in grayscale     - "we defer it to our full version" -- you mean supplement?     - Use ~ to connect a citation to the previous word      Section 3 looks hastily assembled:     - Could really use some white space (e.g., between bullets)     - For random walks on a (weighted) graph, such functions are called...     - Missing some periods under "Graph Diffusions"     - Footnote 2 (subscript following an integer) is very awkward            Section 4:     - state-of-the-art