Definition:

A Markov chain is said to be ergodic if there exists a positive integer $T_0$ such that for all pairs of states $i,j$ in the Markov chain, if it is started at time 0 in state $i$ then for all $t>T_0$, the probability of being in state $j$ at time $t$ is greater than $0$.

For a Markov chain to be ergodic, two technical conditions are required of its states and the non-zero transition probabilities; these conditions are known as irreducibility and aperiodicity. Informally, the first ensures that there is a sequence of transitions of non-zero probability from any state to any other, while the latter ensures that the states are not partitioned into sets such that all state transitions occur cyclically from one set to another.

Theorem. For any ergodic Markov chain, there is a unique steady-state probability vector $\vec{\pi}$ that is the principal left eigenvector of $P$, such that if $\eta(i,t)$ is the number of visits to state $i$ in $t$ steps, then

$$\lim_{t\rightarrow\infty} \frac{\eta(i,t)}{t} = \pi(i),$$ (254)

where $\pi(i)>0$ is the steady-state probability for state $i$. End theorem.

It follows from Theorem 21.2.1 that the random walk with teleporting results in a unique distribution of steady-state probabilities over the states of the induced Markov chain. This steady-state probability for a state is the PageRank of the corresponding web page.