Let us suppose that $P$ is a stochastic matrix (non-negative matrix with $P \mathbf{1} = \mathbf{1}$).

Let $\Delta$ such that $P + \Delta$ is a stochastic matrix (which means $P + \Delta$ is non-negative and $(P+\Delta) \mathbf{1} = \mathbf{1})$.

Let $n \geq 1$. I am seeking a bound on $$\|(P+\Delta)^n - P^n\|_F$$ if possible depending on $\|\Delta\|_F$.

Discussion

When $P$ and $P+\Delta$ are irreductible aperiodic stochastic matrices, I was thinking of studying separately:

• $\|(P+\Delta)^n - \underset{n \to \infty}{\lim} (P+\Delta)^n\|_F$
• $\|P^n - \underset{n \to \infty}{\lim}P^n\|_F$
• $\|\underset{n \to \infty}{\lim} (P+\Delta)^n - \underset{n \to \infty}{\lim}P^n\|_F$

Do you know if there is a straightforward way to bound these quantities?

In general, can we use the convergence in average of the ergodic theorem to find a similar decomposition?