Perturbed Markov Chains and Information Networks

See discussions, stats, and author profiles for this publication at: https://www.researchgate.
net/publication/330775774
Perturbed Markov Chains and Information Networks
Preprint · January 2019
CITATIONS READS
0 63
7 authors, including:
Benard Abola Pitos Seleka Biganda
14 PUBLICATIONS 14 CITATIONS
University of Dar es Salaam
13 PUBLICATIONS 16 CITATIONS
SEE PROFILE
SEE PROFILE
Sergei Silvestrov Christopher Engström

Malardalen University Mälardalen University
307 PUBLICATIONS 4,005 CITATIONS 27 PUBLICATIONS 59 CITATIONS
SEE PROFILE SEE PROFILE
Some of the authors of this publication are also working on these related projects:
non-commutative analysis View project
Sida Bilateral Mathematics Project 316 Uganda View project
All content following this page was uploaded by Pitos Seleka Biganda on 18 August 2020.
The user has requested enhancement of the downloaded file.

Perturbed Markov Chains and
Information Networks
Benard Abola, Pitos Seleka Biganda, Sergei Silvestrov, Dmitrii Silvestrov,

arXiv:1901.11483v3 [math.PR] 2 May 2019
Christopher Engström, John Magero Mango, and Godwin Kakuba1
Abstract. The paper is devoted to studies of perturbed Markov chains

commonly used for description of information networks. In such models,
the matrix of transition probabilities for the corresponding Markov chain
is usually regularised by adding a special damping matrix multiplied by a
small damping (perturbation) parameter ε. We give effective upper bounds
for the rate of approximation for stationary distributions of unperturbed
Markov chains by stationary distributions of perturbed Markov chains with
regularised matrices of transition probabilities, asymptotic expansions for ap-
proximating stationary distributions with respect to damping parameter, as
well as explicit upper bounds for the rate of convergence in ergodic theorems
for n-step transition probabilities in triangular array mode, where perturba-
tion parameter ε → 0 and n → ∞, simultaneously. The results of numerical
experiments are also presented.
1. Introduction
Perturbed Markov chains is one of the popular and important objects of

studies in the theory of Markov processes and their applications to stochastic
1
Benard Abola, Mälardalen University, Västerås, Sweden,
E-mail: benard.abola@mdh.se
Pitos Seleka Biganda, Mälardalen University, Västerås, Sweden and University of Dar es
Salaam, Dar es Salaam, Tanzania
E-mail: pitos.biganda@mdh.se
Sergei Silvestrov, Mälardalen University, Västerås, Sweden
E-mail: sergei.silvestrov@mdh.se
Dmitrii Silvestrov, Stockholm University, Stockholm, Sweden
E-mail: silvestrov@math.su.se
Christopher Engström, Mälardalen University, Västerås, Sweden
E-mail: christopher.engstrom@mdh.se,
John Magero Mango, Makerere University, Kampala, Uganda
E-mail: mango@cns.mak.ac.ug
Godwin Kakuba, Makerere University, Kampala, Uganda
E-mail: godwin.a.kakuba@gmail.com
1
networks, queuing and reliability models, bio-stochastic systems, and many
other stochastic models.
We refer here to some recent books and papers devoted to perturbation
problems for Markov type processes, [4, 5, 10, 12, 20, 24, 29, 30, 31, 34, 35,
36, 37, 46, 47, 49, 50, 51, 52, 53, 54, 55, 58, 59]. In particular, we would like
to mention works [4, 24, 49, 50], where the extended bibliographies of works
in the area and the corresponding methodological and historical remarks can
be found.
We are especially interested in models of Markov chains commonly used
for description of information networks. In such models an information net-
work is represented by the Markov chain associated with the corresponding
node links graph. Stationary distributions and other related characteris-
tics of information Markov chains usually serve as basic tools for ranking of
nodes in information networks. The ranking problem may be complicated by
singularity of the corresponding information Markov chain, where its phase
space is split into several weakly or completely non communicating groups
of states. In such models, the matrix of transition probabilities P0 of in-
formation Markov chain is usually regularised and approximated by matrix
Pε = (1 − ε)P0 + εD, where D is a so-called damping stochastic matrix
with identical rows and all positive elements, while ε ∈ [0, 1] is a damping
(perturbation) parameter.
The power method is often used to approximate the corresponding sta-
tionary distribution π̄ε by rows of matrix Pnε . The damping parameter
0 < ε ≤ 1 should be chosen neither too small nor too large. In the first
case, where ε takes too small values, the damping effect will not work against
absorbing and pseudo-absorbing effects, since the second eigenvalue for such
matrices (determining the rate of convergence in the above mentioned ergodic
approximation) take values approaching 1. In the second case, the ranking
information (accumulated by matrix P0 via the corresponding stationary dis-
tribution) may be partly lost, due to the deviation of matrix Pε from matrix
P0 . This actualises the problem of construction asymptotic expansions for
perturbed stationary distribution π̄ε with respect to damping parameter ε,
as well as studies of asymptotic behaviour of matrices Pnε in triangular array
mode, where ε → 0 and n → ∞, simultaneously.
In this paper, we perform the detailed perturbation analysis of Markov
chains with damping component, using the procedure of artificial regenera-
tion for the approximating Markov chains and the coupling method in ergodic
theorems for perturbed regenerative processes. We get effective explicit se-
2
ries representations for the corresponding stationary distributions π̄ε , upper
bounds for the deviation π̄ε − π̄0 , and asymptotic expansions for π̄ε with re-
spect to the perturbation parameter ε, as well as get ergodic theorems and
effective explicit upper bounds for the rate of convergence in the correspond-
ing ergodic relations for Pnε , as ε → 0 and n → ∞. The results of numerical
experiments illustrating the above results are also presented.
Real world system consists of interacting units or components. These
components constitute what is termed as information networks. With recent
advancement in technology, filtering information has become a challenge in
such systems. Moreover, their significance is visible as they find their ap-
plications in Internet search engines, biological, financial, transport, queuing
networks and many others, [3], [4], [7], [11], [14] – [18], [21], [32], and [57].
PageRank is the link-based criteria that captures the importance of Web
pages and provide rankings of the pages in the search engine Google [4], [7],
[11], [14] – [18], and [32]. The transition matrix (also called Google matrix
G) of a Markov chain in PageRank problem is defined in [3], [26], and [32],
as G = cP + (1 − c)E, where P is an n × n row-stochastic matrix (also called
hyperlink matrix), E (the damping matrix) is the n × n rank-one stochastic
matrix and c ∈ (0, 1) is the damping parameter.
The fundamental concept of PageRank is to use the stationary distribu-
tion of the Markov chain on the network to rank Web pages. However, other
algorithms similar to PageRank exist in literature, for instance, EigenTrust
algorithm [28] and DeptRank algorithm [6]. In addition, variants of PageR-
ank in relation to some specific networks has been studied, e.g. in [8] and [9];
and also updating PageRank due to changes in some network is in literature,
for instance, in [1] and [2].
The parameter c is very important in the PageRank definition, because
it regulates the level of the uniform noise introduced to the system [4, 32]. If
c = 1 there are several absorbing states for the random walk defined by P.
However, if 0 < c < 1, the Markov chain induced by matrix G is ergodic [4].
The authors of [32] argued that the parameter c controls the asymptotic rate
of convergence of power method algorithm. Similar arguments were given in
[3], where it is pointed out that the choice of c is a delicate matter. It may
result into convergence and stability problems, if not carefully chosen.
The damping factor c may be denoted and interpreted differently depend-
ing on a model being studied. For instance, a model of Markov chain with
restart is considered in [5], where parameter p is the probability to restart
the move and 1 − p is the probability to follow the link according to the
3
corresponding transition probability of the above Markov chain. Hence, one
can argue that the parameter p has the same interpretation as the damping
factor in Google’s PageRank problem.
Our representation of perturbed Markov chains is traditional for per-
turbed stochastic processes. In fact, PageRank is the stationary distribu-
tion of the singularly perturbed Markov chain with perturbation parameter
ε = 1 − c. Hence, we wish to point out here that, representation of informa-
tion network model by a Markov chain with matrix of transition probabilities
Pε = (1 − ε)P0 + εD should not create any confusion to the reader. We per-
form asymptotic analysis of such Markov chains, in particular, under the
assumption that ε → 0.
The paper includes 9 sections. In Section 2, we describe the algorithm
for stochastic modelling of Markov chains with damping component and the
procedure of embedding such Markov chains in the model of discrete time
regenerative processes with special damping regenerative times. In Section
3, we present individual ergodic theorems for Markov chains with damping
component and give explicit formulas for the corresponding stationary dis-
tributions. In Section 4, we describe continuity properties of transition prob-
abilities and stationary distributions with respect to dumping parameter. In
Section 5, explicit upper bounds for rates of convergence in approximations
of the stationary distributions for Markov chain with damping component
are given. In Section 6, we present asymptotic expansions for stationary dis-
tribution of Markov chains with damping component with respect to pertur-
bation (damping) parameter. In Section 7, we describe coupling algorithms
for Markov chains with damping component and get explicit estimates for
the rate of convergence in the above mentioned ergodic theorems. In Section
8, we present ergodic theorems for Markov chains with damping component
in a triangular array mode, where time tends to infinity and perturbation
parameter tends to zero, simultaneously. In Section 9, results of numerical
experiments, which show how results presented in Sections 2–8 can be in-
terpreted and useful in studies of information networks, are presented, and
some concluding remarks and comments are given.
2. Markov chains with damping component
In this section, we introduce the model of Markov chains with damping

component, which are used for description of information networks. We
also describe the procedure of embedding such Markov chains in the model
4
of discrete time regenerative processes with special damping regenerative
times and present the corresponding renewal type equations for transition
probabilities.
2.1 Stochastic modelling of Markov chains with damping com-
ponent. Let (a) X = {1, 2, . . . , m} be a finite space, (b) p̄ = hp1 , . . . , pm i,
d¯ = hd1 , . . . , dm i, and q̄ = hq0 , q1 i be three discrete probability distribu-
tions, (c) P0 = kp0,ij k be a m × m stochastic matrix and D = kdij k be a
m×m damping stochastic matrix with elements dij = dj > 0, i, j = 1, . . . , m,
and Pε = kpε,ij k = (1 − ε)P0 + εD is a stochastic matrix with elements
pε,ij = (1 − ε)p0,ij + εdj , i, j = 1, . . . , m, where ε ∈ [0, 1].
Let us first describe an algorithm for stochastic modelling of a discrete
time, homogeneous Markov chain Xε,n , n = 0, 1, . . ., with the phase space X,
the initial distribution p̄, and the matrix of transition probabilities Pε .
Let (a) U be a random variable taking values in space X and such that
P{U = j} = pj , j ∈ X; (b) Ui,n , i ∈ X, n = 1, 2, . . . be a family of independent
random variables taking values in space X and such that P{Ui,n = j} =
p0,ij , i, j ∈ X, n = 1, 2, . . .; (c) Vn , n = 0, 1, . . . be a sequence of independent
random variables taking values in space X and such that P{Vn = j} = dj , j ∈
X, n = 1, 2, . . . (d) W is a binary random variable taking values 0 and 1 with
probabilities, respectively q0 and q1 ; (e) Wε,n , n = 1, 2, . . . be, for every ε ∈
[0, 1], a sequence of independent binary random variables taking values 0 and
1 with probabilities, respectively, 1−ε and ε, for n = 1, 2, . . .; (d) the random
variables U, W , the family of random variables Ui,n , i ∈ X, n = 1, 2, . . ., and
the random sequences Vε,n , n = 1, 2, . . . and Wε,n , n = 1, , 2, . . . are mutually
independent, for every ε ∈ [0, 1].
Let us now define, for every ε ∈ [0, 1], the random sequence Xε,n , n =
0, 1, . . ., by the following recurrent relation,
Xε,n = UXε,n−1 ,n I(Wε,n = 0) + Vn I(Wε,n = 1), n = 1, 2, . . . , Xε,0 = U. (1)
It is readily seen that the random sequence Xε,n , n = 0, 1, . . . is, for every
ε ∈ [0, 1], a homogeneous Markov chain with phase space X, the initial
distribution p̄ and the matrix of transition probabilities Pε .
2.2 Regenerative properties of Markov chains with damping
component. Let us consider the extended random sequence,
Yε,n = (Xε,n , Wε,n ), n = 1, 2, . . . , Xε,0 = U, Wε,0 = W. (2)
This random sequence also is, for every ε ∈ [0, 1], a homogeneous Markov
chain, with phase space Y = X × {0, 1}, the initial distribution pq = hpi qr ,
5
(i, r) ∈ Yi and transition probabilities,
pε,ir,jk = P{Xε,1 = j, Wε,1 = k/Xε,0 = i, Wε,0 = r}

(1 − ε)p0,ij for i, j ∈ X, r = 0, 1, k = 0,
= (3)
εdj for i, j ∈ X, r = 0, 1, k = 1.
It is worth to note that the transition probabilities pε,ir,jk = pε,i,jk , (i, r),
(j, k) ∈ Y do not depend on r ∈ X and on i ∈ X if k = 1.
Let us, assume that the dumping (perturbation) parameter ε ∈ (0, 1].
Let us define times of sequential hitting state 1 by the second component
Wε,n ,
Tε,n = min(n > Tε,n−1 , Wε,n = 1), n = 1, 2, . . . , Tε,0 = 0. (4)
The random sequence Yε,n , n = 0, 1, . . . is also a discrete time regenerative
process with “damping” regeneration times Tε,n , n = 0, 1, . . ..
It follows from independence of transition probabilities pε,ir,jk of the Mar-
kov chain Yε,n , given by relation (3), on (i, r) ∈ Y if k = 1.
This is a standard regenerative process, if the initial distribution pq =
dq 1 = hdi q1,r , (i, r) ∈ Yi, where q̄1 = hq1,0 = 0, q1,1 = 1i.
Otherwise, Yε,n is a regenerative process with the transition period [0, Tε,1 ).
It is also useful to note that the inter-regeneration times Sε,n = Tε,n −
Tε,n−1 , n = 1, 2, . . . are i.i.d. geometrically distributed random variables, with
parameter ε, i.e.,

0 for n = 0,
P{Sε,1 = n} = n−1 (5)
ε(1 − ε) for n = 1, 2, . . . .
2.3 Renewal type equations for transition probabilities of the

Markov chains with damping component. Let us denote by Pm the
class of all initial distributions p̄ = hpi , i ∈ Xi.
Let us introduce n-step transition probabilities for the Markov chain Xε,n ,
for i, j ∈ X, n = 0, 1, . . .,
pε,ij (n) = P{Xε,n = j/Xε,0 = i}, (6)
and n-sep probabilities, for p̄ ∈ Pm , j ∈ X, n = 0, 1, . . .,

X
pε,p̄,j (n) = Pp̄ {Xε,n = j} = pi pε,ij (n). (7)
i∈X
6
Here and henceforth, symbols Pp̄ and Ep̄ are used for probabilities and
expectations related to a Markov chain with an initial distribution p̄. In
the case, where the initial distribution is concentrated in a state i the above
symbols take the forms Pi and Ei .
Obviously, pε,ij (0) = I(i = j), i, j ∈ X and pε,ij (1) = pε,ij , i, j ∈ X. Also,
pε,p̄,j (0) = pj , j ∈ X.
Let us also denote by PQm the class of all initial distributions pq =
hpi qr , (i, r) ∈ Yi.
Analogously, let us introduce n-step transition probabilities for the Markov
chain Yε,n , for (i, r), (j, k) ∈ Y, n = 0, 1, . . .,
pε,ir,jk (n) = P{Yε,n = (j, k)/Yε,0 = (i, r)}, (8)
and n-sep probabilities, for pq ∈ PQm , (j, k) ∈ Y, n = 0, 1, . . .,

X
pε,pq,jk (n) = Ppq {Yε,n = (j, k)} = pi qr pε,ir,jk (n) (9)
(i,r)∈Y
Obviously, pε,ir,jk (0) = I((i, r) = (j, k)), (i, r), (j, k) ∈ Y and pε,ir,jk (1) =
pε,ir,jk , (i, r), (j, k) ∈ Y. Also, pε,pq,(j,k) (0) = pj qk , (j, k) ∈ Y.
Independence of the transition probabilities pε,ir,jk = pε,i,jk , (i, r), (j, k) ∈
Y on r ∈ X and on i ∈ X if k = 1, implies that n-step transition probabilities
pε,ir,jk (n) = pε,i,jk (n), (i, r), (j, k) ∈ Y, n = 0, 1, . . . also are independent on
r ∈ X and on i ∈ X if k = 1.
This also implies that n-step probabilities pε,pq,jk (n) = pε,p,jk (n), pq ∈
PQm , (j, k) ∈ Y, n = 1, 2, . . . are independent on the initial distribution q̄.
Let us assume that the initial distribution pq = dq 1 . As was mentioned
above, Yε,n is, in this case, the standard regenerative process with regenera-
tion times Tε,n , n = 0, 1, . . ..
This fact and relations (3) and (5) imply that probabilities pε,pq1 ,jk (n), n =
0, 1, . . . are, for every j ∈ X, k = 0, 1, the unique bounded solution for the
following discrete time renewal equation,
n
X
pε,dq1 ,jk (n) = qε,dq1 ,ik (n) + pε,dq1 ,jk (n − l)ε(1 − ε)l−1 , n ≥ 0, (10)
l=1
where, for j ∈ X, k = 0, 1, n ≥ 0,
qε,dq1 ,jk (n) = Pdq1 {Yε,n = (j, k), Tε,1 > n}
7
n
¯ (n)(1 − ε) I(n > 0) if k = 0,

