Fast computation of stationary joint probability distribution of sparse Markov chains

Weiyang DING, Kwok Po NG*, Yimin Wei

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

In this paper, we study a fast algorithm for finding stationary joint probability distributions of sparse Markov chains or multilinear PageRank vectors which arise from data mining applications. In these applications, the main computational problem is to calculate and store solutions of many unknowns in joint probability distributions of sparse Markov chains. Our idea is to approximate large-scale solutions of such sparse Markov chains by two components: the sparsity component and the rank-one component. Here the non-zero locations in the sparsity component refer to important associations in the joint probability distribution and the rank-one component refers to a background value of the solution. We propose to determine solutions by formulating and solving sparse and rank-one optimization problems via closed form solutions. The convergence of the truncated power method is established. Numerical examples of multilinear PageRank vector calculation and second-order web-linkage analysis are presented to show the efficiency of the proposed method. It is shown that both computation and storage are significantly reduced by comparing with the traditional power method.

Original languageEnglish
Pages (from-to)68-85
Number of pages18
JournalApplied Numerical Mathematics
Volume125
DOIs
Publication statusPublished - Mar 2018

Scopus Subject Areas

  • Numerical Analysis
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Iterative methods
  • Joint distribution
  • Markov chains
  • Optimization
  • Sparsity

Fingerprint

Dive into the research topics of 'Fast computation of stationary joint probability distribution of sparse Markov chains'. Together they form a unique fingerprint.

Cite this