WNCG Seminar Series: Fast Probability Estimation in Sparse Markov Models
A fundamental problem in Markov Chains is estimating the probability of transitioning to a given terminal state in k steps from some initial distribution. This has received added attention in recent years due to the success of PageRank and related Markov-Chain based centrality measures for networks. Standard approaches to this problem use linear-algebraic methods (power iteration) or Monte Carlo. Both however need order 1/p running time for estimating probabilities on the order of p; moreover, neither can be adapted for a single terminal state, but rather, give estimates for the entire distribution. This is particularly problematic for estimating Personalized PageRank, an ego-centric generalization of PageRank, which has long been recognized as an effective measure for ranking search results, but is rarely used in practice as existing algorithms do not scale well to large networks.