p0,d,j
= (11)
dj I(n = 0) if k = 1.
Let us now consider the general case, with some initial distribution pq =
hpi qr , (i, r) ∈ Yi ∈ PQm . As was mentioned above, Yε,n , is, in this case,
the regenerative process with regeneration times Tε,n , n = 0, 1, . . . and the
transition period [0, Tε,1 ).
In this case, probabilities pε,pq,jk (n) and pε,dq1 ,jk (n) are, for j ∈ X, k = 0, 1,
connected by the following renewal type relation,
n
X
pε,pq,jk (n) = qε,pq,jk (n) + pε,dq1 ,jk (n − l)ε(1 − ε)l−1 , n ≥ 0, (12)
l=1
where, for j ∈ X, k = 0, 1, n ≥ 0,
qε,pq,jk (n) = Ppq {Yε,n = (j, k), Tε,1 > n}
p0,p̄,j (n)(1 − ε)n I(n > 0) if k = 0,

= (13)
pj I(n = 0) if k = 1.
The summation of renewal equations (10) over k = 0, 1 yields the discrete
time renewal equation for probabilities pε,d,j
¯ (n), n = 0, 1, . . ., which are, for
every j ∈ X, the unique bounded solution for this equation,
n
X
n l−1
pε,d,j ¯ (n)(1 − ε) +
¯ (n) = p0,d,j ¯ (n − l)ε(1 − ε)
pε,d,j , n ≥ 0. (14)
l=1
Also, the summation of renewal type equations (12) over k = 0, 1 yields

that, in the case of general initial distribution p = hpi , i ∈ Xi, the probabil-
¯ (n) are, for every j ∈ X, connected by the following
ities pε,p̄,j (n) and pε,d,j
renewal type relation,
n
X
n l−1
pε,p̄,j (n) = p0,p̄,j (n)(1 − ε) + ¯ (n − l)ε(1 − ε)
pε,d,j , n ≥ 0. (15)
l=1
3. Stationary distributions of Markov chains with

damping component
In this section we present ergodic relations for transition probabilities of

Markov chains with damping component.
8
3.1 Stationary distributions of the Markov chains Xε,n and Yε,n .
Let us describe ergodic properties of Markov chains Xε,n and Yε,n , for the
case, where ε ∈ (0, 1].
Lemma 1. Let ε ∈ (0, 1]. Then the following ergodic relation takes place
for any initial distribution pq ∈ PQm and (j, k) ∈ Y,
∞
X
pε,pq,jk (n) → πε,jk = ε qε,dq1 ,jk (l) as n → ∞. (16)
l=0
Proof. The geometrical distribution of the inter-regeneration time Sε,1

is aperiodic and has expectation ε−1 .
This makes it possible to apply the discrete time renewal theorem (see, for
example, [19]) to the renewal equation (10) that yields the following ergodic
relation, for (j, k) ∈ Y,
pε,dq1 ,jk (n) → πε,jk as n → ∞. (17)
Obviously qε,pq,jk (n) → 0 as n → ∞, for (j, k) ∈ Y.

Let us also define pε,dq1 ,jk (n − l) = 0, for l > n. Relation (17) implies that
pε,dq1 ,jk (n − l) → πε,jk as n → ∞, for l ≥ 0 and (j, k) ∈ Y.
Using relation (12), the latter two asymptotic relations and the Lebesgue
theorem, we get, for pq ∈ PQm , (j, k) ∈ Y,
lim pε,pq,jk (n) = lim qε,pq,jk (n)

n→∞ n→∞
∞
X
+ lim pε,dq1 ,jk (n − l)ε(1 − ε)l−1 = πε,jk . (18)
n→∞
l=1
The proof is complete.

The following lemma is the direct corollary of Lemma 1.
Lemma 2. Let ε ∈ (0, 1]. Then the following ergodic relation takes place
for any initial distribution p̄ ∈ Pm and j ∈ X,
∞
X
l
pε,p̄,j (n) → πε,j = ε ¯ (l)(1 − ε) as n → ∞.
p0,d,j (19)
l=0
It is useful to note that, for every ε ∈ (0, 1], the phase space X is one
communicative, aperiodic class of states for the Markov chain Xε,n , and its
9
stationary distribution π̄ε = hπε,j , j ∈ Xi is the unique positive solution for
the system of linear equations,
X X
πε,i pε,ij = πε,j , j ∈ X, πε,j = 1. (20)
i∈X j∈X
Also, the stationary probabilities πε,j can be represented in the form πε,j =
e−1 ∈ X, via the expected return times eε,j , with the use of regeneration
ε,j , , j
property of the Markov chain Xε,n at moments of return in state j.
The series representation (16) for the stationary distribution of Markov
chain Xε,n is based on the use of alternative damping regeneration times.
This representation is, by our opinion, a more effective tool for performing
asymptotic perturbation analysis for Markov chains with damping compo-
nent.
3.2 The stationary distribution of the Markov chain X0,n . Let us
describe ergodic properties of Markov chains X0,n . Its ergodic properties are
determined by communicative properties its phase space X and the matrix of
transition probabilities P0 . The simplest case is where the following condition
holds:
A1 : The phase space X is one aperiodic class of communicative states for

the Markov chain X0,n .
In this case, the following ergodic relation holds, for any p̄ ∈ Pm , j ∈ X,
p0,p̄,j (n) → π0,j as ε → 0, (21)
The stationary distribution π̄0 = hπ0,j , j ∈ Xi is the unique positive

solution of the system for linear equations,
X X
π0,i p0,ij = π0,j , j ∈ X, π0,j = 1. (22)
i∈X j∈X
A more complex is the case, where the following condition holds, for some
h > 1:
B1 : The phase space X = ∪hj=1 X(j) , where X (j) , j = 1, . . . , h are non-

intersecting subsets of X, (b) X (j) , j = 1, . . . , h are non-empty, closed
aperiodic classes of communicative states for the Markov chain X0,n .
10
If the initial distribution of the Markov chain X0,n is concentrated at
(j)
the set X(j) , for some j = 1, . . . , h, then X0,n = X0,n , n = 0, 1, . . . can be
considered as a Markov chain with the reduced phase space X(j) and the
matrix of transition probabilities P0,j = kp0,rk kk,r∈X(j) .
According to condition B1 , there exists, for any r, k ∈ X(j) , j = 1, . . . , h,
(j)
p0,rk (n) → π0,k as n → ∞, (23)
(j) (j)
where π̄0 = hπ0,k , k ∈ X(j) i is, for j = 1, . . . , h, the stationary distribution
(j)
of the Markov chain X0,n .
(j)
The stationary distribution π̄0 is, for every j = 1, . . . , h, the unique
positive solution for the system of linear equations,
(j)
X (j) X (j)
π0,k = π0,r p0,rk , k ∈ X(j) , π0,k = 1. (24)
r∈X(j) k∈X(j)
Let us denote, for p̄ ∈ Pm , j = 1, . . . , h,

(j)
X
fp̄ = pi . (25)
i∈X(j)
Lemma 3. Let condition B1 holds. Then, the following ergodic relation

takes place, for p̄ ∈ Pm and k ∈ X(j) , j = 1, . . . , h,
(j) (j)
p0,p̄,k (n) → π0,p̄,k = fp̄ π0,k as n → ∞. (26)
Remark 1. Ergodic relation (26) shows that in the singular case, where
condition B1 holds, the stationary probabilities π0,p̄,k defined by the asymp-
totic relation (26) may depend on the initial distribution. The stationary
distributions π̄0,p̄ = hπ0,p̄,k , k ∈ Xi and π̄0,d¯ = hπ0,d,k
¯ , k ∈ Xi coincide, if
(g) (g)
probabilities fp̄ = fd¯ , g = 1, . . . , h. These relations obviously hold for any
initial distribution p̄ ∈ Pm in the regular case, where condition A1 holds.
4. A perturbation model for Markov chains with

damping component.
In this section, we show in which way Markov chains with damping com-
ponent can be interpreted as a stochastic perturbed model. We also present
11
results concerned with continuity of stationary distributions π̄ε with respect
to damping (perturbation) parameter ε → 0.
4.1 Continuity property transition probabilities. In what follows,
relation ε → 0 is a reduced version of relation 0 < ε → 0.
The Markov chain Xε,n has the matrix of transition probabilities Pε =
(1 − ε)P0 + εD. Obviously, for i, j ∈ X,
pε,ij → p0,ij as ε → 0. (27)
Also, as well known, matrix kpε,ij (n)k = Pnε , for n = 0, 1, . . ., where

P0ε = kI(i = j)k.
Therefore, the following asymptotic relation holds, for n ≥ 0, i, j ∈ X,
pε,ij (n) → p0,ij (n) as ε → 0. (28)
This relation let one consider the Markov chain Xε,n , for ε ∈ (0, 1], as
a perturbed version of the Markov chain X0,n and to interpret the damping
parameter ε as a perturbation parameter.
It was mentioned above, that the phase space X of the perturbed Markov
chain Xε,n is one communicative, aperiodic class of states, for every ε ∈ (0, 1].
As far as the unperturbed Markov chain X0,n is concerned, there are two
different cases.
The first one is, where condition A1 holds, i.e., the phase space X is also
one communicative class of states for the Markov chain X0,n . In this case,
one can refer to the corresponding perturbation model as regular.
The second one is, where condition B1 holds, i.e., the phase space X is
not one communicative class of states for the Markov chain X0,n . In this
case, one can refer to the corresponding perturbation model as singular.
4.2 Continuity property of stationary distributions for regularly
perturbed Markov chains with damping component. The following
proposition takes place.
Lemma 4. Let condition A1 holds. Then, the following asymptotic rela-
tion holds, for j ∈ X,
πε,j → π0,j as ε → 0. (29)
Proof. Let νε be a random variable geometrically distributed with pa-
rameter ε, i.e., P{νε = n} = ε(1 − ε)n−1 , n = 1, 2, . . .. Obviously,
P
νε − 1 −→ ∞ as ε → 0. (30)
12
In the case, where condition A1 holds, we get using relations (21) and
(30) that the following asymptotic relation holds, for j ∈ X,
P
¯ (νε − 1) −→ π0,j as ε → 0.
p0,d,j (31)
It is readily seen that the following representation takes place for the
stationary probabilities πε,j , i ∈ X,
∞
X
l
πε,j = ε ¯ (l)(1 − ε) = Ep0,d,j
p0,d,j ¯ (νε − 1). (32)
l=0
Since the sequence pp̄,j (n), n = 0, 1, . . . is a bounded, relations (31), (32)

and the corresponding variant of the Lebesgue theorem imply that the fol-
lowing asymptotic relation holds, for j ∈ X,
¯ (νε − 1) → π0,j as ε → 0.
πε,j = Ep0,d,j (33)

4.3 Continuity property of stationary distributions for singularly
perturbed Markov chains with damping component. In this case the
following lemma takes place.
Lemma 5. Let condition B1 holds. Then, the following asymptotic rela-
tion holds, for k ∈ X,
πε,k → π0,d,k
¯ as ε → 0. (34)
Proof. In the case, where condition B1 holds, we get using relations (26)
and (30) that the following asymptotic relation holds,
P
¯ (νε − 1) −→ π0,d,k
p0,d,k ¯ as ε → 0, for k ∈ X. (35)
Analogously to the relation (33), we get, using relatins (31) and (35), the
following asymptotic relation, for k ∈ X,
¯ (νε − 1) → π0,d,k
πε,k = Ep0,d,k ¯ as ε → 0. (36)

Remark 2. Lemmas 4 and 5 imply that, in the case where condition
A1 holds, the continuity property for stationary distributions π̄ε (as ε → 0)
takes place. However, in the case where condition B1 holds, the continuity
13
property for stationary distributions π̄ε (as ε → 0) takes place under the
(g) (g)
additional assumption under that fp̄ = fd¯ , g = 1, . . . , h.
5. Rate of convergence for perturbed stationary distributions
In this section, we obtain explicit upper bounds for deviations of station-

ary distributions of Markov chains Xε,n and X0,n .
5.1 Rate of convergence for stationary distributions of regularly
perturbed Markov chains with damping component. Let us get some
explicit upper bound for the rate of convergence in the asymptotic relation
(29) for the case, where condition A1 holds.
It is well known that, under condition A1 , the rate of convergence in
the ergodic relation (29) is exponential. This means that there exist some
constants C = C(P0 ) ∈ [0, ∞), λ = λ(P0 ) ∈ [0, 1), and distribution π̄0 =
hπ0,j , j ∈ Xi, with all positive components such that the following relation
holds,
max |p0,ij (n) − π0,j | ≤ Cλn , n ≥ 1. (37)
i,j∈X
In fact, condition A1 is equivalent to the following condition:
A2 : There exist a constants C = C(P0 ) ∈ [0, ∞), λ = λ(P0 ) ∈ [0, 1), and a
distribution π̄0 = hπ0,j , j ∈ Xi with all positive components such that
relation (37) holds.
Indeed, condition A2 implies that probabilities p0,ij (n) > 0, i, j ∈ X for all
large enough n. This implies that X is one aperiodic class of communicative
states. Also, condition A2 implies that p0,ij (n) → π0,j as n → ∞, for i, j ∈ X,
and, thus, π̄0 is the stationary distribution for the Markov chain X0,n .
According to the Perron-Frobenius theorem, the role of λ can play the
absolute value of the second (by absolute value), eigenvalue for matrix P0 .
As far as constant C is concerned, we refer to the book [19], where one can
find the algorithms which let one compute this constant.
An alternative and more simple variant of inequalities appearing in con-
dition A2 may be obtained with the use of coupling method. We give them
in Section 8.
The following theorem present explicit upper bounds for deviation of
stationary distributions for Markov chains Xε,n and X0,n .
14
Theorem 1. Let condition A2 holds. Then the following relation holds,
for j ∈ X,
Cλ
|πε,j − π0,j | ≤ ε(|dj − π0,j | + ). (38)
1−λ
Proof. The inequalities appearing in condition A2 imply that the fol-
lowing relation holds, for n ≥ 1, j ∈ X,
X
|p0,d,j
¯ (n) − π0,j | = | (di p0,ij (n) − di π0,j )|
i∈X
X
≤ di |p0,ij (n) − π0,j )| ≤ Cλn . (39)
i∈X
Using relations (16) and (39), we get the following estimate, for j ∈ X,
∞
X
l
|πε,j − π0,j | ≤ |ε ¯ (l)(1 − ε) − π0,j |
p0,d,j
l=0
X∞ ∞
X
l
= |ε ¯ (l)(1 − ε) − ε
p0,d,j π0,j (1 − ε)l |
l=0 l=0
∞
X
≤ ε|dj − π0,j | + ε Cλl (1 − ε)l
l=1
Cλ(1 − ε)
≤ ε(|dj − π0,j | + )
1 − λ(1 − ε)
Cλ
≤ ε(|dj − π0,j | + ). (40)
1−λ
Remark 3. The quantities |dj − π0,j | appearing in inequality (38) is, in
some sense, determined by a prior information about the stationary proba-
bilities π0,j . They take smaller values if one can choose initial distribution
p̄ with smaller deviation from the stationary distribution π̄0 . Inequalities
|dj − π0,j | ≤ dj ∨ (1 − dj ) ≤ 1 let one replace the term |dj − π0,j | in inequality
(38) by quantities independent on the corresponding stationary probabilities
π0,j .
Remark 4. Theorem 1 remains valid even we weaken condition A2 by
omitting in it the assumption of positivity for the distribution π̄0 = hπ0,i , i ∈
Xi. In this case, condition A2 implies that the phase space X = X1 ∪ X0 ,
15
where X1 = {i ∈ X : π0,i > 0} is the non-empty closed, aperiodic class of
communicative states, while X0 = {i ∈ X : π0,i = 0} is the class (possibly
empty) of transient states, for the Markov chain X0,n . Note that π̄0 still is
the stationary distribution for the Markov chain X0,n .
We would like also to refer to paper [34], where one can find alterna-
tive upper bounds for the rate of convergence of stationary distributions for
perturbed Markov chains and further related references.
5.2 Rate of convergence for stationary distributions of singularly
perturbed Markov chains with damping component. Let now assume
that condition B1 holds.
Let us consider matrices, for j = 1, . . . , h and n = 0, 1, . . .,
(j)
Pn0,j = kp0,rk (n)kr,k∈X(j) . (41)
(j)
Note that, for j = 1, . . . , h, probabilities p0,rk (n) = p0,rk (n), r, k ∈ X(j) , n ≥
0, since X(j) , j = 1, . . . , h are closed classes of states.
(j)
The reduced Markov chain X0,n with the phase space X(j) and the matrix
of transition probabilities P0,j is, for every j = 1, . . . , h, exponentially ergodic
and the following estimates take place, for k ∈ X(j) , j = 1, . . . , h and n =
0, 1, . . .,
(j) (j)
max |p0,rk (n) − π0,k | ≤ Cj λnj , (42)
r,k∈X(j)
with some constants Cj = Cj (P0,j ) ∈ [0, ∞), λj = λj (P0,j ) ∈ [0, 1), j =

(j) (j)
1, . . . , h and distributions π̄0 = hπ0,k , k ∈ X(j) i, j = 1, . . . , h, with all positive
components.
(j) (j)
Obviously, inequalities (42) imply that p0,rk (n) → π0,k as n → ∞, for
(j)
r, k ∈ X(j) , j = 1, . . . , h. Thus, distribution π̄0 is the stationary distribution
(j)
for the Markov chain X0,n , for every j = 1, . . . , h.
As has been mentioned above the role of λj can play, for every j =
1, . . . , h, the absolute value of the second (by absolute value), eigenvalue
for matrix P0,j , and Cj is the constant, which can be computed using the
algorithm described in the above mentioned book [19].
Let us denote,
λ = max λj , C = max Cj . (43)
1≤j≤h 1≤j≤h
Condition B1 is, in fact, equivalent to the following condition:
16
B2 : The phase space X = ∪hj=1 X(j) , where: (a) X (j) , j = 0, . . . , h are non-
classes of states for the Markov chain X0,n such that inequalities (42)
hold.
(j)
Indeed, condition B2 implies that probabilities p0,rk (n) > 0, r, k ∈ X(j) , j =
1, . . . , h for all large enough n. This implies that X(j) , j = 1, . . . , h are
closed, aperiodic classes of communicative states. Also, inequalities (42)
(j) (j)
imply that p0,rk (n) → π0,k as n → ∞, for r, k ∈ X(j) , j = 1, . . . , h, and, thus,
(j) (j)
π̄0 = hπ0,k , k ∈ X(j) i is the stationary distribution for the Markov chain
(j)
X0,n , for every j = 1, . . . , h.
Theorem 2. Let condition B2 holds. Then the following relation holds,
for k ∈ X,
Cλ
|πε,k − π0,d,k ¯ | ≤ ε(|dk − π0,d,k
¯ |+ ). (44)
1−λ
The proof of Theorem 2 is analogous to the proof of Theorem 1.
6. Asymptotic expansions for perturbed stationary

distributions
In this section, we present asymptotic expansions for stationary distribu-

tions of Markov chains with damping component with respect to damping
parameter.
6.1 Asymptotic expansions for stationary distributions of reg-
ularly perturbed Markov chains with damping component. Let us
get some asymptotic expansions for perturbed stationary distributions in the
case, where condition A1 holds.
According to the Perron-Frobenious theorem, in this case, the eigenvalues
ρ1 , . . ., ρm of the stochastic matrix P0 satisfy the following condition:
A3 : ρ1 = 1 > |ρ2 | ≥ · · · ≥ |ρm |.
Note that some of eigenvalues ρ2 , . . . , ρm can be complex numbers.

As well known, condition A3 implies that the following eigenvalues de-
composition representation takes place, for i, j ∈ X and n ≥ 1,
p0,ij (n) = π0,j + ρn2 π0,ij [2] + · · · + ρnm π0,ij [m], (45)
17
where: (a) π̄0 = hπ0,j , j ∈ Xi is distribution with all positive component, (b)
π0,ij [l], i, j ∈ X, l = 2, . . . , m are some real or complex valued coefficients, (c)
π0,ij [k] = π0,ij [l], i, j ∈ X, if ρk = ρl , for some 2 ≤ k, l ≤ m.
In is useful to note that the eigenvalues decomposition representation
can be rewritten in the alternative form based on distinct eigenvalues for
matrix P0 . Let ρ̄k , k = 1, . . . , m̄ be the above mentioned distinct eigenvalues,
Xk = {1 ≤ l ≤ m : ρl = ρ̄k }, and vk be the index of multiplicity of the
eigenvalue ρ̄k (the number of items in set Xk ), for k = 1, . . . , m̄. Also, let us
assume that ρ̄1 = 1 > |ρ̄2 | ≥ · · · ≥ |ρ̄m̄ |, and denote π̄0,ij [k] = vk π0,ij [lk ], i, j ∈
X, lk ∈ Xk , k = 2, . . . , m̄ (these coefficients do not depend on the choice of
lk ∈ Xk , k = 1, . . . , m̄).
Then, the eigenvalues decomposition representation (45) can be rewritten
in the following form, for i, j ∈ X and n ≥ 1,
p0,ij (n) = π0,j + ρ̄n2 π̄0,ij [2] + · · · + ρ̄nm̄ π̄0,ij [m̄]. (46)
Obviously, relation (45) implies that probabilities pij (n) → π0,j as n →

∞, for i, j ∈ X. Thus, π̄0 is the stationary distribution for the Markov chain
X0,n .
In fact, condition A3 is equivalent to condition A1 .
Indeed, the convergence relation, p0,ij (n) → π0,j as n → ∞, for i, j ∈ X,
implies that p0,ij (n) > 0, i, j ∈ X, for all large enough n. This implies that
X is one aperiodic class of communicative states.
We refer to book [19], where one can find the description of effective
algorithm for finding matrices Πl = kπ0,ij [l]k, l = 2, . . . , m.
Relation (45) implies the following relation holds, for j ∈ X and n ≥ 1,
n n
p0,d,j ¯ [2] + · · · + ρm π0,d,j
¯ (n) = π0,j + ρ2 π0,d,j ¯ [m], (47)
where, for j ∈ X, l = 2, . . . , m,
X
π0,d,j
¯ [l] = di π0,ij [l]. (48)
i∈X
Let also define coefficients, for j ∈ X, n ≥ 1,


 dj − π0,j + m ρl
P
l=2 π0,d,j
¯ [l] 1−ρ
l
for n = 1,
π̃0,d,j
¯ [n] = n−1 (49)
 (−1)n−1 Pm π ¯ [l] ρl n for n > 1.
l=2 0,d,j (1−ρl )
18
Below, symbol O(εn ) is used for quantitiies such that O(εn )/εn is bounded
as function of ε ∈ (0, 1].
The following theorem takes place.
Theorem 3. Let condition A3 holds. Then, the following asymptotic
expansions take place for every j ∈ X and n ≥ 1,
n n+1
¯ [1]ε + · · · + π̃0,d,j
πε,j = π0,j + π̃0,d,j ¯ [n]ε + O(ε ). (50)
Proof. Relations (16) and (47) imply that the following relation holds,
for j ∈ X,
∞
X
n
πε,j = ε ¯ (n)(1 − ε)
p0,d,j
n=0
∞
X m
X
= εdj + ε (π0,j + ρnl π0,d,j
¯ [l])(1 − ε)
n
n=1 l=2
m
X ∞
X
= π0,j + ε(dj − π0,j ) + π0,d,j
¯ [l]ε ρnl (1 − ε)n
l=2 n=1
m
X ρl ε(1 − ε)
= π0,j + ε(dj − π0,j ) + π0,d,j
¯ [l]
l=2
1 − ρl (1 − ε)
Xm
−1
= π0,j + ε(dj − π0,j ) + ¯ [l]ρl ε(1 − ε)(1 − ρl + ρl ε) .
π0,d,j (51)
l=2
Functions (a + bε)−1 , ε ∈ [0, 1] and bε(1 − ε)(a + bε)−1 , ε ∈ [0, 1] admit,

for any complex numbers a 6= 0 and b, the following Taylor asymptotic
expansions, for every n ≥ 1 and ε → 0,
(a + bε)−1 = a−1 − a−2 bε + a−3 b2 ε2

+ · · · + (−1)n a−(n+1) bn εn + O(εn+1 ), (52)
and
bε(1 − ε)(a + bε)−1 = a−1 bε − a−1 b(1 + a−1 b)ε2 + a−2 b2 (1 + a−1 b)ε3
+ · · · + (−1)n−1 a−(n−1) bn−1 (1 + a−1 b)εn + O(εn+1 ). (53)
19
Relations (51) – (53) let us write down the following Taylor asymptotic
expansions for stationary probabilities πε,j , j ∈ X, for every n ≥ 1 and ε → 0,
m
X
−1
πε,j = π0,j + ε(dj − π0,j ) + ¯ [l]ρl ε(1 − ε)(1 − ρl + ρl ε)
π0,d,j
l=2
n n+1
¯ [1]ε + · · · + π̃0,d,j
= π0,j + π̃0,d,j ¯ [n]ε + O(ε ). (54)
It worth noting that some of eigenvalues ρl and coefficients π0,ij [r] can
be complex numbers. Despite of this, coefficients π̃0,d,j ¯ [n], n ≥ 1 in the
expansions given in relation (50) are real numbers.
Indeed, πε,j is a positive number, for every ε ∈ [0, 1]. Relation (54) implies
that (πε,j − π0,j )ε−1 → π̃0,d,j
¯ [1] as ε → 0. Thus, π̃0,d,j ¯ [1] is a real number. In
this way, the above proposition can be proved for all coefficients in expansions
(50). This implies that the remainders of these expansions O(εn+1 ) also are
real-valued functions of ε.
Moreover, since π̄ε = hπε,j , j ∈ Xi, ε ∈ (0, 1] and π̄0 = hπ0,j , j ∈ Xi are
probability distributions, theP following equalities connect coefficients in the
asymptotic expansions (50), j∈X π̃0,d,j ¯ [n] = 0, for n ≥ 1.
6.2 Asymptotic expansions for stationary distributions of singu-

larly perturbed Markov chains with damping component. Let now
consider the case, where condition B1 holds. We can assume that class X(j)
includes mj states, for j = 1, . . . , h, where mj > 0, j = 1, . . . , h.
Let us denote by ρj,1 , . . ., ρj,mj the eigenvalues of the stochastic matrices
P0,j , j = 1, . . . , h. We can assume that these eigenvalues are ordered by
absolute values , i.e. |ρj,1 | ≥ |ρj,2 | ≥ · · · ≥ |ρj,mj |, for j = 1, . . . , h.
Condition B1 is, in fact, equivalent to the following condition:
classes of states for the Markov chain X0,n such that inequalities ρj,1 =
1 > |ρj,2 | ≥ · · · ≥ |ρj,mj |, j = 1, . . . , h, hold.
Condition B1 implies that condition B3 holds. This follows from the
Perron-Frobenius theorem.
Condition B3 imply that the following eigenvalues decomposition repre-
sentations take place, for r, k ∈ X(i) , j = 1, . . . , h and n ≥ 1,
(j) (j) (j) (j)
p0,rk (n) = π0,k + ρnj,2 π0,rk [2] + · · · + ρnj,mj π0,rk [mj ], (55)
20
(j) (j)
where: (a) π̄0 = hπ0,k , k ∈ X(j) i is a distribution with all positive com-
(j)
ponent, for j = 1, . . . , h, (b) π0,rk [l], r, k ∈ X(j) , l = 2, . . . , mj , j = 1, . . . , h
(j)
are some real or complex valued coefficients satisfying equalities π0,rk [s] =
(j)
π0,rk [t], r, k ∈ X(j) , if ρj,s = ρj,t , for some 2 ≤ s, t ≤ mj , j = 1, . . . , h.
(j)
Obviously, relation (46) implies that probabilities prk (n) → π0,j as n →
(j)
∞, for r, k ∈ X(j) , j = 1, . . . , h. Thus, π̄0 is the stationary distribution of
(j)
the Markov chain X0,n , for j = 1, . . . , h.
In fact, condition B3 is equivalent to condition B1 .
Indeed, as was mentioned above, relation (46) implies that probabilities
(j) (j)
p0,rk (n) → π0,k as n → ∞, for r, k ∈ X(j) , j = 1, . . . , h. Thus, probabilities
(j)
p0,rk (n) > 0, r, k ∈ X, j = 1, . . . , h, for all large enough n. This implies
that X(j) is, for every j = 1, . . . , h a closed aperiodic class of communicative
states for the Markov chain X0,n . Thus, condition B3 implies that condition
B1 holds.
We again refer to book [19], where one can find the description of effective
(j) (j)
algorithm for finding matrices Πl = kπ0,rk [l]k, l = 2, . . . , mj , j = 1, . . . , h.
Relation (46) implies, in this case, the following relation holds, for any
k ∈ X(j) , j = 1, . . . , h and n ≥ 1,
n (j) n (j)
p0,d,k ¯ + ρj,2 π ¯ [2] + · · · + ρj,mj π ¯ [mj ],
¯ (n) = π0,d,k (56)
0,d,k 0,d,k
where, for k ∈ X(j) , l = 2, . . . , mj , j = 1, . . . , h,

(j)
X (j)
π0,d,k¯ [l] = dr π0,rk [l]. (57)
r∈X(j)
Let also define coefficients, for k ∈ X(j) , j = 1, . . . , h, n ≥ 1,

 (j) Pm (j) ρj,l
 dk − π0,k + l=2j π0,d,k ¯ [l] 1−ρj,l for n = 1,
(j)
π̃0,d,k
¯ [n] = (58)
 (−1)n−1 Pmj π (j) [l] ρn−1 j,l
for n > 1.
¯
l=2 0,d,k (1−ρj,l )n
The following theorem takes place.

Theorem 4. Let condition B3 holds. Then, the following asymptotic
expansion take place for every for k ∈ X(j) , j = 1, . . . , h, n ≥ 1,
(j) (j)n n+1
¯ + π̃ ¯ [1]ε + · · · + π̃ ¯ [n]ε + O(ε
πε,k = π0,d,k ). (59)
0,d,k 0,d,k
21
The proof is similar with the proof of Theorem 3.
7. Coupling for regularly perturbed Markov chains

with damping component
In this section, we present coupling algorithms and get the effective upper
bound for the rate of convergence in ergodic theorems for regularly perturbed
Markov chains with damping component.
7.1 Maximal coupling for discrete distributions. Let p̄0 = hp0i , i ∈
Xi and p̄00 = hp001 , i ∈ Xi be two discrete probability distributions. Let us
denote by L[p̄0 , p̄00 ] the class of two-dimensional distribution
P P̄ = hPij ,0 (i, j) ∈
0
X × Xi which satisfy the following conditions (a) P i = j∈X Pij = pi , i ∈ X;
00 00
P
(b) Pj = i∈X Pij = pj , j ∈ X.
Let us also denote, X
QP̄ = Pii (60)
i∈X
and
Q(p̄0 , p̄00 ) = sup QP̄ . (61)
P̄ ∈L[p̄0 ,p̄00 ]
The following lemma presents the well known “coupling” result, which
variants can be found in [22, 27, 33, 38] and [41, 42, 43, 44, 48].
Lemma 6. There exists the two-dimensional distribution P̄ ∗ = hPij∗ , i, j ∈
Xi ∈ L[p̄0 , p̄00 ] such that:
X
QP̄ ∗ = Q∗ = min(p0i , p00i ) = Q(p̄0 , p̄00 ). (62)
i∈X
The distribution P̄ ∗ is given by the following relations:

(i) If Q∗ ∈ (0, 1), then
Pij∗ = min(p0i , p00j )I(i = j)

1
+ (p0 − min(p0i , p00i ))(p00j − min(p0j , p00j )), i, j ∈ X. (63)
1 − Q∗ i
(ii) Q∗ = 1 if and only if p0k = p00k , k ∈ X and, in this case,
Pij∗ = min(p0i , p00j )I(i = j), i, j ∈ X. (64)
22
(iii) Q∗ = 0 if and only if p0k p00k = 0, k ∈ X and, in this case,
Pij∗ = p0i p00j , i, j ∈ X. (65)
Proof. It can be found in the above mentioned works. In order, to

improve self-readability of the present paper, we just give a short sketch
of the proof. Obviously, probability Pii ≤ p0i ∧ p00i , i ∈ X, for any two-
ij , (i, j) ∈ X × Xi ∈ L[p̄ , p̄ ]. This rela-
0 00
dimensional distribution P̄ = hP
tion implies that QP̄ ≤ Q∗ = 0 00
P
i∈X pi ∧ pi . This is easily to check that
every relation (63), (64), or (65) defines a two-dimensional distribution P̄ ∗
from the class L[p̄0 , p̄00 ]. Moreover, the corresponding quantity QP̄ ∗ = Q∗ .
This is obvious for two cases presented in propositions (ii) and (iii). In
the first case presented in proposition (i), this follows from the relation,
(p0i − min(p0i , p00i ))(p00i − min(p0i , p00i )) = 0, i ∈ X.
7.2 A one-step coupling for regularly perturbed Markov chains
with damping component. Let us recall the matrix of transition proba-
bilities Pε = kpε,ij k and define the quantities,
X
Qε,ij = min(pε,ir , pε,jr ), i, j ∈ X. (66)
r∈X
Let now use the “one-step” coupling algorithm for construction a “cou-
0 00
pling” Markov chain Zε,n = (Xε,n , Xε,n ), n = 0, 1, . . ., with:
(i) the phase space Z = X × X;
(ii) the initial distribution P̄ε = hPε,ij , (i, j) ∈ Zi constructing according
to relation (63), (64), or (65) for distributions p̄0 = p̄ = hpi , i ∈ Xi and
p̄00 = π̄ε = hπε,i , i ∈ Xi;
(iii) the transition probabilities Pε,ij,rk defined by the following relations,
for (i, j), (r, k) ∈ Z:
(a) If Qε,ij ∈ (0, 1), then,
0 00 0 00
Pε,ij,rk = P{Xε,1 = k, Xε,1 = r/Xε,0 = i, Xε,0 = j}
= min(pε,ir , pε,jk )I(r = k)
1
+ (pε,ir − min(pε,ir , pε,jr ))(pε,jk − min(pε,ik , pε,jk )). (67)
1 − Qε,ij
(b) If Qε,ij = 1, then pε,ir = pε,jr , r ∈ X and,
Pε,ij,rk = min(pε,ir , pε,jk )I(r = k). (68)
23
(c) If Qε,ij = 0, then pε,ir pε,jr = 0, r ∈ X and,
Pε,ij,rk = pε,ir pε,jk . (69)
The above construction of coupling Markov chain and the following lemma
originate from works [22] and [38] and plays an important role in what fol-
lows.
0 00
Lemma 7. Let Zε,n = (Xε,n , Xε,n ), n = 0, 1, . . . be a homogeneous Markov
chain with the phase space Z = X × X, the initial distribution P̄ε and transi-
tion probabilities given by relations (67) – (69). Then:
0
(i) The first component, Xε,n , n = 0, 1, . . ., is a homogeneous Markov
chain with the phase space X, the initial distribution p̄ and the matrix of
transition probabilities Pε .
00
(ii) The second component Xε,n , n = 0, 1, . . . is a homogeneous Markov
chain with the phase space X, the initial distribution π̄ε and the matrix of
transition probabilities Pε .
(iii) The set Z0 = {(i, i), i ∈ X} is an absorbing set for the Markov chain
Zε,n , i.e., probabilities Pε,ii,rk = 0, for i, r, k ∈ X, r 6= k.
Proof. Variants of the proof can be found in the above mentioned works.
In order, to improve self-readability of the present paper, we just give a short
sketch of the proof. Let us consider the case, where transition probabilities
Pε,ij,rk are given by relation (67). According to Lemma 6, the following
relation takes place, for i, j, r ∈ X,
X X
Pε,ij,rk = min(pε,ir , pε,jk )I(r = k)
k∈X k∈X
1 X
+ (pε,ir − min(pε,ir , pε,jr )) (pε,jk − min(pε,ik , pε,jk ))
1 − Qε,ij k∈X
= min(pε,ir , pε,jr ) + pε,ir − min(pε,ir , pε,jr ) = pε,ir . (70)
The proof of relation (70) in the cases where transition probabilities Pε,ij,rk
are given by relation (68) or (69) is trivial.
Using the assumption that Zε,n is a Markov chain and relation (70), we
24
get the following relation, for any chain of states i0 , . . . , in ∈ X, n ≥ 0,
X
0 0 00
P{Xε,l = il , l = 0, . . . , n} = P{Xε,l = il , Xε,l = jl , l = 0, . . . , n}
j0 ,...,jn ∈X
X X X
= pi0 πε,j0 Pε,i0 j0 ,i1 j1 · · · Pε,in−1 jn−1 ,in jn
j0 ∈X j1 ∈X jn ∈X
X X X
= pi0 πε,j0 Pε,i0 j0 ,i1 j1 · · · Pε,in−2 jn−2 ,in−1 jn−1 · pε,in−1 ,in
j0 ∈X j1 ∈X jn−1 ∈X
X
= ··· = pi0 πε,j0 pε,i0 ,i1 · · · pε,in−1 ,in
j0 ∈X
= pi0 pε,i0 ,i1 · · · pε,in−1 ,in . (71)

Relation (71) proves proposition (i). The proof of proposition (ii) is
analogous.
According to relation (68), the quantities Qε,ii = 1, i ∈ X. This proves
proposition (iii).
Let A = kaij k be a m × m a matrix with real-valued elements. Let us
introduce functional,
m
X
Q(A) = min aik ∧ ajk . (72)
1≤i,j≤m
k=1
The following simple lemma presents some basic properties of functional

Q(A).
Lemma 8. Functional Q(A) possesses the following properties: (a)
Q(aA) = aQ(A), for any a ≥ 0; (b) Q(A) ≥ a1 Q(A1 ) + · · · + an Q(An ), for
any m×m matrices A1 , . . . , An with real-valued elements, numbers a1 , . . . , an
≥ 0, a1 · · ·+an = 1, and matrix A = a1 A1 +· · ·+an An , for n ≥ 2; (c) Q(A) ∈
[0, 1], for any stochastic matrix A; (d) Q(A) = 1, for any m × m stochastic
damping type matrix A = kaij k, with elements aij = aj ≥ 0, i, j = 1, . . . , m.
Lemma 8 implies that the following inequality holds,
Q(Pε ) ≥ (1 − ε)Q(P0 ) + εQ(D)
= (1 − ε)Q(P0 ) + ε, (73)
Let us also introduce quantities,
X
Qε,p̄ = Q(p̄, π̄ε ) = min(pi , πε,i ). (74)
i∈X
25
The given below Theorems 5 and 6 present effective upper bounds for the
rate of convergence in the individual ergodic theorem for perturbed Markov
chain with damping component based on corresponding general coupling re-
sults for Markov chains given in [22, 33, 38]. Theorems 5 and 6 specify and
detail coupling upper bounds for the rate of convergence for Markov chains
with damping component.
Note that condition A1 is not required in Theorem 5 formulated below.
Also, we count (1 − Q(P0 ))0 = 1, if 1 − Q(P0 ) = 0.
Theorem 5. The following relation takes place, for every ε ∈ (0, 1] and
p̄ ∈ Pm , j ∈ X, n ≥ 0,
|pε,p̄,j (n) − πε,j | ≤ (1 − Qε,p̄ )(1 − Q(P0 ))n (1 − ε)n , (75)
Proof. Obviously, for p̄ ∈ Pm , j ∈ X, n ≥ 0,
0
P{Xε,n = j} = pε,p̄,j (n). (76)
00
Since, the initial distribution of Markov chain Xε,n coincides with its
stationary distribution, this Markov chain is a stationary random sequence
and, thus, for j ∈ X, n ≥ 0,
00
P{Xε,n = j} = πε,j . (77)
Let now define the hitting (coupling) time,
0 00
Tε = min(n ≥ 0 : Xε,n = Xε,n ) = min(n ≥ 0 : Zε,n ∈ Z0 ). (78)
Since Z0 is an absorbing set for the Markov chain Zε,n , the following
relation holds,
P{Zε,n ∈ Z0 , n ≥ Tε } = 1. (79)
Using the above remarks, we get the following relation, for j ∈ X, n ≥ 0,
0 00
|pε,p̄,j (n) − πε,j | = |P{Xε,n = j} − P{Xε,n = j}|
0 00 0 00
= |P{Xε,n = j, Xε,n 6= j} − P{Xε,n 6= j, Xε,n = j}|
0 00 0 00
≤ P{Xε,n = j, Xε,n 6= j} + P{Xε,n 6= j, Xε,n = j}
≤ P{Tε > n}. (80)
Using Lemma 6, we get, p̄ ∈ Pm , j ∈ X,
0 00 0 00
|pε,p̄,j (0) − πε,j | ≤ P{Xε,0 = j, Xε,0 6= j} + P{Xε,0 6= j, Xε,0 = j}
≤ P{Tε > 0} = 1 − Qε,p̄ . (81)
26
Also, by continuing the inequalities (80) we get, for p̄ ∈ Pm , j ∈ X, n ≥ 1,
|pε,p̄,j (n) − πε,j | ≤ P{Tε > n}
X
0 00
= P{Tε > n − 1, Xε,n−1 = i, Xε,n−1 = j}
i,j∈X
0 0 0 0
× P{Xε,n 6= Xε,n /Xε,n−1 = i, Xε,n−1 = j}
X
0 00
= P{Tε > n − 1, Xε,n−1 = i, Xε,n−1 = j}(1 − Qε,ij )
i,j∈X
≤ P{Tε > n − 1}(1 − Q(Pε ))

≤ · · · ≤ P{Tε > 0}(1 − Q(Pε ))n
= (1 − Qε,p̄ )(1 − Q(P0 ))n (1 − ε)n . (82)
Remark 5. The upper bounds given in relation (75) become better if
quantities 1 − Qε,p̄ , 1 − Q(P0 ) and 1 − ε take smaller values. The factor 1 −
Qε,p̄ , is determined by a prior information about the stationary probabilities.
It takes smaller values if one can choose initial distribution p̄ with smaller
deviation from the stationary distribution π̄ε . Relation (75) gives an effective
upper bounds for the rate of convergence in the corresponding individual
ergodic theorem even in the case where factor 1 − Q(P0 ) = 1.
It worth noting that the upper bound (1 − ε)n on the the right hand side
of inequality (75) have been given for Markov chains with a general phase
and damping component, in the recent paper [5].
As it was shown in [38], the following formula takes place,
X
∆1 (P0 ) = 1 − Q(P0 ) = max(1 − p0,ik ∧ p0,jk )
i,j∈X
k∈X
1 X X
= max (p0,ik − p0,ik ∧ p0,jk ) + (p0,jk − p0,ik ∧ p0,jk )
2 i,j∈X k∈X k∈X
1 X X
= max (p0,ik − p0,jk ) + (p0,jk − p0,ik )
2 i,j∈X k:p ≥p k:p ≥p
0,ik 0,jk 0,jk 0,ik
1 X
= max |p0,ik − p0,jk |. (83)
2 i,j∈X k∈X
The quantity ∆1 (P0 ) is known as an ergodicity coefficient. It determines

ergodic properties of the Markov chain X0,n .
27
This Markov chain is ergodic with an exponential rate of convergence in
the corresponding ergodic theorem, if the following condition holds:
C(1) : ∆1 (P0 ) ∈ [0, 1).
Condition C(1) is sufficient for holding the weaken variant of condition
A1 mentioned in Remark 4.
Indeed, probabilities pε,p̄,j (n) → p0,p̄,j (n) as ε → 0, for any j ∈ X, n ≥ 0.
Since stationary probabilities πε,j ∈ [0, 1], j ∈ X, any sequence 0 < εn → 0 as
n → ∞ contain a subsequence 0 < εnl → 0 as l → ∞ such that πεnl ,j → π0,j
as l → ∞, for j ∈ X. By passing ε → 0 in the inequality (75), we get the
following relation holding for p̄ ∈ Pm , j ∈ X, n ≥ 0,
|p0,p̄,j (n) − π0,j | ≤ (1 − Q0,p̄ )∆1 (P0 )n , (84)
where one should count ∆1 (P0 )0 = 1, if ∆1 (P0 ) = 0.

Relation (102) obviously implies that p0,p̄,j (n) → π0,j as n → ∞, for
j ∈ X. Thus limits π0,j , j ∈ X are the same for any subsequences εn and εnl
and, thus, stationary probabilities πε,j → π0,j as ε → 0, for j ∈ X. By passing
ε → 0 in the equations given in relation (20), we get that limits π0,j , j ∈ X
satisfy the system of linear equations (22) and, thus, π̄0 = hπ0,j , j ∈ Xi is
the stationary distribution for the Markov chain X0,n . Some components
of this stationary distribution can equal 0. In this case, set X (1) = {j ∈
X : π0,j > 0} is a closed, aperiodic class of communicative states, while set
X (0) = {j ∈ X : π0,j = 0} is the class of transient states, for the Markov
chain X0,n .
If the stationary distribution π̄0 = hπ0,j , j ∈ Xi is positive, then X (0) = ∅.
In this case, condition C(1) is sufficient for holding of condition A1 .
Relation (84) implies that the Markov chain X0,n is ergodic with an expo-
nential rate of convergence in the corresponding ergodic theorem, if condition
C(1) holds.
7.3 A multi-step coupling for regularly perturbed Markov chains
with damping component. The problem with the ergodicity coefficient
∆1 (P0 ) is that it can take value 1 even in the case where condition A1 holds.
This happens if there exists two states i, j ∈ X such that the distributions
0,i = hp0,ir , r ∈ Xi and p̄0,j = hp0,jr , r ∈ Xi are singular, i.e., Q0,ij =
p̄P
r∈X min(p0,ir , p0,jr ) = 0.
(N )
Let us consider the random sequence Xε,n = Xε,N n , n = 0, 1, . . ., for
some natural N > 1. It is a homogeneous Markov chain, with the initial
28
distribution p̄, the phase space X, and the matrix of transition probabilities
PNε = kpε,ij (N )k.
Let us define the quantities, for i, j ∈ X and N > 1,
(N )
X
Qε,ij = min(pε,ir (N ), pε,jr (N )). (85)
r∈X
Let now use the “multi-step” coupling algorithm for construction a “cou-
(N ) 0(N ) 00(N )
pling” Markov chain Zε,n = (Xε,n , Xε,n ), n = 0, 1, . . ., with:
(i) the phase space Z = X × X;
(ii) the initial distribution P̄ε = hpε,ij , (i, j) ∈ Zi constructing according
to relation (63), (64), or (65) for distributions p̄0 = p̄ = hpi , i ∈ Xi and
p̄00 = π̄ε = hπε,i , i ∈ Xi;
(N )
(iii) transition probabilities Pε,ij,rk defined by the following relations, for
(i, j), (r, k) ∈ Z:
(N )
(a) If Qε,ij ∈ (0, 1), then,
(N ) 0(N ) 00(N ) 0(N ) 00(N )
Pε,ij,rk = P{Xε,1 = k, Xε,1 = r/Xε,0 = i, Xε,0 = j}
= min(pε,ir (N ), pε,jk (N ))I(r = k)
1
+ (N )
(pε,ir (N ) − min(pε,ir (N ), pε,jr (N )))
1 − Qε,ij
× (pε,jk (N ) − min(pε,ik (N ), pε,jk (N ))), (86)
(N )
(b) If Qε,ij = 1, then pε,ir (N ) = pε,jr (N ), r ∈ X and,
(N )
Pε,ij,rk = min(pε,ir (N ), pε,jk (N ))I(r = k), r, k ∈ X. (87)
(N )
(c) If Qε,ij = 0, then pε,ir (N )pε,jr (N ) = 0, r ∈ X and,
(N )
Pε,ij,rk = pε,ir (N )pε,jk (N ), r, k ∈ X. (88)
The following lemma is the direct corollary of Lemma 7.
(N ) 0(N ) 00(N )
Lemma 8. Zε,n = (Xε,n , Xε,n ), n = 0, 1, . . ., be a homogeneous Markov
chain with the phase space Z = X × X, the initial distribution P̄ε and transi-
tion probabilities given by relations (86) – (88). Then:
0(N )
(i) The first component, Xε,n , n = 0, 1, . . ., is a homogeneous Markov
chain with the phase space X, the initial distribution p̄ and the matrix of
transition probabilities PN
ε .
29
00(N )
(ii) The second component Xε,n , n = 0, 1, . . . is a homogeneous Markov
chain with the phase space X, the initial distribution π̄ε and the matrix of
transition probabilities PN ε .
(iii) The set Z0 = {(i, i), i ∈ X} is an absorbing set for the Markov chain
(N ) (N )
Zε,n , i.e., probabilities Pε,ii,rk = 0, for i, r, k ∈ X, r 6= k.
Relation, AB = B, holds for any m × m stochastic matrix A = kaij k and
m × m stochastic damping type matrix B = kbij k, with elements bij = bj ≥
0,
Pi,mj = 1, . . . , m. Also, matrix C = BA, which has elements, cij = cj =
k=1 bk akj ≥ 0, i, j = 1, . . . , m, is a stochastic damping type matrix, i.e., it
has all rows the same.
Using these remarks, we get the following formula,
PN
ε = ((1 − ε)P0 + εD)
N
= PεN −1 (1 − ε)P0 + PN
ε
−1
εD
= PεN −1 (1 − ε)P0 + εD
= PεN −2 (1 − ε)2 P20 + PN
ε
−2
ε(1 − ε)DP0 + εD
N −1 −1
= · · · = (1 − ε)N PN
0 + ε(1 − ε) DPN
0 + · · · + εD. (89)
Using relation (89) and the above remarks we get the following relation,
Q(N
ε
)
= Q(PN
ε )
N −1 −1
≥ (1 − ε)N Q(PN
0 ) + ε(1 − ε) Q(DPN
0 ) + · · · + εQ(D)
N −1
= (1 − ε)N Q(PN
0 ) + ε(1 − ε) + ··· + ε
= (1 − ε)N Q(PN N
0 ) + 1 − (1 − ε) . (90)
Let us introduce, for N ≥ 1, the coefficient of ergodicity,
∆N (P0 ) = (1 − Q(PN
0 ))
1/N
. (91)
Note that condition A1 is not required in this theorem.
Below, we count ∆N (P0 )0 = 1, if ∆N (P0 ) = 0.
Theorem 6. The following relation takes place for every ε ∈ (0, 1] and
p̄ ∈ Pm , j ∈ X, n ≥ 0,
|pε,p̄,j (n) − πε,j | ≤ (1 − Qε,p̄ )∆N (P0 )[n/N ]N (1 − ε)[n/N ]N . (92)
Proof. Obviously, for p̄ ∈ Pm , j ∈ X, n ≥ 0,
0(N )
P{Xε,n = j} = pε,p̄,j (N n). (93)
30
00(N )
Since, the initial distribution of Markov chain Xε,n coincides with its
stationary distribution, this Markov chain is a stationary random sequence
and, thus, for j ∈ X, n ≥ 0,
00(N )
P{Xε,n = j} = πε,j . (94)
Let now define a hitting (coupling) time
0(N ) 00(N )
Tε(N ) = min(n ≥ 0 : Xε,n = Xε,n (N )
) = min(n ≥ 0 : Zε,n ∈ Z0 ). (95)
Since Z0 is an absorbing set for the Markov chain Zε,n , the following
relation holds,
(N )
P{Zε,n ∈ Z0 , n ≥ Tε(N ) } = 1. (96)
Using the above remarks, we get the following relation, for j ∈ X, n ≥ 0,
0(N ) 00(N )
|pε,p̄,j (N n) − πε,j | = |P{Xε,n = j} − P{Xε,n = j}|
0(N ) 00(N ) 0(N ) 00(N )
= |P{Xε,n = j, Xε,n 6= j} − P{Xε,n 6= j, Xε,n = j}|
0(N ) 00(2) 0(N ) 00(N )
≤ P{Xε,n = j, Xε,n 6= j} + P{Xε,n 6= j, Xε,n = j}
≤ P{Tε(N ) > n}. (97)
Using Lemma 6, we get, p̄ ∈ Pm , j ∈ X,
0(N ) 00(N )
|pε,p̄,j (0) − πε,j | ≤ P{Xε,0 = j, Xε,0 6= j}
0(N ) 00(N )
+ P{Xε,0 6= j, Xε,0 = j}
≤ P{Tε(N ) > 0} = 1 − Qε,p̄ . (98)
Also, by continuing the inequalities (80) we get, for p̄ ∈ Pm , j ∈ X, n ≥ 1,
|pε,p̄,j (N n) − πε,j | ≤ P{Tε(N ) > n}
0(N ) 00(N )
X
= P{Tε(N ) > n − 1, Xε,n−1 = i, Xε,n−1 = j}
i,j∈X
0(N ) 0(N ) 0(N ) 0(N )
× P{Xε,n 6= Xε,n /Xε,n−1 = i, Xε,n−1 = j}
0(N ) 00(N )
X (N )
= P{Tε(N ) > n − 1, Xε,n−1 = i, Xε,n−1 = j}(1 − Qε,ij )
i,j∈X
≤ P{Tε(N ) > n − 1}(1 − Q(PN

ε ))
≤ · · · ≤ P{Tε > 0}(1 − Q(PN
ε ))
n
= (1 − Qε,p̄ )(1 − Q(PN n

0 )) (1 − ε)
Nn
= (1 − Qε,p̄ )∆N (P0 ))N n (1 − ε)N n . (99)
31
Also, for p̄ ∈ Pm , j ∈ X, n ≥ 0 and l = 0, . . . , N − 1,
X X
|pε,p̄,j (N n + l) − πε,j | = | pε,p̄,k (nN )pε,kj (l) − πε,k pε,kj (l)|
k∈X k∈X
X
≤ |pε,p̄,k (N n) − πε,k |pε,kj (l)
k∈X
≤ max |pε,p̄,k (N n) − πε,k |
k∈X
≤ (1 − Qε,p̄ )∆N (P0 )N n (1 − ε)N n . (100)
Inequalities (98) and (100) imply inequalities given in relation (92). The
proof is complete.
The following formula, analogous to (83), takes place,
1 X
∆N (P0 ) = (1 − Q(PN
0 ))1/N
= ( max |p0,ik (N ) − p0,jk (N )|)1/N . (101)
2 i,j∈X k∈X
In the case, where condition A1 holds, 1 − Q(PN0 ) → 0 as N → ∞, i.e.,

