Bounding error of approximating $(I-A)^t$ with $\exp(-At)$ for large $t$

Question

Suppose $A$ is a diagonal matrix with diagonal entries $\in (0,1]$

I'm interested in bounding the following quantity in terms of $t$: $$f_A(t)=\operatorname{Tr}\exp(-At)-\operatorname{Tr}(I-A)^t$$

Suppose $\operatorname{Tr}(A^2)>1$ and $f_A(t)$ is a decreasing function of $t$, what is a good bound in this regime?

Example, plotting $f_A(t)$ for diagonal $A$ with diagonal values $1,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{100}$

Notebook

Motivation: see previous question solved with a bound which is tight for small values of $\operatorname{Tr}(A^2)$

Answer 1

As in the previous question, we may suppose without losing generality that $A$ is diagonal. Let $\lambda_i$ be the eigenvalues of $A$.

We can show that $\lambda_{min} = \min_i \lambda_i$ controls the asymptotic behavior of the error $f_A(t)$ as $t\to \infty$.

For simplicity, let us suppose $\lambda_i > \lambda_{min}$ except for $i=i_0$ such that $\lambda_{i_0} = \lambda_{min}$. Then for any $i \neq i_0$, we have $e^{-\lambda_i}<e^{-\lambda_{min}}(<1)$. Likewise $(0\leq)1-\lambda_i < 1-\lambda_{min}(<1)$. Furthermore, $e^x\geq 1+x$ implies $1-\lambda_{min}<e^{-\lambda_{min}}$. These observation implies that terms that appears in $f_A(t)$ are negligible relative to $e^{-\lambda_{min}t}$. That means the asymptotic behavior of $f_A(t)$ is controlled by $e^{-\lambda_{min}t}$.

Since the sum is a finite sum, we conclude that $f_A(t) = e^{-\lambda_{min}t} + o(e^{-\lambda_{min}t})$.

Just for completion, if there are $k$ $\lambda_i$'s that attain the minimum, then we have $f_A(t) = ke^{-\lambda_{min}t} + o(e^{-\lambda_{min}t})$ instead. So, the asymptotic nature does not change very much.

Answer 2

I will assume that the matrix $A\in \mathbb{M}_{N\times N}$, with a set of eigenvalues $\lambda_n=\frac{c}{n^p}~,~ n=1,..., N$ and will provide asymptotics in the large time limit, taken after the size of the matrix has been taken to infinity. I will estimate

$$f(t,N)=\text{Tr} (e^{-At}-(I-A)^t)~~,~~ N\gg t\gg1$$

This reduces to finding the long time behavior of the sum

$$f(t,\infty)=\sum_{n=1}^\infty \left(e^{-ct/n^p}-\left(1-\frac{c}{n^p}\right)^t\right)$$

With some thought one can conclude that qualitatively, the bulk of the asymptotic behavior of this sum is dependent on the accumulation point of the eigenvalues.

This sum can be approximated by an integral using the Euler-Maclaurin formula. In the $t \to \infty$ limit, it can be shown that all the remainder terms in that formula decay as $e^{-ct}$, so we expect that majority of the contributions to the sum can be efficiently summarized by an asymptotic expansion of the integral

$$I(t)=\int_{1}^{\infty}\left(e^{-ct/u^p}-\left(1-\frac{c}{u^p}\right)^t\right)du$$

Performing the substitution $x=ctu^{-p}$ we obtain

$$I(t)=\frac{(ct)^{1/p}}{p}\int_{0}^{ct}\frac{e^{-x}-(1-x/t)^t}{x^{1+1/p}}dx$$

We see that the integral converges only for $p\geq 1$ so we restrict to this case. Now, using the Taylor expansion for $-\ln(1-x)=x+x^2/2+...$ we can compute arbitrary terms of the expansion of $(1-x/t)^t$ compared to it's asymptotic limit by expanding the remaining exponential

$$(1-x/t)^t=e^{-x}e^{-x^2/2t-x^3/3t^2+...}=\left(\frac{x^2}{2 t}+ \frac{x^3}{3 t^2} - \frac{(-2 + t) x^4}{8 t^3}+\mathcal{O(x^5)}\right)e^{-x}$$

We can generate as many terms as we would like (no closed formula however). Substituting this expansion into the integral and integrating term by term and taking the upper limit of integration to be infinity we obtain an asymptotic series

$$\frac{I(t)}{c^{1/p}}\sim \frac{ \Gamma(2 - 1/p)}{2pt^{1 - 1/p}}+\frac{(-15 p + 35 p^2 - 10 p^3) \Gamma(2 - 1/p)}{120 p^4 t^{2 - 1/p}} + \mathcal{O}(t^{-3+1/p})~~, ~~p\geq 1$$

We see clearly that in your special case, $c=n=1$, the integral (and hence the sum) asymptotes to $1/2$ for large enough matrices.

There is no indication for a universal behavior of the difference of traces in question for infinite matrix sizes, since the integral asymptotics depend explicitly on the behavior of the sequence of eigenvalues. Finally, note that the late time behavior is very different than the one for finite matrices. However, for large matrices with an accumulation point for the eigenvalues, we expect that numerical simulations will give a relatively large region of times where the behavior is described well by the infinite time asymptote, before it actually starts decaying as an exponential $e^{-\lambda_{min}t}$.

EDIT: It is clear that since the matrix is finite and the series is slowly converging that the agreement between the $N=\infty$ and the finite matrix curves leaves something to be desired in terms of accuracy. Here is what happens as one increases $N$:

The black dashed line represents the asymptote to order $t^{-13}$. One can see that $f$ approximates the asymptote well for large $N$ and intermediate times that obey $t/N\lessapprox 1$. However, one can match the finite matrix curves much better for intermediate times by simply performing asymptotic analysis on

$$I_{N}(t)=\int_{1}^{N}\left(e^{-ct/u^p}-\left(1-\frac{c}{u^p}\right)^t\right)du$$

instead, which yields a leading $-t/2N$ correction that needs to be added to the $N=\infty$ asymptote. It is clear that the expansion does not hold for long times anymore, but the agreement in the intermediate time regime is excellent as seen in the graph below: