I was reading though Link Analysis, Eigenvectors and Stability by Ng Et al. I am stuck at the last part of the proof of the stability of the PageRank algorithm.
I do not understand how the asymptotic upper bound $d_{\infty} \leq (\sum_{i \in \mathcal{P}} p_{i})/\epsilon$ is found.
If someone could explain what "Using the fact that $d_{0} = 0$ and by iterating this bound on $d_{t+1}$ in terms of $d_{t}$, we obtain an asymptotic upper bound: $d_{\infty} \leq (\sum_{i \in \mathcal{P}} p_{i})/\epsilon$" means that would be helpful.
The paper can be found here (the pertinent section is pasted below): http://www.robotics.stanford.edu/~ang/papers/ijcai01-linkanalysis.pdf
Thank you for your help
The paper establishes the inequality $$ d_{t+1}\le (1-\epsilon)(d_t + p)\tag1 $$ where for laziness I write $p:=\sum_{i\in\cal P}p_i$. Plug $t=0$ into (1), using $d_0=0$, to get the inequality $$ d_1\le p(1-\epsilon)\tag2 $$ Plug $t=1$ and (2) into (1) to get an inequality for $d_2$. Continuing in this manner you should be able to prove (use induction!) $$ d_t\le p\sum_{k=1}^t (1-\epsilon)^k\tag3 $$ Now let $t\to\infty$. The RHS of (3) becomes a geometric series that converges to $$\frac{\text {first term}}{1-\text {common ratio}}=\frac{p(1-\epsilon)}{1-(1-\epsilon)}=\frac {p(1-\epsilon)}\epsilon<\frac p\epsilon.$$