3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ If $P1=1$ and $P1+Q1=1$, and both $P$ and $Q$ are nonnegative, doesn't that imply that $Q$ must be zero? Something is missing here it seems.... $\endgroup$
    – Suvrit
    Commented Jun 17, 2018 at 11:07
  • $\begingroup$ What kinds of dependence of the bound on $n$ and the dimension would be considered acceptable? $\endgroup$
    – Iosif Pinelis
    Commented Jun 17, 2018 at 12:28
  • $\begingroup$ @Suvrit : I think it is not assumed here that $Q$ is nonnegative. I found the notation $P+Q$ instead of $Q$ (say) slightly misleading, though. $\endgroup$
    – Iosif Pinelis
    Commented Jun 17, 2018 at 12:30
  • $\begingroup$ Indeed, $\Delta$ (I changed the notation) is not assumed to be non-negative. $\endgroup$
    – mfrt
    Commented Jun 17, 2018 at 12:44
  • 1
    $\begingroup$ This could be reworded a bit further, because it says: ...**two** stochastic matrices (nonegative coefficients...)... -- so to me at first look it seemed as if both matrices are non-negative...even though I see, what is really meant is that $P$ is stochastic and so is $P+\Delta$. $\endgroup$
    – Suvrit
    Commented Jun 17, 2018 at 13:07

1 Answer 1

Reset to default
2
$\begingroup$

One possible starting point is via the telescopic sum $$ \|(P+\Delta)^n-P^n\| = \|\sum_{i=0}^{n-1} (P+\Delta)^i ((P+\Delta) - P) P^{n-1-i}\| \leq \|(P+\Delta)^i\| \|\Delta\| \|P^{n-1-i}\|. $$ Since all norms are equivalent, $\|P^{n-1-i}\|$ and $\|(P+\Delta)^i\|$ are uniformly bounded, so you get a bound that is essentially $O(n)\|\Delta\|$.

This should be optimal for small values of $n$, but intuitively I'd expect that for large values of $n$ your original approach (using common convergence to the Perron vector) should give better results.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What are general convergence rates to the Perron vector if we suppose $P$ and $P+\Delta$ are both irreductible and aperiodic ? $\endgroup$
    – mfrt
    Commented Jun 17, 2018 at 14:21
  • 1
    $\begingroup$ @mfrt You can't say anything in general. They depend on the second largest eigenvalue $\lambda_2$ of $P$ (resp. $P+\Delta$), which requires some work to compute, and they can be arbitrarily slow if $\lambda_2 \approx 1$. $\endgroup$
    – Federico Poloni
    Commented Jun 17, 2018 at 15:12
  • $\begingroup$ If we have access to this $\lambda_2$ (and its algebraic multiplicity), what is the convergence rate to the Perron vector ? Is this an exact bound or a $O(\ldots)$ ? $\endgroup$
    – mfrt
    Commented Jun 18, 2018 at 9:03
  • $\begingroup$ The error is $O(\lambda_2^k)$. Look up "power method" / "power iteration". $\endgroup$
    – Federico Poloni
    Commented Jun 18, 2018 at 9:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .