Export Reviews, Discussions, Author Feedback and Meta-Reviews

The paper presents a new algorithm for estimating multi-step transition probability (MSTP) for first order time homogeneous Markov chains with finite state space. In the introduction the authors give a clear overview of their results and discusses existing approaches for MSTP estimation. This is followed by a description of their Bidirectional-MSTP algorithm and a theoretical analysis of the algorithm. Finally the authors describe a list of applications of the algorithm and show that their algorithm empirically gives a speed up of at least two orders of magnitude for estimating heat kernels on four standard datasets. The paper is in general well writing.