Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem (Q544781)

This paper gives a proof of a result, previously announced without proof by the authors [Dokl. Math. 79, No. 3, 424--427 (2009; Zbl 1176.65042)], concerning the rate of convergence of their randomized algorithm for computing a Perron eigenvector of a large sparse stochastic \(N\times N\) matrix \(A\). It bounds the expected value of \(\|Ax_n-x_n\|^2\) above by \(8[(n+1)\log (N)]^{1/2}/n\), where \(x_n\) is the \(n\)th approximation of the eigenvector. The slow growth with \(N\) is important in the PageRank application, where often \(N>10^9\).