No label defined (Q4234745)

Let \(\{M(t)\); \(t\geq 0\}\) be a Markov chain with finite state space and \(G\) be its generator matrix. Given an initial distribution \(\pi(0)=(\pi_i(0))\), put \(\pi_i(t)=P(M(t)=i)\). Then the stationary distribution \(\pi=(\pi_i)\) is given by \(\pi_i=\lim_{t\to \infty}\pi_i(t)\). For any \(0<k<\sqrt{2}\), define the \(k\)-distance relaxation time by \(\tau_k=\min\{t:\| \pi(t)-\pi\| \leq k\}\), where \(\|\cdot\|\) is the Euclidean norm. Put \(x(t)=\pi(t)-\pi\). Then it satisfies \(\dot{x}(t)=Ax(t)\) for a matrix \(A\) determined by \(G\). Given a positive definite matrix \(P\), put \(Q=-(A^TP+PA)\). Using a Lyapunov function approach, \(\tau_k\) can be evaluated as \(-T_L \log(\lambda_{P,\max} k^2/ \lambda_{P,\min}\| x(0)\| ^2) \leq \tau_k \leq -T_u \log(\lambda_{P,\min}k^2/\lambda_{P,\max}\| x(0)\| ^2)\), where \(\lambda_{P,\max}\) and \(\lambda_{P,\min}\) are the maximum and the minimum eigenvalues of \(P\) and \(T_L=\lambda_{P,\min}/\lambda_{Q,\max}\), \(T_u=\lambda_{P,\max}/\lambda_{Q,\min}\). Some computational results of the relaxation times are also given. For the entire collection see [Zbl 0903.00111].