the following condition holds for N large enough:
C(N ) : ∆N (P0 ) ∈ [0, 1).
Also, condition C(N ) is, for every N ≥ 1, sufficient for holding the weaken
variant of condition A1 mentioned in Remark 4. If the corresponding sta-
tionary distribution π̄0 = hπ0,j , j ∈ Xi is positive, condition C(N ) is, for every
N ≥ 1, sufficient for holding condition A1 .
As in Subsection 7.2, by passing ε → 0 in the first inequality given in
relation (92) we get the inequality holding for any p̄ ∈ Pm , j ∈ X, n ≥ 0,
|p0,p̄,j (n) − π0,j | ≤ (1 − Q0,p̄ )∆N (P0 ))[n/N ]N . (102)
In the case, where condition A1 holds, the eigenvalues decomposition

representation (45) implies that the following relation holds, under the as-
sumption that the second eigenvalue ρ2 and the factor which stays in front
of |ρ2 | in relation (103) are not equal 0,
1 X X 1/N
∆N P0 ) ∼ ( max | (π0,ik [l] − π0,jk [l])| |ρ2 |
2 i,j∈X k∈X
2≤l≤m:|ρl |=|ρ2 |
→ |ρ2 | as N → ∞. (103)
32
Relations (102) and (103) show that, in the case where condition A1 holds,
the “coupling” upper bounds for rate of convergence in individual ergodic re-
lations given in Theorem 6 are asymptotically equivalent with analogous up-
per bounds, which can be obtained with the use of eigenvalue decomposition
representation for transition probabilities. At the same time, computing of
coefficients of ergodicity ∆N (P0 ) does not require solving of the polynomial
equation, det(ρI − P0 ) = 0, that is required for finding eigenvalues.
7.4 Coupling for singularly perturbed Markov chains with damp-
ing component. In this subsection, we present coupling algorithms and get
the effective upper bound for the rate of convergence in ergodic theorems
for singularly perturbed Markov chains with damping component. Thus, we
assume that following weaken variant of condition B1 holds:
classes of states for the Markov chain X0,n .
(j)
Let us introduce the discrete distributions f¯p̄ = hfp̄ , j = 1, . . . , hi, where
(j) (j) (j) (j)
= hpk = pk /fp̄ , k ∈ X(j) i, for
P
fp̄ = k∈X(j) pk , , j = 1, . . . , h and p̄
(j)
j ∈ Hp̄ = {j : 1 ≤ j ≤ h, fp̄ > 0}.
We also use the above notations for the case, where distribution p̄ co-
incides with distributions d¯ = hdk , k ∈ Xi, π̄ε = hπε,k , k ∈ Xi, and π̄0,p̄ =
hπ0,p̄,k , k ∈ Xi.
Let ε ∈ (0, 1], and π̄ε = hπε,k , k ∈ Xi be the stationary distribution for
the Markov chain Xε,n .
The following representation takes place, for k ∈ X(j) , j = 1, . . . , h,
∞
X
l (j) (j)
πε,k = ε ¯ (l)(1 − ε) = f ¯ πε,k ,
p0,d,k (104)
d
l=0
where, for k ∈ X(j) , j = 1, . . . , h,

∞
X
(j)
πε,k =ε p0,d¯(j) ,k (l)(1 − ε)l . (105)
l=0
(j) (j)
It is readily seen that π̄ε = hπε,k , k ∈ Xi is, for every j = 1, . . . , h,
(j)
the stationary distribution for the Markov chain Xε,n , with the phase space
33
X(j) and the matrix of transition probabilities Pε,j = (1 − ε)P0,j + εDj ,
where P0,j = kp0,rk kr,k∈X(j) is, according to condition B4 , a stochastic matrix,
(j)
while Dj = kdrk kr,k∈X(j) is the stochastic damping matrix with elements
(j) (j) (j)
drk = dk = dk /fd¯ , k, r ∈ X(j) .
Note that relation (104) implies that, for j = 1, . . . , h,
(j)
X X (j) (j) (j)
fπ̄ε = πε,k = fd¯ πε,k = fd¯ . (106)
k∈X(j) k∈X(j)
Let us also introduce quantities, for j = 1, . . . , h, N ≥ 1,

(j)
X
QN (P0 ) = min p0,ki (N ) ∧ p0,ri (N ), (107)
k,r∈X(j)
i∈X(j)
and
(j) (j)
∆N (P0 ) = (1 − QN (P0 ))1/N . (108)
(j) (j)
It is useful to note that ∆N (P0 ) → 0 as N → ∞, and, thus, ∆N (P0 ) < 1,
(j)
for all N large enough, if condition A1 holds for the Markov chain X0,n .
Also the weaken variant of condition A1 , pointed out in Remark 4, holds
(j) (j)
for the Markov chain X0,n , if ∆N (P0 ) < 1, for some N ≥ 1.
(j) (j)
In this case, the Markov chain X0,n has the stationary distribution π̄0 =
(j)
hπ0,k , k ∈ X(j) i.
Let us now assume that the following condition holds, for some N ≥ 1:
(j)
D(N ) : (a) Condition B4 holds, (b) ∆N (P0 ) < 1, for j = 1, . . . , h.
According to Remark 4, the Markov chain X0,n has the stationary dis-
tribution π̄0,p̄ = hπ0,p̄,k , k ∈ X(j) i, for which the following relation holds, for
k ∈ X(j) , j = 1, . . . , h,
(j) (j)
π0,p̄,k = fp̄ π0,k . (109)
It is useful to note that transition probabilities p0,p̄,k (n) = 0, n ≥ 0 and
stationary probabilities π0,p̄,k = 0, for k ∈ X(j) , j ∈
/ Hp̄ .
(j)
Moreover, if k ∈ X , for some j = 1, . . . , h, then,
(j) (j)
p0,p̄,k (n) = fp̄ Pp̄(j) {X0,n = k}. (110)
(j) (j)
Below, we count ∆N (P0 )0 = 1, if ∆N (P0 ) = 0.
34
Theorem 7. Let condition D(N ) holds. Then, if p̄ ∈ Pm , and k ∈ X(j) ,
for some j = 1, . . . , h, the following propositions take place, for every ε ∈
(0, 1] and n ≥ 0:
(j) (j)
|pε,p̄,k (n) − πε,k | ≤ (fd¯ (1 − Q(π̄ε(j) , π̄0 ))
(j) (j) (j)
+ fp̄ (1 − Q(p̄(j) , π̄0 )))∆N (P0 )[n/N ]N
(j) (j) (j)
+ |fp̄ − fd¯ |π0,k (1 − ε)n . (111)
Proof. By using the renewal equation (14) and the renewal type type
relation (15) and taking into account stationarity of the Markov chain Xε,n ,
with the initial distribution π̄ε , condition B4 , and relations (104), (109) and
(110), we get the following relation, for k ∈ X(j) and n ≥ 0,
|pε,p̄,k (n) − πε,k | = |pε,p̄,k (n) − pε,π̄ε ,k (n)|

= |p0,p̄,k (n) − p0,π̄ε ,k (n)|(1 − ε)n
(j) (j) (j) (j)
= |fp̄ Pp̄(j) {X0,n = k} − fd¯ Pπ̄ε(j) {X0,n = k}|(1 − ε)n
(j) (j) (j)
≤ fp̄ |Pp̄(j) {X0,n = k} − π0,k |
(j) (j) (j)
+ fd¯ |Pπ̄ε(j) {X0,n = k} − π0,k |
(j) (j) (j)
+ |fp̄ − fd¯ |π0,k (1 − ε)n . (112)
(j)
Condition D(N ) let one apply inequality (102) to the Markov chain X0,n
and transforms relation (112) to the form of relation (111).
As in Subsection 7.3, by passing ε → 0 in the first inequality given
in relation (111) and taking into account Lemma 5 (which implies that
(j) (j)
Q(π̄ε , π̄0 ) → 1 as ε → 0), we get the following relation holding for any
p̄ ∈ Pm , k ∈ X(j) , j = 1, . . . , h, n ≥ 0,
|p0,p̄,k (n) − π0,d,k

¯ |
(j) (j) (j) (j) (j) (j)
≤ fp̄ (1 − Q(p̄(j) , π̄0 ))∆N (P0 )[n/N ]N + |fp̄ − fd¯ |π0,k . (113)
This relation let one extend the conclusion made in Remark 2.

(j) (j)
If fp̄ = fd¯ , then, for k ∈ X(j) , probabilities p0,p̄,k (n) → π0,d,k
¯ as n → ∞,
with the exponential rate.
(j) (j)
If fp̄ 6= fd¯ , then, for k ∈ X(j) (as follows from Lemma 5 and relations
(j) (j) (j)
(104) and (109)), probabilities p0,p̄,k (n) → π0,p̄,k = π0,d,k
¯ + (fp̄ − f ¯ )π0,k as
d
35
n → ∞, with the exponential rate. More precisely, relations (102), (109),
and (110) imply that the following relation holds, for k ∈ X(j) , n ≥ 0,
(j) (j) (j) (j)
|p0,p̄,k (n) − π0,p̄,k | = |fp̄ Pp̄(j) {X0,n = k} − fp̄ π0,k |
(j) (j) (j)
≤ fp̄ (1 − Q(p̄(j) , π̄0 ))∆N (P0 )[n/N ]N . (114)
8. Ergodic theorems for perturbed Markov chains with

damping component in the triangular array mode
In this section, we present ergodic theorems for Markov chains with damp-
ing component in the triangular array mode, where time n tends to infinity
and damping parameter ε tends to zero simultaneously. In this mode, the
asymptotic behaviour of transition probabilities
8.1 Asymptotic behaviour of transition probabilities in the tri-
angular array mode. In this mode, the asymptotic behaviour of transition
probabilities pε,p̄,k (n) is studied when time n → ∞ and the damping param-
eter ε → 0, simultaneously. One can assume that time n = nε depends on ε
in such way that nε → ∞ as ε → 0.
Asymptotic behaviour of transition probabilities pε,p̄,k (nε ) as ε → 0 should
be compared with repeated limits for pε,p̄,k (n) as n → ∞ and, then, ε → 0
and, vice versa, as ε → 0 and, then n → ∞.
Let as first consider the case, where condition A1 holds.
In this case, according to Lemma 2, transition probabilities pε,p̄,k (n) →
πε,k as n → ∞, for every ε ∈ (0, 1]. Also, according to Lemma 4, stationary
probabilities πε,k → π0,k as ε → 0, where π0,k are stationary probabilities for
the Markov chain X0,n .
As follows from relation (28), in this case, transition probabilities pε,p̄,k (n)
→ p0,p̄,k (n) as ε → 0, for any n ≥ 0. Also, according to relation (21),
transition probabilities p0,p̄,k (n) → π0,k as n → 0.
The coincidence, of the repeated limits for transition probabilities pε,p̄,k (n)
let one expect that, in this case, transition probabilities pε,p̄,k (nε ) should
converge to stationary probabilities π0,k as ε → 0, for an arbitrary nε → ∞
as ε → 0.
The situation is different, in the case, where condition B1 holds.
Again, Lemma 2 implies that transition probabilities pε,p̄,k (n) → πε,k
as n → ∞, for every ε ∈ (0, 1]. Also, according to Lemma 4, stationary
36
probabilities πε,k → π0,d,k ¯ as ε → 0, where π0,d,k
¯ are stationary probabilities
of the Markov chain X0,n , with the initial distribution d. ¯
Again, according to relation (28), transition probabilities pε,p̄,k (n) →
p0,p̄,k (n) as ε → 0, for any n ≥ 0. However, as Lemma 3 implies that, in
this case, transition probabilities p0,p̄,k (n) → π0,p̄,k as n → ∞.
Thus, the repeated limits for transition probabilities pε,p̄,k (n) coincides,
under additional assumption that the initial distribution p̄ = d. ¯ But, they
may not coincide if p̄ 6= d. ¯
The transition probabilities pε,p̄,k (n) satisfy the renewal type relation (15).
This relation shows that the initial state Xε,0 influences the behaviour of the
Markov chain Xε,n only up to the first damping regeneration time Tε,1 .
The random variables Tε,1 has the geometric distribution with parameter
d
ε. Its rate of growth is ε−1 as ε → 0. Moreover, random variables εTε.1 −→
ν(1) as ε → 0, where ν(1) is a random variable, which has exponential
distribution with parameter 1.
This hints one that it would be natural to study the asymptotic behaviour
of transition probabilities pε,p̄,k (nε ) for nε → ∞ as ε → 0 such that εnε →
t ∈ [0, ∞] as ε → 0.
Moreover, it can be expected that in two extremal cases, where t = ∞
or t = 0, the transition probabilities pε,p̄,k (nε ) converge as ε → 0 to the
corresponding repeated limits, respectively, π0,d,k ¯ or π0,p̄,k .
The question arises about the asymptotic behaviour of transition proba-
bilities pε,p̄,k (nε ) in the intermediate case, where the above limit t ∈ (0, ∞).
In conclusion of this informal discussion, we would like to mention works
[12, 13, 23, 24, 37, 39, 40, 45, 46], which contain results related to ergodic the-
orems in triangular array mode and to so-called quasi-stationary ergodic the-
orems for perturbed regenerative processes, Markov chains and semi-Markov
processes.
8.2 Ergodic theorems for regularly perturbed Markov chains
with damping component in the triangular array mode. The follow-
ing theorem takes place.
Theorem 8. Let condition C(N ) holds for some N ≥ 1. Then, for any
nε → ∞ as ε → 0 and p̄ ∈ Pm , k ∈ X,
pε,p̄,k (nε ) → π0,k as ε → 0. (115)
Proof. Using the renewal type relation (15) and inequality (102), we get
37
the following relation holding for any nε → ∞ as ε → 0 and k ∈ X,
|pε,p̄,k (nε ) − π0,k | = |pε,p̄,k (nε ) − π0,k (1 − ε)nε − π0,k (1 − (1 − ε)nε )|

= |(p0,p̄,k (nε ) − π0,k )(1 − ε)nε
X nε
l−1
+ ¯ (nε − l) − π0,k )ε(1 − ε)
(p0,d,k |
l=1
≤ (1 − Q(p̄, π̄0 ))∆N (P0 )[nε /N ]N

Xnε
¯
+ (1 − Q(d, π̄0 ))ε ∆N (P0 )[(nε −l)/N ]N
l=1
≤ (1 − Q(p̄, π̄0 ))∆N (P0 )[nε /N ]N

+ (1 − Q(d,¯ π̄0 ))εN (1 − ∆N (P0 )N )−1
→ 0 as ε → 0. (116)

Remark 6. Relation (116) gives, in fact, explicit upper bounds for the
rate of convergence in ergodic relation given in Theorem 8.
8.3 Ergodic theorems for singularly perturbed Markov chains
with damping component in the triangular array mode. As follows
from remarks made in Subsection 8.1, the ergodic relations take in this case
much more complex forms.
Theorem 9. Let condition D(N ) holds for some N ≥ 1. Then the fol-
lowing propositions take place:
(i) If nε → ∞ and εnε → ∞ as ε → 0, then, for p̄ ∈ Pm , k ∈ Xj , j =
1, . . . , h,
pε,p̄,k (nε ) → π0,p̄,k (∞) = π0,d,k

¯ as ε → 0. (117)
(ii) If nε → ∞ and εnε → t ∈ (0, ∞) as ε → 0, then, for p̄ ∈ Pm , k ∈

Xj , j = 1, . . . , h,
pε,p̄,k (nε ) → π0,p̄,k (t) = π0,p̄,k e−t + π0,d,k −t

¯ (1 − e ) as ε → 0. (118)
(iii) If nε → ∞ and εnε → 0 as ε → 0, then, for p̄ ∈ Pm , k ∈ Xj , j =

1, . . . , h,
pε,p̄,k (nε ) → π0,p̄,k (0) = π0,p̄,k as ε → 0. (119)
38
Proof. The renewal type relation (15) written for n = nε takes the following
form, for p̄ ∈ Pm , k ∈ X(j) , k = 1, . . . , h,
Xnε
nε l−1
pε,p̄,k (nε ) = p0,p̄,k (nε )(1 − ε) + ¯ (nε − l)ε(1 − ε)
p0,d,k . (120)
l=1
By applying inequality (114) to the transition probabilities appearing in

the above renewal type relation, we get the following inequality,
|pε,p̄,k (nε ) − π0,p̄,k (1 − ε)nε − π0,d,k nε
¯ (1 − (1 − ε) )|
= |(p0,p̄,k (nε ) − π0,p̄,k )(1 − ε)nε

nε
X
l−1
+ ¯ (nε − l) − π0,d,k
(p0,d,k ¯ )ε(1 − ε) |
l=1
(j) (j) (j)
≤ fp̄ (1 − Q(p̄(j) , π̄0 ))∆N (P0 )[nε /N ]N +
nε
X
(j) (j) (j)
+ fd¯ (1 − Q(d¯(j) , π̄0 ))ε ∆N (P0 )[(nε −l)/N ]N
l=1
(j) (j) (j)
≤ fp̄ (1 − Q(p̄ , π̄0 ))∆N (P0 )[nε /N ]N
(j)
(j) (j) (j)

+ fd¯ (1 − Q(d¯(j) , π̄0 ))εN (1 − ∆N (P0 )N )−1 . (121)
Let us introduce function Rε (t) = |(1 − ε)nε − e−t |, t ∈ [0, ∞].
If nε → ∞ and εnε → t ∈ [0, ∞] as ε → 0, then,
Rε (t) → 0 as ε → 0. (122)
The following inequality takes place,
|π0,p̄,k e−t + π0,d,k −t
¯ (1 − e ) − π0,p̄,k (1 − ε)
nε
− π0,d,k nε
¯ (1 − (1 − ε) )|
≤ |π0,p̄,k − π0,d,k
¯ |Rε (t)
(j) (j) (j)
= |fp̄ − fd¯ |π0,k Rε (t). (123)
Relations (121) and (123) obviously imply that the following relation
holds, for k ∈ X(j) , k = 1, . . . , h, if nε → ∞ and εnε → t ∈ [0, ∞] as ε → 0,
|pε,p̄,k (nε ) − π0,p̄,k (t)|

(j) (j) (j)
≤ fp̄ (1 − Q(p̄(j) , π̄0 ))∆N (P0 )[nε /N ]N
(j) (j) (j)
+ f ¯ (1 − Q(d¯(j) , π̄ ))εN (1 − ∆ (P0 )N )−1
d 0 N
(j) (j) (j)
+ |fp̄ − fd¯ |π0,k Rε (t) → 0 as ε → 0. (124)
39
This relation proves the theorem.
Remark 7. Inequality (124) gives, in fact, explicit upper bounds for the
rate of convergence in ergodic relation given in Theorem 9. Of course, it
is possible to get some simple explicit upper bounds for Rε (t) in terms of
quantities εnε and t.
9. Examples and results of numerical experiments
In this section we present examples illustrating the theoretical results of

the present paper using some related numerical experiments. The first ex-
ample demonstrates results associated to regularly perturbed Markov chains.
For instance, asymptotic representation of stationary distribution, estima-
tion of coefficient of ergodicity and associated upper bounds for the rate of
convergence for stationary distribution. The second example focuses on the
advantage of higher order terms of asymptotic expansion in regularly per-
turbed Markov chains. Lastly, we present information network that capture
results associated with singularly perturbed Markov chains with damping
component in the triangular array mode.
9.1 A simple information network with a complete link graph.
In this subsection we consider the Markov chain associated with a simple
information network with five nodes and a complete link graph. We also
restrict consideration by the model with the simplest damping matrix with
all equal elements. The matrices P0 and D have the following forms,
1 1 1 1 1 1 1 1 1 1
5 5 5 5 5 5 5 5 5 5

1 1 1 1 1 1 1 1 1
4 0 4 4 4

5 5 5 5 5
P0 = 0 13 0 13 13 , D = 51 15 51 15 15 . (125)

1 1 1
1 1 1 1 1
0 0 3
3 3 5 5 5 5 5
0 1 1 1 0 1 1 1 1 1
3 3 3 5 5 5 5 5
The corresponding link graph is presented in Figure 1.
40
1
3 5
Figure 1: A links graph of simple information network
In this case, condition A1 holds.

The eigenvalues of matrix P0 (computed by solving equation, det(ρI − P0 )
= 0), are,
√ √
1 1 34 1 34
ρ1 = 1, ρ2 = ρ3 = − , ρ4 = − − , ρ5 = − + . (126)
3 15 30 15 30
The stationary projector matrix Π = kπ0,ij k, with elements π0,ij =
π0,j , i, j = 1, . . . , m (computed by solving the system of linear equations
(22)), and matrices Π̄k = kπ̄ij [k]k, k = 2, 3, 4 (computed with the use of the
algorithm described in [19]), take the following forms,
5 8 5 5 5

0 0 0 0 0
66 33 22 22 22
5 8 5 5 5
0 0 0 0 0

66 33 22 22 22
2
− 31 − 13
5 8 5 5 5

Π= , Π̄2 = 0 0 , (127)
66 33 22 22 22 3
5 8 5 5 5
0 0 − 13 2
− 13

66 33 22 22 22 3
5 8 5 5 5
− 13 − 31 2

0 0
66 33 22 22 22 3
and

−a1 −b1 c1 c1 c1

e1
f1 −g1 −g1 −g1

a2 b2 −c2 −c2 −c2 e2 −f2 g2 g2 g2

Π̄3 =
−a3 −b3 c3 c3 c3 , Π̄4 = −e3
−f3 g3 g3 g3 , (128)

−a3 −b3 c3 c3 c3 −e3 −f3 g3 g3 g3

−a3 −b3 c3 c3 c3 −e3 −f3 g3 g3 g3
41
where
√ √ √
46 34
a1 = 561√
61
− 132 , a2 = − 335 34
4488
− 5
132
, a3 = − 2056134 + 5
132
,
√ √
29 34 4 95 34 37 34
b1 = − 1122 + 33 , b2 = 1122
+ 25
66
, b3 = 1122
4
+ 33 ,
√ √ √
7 34 5 5 34 5 34 7
c1 = 374
− 44 , c2 = 1496
+ 44 , c3 = − 1122 + 132 ,
√
46 34 61
√
67 34 1
√
20 34 5
(129)
e1 = 561√
+ 132 , e2 = 4488
− 132 , e3 = 561√
+ 132 ,
√
f1 = − 29112234 − 33 4
, f2 = 95 34
1122
− 25
66
, f3 = − 37112234 + 33 4
,
√ √ √
7 34 5 5 34 5 34 7
g1 = 374
+ 44 , g2 = 1496
− 44 , g3 = 1122
+ 132 .
Respectively, the matrix eigenvalues representation based on relation (46)
takes the following form, for n ≥ 1,
1 1 1√ n
Pn0 = Π + (− )n Π̄2 + (− − 34) Π̄3
3 15 30
1 1√ n
+ (− + 34) Π̄4 . (130)
15 30
Taking into account the specific forms of the damping matrix D and
matrices Π̄2 = 2Π2 , we get that, in this case, coefficients π0,d,j ¯ [2] = 0, j =
1, . . . , m, and, thus, the coefficients of the eigenvalues representation given
in relation (47) take the following forms, for n ≥ 1,
 √ √ n
5 223 34 41 1 34


 66
+ − 22440
+ 660
− 15
− 30

√ √ n


223 34 41 1 34




 + − 22440
− 660
− 15
+ 30
, for j = 1,

√ √ n


8
− 13561034 − 330 7 1
− 15 − 3034


 33




 √ √ n
13 34
+ 5610 + 330 − 15 + 3034 ,
7 1
for j = 2,





 5 + 211√34 − 37 √

 n
1 34

22 36720 1080
− 15
− 30
p0,d,j
¯ (n) = (131)
 √ √ n
19 34 3 1 34
+ 7480 + 220 − 15 + 30



 , for j = 3,
√ √ n


5
+ 211 34 37
− 1080 1
− 15 − 3034


 22
 36720



 √ √ n
19 34
+ 7480 + 220 − 15 + 3034 ,
3 1
for j = 4,





 √ √ n
5
+ 211 34 37
− 1080 1
− 15 − 3034


22 36720





 √ √ n
 + 19 34 + 3

− 1
+ 34
, for j = 5.
7480 220 15 30
42
Finally, the coefficients in the asymptotic expansion (50) given by relation
(49) take the following form, for all j ∈ X and n ≥ 1,
307


 2178
, for n = 1,
√ 1


 √ n−1
307 853 34
π̃0,d,1
¯ [n] = 4356
− 74052
34 33
+ 33 (132)
√


 √ n−1
+ 4356 + 74052 34 33 − 3334
307 853 1

, for n > 1.


50


 − 1089 , for n = 1,
√ 1


 √ n−1
25 107 34
π̃0,d,2
¯ [n] =
− 1089
+ 37026
34 33
+ 33 (133)
√


 √ n−1
 − 25 + 107 34 1 − 34

, for n > 1.
1089 37026 33 33
π̃0,d,3
¯ [n] = π̃0,d,4
¯ [n] = π̃0,d,5
¯ [n]
 23

 − 726 , for n = 1,
√ 1


 √ n−1
=
23
− 1452 71
+ 24684 34 33 + 3334 (134)
√ 1


 √ n−1
23
− 1452 71
+ 24684 34 33 − 3334 , for n > 1.


For example, the second order expansions (50), for stationary probabili-
ties πε,j , j = 1, . . . , 5, take the forms given below in relation (135). The terms
of the expansions, except the stationary probabilities (first terms) which are
exact values, are computed correct to 5 decimal digits.
 5

 66
+ 0.14096ε − 0.01946ε2 + O(ε3 ) for j = 1,

8
− 0.04591ε + 0.00456ε2 + O(ε3 ) for j = 2,


 33


5
πε,j ≈ 22
− 0.03168ε + 0.00497ε2 + O(ε3 ) for j = 3, (135)

5
− 0.03168ε + 0.00497ε2 + O(ε3 ) for j = 4,



 22


5
− 0.03168ε + 0.00497ε2 + O(ε3 ) for j = 5.

22
It can be observed from relation (135) that contributions of second terms

in the above expansions are insignificant and, therefore, can be neglected
43
even for moderate value of ε = 0.2. For example, the first term 0.14096ε
in the above asymptotic expansion for the stationary probability π0,d,1 ¯ =
5
66
≈ 0.07576 takes value 0.02820 that is about 37.22% of the correspond-
ing stationary probability. While, the second term 0.01946ε2 in the above
asymptotic expansion takes value 0.00078 that is only about 2.76% of the
first term and about 1.03% of the corresponding
P stationary probability.
Let us also mention that the equalities j∈X π̃0,d,j ¯ [n] = 0, n ≥ 1 hold for
coefficients given in relations (132)-(134) as well as, approximately up to the
corresponding rounding corrections, for coefficients given in relation (135).
Relation (46) imply that inequality (37) holds with the quantities,
m̄
X ρ̄l
λ = |ρ2 | and C = max |π̄0,rk [l]| | |.
r,k∈X
l=2
ρ̄2
The inequality (40) takes the following form, for ε ∈ (0, 1] and j =
1, . . . , 5,
67 √

1 49
|πε,j − π0,j | ≤ ε | − π0,j | + 34 + , (136)
5 4488 132
5 8 5
where the stationary probabilities, π0,1 = 66 , π0,2 = 33 , π0,r = 22 , r = 3, 4, 5.
Table 1 give values πε,j , π0,j , and |πε,j − π0,j | computed with the use of
rounded solutions of the system of linear equations (20) and (22) and the
upper bounds given by inequality (136), for the moderate value ε = 0.15,
j∈X πε,j π0,j |πε,j − π0,j | Upper bound

1 0.09646 0.07576 0.02071 0.08738
2 0.23564 0.24242 0.00678 0.07510
3,4,5 0.22263 0.22727 0.00464 0.07283
Table 1: Upper bounds for the rate of convergence (ε = 0.15).
Figure 2 displays the asymptotical behaviour of the ergodicity coefficient

∆N (P0 ) (computed with the use of relation (101), as N → ∞. In this case,
coefficients of ergodicity ∆N (P0 ) → |ρ2 | = 31 as N → ∞ consistently with
relation (103).
44
0.5
0.48 N
(P 0 )
1,2
0.46
0.44
0.42
0.4
0.38
0.36
0.34
0.32
0 5 10 15 20 25 30 35 40 45 50
Figure 2: Ergodicity coefficient.
9.2 High order terms in the expansions for stationary probabil-

ities of perturbed Markov chain. Let us now present an the example,
where the second term in the corresponding asymptotic expansion for sta-
tionary probability can not be ignored.
Here, we consider a regularly perturbed Markov chain with matrices P0
and D given in relation (137) and the link graph shown in Figure 3.
3 4
Figure 3: A simple information network
45
1 1 1 1

0 1 0 0
4 4 4 4

1 1 1 1 1
0 13 13

3 4 4 4 4
P0 = , D = . (137)

0 1 0 1 1 1 1 1
2 2 4 4 4 4

0 1 1 0
1 1 1 1

2 2
4 4 4 4
In this case, condition A1 also holds.

The eigenvalues ρk = ρ1,k , k = 1, . . . , 4 of the matrix P0 are,
√ √
1 33 1 1 33
ρ1 = 1, ρ2 = − − , ρ3 = − , ρ4 = − + .
4 12 2 4 12
Computations, analogous to performed above in the first example, give
the following values for the coefficients of the eigenvalues representation given
in relation (56), for n ≥ 1,
 √ √ n
1 1 33 1 33


 8
+ 16
+ 528
− 4
− 12

√ √

 + 1 − 33 − 1 + 33 n ,




 16 528 4 12
for j = 1,


 √ √ n
 83 − 16 1
+ 317633 − 41 − 1233


p0,d,j
¯ (n) = √ √ n (138)
1 3 33 1 33
+ − 16 + 176 − 4 + 12 , for j = 2,





√ √ n


1 33 1 33
− −




 4
+ 132 4 12


 √ √ n
 − 33 − 1 + 33 ,

for j = 3, 4.
132 4 12
Finally, the coefficients in the asymptotic expansion (59) given by relation

(58) take the following form, for j ∈ X,
 7
 64
, for n = 1,

 √ n
(−1)2n+1


 3+ √33
16

 15+ 33
π̃0,d,1
¯ [n] = √
11+5 33
√ n
−3+ √33
(139)


 − 176 −15+ 33

√ √
 +(−1)2n 5 33 3+ √33 n , for n > 1.



176 15+ 33
46
 3
 − 64 , for n = 1,

 √ √ n
1+2n 33+ 33 3+ √33

π̃0,d,2
¯ [n] =
(−1) 176 15+ 33 (140)

 √ √ n
 + −33+ 33
 −3+ √33
, for n > 1.
176 −15+ 33
π̃0,d,3
¯ [n] = π̃0,d,4
¯ [n]
 1
 − 32 , for n = 1,
√ √ n


33
(−1)n −3− √ 33

√
= 11(3+ 33) 15+ 33 (141)

 √ √ n
 + 33√ n −3+√ 33
(−1) , for n > 1.

11(−3+ 33) 15− 33
Consequently, the second order asymptotic expansions (59), for stationary

probabilities πε,j , j = 1, . . . , 4, take the forms given below in relation (143).
The terms of the expansions, except the stationary probabilities (first terms)
which are exact values, are computed correct to 5 decimal digits.
1 7 1 2
+ O(ε3 ),


 8
+ 64
ε − 512
ε for j = 1,
3 3 27 2
+ O(ε3 ),


8
− 64
ε − 512
ε for j = 2,
πε,j = 1 1 7 2 (142)

 4
− 32
ε + 256
ε + O(ε3 ), for j = 3,

1 1 7 2
− ε + ε + O(ε3 ), for j = 4.

4 32 256
1
+ 0.10937ε − 0.00195ε2 + O(ε3 ),


 8
for j = 1,
3
− 0.04687ε − 0.05273ε2 + O(ε3 ),


8
for j = 2,
≈ 1 2 3
(143)

 − 0.03125ε + 0.02734ε + O(ε ),
4
for j = 3,

1
− 0.03125ε + 0.02734ε2 + O(ε3 ), for j = 4.

4
P
Let us mention again that equalities j∈X π̃0,d,j ¯ [n] = 0, n ≥ 1 hold for
coefficients given in relations (139)-(141) and (142) as well as, approximately
up to the corresponding rounding corrections, for coefficients given in relation
(143).
We see that in the third (j = 3) and fourth (j = 4) expansions in rela-
tion (143) for ε = 0.2, the term 321 ε is about 2.5% of the limiting stationary
7 2
probability 0.25, while the term 256 ε is about 0.4% of 0.25, i.e. it improves
the accuracy of approximation for the stationary probability for about 16%.
47
9.3 Singularly perturbed Markov chains with damping compo-
nent in the triangular array mode. In this example we consider an er-
godic singularly perturbed Markov chains with damping component as stated
in Theorem 9. We use a two-disjoint information networks given in Figure
4, whose matrices P0 and D are given by (144).
1 5
2 6
3 4 7 8
Figure 4: A simple two disjoint information networks
1 1 1 1 1 1 1 1

0 1 0 0 0 0 0 0

8 8 8 8 8 8 8 8

1 1 1

3 0 3 3 0 0 0 0

1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8

1 1
0 0 0 0 0 0 1 1 1 1 1 1 1 1

2 2

8 8 8 8 8 8 8 8

1 1
0 2 2 0 0 0 0 0 1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8

P0 = , D = (144)

0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1
8 8 8 8 8 8 8 8

1 1

0 0 0 0 0 0 2 2

1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8

1 1 1
0 0 0 0 0 1 1 1 1 1 1 1 1

3 3 3
8 8 8 8 8 8 8 8

1 1 1

0 0 0 0 3 3 3 0 1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8

Here we define a phase space X corresponding to P0 as X = X(1) ∪ X(2) ,

where X(1) = {1, 2, 3, 4} and X(2) = {5, 6, 7, 8}. The corresponding matrices
of transition probabilities for the two ergodic classes are, respectively, P0,1
and P0,2 , where

0 1 0 0 0 1 0 0

1 0 1 1 0 0 1 1
P0,1 = 3 1 3 31 , P0,2 = 1 1 2 21 .

0 2 0 2 3 3 0 3

0 1 1 0 1 1 1 0
2 2 3 3 3
In this case, condition B1 holds, with h = 2.
48
We are going to get the second order asymptotic expansion for stationary
probabilities πε,k , k ∈ X given by relation (59). In fact, we can use Theorem 4
(1)
and to give the corresponding expansions for stationary probabilities πε,k , k ∈
(2)
X(1) and πε,k , k ∈ X(2) . Then, these expansions can be transformed in the
(g) (g)
corresponding expansions for πε,k , k ∈ X, using relations πε,k = fd¯ πε,k , k ∈
(g) (g)
P , g = 1, 2 and
X
1
taking into account that, in this case, probabilities fd¯ =
k∈X(g) dk = 2 , g = 1, 2.
One can easily notice that matrix P0,1 coincides with matrix P0 given in
relation (137). Thus, the second order asymptotic expansions for stationary
(1)
probabilities πε,k , k ∈ X(1) take forms given in relation (143), and, thus,
the corresponding asymptotic expansions for stationary probabilities πε,k =
1 (1)
π , k ∈ X(1) take the following forms,
2 ε,k

1 7 1


 16
+ 128 ε − 1024 ε2 + O(ε3 ), for k = 1,

 3 − 3 ε − 27 ε2 + O(ε3 ),

for k = 2,
πε,k = 16 1
128
1
1024
7 2
(145)
3


 8
− 64
ε + 512
ε + O(ε ), for k = 3,

 1 − 1 ε + 7 ε2 + O(ε3 ),

for k = 4.
8 64 512
(2)
Similarly, the asymptotic expansion πε,k for phase space X(2) can be com-
puted. The eigenvalues corresponding to P0,2 are,
√ √
1 2 1 2 1
ρ2,1 = 1, ρ2,2 = − − i, ρ2,3 = − + i, ρ2,4 = − ,
3 3 3 3 3
2
where i = −1. Hence, from relation (56), we obtain eigenvalues decomposi-
tion of P0,2 , for k ∈ X(2) , n ≥ 1, as
 √ √ n



1
6
+ 16(1+ 2i) − 3 − 32 i
2i
√ 1


 √ √ n
(−1+2 2i)
+ 24(−2+ 2i) − 3 + 32 i , for k = 5,
1



 √



 √ n
 1− √1 − 3 − 32 i
1

3
 8+ 128i
p0,d,k
¯ (n) = √ √ n (146)
−4− √ 2i 1 2
− − + i , for k = 6,



 24(−2+ 2i) 3 3

√ √ n


1 2i 1 2
− − −




 4 32 3 3
i


 √ √ n
 + 2i − 1 + 2 i ,

for k = 7, 8.
32 3 3
49
(2) (2)
¯ [n], k ∈ X
Next, the coefficients π̃0,d,k (computed from relation (58)), for
n ≥ 1, take the form,

5

 72
, for n = 1,
√ √

 n−1
2i
+ 62i
 5 1
(2)
π̃0,d,5 [n] = 144
+ 144 3 (147)
¯
√ √

 n−1
 + 5 − 2i 1
− 62i


144 144 3
, for n > 1.

1

 − 36 , for n = 1,
√ √

 n−1
1
+ 51442i 1
+ 62i

(2)
π̃0,d,6 [n] = − 72 3 (148)
¯
√ √ n−1


 − 1 + 5 2i 1 2i


72 144 3
− 6
, for n > 1.
(2) (2)
π̃0,d,7 ¯ [n]
¯ [n] = π̃0,d,8

1

 − 48 , for n = 1,
√ √ n−1

 1

= − 96 − 482i 1
3
+ 62i (149)
√ √ n−1


 + − 1 + 2i 1
− 62i


96 48 3
, for n > 1.
Note that, according to remarks made in Subsection 6.1, coefficients

(2)
¯ [n]
π̃0,d,k are real numbers. They are given in relations (147)-(149) in the
compact form, which can create a false impression that these coefficients
may be complex numbers. However, one can see that the use Newton bino-
mial formula and following multiplication in the corresponding expressions
yields cancelation of all complex terms.
(2)
The asymptotic expansions for πε,k = 21 πε,k , k ∈ X(2) take the following
forms,  1 5 1 2

 12
+ 144 ε + 108 ε + O(ε3 ), for k = 5,

 1 − 1 ε − 7 ε2 + O(ε3 ),

for k = 6,
6 72 432
πε,k = 1 1 1 2 3
(150)


 8
− 96
ε + 288
ε + O(ε ), for k = 7,

 1 1 1 2
8
− 96 ε + 288 ε + O(ε3 ), for k = 8.
Hence, by combining relations (145) and (150), we obtain the asymptotic
50
expansions for stationary probabilities πε,k , k ∈ X = X(1) ∪ X(2) ,
 1 7 1

 16
+ 128 ε − 1024 ε2 + O(ε3 ), for k = 1,

3 3 27 2 3
 16 − 128 ε − 1024 ε + O(ε ), for k = 2,




1 1 7
− 64 ε + 512 ε2 + O(ε3 ),




 8
for k = 3,

1 1 7
 8 − 64 ε + 512 ε2 + O(ε3 ),

 for k = 4.
πε,k = 1 5 1 2 (151)

 12
+ 144 ε + 108 ε + O(ε3 ), for k = 5,

1 1 7 2
ε + O(ε3 ),




 6
− 72 ε − 432 for k = 6,

1 1 1 2
− 96 ε + 288 ε + O(ε3 ), for k = 7,


8



 1 − 1 ε + 1 ε2 + O(ε3 ),


8 96 288
for k = 8.
P
Let us mention ones more time that equalities k∈X π̃0,d,k ¯ [n] = 0, n ≥ 1
hold for coefficients given in relations (147)-(149) and (151).
Expansions (151) let us illustrate the results presented in Theorem 9. The
most interesting in this theorem is the asymptotic relation (118).
In order to illustrate this relation, we choose the initial distribution p̄ =
h1, 0, 0, 0, 0, 0, 0, 0i, which is concentrated in one ergodic class X(1) . In this
(1) (2) (1) (2)
case, probabilities fp̄ = 1, fp̄ = 0. Note that probabilities fd¯ = fd¯ = 12
for the initial distribution p̄ = d. ¯ Probabilities π0,p̄,k and π0,d,k
¯ are computed
using relation (26). The asymptotic relation (118) takes, for k = 1, the form,
pε,p̄,1 (nε ) → π0,p̄,1 (t) for nε → ∞, εnε → t and ε → 0. Further, we choose
ε = 0.1. According to the asymptotic relation (118), the values pε,p̄,1 (nε ),
for nε such that εnε ≈ t can be expected to take values close to π0,p̄,1 (t), for
1 ≤ t ≤ 3. This, indeed, can be seen in Figure 5.
In addition to that result shows that the relative absolute errors, |π0,p̄,1 (t)−
¯ | decreases dramatically from about 37% to 4% as εnε increases from 1
π0,d,1
to 3 respectively.
51
0.13
0.12
p
Stationary probability
0.11 d
(t)
pp (n )
0.1
0.09
0.08
0.07
0.06
0.05
1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3
Figure 5: An illustration of Theorem 8 (ii), where πp , pp (nε ), π(t) and πd

represent π0,p̄,1 , pε,p̄,1 (nε ), π0,p̄,1 (t) and pε,d,1
¯ respectively.
9.4 Concluding remarks and comments. One of the main reasons

for approximation of the Markov chain X0,n , with the matrix of transition
probabilities P0 , by perturbed (regularised) Markov chains with damping
component Xε,n , with the matrix of transition probabilities Pε = (1 − ε)P0 +
εD, is to use it for approximation of the stationary distribution π̄0 = hπ0,j , j ∈
Xi of the Markov chain X0,n by the stationary distribution π̄ε = hπε,j , j ∈ Xi
of the Markov chain Xε,n .
Since the corresponding phase space X = {1, . . . , m} can be large, the
power method can be used for approximative computing of stationary dis-
tribution π̄P ε , where its components πε,j are approximated by probabilities
pε,p̄,j (n) = i∈X pi pε,ij (n), where pε,ij (n) are elements of the matrix Pnε and
p̄ = hpj , j ∈ Xi is some initial distribution.
The results given in Theorems 1 – 9 show that the situation significantly
differs for two models, (a) where the phase space X is one class of commu-
nicative states for the Markov chain X0,n , i.e., this Markov chain is ergodic,
and, (b) where the phase space X splits in several closed classes of commu-
nicative states for the Markov chain X0,n , and, thus, this Markov chain is
52
not ergodic.
Rates of convergence of stationary probabilities πε,j to π0,j as ε → 0 and
probabilities pε,p̄,j (n) to stationary probabilities π0,p̄,j as n → ∞ play the key
role in the above method.
We give explicit upper bounds for rates of convergence of stationary prob-
abilities πε,j to π0,j and asymptotic expansions for πε,j , with respect to damp-
ing parameter ε, in Theorems 1 – 4. We also give explicit upper bounds for
rates of convergence of probabilities pε,p̄,j (n) to stationary probabilities πε,p̄,j ,
in Theorems 5 – 7.
These results let one construct the two-stage effective algorithms for ap-
proximating the stationary distribution π̄0 in the case, where the phase space
X is one class of communicative states for the Markov chain X0,n , and, thus,
this Markov chain is ergodic.
At the first stage, one approximates the stationary probabilities πε,j
by probabilities pε,p̄,j (n). The rate of this approximation has the order
O(∆N (P0 )n (1 − ε)n ). The effectiveness of this approximation declines for
small values of damping parameter ε and values of ergodicity coefficient
∆N (P0 ) closed to 1 that is typical for models with the phase space X nearly
decomposed in several closed classes of states.
At the second stage, one approximate stationary probabilities π0,j by sta-
tionary probabilities πε,j . The rate of approximation has the order O(ε),
which also, can be improved by using the corresponding asymptotic expan-
sions.
Here, some dual effect takes place. At the second stage it would be better
to use small values of regularisation parameter ε, while at the first stage using
small values of ε are not desirable.
Theorem 8 let one also to use the one-step variant of the algorithm de-
scribed above and approximate the stationary probabilities π0,j by probabil-
ities pε,p̄,j (nε ), with an arbitrary positive integers nε → ∞ as ε → 0. More-
over, the explicit upper bounds for |pε,p̄,j (nε ) − π0,j | pointed out in Remark
6 let one balance the choice of ε and nε .
The case, where the phase space X splits in several closed classes of com-
municative states for the Markov chain X0,n , and, thus, this Markov chain is
not ergodic, is more complex.
As a matter of fact, in this case, (c) stationary probabilities π0,p̄,k for
the Markov chain X0,n depend on the initial distribution p̄, (d) the station-
ary probabilities πε,k for the Markov chain Xε,n converge to the stationary
probabilities π0,d,k ¯ as ε → 0.
53
If the initial distribution p̄ = d¯ then the two-stage algorithm as well as
its one-stage variant described above can be applied.
However, if p̄ 6= d, ¯ one should be more careful, since in this case it may
be that the stationary probability π0,d,k ¯ 6= π0,p̄,k and, thus, the two-stage
algorithm described above does not work.
In this case, Theorem 9 answers the question about applicability quanti-
ties pε,p̄,j (nε ) as approximations for stationary probabilities for the Markov
chain X0,n . In fact, these probabilities converge to some mixture of station-
−t −t
ary probabilities π0,p̄,k and π0,d,k ¯ (1 − e ),
¯ , namely, π0,p̄,k (t) = π0,p̄,k e + π0,d,k
as nε → ∞ in such way that εnε → t ∈ [0, ∞] as ε → 0. Moreover, the
explicit upper bounds for |pε,p̄,k (nε ) − π0,p̄,k (t)| pointed out in Remark 7 let
one balance the choice of ε and nε and, in some sense, predict the value of
limit π0,p̄,k (t) depending on the value of quantity εnε .
The computational examples presented in Section 9 illustrate in which
way results given in Theorems 1 - 9 can be used in experimental studies of
Markov chains with damping components associated with information net-
works, in particular, in studies of PageRank algorithms.
In conclusion, we would like to note that Theorems 1 – 9 present results
of perturbation analysis for Markov chains with damping component for the
basic cases, where the phase space of the unperturbed Markov chain X0,n
either is one aperiodic class of communicative states or split in several closed
aperiodic classes of communicative states. Despite some technical complica-
tions, analogous results can be also obtained for the cases, where the phase
space of the unperturbed Markov chain X0,n either is one periodic class of
communicative states or split in several closed periodic classes of communica-
tive states plus possibly a class of transient states. We are going to present
such results in future publications as well as results of the corresponding ex-
perimental studies.
Acknowledgements
This research was supported by the Swedish International Development

Cooperation Agency (Sida), International Science Programme (ISP) in Math-
ematical Sciences (IPMS) and Sida Bilateral Research Programmes for re-
search and education capacity development in Mathematics in Uganda and
Tanzania. The authors are also grateful to the research environment Mathe-
matics and Applied Mathematics (MAM), Division of Applied Mathematics,
Mälardalen University for providing an excellent and inspiring environment
54
for research education and research.
References
[1] Abola, B., Biganda, P.S., Engström, C., Mango, J.M., Kakuba, G., Silve-
strov, S. (2018). PageRank in evolving tree graphs. In: Silvestrov, S., Ranc̆ić,
M., Malyarenko, A. (Eds.) Stochastic Processes and Applications, Chapter
16. Springer Proceedings in Mathematics & Statistics, 271, Springer, Cham,
375–390.
[2] Abola, B., Biganda, P.S., Engström, C., John Magero Mango, Kakuba, G.,
Silvestrov, S. (2018). Updating of PageRank in evolving tree graphs. In: Ski-
adas, C.H. (Ed.) Proceedings of the 5th Stochastic Modeling Techniques and
Data Analysis International Conference with Demographics Workshop. Cha-
nia, Crete, Greece, 2018. ISAST: International Society for the Advancement
of Science and Technology, 15–26.
[3] Andersson, F.K., Silvestrov, S. D. (2008). The mathematics of internet search

engines. Acta Applic. Math., 104(2), 211–242.
[4] Avrachenkov, K.E., Filar, J.A., Howlett, P.G. (2013). Analytic Perturbation
Theory and Its Applications. SIAM, Philadelphia, xii+372 pp.
[5] Avrachenkov, K., Piunovskiy, A., Zhang, Yi (2018). Hitting times in Markov
chains with restart and their application to network centrality. Methodol.
Comput. Appl. Probab., 20, 4, 1173–1188.
[6] Battiston, S., Puliga, M., Kaushik, R., Tasca, P., Caldarelli, G. (2012). Deb-
trank: Too central to fail? financial networks, the fed and systemic risk.
Scientific Reports, 2, Art. num. 541.
[7] Biganda, P.S., Abola, B., Engström, C., Silvestrov, S. (2017). PageRank,
connecting a line of nodes with multiple complete graphs. In: Skiadas, C.H.
(Ed.) Proceedings of the 17th Applied Stochastic Models and Data Analy-
sis International Conference with the 6th Demographics Workshop. London,
UK, 2017. ISAST: International Society for the Advancement of Science and
Technology, 113–126.
[8] Biganda, P.S., Abola, B., Engström, C., Mango Magero, J., Kakuba, G.,
Silvestrov, S. (2018). Exploring the relationship between ordinary PageR-
ank, lazy PageRank and random walk with backstep PageRank for different
graph structures. In: Skiadas, C.H. (Ed.) Proceedings of the 5th Stochastic
55
Modeling Techniques and Data Analysis International Conference with De-
mographics Workshop. Chania, Crete, Greece, 2018. ISAST: International
Society for the Advancement of Science and Technology, 71–85.
[9] Biganda, P.S., Abola, B., Engström, C., Mango, J.M., Kakuba, G., Silve-
strov, S. (2018). Traditional and lazy PageRanks for a line of nodes connected
with complete graphs. In: Silvestrov, S., Ranc̆ić, M., Malyarenko, A. (Eds.)
Stochastic Processes and Applications, Chapter 17. Springer Proceedings in
Mathematics & Statistics, 271, Springer, Cham, 391–412.
[10] Bini, D.A., Latouche, G., Meini, B. (2005). Numerical Methods for Struc-
tured Markov Chains. Numerical Mathematics and Scientific Computation,
Oxford Science Publications, Oxford University Press, New York, xii+327
pp.
[11] Brin, S., Page, L. (1998). The anatomy of a large-scale hypertextual web
search engine. Comp. Networks, ISDN Syst., 30(1-7), 107–117.
[12] Englund, E. (2001). Nonlinearly Perturbed Renewal Equations with Appli-
cations. Doctoral dissertation, Umeå University.
[13] Englund, E., Silvestrov, D.S. (1997). Mixed large deviation and ergodic
theorems for regenerative processes with discrete time. In: Jagers, P.,
Kulldorff, G., Portenko, N., Silvestrov, D. (Eds.) Proceedings of the Sec-
ond Scandinavian–Ukrainian Conference in Mathematical Statistics, Vol. I,
Umeå, 1997. Theory Stoch. Process., 3(19), no. 1-2, 164–176.
[14] Engström, C. (2016). PageRank in Evolving Networks and Applications of
Graphs in Natural Language Processing and Biology. Doctoral dissertation
217, Mälardalen University, Västerås.
[15] Engström, C., Silvestrov, S. (2014). Generalisation of the damping fac-
tor in PageRank for weighted networks. In: Silvestrov, D., Martin-Löf, A.
(Eds.) Modern Problems in Insurance Mathematics, Chapter 19. EAA series,
Springer, Cham, 313–334.
[16] Engström, C., Silvestrov, S. (2016). PageRank, a look at small changes in a
line of nodes and the complete graph. In: Silvestrov, S., Ranc̆ić, M. (Eds.)
Engineering Mathematics II. Algebraic, Stochastic and Analysis Structures
for Networks, Data Classification and Optimization, Chapter 11. Springer
Proceedings in Mathematics & Statistics 179, Springer, Cham, 223–248.
[17] Engström, C., Silvestrov, S. (2016). PageRank, connecting a line of nodes
with a complete graph. In: Silvestrov, S., Ranc̆ić, M. (Eds.) Engineering
56
Mathematics II. Algebraic, Stochastic and Analysis Structures for Networks,
Data Classification and Optimization, Chapter 12. Springer Proceedings in
Mathematics & Statistics 179, Springer, Cham, 249–274.
[18] Engström, C., Silvestrov, S. (2017). PageRank for networks, graphs, and
Markov chains. Teor. Ĭmovirn. Mat. Stat., 96, 61–83 (Also, in Theor. Probab.
Math. Statist., 96, 59–82).
[19] Feller, W. (1968). An Introduction to Probability Theory and Its Applica-

tions. Vol. I. Third edition, Wiley, New York, xviii+509 pp.
[20] Gambini, A., Krzyanowski. P., Pokarowski, P. (2008). Aggregation algo-

rithms for perturbed Markov chains with applications to networks modeling.
SIAM J. Sci. Comput. 31, no. 1, 45–73.
[21] Gleich, D. F. (2015). PageRank beyond the Web. SIAM Review, 57(3), 321–
363.
[22] Griffeath, D. (1975). A maximal coupling for Markov chains. Z. Wahrsch.

verw. Gebiete, 31, 95–106.
[23] Gyllenberg, M., Silvestrov, D.S. (2000). Nonlinearly perturbed regenerative

processes and pseudo-stationary phenomena for stochastic systems. Stoch.
Process. Appl., 86, 1–27.
[24] Gyllenberg, M., Silvestrov, D.S. (2008). Quasi-Stationary Phenomena in

Nonlinearly Perturbed Stochastic Systems. De Gruyter Expositions in Math-
ematics, 44, Walter de Gruyter, Berlin, ix+579 pp.
[25] Hartfiel, D.J., Meyer, C.D. (1998). On the structure of stochastic matrices
with a subdominant eigenvalue near 1. Linear Algebra, Appl., 272(1-3), 193–
203.
[26] Haveliwala, T., Kamvar, S. (2003). The second eigenvalue of the Google
matrix. Technical Report 2003-20, Stanford University.
[27] Kalashnikov, V.V. (1989). Coupling method, development and applications.

Supplement to the Russian edition of the book by Nummelin, E. (1984).
General lrreducible Markov Chains and Non-negative Operators. Cambridge
University Press (Russian edition, MIR, Moscow, 1989, 176–190).
[28] Kamvar, S.D., Schlosser, M.T., Garcia-Molina, H. (2003). The eigentrust

algorithm for reputation management in p2p networks. In: Proceedings of
the 12th international conference on World Wide Web. ACM, 640–651.
57
[29] Konstantinov, M., Gu, D.W., Mehrmann, V., Petkov, P. (2003). Perturbation
Theory for Matrix Equations. Studies in Computational Mathematics, 9,
North-Holland, Amsterdam, xii+429 pp.
[30] Koroliuk, V.S., Limnios, N. (2005). Stochastic Systems in Merging Phase

Space. World Scientific, Singapore, xv+331 pp.
[31] Korolyuk, V.S., Korolyuk, V.V. (1999). Stochastic Models of Systems. Math-
ematics and Its Applications, 469, Kluwer, Dordrecht, xii+185 pp.
[32] Langville, A.N., Meyer, C.D. (2011). Google’s PageRank and Beyond: The
Science of Search Engine Rankings. Princeton University Press, Princeton,
x+224 pp.
[33] Lindvall, T. (2002). Lectures on the Coupling Method. Wiley Series in Proba-
bility and Mathematical Statistics: Probability and Mathematical Statistics,
Wiley, New York, xiv+257 pp. (A revised reprint of the 1992 original).
[34] Mitrophanov, A.Yu. (2005). Sensitivity and convergence of uniformly ergodic

Markov chains. J. Appl. Prob., 42, 1003–1014.
[35] Ni, Y. (2011). Nonlinearly Perturbed Renewal Equations: Asymptotic Re-

sults and Applications. Doctoral dissertation 106, Mälardalen University,
Västerås.
[36] Ni, Y., Silvestrov, D., Malyarenko, A. (2008). Exponential asymptotics for
nonlinearly perturbed renewal equation with non-polynomial perturbations.
J. Numer. Appl. Math. 1(96), 173–197.
[37] Petersson, M. (2016). Perturbed Discrete Time Stochastic Models. Doctoral

dissertation, Stockholm University.
[38] Pitman, J.W. (1979). On coupling of Markov chains, Z. Wahrsch. verw. Ge-
biete, 35, 315–322.
[39] Silvestrov, D.S. (1978). The renewal theorem in a series scheme. 1. Teor.
Veroyatn. Mat. Stat. 18, 144–161 (English translation in Theory Probab.
Math. Statist., 18, 155–172).
[40] Silvestrov, D.S. (1979). The renewal theorem in a series scheme 2. Teor.
Veroyatn. Mat. Stat., 20, 97–116 (English translation in Theory Probab.
Math. Statist., 20, 113–130).
58
[41] Silvestrov, D.S. (1983). Method of a single probability space in ergodic the-
orems for regenerative processes 1. Math. Operat. Statist., Ser. Optim., 14,
285–299.
601–612.
613–622.
[44] Silvestrov, D. (1994). Coupling for Markov renewal processes and the rate of
convergence in ergodic theorems for processes with semi-Markov switchings.
Acta Applic. Math., 34, 109–124.
[45] Silvestrov, D. (2018). Individual ergodic theorems for perturbed alternating

regenerative processes. In: Silvestrov, S., Ranc̆ić, M., Malyarenko, A. (Eds.)
Stochastic Processes and Applications, Chapter 3. Springer Proceedings in
Mathematics & Statistics, 271, Springer, Cham, 23–89.
[46] Silvestrov, D.S., Petersson, M. (2014). Exponential expansions for per-

turbed discrete time renewal equations. In: Karagrigoriou, A., Lisnianski,
A., Kleyner, A., Frenkel, I. (Eds.) Applied Reliability Engineering and Risk
Analysis, Chapter 23. Probabilistic Models and Statistical Inference, Wiley,
New York, 349–362.
[47] Silvestrov, D., Petersson, M., Hössjer, O. (2018). Nonlinearly perturbed

birth-death-type models. In: Silvestrov, S., Ranc̆ić, M., Malyarenko, A.
(Eds.) Stochastic Processes and Applications, Chapter 3. Springer Proceed-
ings in Mathematics & Statistics, 271, Springer, Cham, 189–244.
[48] Silvestrov, D.S., Pezinska, G. (1985). On maximally coinciding random vari-

ables. Teor. Veroyatn. Mat. Stat., 32, 102–105 (English translation in Theory
Probab. Math. Statist., 32, 113–115).
[49] Silvestrov, D., Silvestrov, S. (2016). Asymptotic expansions for stationary

distributions of perturbed semi-Markov processes. In: Silvestrov, S., Ranc̆ić,
M. (Eds.) Engineering Mathematics II. Algebraic, Stochastic and Analysis
Structures for Networks, Data Classification and Optimization, Chapter 10.
Springer Proceedings in Mathematics & Statistics, 179, Springer, Cham,
151–222.
59
[50] Silvestrov, D., Silvestrov, S. (2017). Nonlinearly Perturbed Semi-Markov Pro-
cesses. Springer Briefs in Probability and Mathematical Statistics, Springer,
Cham, xiv+143 pp.

distributions of nonlinearly perturbed semi-Markov processes. 1. Methodol.
Comput. Appl. Probab., doi.org/10.1007/s11009-017-9605-0, 20 pp.

distributions of nonlinearly perturbed semi-Markov processes. 2. Methodol.
Comput. Appl. Probab., doi.org/10.1007/s11009-017-9607-yh, 20 pp.
[53] Silvestrov, D., Silvestrov, S. (2017). Asymptotic expansions for power-

exponential moments of hitting times for nonlinearly perturbed semi-Markov
processes. Teor. Ĭmovirn. Mat. Stat., 97, 171–187 (Also, in Theory Probab.
Math. Statist., 97, 183–200).
[54] Stewart, G.W. (1998). Matrix Algorithms. Vol. I. Basic Decompositions.

SIAM, Philadelphia, PA, xx+458 pp.
[55] Stewart, G.W. (2001). Matrix Algorithms. Vol. II. Eigensystems. SIAM,
Philadelphia, PA, xx+469 pp.
[56] Stewart, W.J. (1994). Introduction to the Numerical Solution of Markov

Chains. Princeton University Press, Princeton, NJ, xx+539 pp.
[57] Sun, Y., Han, J. (2013). Mining heterogeneous Information networks: a struc-
tural analysis approach. ACM SIGKDD Explor. Newslet. 14(2), 20–28.
[58] Yin, G.G., Zhang, Q. (2005). Discrete-Time Markov Chains. Two-Time-Scale

Methods and Applications. Stochastic Modelling and Applied Probability,
55, Springer, New York, xix+348 pp.
[59] Yin, G.G., Zhang, Q. (2013). Continuous-Time Markov Chains and Appli-
cations. A Two-Time-Scale Approach. Second edition, Stochastic Modelling
and Applied Probability, 37, Springer, New York, xxii+427 pp. (An extended
variant of the first (1998) edition).
60
View publication stats

Perturbed Markov Chains and Information Networks

Uploaded by

Copyright:

Available Formats

Perturbed Markov Chains and Information Networks

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Perturbed Markov Chains and Information Networks

Uploaded by

Copyright:

Available Formats

See discussions, stats, and author profiles for this publication at: https://www.researchgate.

Perturbed Markov Chains and Information Networks

Preprint · January 2019

Benard Abola Pitos Seleka Biganda

Sergei Silvestrov Christopher Engström

SEE PROFILE SEE PROFILE

non-commutative analysis View project

Sida Bilateral Mathematics Project 316 Uganda View project

The user has requested enhancement of the downloaded file.

Benard Abola, Pitos Seleka Biganda, Sergei Silvestrov, Dmitrii Silvestrov,

Christopher Engström, John Magero Mango, and Godwin Kakuba1

Abstract. The paper is devoted to studies of perturbed Markov chains

Perturbed Markov chains is one of the popular and important objects of

2. Markov chains with damping component

In this section, we introduce the model of Markov chains with damping

pε,ir,jk = P{Xε,1 = j, Wε,1 = k/Xε,0 = i, Wε,0 = r}

2.3 Renewal type equations for transition probabilities of the

pε,ij (n) = P{Xε,n = j/Xε,0 = i}, (6)

and n-sep probabilities, for p̄ ∈ Pm , j ∈ X, n = 0, 1, . . .,

pε,ir,jk (n) = P{Yε,n = (j, k)/Yε,0 = (i, r)}, (8)

and n-sep probabilities, for pq ∈ PQm , (j, k) ∈ Y, n = 0, 1, . . .,

qε,dq1 ,jk (n) = Pdq1 {Yε,n = (j, k), Tε,1 > n}

qε,pq,jk (n) = Ppq {Yε,n = (j, k), Tε,1 > n}

p0,p̄,j (n)(1 − ε)n I(n > 0) if k = 0,

Also, the summation of renewal type equations (12) over k = 0, 1 yields

3. Stationary distributions of Markov chains with

In this section we present ergodic relations for transition probabilities of

Proof. The geometrical distribution of the inter-regeneration time Sε,1

pε,dq1 ,jk (n) → πε,jk as n → ∞. (17)

Obviously qε,pq,jk (n) → 0 as n → ∞, for (j, k) ∈ Y.

lim pε,pq,jk (n) = lim qε,pq,jk (n)

The proof is complete.

A1 : The phase space X is one aperiodic class of communicative states for

In this case, the following ergodic relation holds, for any p̄ ∈ Pm , j ∈ X,

p0,p̄,j (n) → π0,j as ε → 0, (21)

The stationary distribution π̄0 = hπ0,j , j ∈ Xi is the unique positive

B1 : The phase space X = ∪hj=1 X(j) , where X (j) , j = 1, . . . , h are non-

Let us denote, for p̄ ∈ Pm , j = 1, . . . , h,

Lemma 3. Let condition B1 holds. Then, the following ergodic relation

4. A perturbation model for Markov chains with

pε,ij → p0,ij as ε → 0. (27)

Also, as well known, matrix kpε,ij (n)k = Pnε , for n = 0, 1, . . ., where

pε,ij (n) → p0,ij (n) as ε → 0. (28)

Since the sequence pp̄,j (n), n = 0, 1, . . . is a bounded, relations (31), (32)

The proof is complete.

The proof is complete.

5. Rate of convergence for perturbed stationary distributions

In this section, we obtain explicit upper bounds for deviations of station-

In fact, condition A1 is equivalent to the following condition:

with some constants Cj = Cj (P0,j ) ∈ [0, ∞), λj = λj (P0,j ) ∈ [0, 1), j =

Condition B1 is, in fact, equivalent to the following condition:

6. Asymptotic expansions for perturbed stationary

In this section, we present asymptotic expansions for stationary distribu-

A3 : ρ1 = 1 > |ρ2 | ≥ · · · ≥ |ρm |.

Note that some of eigenvalues ρ2 , . . . , ρm can be complex numbers.

Obviously, relation (45) implies that probabilities pij (n) → π0,j as n →

Let also define coefficients, for j ∈ X, n ≥ 1,

Functions (a + bε)−1 , ε ∈ [0, 1] and bε(1 − ε)(a + bε)−1 , ε ∈ [0, 1] admit,