INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS
YURI N.KARTASHOV, ALEXEY M.KULIK
Abstract. We consider a sequence of additive functionals {φn}, set on a sequence of Markov chains {Xn}
that weakly converges to a Markov process X. We give sufficient condition for such a sequence to converge in
distribution, formulated in terms of the characteristics of the additive functionals, and related to the Dynkin’s
theorem on the convergence of W -functionals. As an application of the main theorem, the general sufficient
condition for convergence of additive functionals in terms of transition probabilities of the chains Xn is proved.
1. Introduction
Let a sequence of processes Xn = Xn(·) be given, converging in distribution (in some sense, e.g., in a
sense of convergence of finite-dimensional distributions, distributions in spaces C or D, etc.) to a limit process
X = X(·). Also let the family of functionals φn of the processes Xn be given. Assume that they are additive
in an appropriate sense with respect to time variable. The general question, considered in the present paper,
is what an information about the limit behavior of the distributions of functionals φn can be obtained in a
situation where the processesXn, X possess certain Markov properties. The starting point in our considerations
is provided by the comparatively simple, but important particular case of the problem outlined above, in which
all the processes Xn coincide. In this situation, φn are a functionals of the same process X , and if X is Markov
process and φn are W -functionals (see [1], Chapter 6), then their limit behavior, according to the well known
theorem by E.B.Dynkin ([1], Theorem 6.4), is determined by the limit behavior of their characteristics (that
is, their expectations).
In the present paper we consider the processes Xn that differ one from another. The class of sequences
of processes Xn, considered in the framework of our approach, contains sequences of Markov chains with
appropriately normalized time, embedded into C or D (for example, by means of standard operations of
linearization or construction of graduated processes), and weakly convergent to Markov process X . Important
partial case is provided by random broken lines (or random step functions) Xn, constructed by a random walk
in Rd and weakly convergent to a homogenous stable process X (particularly, to the Brownian motion).
We show that, under some structural assumption about processes Xn, X (the condition is that the sequence
{Xn} provides Markov approximation for the process X), the full analogue of the Dynkin’s theorem takes
place: if the characteristics of functionals φn converge weakly to the characteristics of W -functional φ of the
limit process X , then the distributions of φn converge to the distribution of φ. Our method of proof is based
on L2-estimates for the distance between additive functionals, similar to those given in Lemma 6.5 [1]. The
proof of these estimates is concerned with a preliminary construction of processes Xn, X on one probability
space in such a way, that the functionals φn, φ, associated initially with a different processes, are interpreted
as a functionals of one two-component process. The (some kind of) Markov property of the two-component
process is essential for the estimates, analogous to those given in Lemma 6.5 [1]; the structural assumption
mentioned above is just the claim for such a property to hold true in an appropriate form.
The method, proposed by authors, allows one to reduce the problem of studying of asymptotic behavior
of the distributions of additive functionals to a priori more simple problem of studying of their means. In
our opinion, it provides a good addition to the available methods of studying the limit behavior of additive
functionals both for the important partial case of random walks (we do not give the detailed review here,
2000 Mathematics Subject Classification. Primary 60J55; Secondary 60F17.
Key words and phrases. additive functional, characteristics of additive functional, Markov approximation.
http://arxiv.org/abs/0704.0508v1
2 YURI N.KARTASHOV, ALEXEY M.KULIK
referring the reader to monographs [2],[3],[4], papers [5],[6] and reviews there), and for general Markov chains.
Among the latter, it is necessary to mention the method that is based on the passing to the limit in the difference
equations that describe characteristic functions of additive functionals of Markov chains, and ascends to the
works of I.I.Gikhman at 50-ies (see [7],[8], also [9] and the survey paper [10]).
The structure of the article is following. In Chapter 2, we introduce the notion of Markov approximation
and give examples that illustrate it. In Chapter 3, the main theorem of the article is introduced and proved.
In Chapters 4,5, the two elementary examples of application of this theorem are given. In Chapter 6, the main
theorem is applied to the proof of a general sufficient condition for weak convergence of additive functionals,
set on the sequence of Markov chains, that is formulated in terms of transition probabilities of the chains.
2. Markov approximation.
Further we assume that the processes Xn, X are defined on R
+ and have a locally compact metric phase
space (X, ρ). We say that the process X possesses the Markov property at the time moment s ∈ R+ w.r.t.
filtration {Gt, t ∈ R+}, if X is adapted to this filtration and for each k ∈ N, t1, . . . , tk > s there exists a
stochastic kernel {Pst1...tk(x,A), x ∈ X, A ∈ B(Xk)} such that
(2.1) E[1IA((X(t1), . . . , X(tk)))|Gs] = Pst1...tk(X(s), A) a.s., A ∈ B(Xk).
The measure Pst1...tk(x, ·) has a natural interpretation as the finite-dimensional distribution of X at the points
t1, . . . , tk, conditioned by {X(s) = x}; we denote below Pst1...tk(x, ·) = P ((X(t1), . . . , X(tk)) ∈ ·|X(s) = x).
Remark 1. In some cases, (2.1) implies the following functional analogue of (2.1):
(2.2) E[1I·(X |∞s )|Gs] = E[1I·(X |∞s )|X(s)],
where X |∞s denotes the trajectory of the process X on the time interval [s,+∞), considered as an element of
appropriate functional space. For instance, if the Kolmogorov’s sufficient condition for existence of continuous
modification holds true both for unconditional and conditional distributions of X , then (2.2) holds with X |∞s
considered as an element of C([s,+∞),X).
Everywhere below we assume that the process X possesses the Markov property w.r.t. its canonic filtration
at every point s ∈ R+ and for the processesXn the same property holds true at every point of the type in , i ∈ Z+
(the choice of the denominator here is quite arbitrary; it is possible to put any expression N(n) → ∞, n→ ∞
instead of n, but we avoid to do this in order to shorten the notation).
The next definition is introduced in [11].
Definition 1. The sequence {Xn} provides Markov approximation for the process X , if for arbitrary γ >
0, T < +∞ there exists K(γ, T ) ∈ N and a sequence of two-componential processes {Ŷn = (X̂n, X̂n)}, defined
on another probability space, such that
(i) X̂n
=Xn, X̂
n d=X ;
(ii) the process Ŷn, together with the processes X̂n, X̂
n, possesses the Markov property at the points
iK(γ,T )
, i ∈ N w.r.t. filtration {F̂nt = σ(Ŷn(s), s ≤ t)};
(iii) lim sup
 sup
i≤ Tn
K(γ,T )
iK(γ,T )
, X̂n
iK(γ,T )
 < γ.
Remark 2. Condition (ii) implies that, for i, k ∈ N, t1, . . . , tk > iK(γ,T )n , (x, y) ∈ X
2, the marginal distributions
(Ŷn(t1), . . . , Ŷn(tk)) ∈ ·|Ŷn( iK(γ,T )n ) = (x, y)
are equal to P
(Xn(t1), . . . , Xn(tk)) ∈ ·|Xn( iK(γ,T )n ) = x
and P
(X(t1), . . . , X(tk)) ∈ ·|X
iK(γ,T )
respectively.
Let us give some examples that illustrate Definition 1.
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 3
Example 1. Let {ξk} be a sequence of i.i.d random vectors in Rd with E‖ξk‖2+δRd < +∞ for some δ > 0.
Assume {ξk} to have zero mean and identity for their covariance matrix. Let us introduce the sequence of
processes Xn (”random broken lines”) on R
(2.3) Xn(t) =
Sk−1√
+ (nt− k + 1)
− Sk−1√
, t ∈
k − 1
, k ∈ N,
where Sn =
k=1 ξk. Then Xn converge by distribution in C(R
+,Rd) to the Brownian motion X in Rd.
It is shown in [11] that the sequence {Xn} provides Markov approximation for the process X (part I. of
Theorem 1 [11]). On the other hand, in the same paper (part II. of the same Theorem) the following effect
is revealed. Let us denote by K(γ, T ) the minimal constant K(γ, T ) such that there exists a process Ŷn
satisfying conditions (i)-(iii) of Definition 1. Then, in all the cases except one trivial case ξk ∼ N (0, I), for
each fixed T > 0 the convergence K(γ, T ) → +∞, γ → 0+ takes place. In other words, while the accuracy of
approximation of the Brownian motion X by the random walk Xn becomes better (this accuracy is described
by the parameter γ), the Markov properties of the pair of processes (X,Xn) necessarily become worse (these
properties are characterized by K(γ, T )).
Example 2. Let {ξk} be i.i.d random variables, belonging to the normal domain of attraction for α-stable
distribution L, α ∈ (0, 2). By the definition, this means that
α [Sn − an] ⇒ L, an =
0, α ∈ (0, 1)
nEξ1, α ∈ (1, 2)
n2E sin ξ1
, α = 1
([12], Chapter XVII.5). In order to shorten the notation, we assume that an ≡ 0 and consider processes Xn
on R+ of the type
(2.4) Xn(t) = n
αSk−1 + (nt− k + 1)
αSk − n−
αSk−1
, t ∈
k − 1
, k ∈ N.
Then Xn converge by distribution in D(R
+) to the homogeneous process with independent increments X in
R, for which X(1)−X(0) d=L (we call such process a process an α-stable one).
It is shown in [11] (Theorem 2) that the sequence {Xn} provides Markov approximation for the process X .
Furthermore, in this situation, on the contrary to the previous example, K(γ, T ) = 1 for all γ, T . This means
that, in this case, the Markov properties do not become worse while accuracy of approximation improves.
Remark 3. The last example shows that the property of Markov approximation does imply, in general, the
convergence of distributions of the processes Xn to the distribution of X in C = C(R
+,X) even if Xn has
continuous trajectories. The same can be said about convergence in D = D(R+,X) (we omit the corresponding
example).
Let us remark that the approach, introduced in the present paper, is closely related to the Skorokhod’s
method of embedding of random walk into Wiener process by means of of appropriate sequence of stopping
moments ([13]), widely used in literature. The basic idea is the same: we have to construct two processes on
the same probability space, with the pair keeping Markov or martingale properties. However, the Skorokhod’s
method, while being quite efficient for one-dimensional random walks that approximate Wiener process, is
much less appropriate in a multi-dimensional situation or for stable domain of attraction. Examples 1 and 2
show that the claim for the Markov approximation to hold true is not restrictive, at least for all basic classes
of random walks with no regard to the dimension of the phase space or to the type of limit distribution.
The following example shows that the property of Markov approximation is ”stable” in the following sense.
This property is preserved under construction of a new pair (Zn, Z) from the pair (Xn, X), possessing this
property, in some regular way (e.g., as a solution of a family of stochastic equations).
4 YURI N.KARTASHOV, ALEXEY M.KULIK
Example 3. Let Xn, X be as in Example 1, functions a : R
m → Rm, b : Rd → Rd×m be Lipschitz and
b∗(x)b(x) > 0, x ∈ Rm (the sign ∗ denotes the operation of taking of the adjoint matrix). Define
(2.5) Zn
k + 1
, Zn(0) = z,
) ≡ [Xn(k+1n )−Xn(
)]. Then ([14], [15]) Zn converge by distribution in C(R
+,Rm) to the process Z,
defined by SDE
(2.6) dZ(t) = a(Z(t))dt + b(Z(t))dX(t), Z(0) = z,
where X is the Brownian motion in Rd. It is natural to call the sequence Zn the difference approximation of
the diffusion process Z.
Let us show that the sequence {Zn} provides Markov approximation for the process Z. For arbitrary γ, T ,
we construct a pair (X̂n, X̂
n), corresponding to processes Xn, X and satisfying conditions of Definition 1 (such
construction is possible due to Example 1).
Let us construct the processes Ẑn, Ẑ
n as the functionals of the processes X̂n, X̂
n by equalities (2.5),(2.6) with
Xn replaced by X̂n and X replaced by X̂
n (note that (2.6) has unique strong solution, hence this procedure
is correct). By the construction, the pair (Ẑn, Ẑ
n) satisfies condition (i) of Definition 1. It is easy to verify
that the Markov condition (ii) for the pair (X̂n, X̂
n) holds in the functional form (2.2) with Ŷn|∞s considered
as an element of C([s,+∞),Rd × Rd) (see Remark 1). Hence, the pair (Ẑn, Ẑn) also satisfies condition (ii) of
Definition 1. Let us write
∆(γ) = lim sup
 sup
i≤ Tn
K(γ,T )
iK(γ, T )
, Ẑn
iK(γ, T )
and show that
(2.7) ∆(γ) → 0+, γ → 0 + .
Note that (2.7) immediately implies Markov approximation: for arbitrary δ > 0 we chose, using (2.7), γ = γ(δ)
such that inequalities γ < δ and ∆(γ) < δ hold. Then the pair (Ẑn, Ẑ
n), constructed by the scheme described
above, satisfy Definition 1 with the constant γ replaced by δ (note that, under this construction, the value
K(δ, T ) ≡ KZ(δ, T ) for the pair (Ẑn, Ẑn) is expressed through the same value for the pair (X̂n, X̂n) by
KZ(δ, T ) = KX(γ(δ), T )).
Now assume that (2.7) does not hold, then there exist constant c > 0 and sequence γk → 0+, nk → +∞
such that
(2.8)
K(γk, T )
→ 0, P
 sup
i≤ Tnk
K(γk,T )
iK(γk, T )
iK(γk, T )
 > c.
Consider the sequence of four-component processes (X̂nk , X̂
nk , Ẑnk , Ẑ
nk). Every component of this sequence is
weakly compact in C(R+,Rd) or C(R+,Rm), hence the whole sequence is also weakly compact in C(R+,Rd×
d ×Rm ×Rm). Consider arbitrary limit point (X̂∗, X̂∗, Ẑ∗, Ẑ∗) (in a sense of convergence by distribution) of
this sequence. It follows from (2.8) that
(2.9) P (Z∗ 6= Z∗) > 0.
It follows from Theorem 2.2 [15] (see also Chapter 9.5 [14]) that the processes Z∗, Z
∗ satisfy SDE (2.6) with X
replaced by X∗, X
∗. However, the SDE (2.6) possesses the property of pathwise uniqueness (see [16]), and the
property (iii) of the pair (Xnk , X̂
nk) implies that the processes X∗, X
∗ coincide a.s. Therefore, the processes
Z∗, Z
∗ also coincide a.s., that contradicts to (2.9) and show that our assumption that ∆(γ) 6→ 0+, γ → 0+ is
false.
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 5
The examples given above show that the claim for the Markov approximation to hold is not very restrictive,
and is provided in a typical situations. On the other hand, this claim is strong enough to provide one the
opportunity to obtain an analog of the Dynkin’s theorem; this will be shown in the next chapter.
3. Main theorem
We consider the functionals of the type
(3.1) φs,tn (Y )
k:s≤k/n<t
k + 1
, . . . , Y
k + L− 1
, 0 ≤ s < t,
where the functions Fn(·) are nonnegative, L is a fixed integer. Together with the functionals φn, that are
”stepwise” functions w.r.t. every time variable, we consider random broken lines, related to these functions:
n = φ
n + (ns− j + 1)φ
n + (nt− k + 1)φ
n , s ∈
j − 1
, t ∈
k − 1
We interpret the random broken lines ψn as a random elements in space C(T,R
+), where T
= {(s, t)|0 ≤ s ≤
If process Y possesses Markov property w.r.t. the filtration, associated with this process, at the points of
the type s = i
, i ∈ Z+, then, for functional φn, its characteristic fn is naturally defined by the formula
(3.2) f s,tn (x)
= E[φs,tn (Y )|Y (s) = x], s =
, i ∈ Z+, t > s, x ∈ X.
Note that the functional (3.1) is a function of values of Y at finite number of time moments, thus the mean
value in (3.2) is well defined as the integral over the family {Pst1...tk(x, ·), t1, . . . , tk > s, k ∈ N} of conditional
finite-dimensional distributions of the process Y .
The main result of this chapter is given in the following theorem.
Theorem 1. Assume that there exist the sequence Xn that provides Markov approximation for the homoge-
neous Markov process X and the sequence {φn ≡ φn(Xn)} of the functionals of the type (3.1). Let the following
conditions hold true:
(1) The functions Fn(·) are bounded and uniformly tend to zero:
δ(Fn)
= sup{Fn(x1, . . . , xL)|x1, . . . , xL ∈ X} → 0, n→ ∞.
(2) There exists a function f , that appears to be a characteristics (in a sense of Chapter 6 [1]) of some
W -functional φ = φ(X) of the limiting Markov process X, such that, for each T ,
,t∈(s,T )
∥∥f s,tn (·)− f s,t(·)
∥∥→ 0, n→ ∞,
where ‖g(·)‖ ≡ sup
|g(x)|.
(3) The limiting function f is uniformly continuous with respect to variable x, that is, for arbitrary T
0≤s≤t<T
∣∣f s,t(x′)− f s,t(x′′)
∣∣→ 0, |x′ − x′′| → 0.
ψn(Xn) ⇒ φ(X) ≡ {φs,t(X), (s, t) ∈ T},
where ψn are the random broken lines corresponding to the functionals φn and convergence is understood in a
sense of C(T,R+).
Remark 4. Conditions 1,2 are analogous to those of the Dynkin’s theorem: condition 2 is exactly the condition
for the characteristics to converge, condition 1 corresponds to the assumption that the prelimit functionals are
W -functionals. In the present situation, of course, we can not say that φn are W -functionals, particulary, φn
are not continuous with respect to temporary variable. Condition 1 means exactly that the values of jumps
6 YURI N.KARTASHOV, ALEXEY M.KULIK
are negligible while n→ ∞. Condition 3, though not very restrictive, is specific, and is caused by necessity to
consider functionals, set over different processes.
Remark 5. If Xn ⇒ X in C or in D (this condition is not provided by the conditions of the Theorem, see
Remark 3), then, as one can easily see from the proof, (Xn, ψn(Xn)) ⇒ (X,φ(X)) in C × C(T,R+) or in
D× C(T,R+), respectively.
Note that the result of the theorem also holds for the Markov process X that is not homogeneous w.r.t.
time variable; the claim for the limit Markov process to be homogeneous is imposed in order to shorten the
notation only. This remark concerns also the most of the results stated below.
Proof of the theorem. The general scheme of the proof is close to the one, proposed in [17] in order to
prove the analogue of the Dynkin’s theorem for the family of functionals of a single Markov process, for which
the properties of additivity, continuity and homogeneity may fail, but the violations become negligible while
n→ ∞.
First let us show that the finite-dimensional distributions of φn converge to the corresponding distributions
of φ. Let the constants γ, T be fixed and X̂n, X̂
n be processes satisfying conditions (i)-(iii) of Definition 1
with these constants. For these processes, one can consider the functionals φn(X̂n), φ(X̂
n); obviously, their
distributions and characteristics coincide with those for φn(Xn), φ(X). In order to shorten notation, we denote
further φn = φn(X̂n), φ = φ(X̂
n),K = K(γ, T ),Ft = F̂nt ≡ σ(X̂n(s), X̂n(s), s ≤ t).
It follows from the condition (iii) and the definition of characteristics that, for arbitrary t ∈
(3.3) E
,t|FKi
n |FKi
almost surely.
Lemma 1. For 0 ≤ s ≤ t ≤ T , the following estimate holds:
lim sup
n (X̂n)− φs,t(X̂)
∥∥f0,T
∥∥G(f, γ, T ) + 4
∥∥f0,T
∥∥2 ,
where G(f, γ, T ) = sup
0≤s≤t≤T,|x′−x′′|<γ
|f s,t(x′)− f s,t(x′′)|.
Proof. We will prove the statement of lemma for s = 0, t = T ; in general case the proof is exactly the same.
Consider the partition of the axis R+ by points of the type Ki
, i ∈ N. Denote Mn = [nTK ] + 1,
(i−1)K
,( iK
n , ∆̃
(i−1)K
T , i = 1,Mn.
We have that
φ0,Tn − φ0,T
∆ni − ∆̃ni
∆ni ∆̃
j = Σ
1 + 2Σ
where
(∆ni )
(∆̃ni )
2 − 2
∆ni ∆̃
1≤i<l≤Mn
∆ni ∆
1≤i<j≤Mn
∆ni ∆̃
1≤j<k≤Mn
∆̃nj ∆̃
1≤j<i≤Mn
∆ni ∆̃
Let us estimate the expectations Σn1 ,Σ
2 separately. Since the increments ∆
i , ∆̃
i are non-negative, the first
sum can be estimated by the sum of the first two terms:
(3.4) Σn1 ≤
(∆ni )
(∆̃ni )
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 7
The expectation of the first term in (3.4) can be estimated via the definition of φn:
(∆ni )
2 ≤ E
i=1,Mn
) Mn∑
∆ni ≤ Kδnf0,Tn
X̂n(0)
≤ Kδn
∥∥f0,Tn
∥∥→ 0, n→ +∞,
where δn ≡ δ(Fn). Convergence to zero of the expectation of the second term in (3.4) is provided by the
arguments, analogous to those used in [1] Chapter 6: on the one hand, by the continuity of functional φ,∑Mn
i=1(∆̃
2 → 0 by probability; on the other hand,
i=1(∆̃
2 is dominated by the variable (φ0,T )2; the
expectation of this variable, due to Lemma 6.4 [1], does not exceed 2
∥∥f0,T
∥∥2 <∞. Therefore, E
i=1(∆̃
0 due to the Lebesgue theorem on dominated convergence. Hence, lim sup
EΣn1 ≤ 0.
The expectation of Σn2 is equal
EΣn2 = E
1≤i<l≤Mn
∆ni ∆
1≤i<j≤Mn
∆ni ∆̃
1≤j<k≤Mn
∆̃nj ∆̃
1≤j<i≤Mn
∆ni ∆̃
(3.5) = E
Mn−1∑
n − φ
Mn−1∑
n − φ
We estimate the second term in (3.5), using property (3.3). Since ∆̃ni is measurable w.r.t. FKi
, the following
estimate holds:
Mn−1∑
n − φ
Mn−1∑
∆̃ni E
n − φ
Mn−1∑
− f Kin ,T
Mn−1∑
n − f
∣∣∣+ E
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣ ≤
(3.6) ≤ ‖f0,T‖ sup
,t∈(s,T )
∥∥f s,tn (·)− f s,t(·)
∥∥+ E
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣
(in the last inequality, we have used that
∑Mn−1
i=1 ∆̃
i ≤ φ0,T and Eφ0,T ≤ ‖f0,T‖). The first term in (3.6)
tends to zero. In order to estimate the second term, we put Ωγ,T =
i≤ Tn
, X̂n
(recall
that P (Ωγ,T ) < γ due to the claim (iii) of Definition 1). We have
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣ ≤ Eφ
G(f, γ, T )1IΩ\Ωγ,T+
(3.7) + E
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣ 1IΩγ,T .
The first term in (3.7) can be estimated by ‖f0,T‖G(f, γ, T ). The second term is estimated by Cauchy
inequality:
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣ 1IΩγ,T ≤
∥∥f0,T
∥∥Eφ0,T 1IΩγ,T ≤
∥∥f0,T
∥∥ [E(φ0,T )2
2 [P (Ωγ,T )]
∥∥f0,T
∥∥2√2γ
8 YURI N.KARTASHOV, ALEXEY M.KULIK
(here, the Lemma 6.4 [1] was applied). Summing up the above relations, we deduce that
(3.8) lim sup
Mn−1∑
n − φ
∥∥f0,T
∥∥G(f, γ, T ) +
∥∥f0,T
∥∥2√2γ.
Now, let us proceed with the estimation of the first item in (3.5). Straightforward use of the property
(3.3) is impossible here, since the variable ∆ni is a functional of values of the process X̂n at the points
, Ki+1
, . . . Ki+L
, that is, it is not measurable with respect to FKi
. Without loss of generality, one can
assume that K ≥ L (otherwise one can make the same procedure with the constant K replaced by K · L).
Then the variable ∆ni is measurable with respect to FK(i+1)
. The functionals φn, φ are additive at points of
the type j
. Applying (3.3) and condition 1 of the Theorem, we obtain the following relation
Mn−1∑
n − φ
Mn−1∑
K(i+1)
n − φ
K(i+1)
Mn−1∑
K(i+1)
K(i+ 1)
K(i+1)
K(i+ 1)
(3.9) ≤ Kδn
∣∣f0,Tn
∣∣+ E
Mn−1∑
K(i+1)
K(i+ 1)
K(i+1)
K(i+ 1)
The first term in (3.9) tends to zero. The second term in (3.9) is estimated in the same way with the second
term in (3.5), with one necessary change. We cannot apply Lemma 6.4 [1] in order to estimate the second
moment φ0,Tn , therefore this estimate must be obtained separately. This can be done in a following way:
E(φ0,Tn )
2 = E
(∆ni )
2 + 2E
1≤i<j≤Mn
∆ni ∆
j = E
(∆ni )
2 + 2E
1≤i≤Mn
∆ni φ
(∆ni )
2 + 2E
1≤i≤Mn
∆ni [φ
iK/n,(i+1)K/n
n + φ
(i+1)K/n,T
n ] ≤
(∆ni )
2 + 2KδnE
1≤i≤Mn
∆ni + 2E
1≤i≤Mn
∥∥f0,Tn
(3.10) ≤
(2K + 1)δn + 2‖f0,Tn ‖
n ≤ (2K + 1)δn
∥∥f0,Tn
∥∥+ 2
∥∥f0,Tn
∥∥2 ,
all transitions here are analogous to those given above, and thus are not discussed in details. Repeating literally
the estimates for the second term in (3.5), we obtain the estimate
(3.11) lim sup
Mn−1∑
n − φ
∥∥f0,T
∥∥G(f, γ, T ) +
∥∥f0,T
∥∥2√2γ.
It follows from (3.8),(3.11) that lim sup
[2Σn2 ] ≤ 4
∥∥f0,T
∥∥G(f, γ, T ) + 4
∥∥f0,T
∥∥2. This, combined with the
estimate lim sup
[Σn1 ] ≤ 0 proved before, provides the needed statement. The lemma is proved.
Now, we can complete the proof of the convergence of finite-dimensional distributions of φn to those of φ.
In order to shorten notation we consider the one-dimensional distributions only; in general case considerations
are completely the same.
Take arbitrary s, t, s < t. In order to prove weak convergence φs,tn (Xn) to φ
s,t(X), it is sufficient to show
that, for arbitrary bounded Lipschitz function g,
(3.12) lim sup
∣∣Eg(φs,tn (Xn))− Eg(φs,t(X))
∣∣ = 0.
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 9
Let g be fixed, consider a pair of processes X̂n, X̂
n, corresponding (in a sence of Definition 1) to T = t and
given positive γ. By construction, φs,tn (Xn)
=φs,tn (X̂n), φ
s,t(X)
=φs,t(X̂n). Applying Lemma 1, we obtain
lim sup
∣∣Eg(φs,tn (Xn))− Eg(φs,t(X))
∣∣ ≤ lim sup
∣∣∣g(φs,tn (X̂n))− φs,t(X̂n)
∣∣∣ ≤
≤ Lip(g) lim sup
∣∣∣φs,tn
− φs,t
)∣∣∣ ≤ 2Lip(g)
‖f0,t‖G(f, γ, t) +
2γ ‖f0,t‖2,
here Lip(g) denotes the Lipshits constant for g. Condition 3 of the Theorem provides that G(f, γ, t) → 0, γ →
0+. Therefore, since γ > 0 is arbitrary, (3.12) follows from the estimate given above.
Since sups,t |ψs,tn − φs,tn | ≤ δn → 0, the finite-dimensional distributions of φn converge to corresponding
distributions of φ. Thus, the only thing left to show in order to prove the Theorem, is that the family of
distributions of ψn is dense in C(T,R
+). The values of the functions ψn at the point s, t differ from the values
at the closest knots of partition s∗, t∗ ∈ 1nZ+ at most on δn, and ψn are monotone as the functions of the time
variables. Hence, in order to prove the required statement, it is sufficient to show that, for arbitrary sequence
of partitions
Sn = {sn0 = 0 < sn1 < · · · < snk < . . . } ⊂ 1nZ+, n ∈ N
with σn ≡ maxk(snk −snk−1) → 0, n→ +∞
and arbitrary T ∈ R+,
k:sk≤T
snk−1,s
→ 0, n→ +∞.
Set γn,T = sup0<t−s<σn,t<T ‖f
n ‖, note, that γn,T → 0, n→ +∞ due to continuity of the limit characteristics
f and uniform convergence of fn ⇒ f . In the same way with (3.10) we obtain the estimate
(3.13) E
snk−1,s
≤ {(2K + 1)δn + 2γn,T }Eφ
snk−1,s
Summing up the estimates (3.13) w.r.t. k (recall that φs,tn = ψ
n when s, t ∈ 1nZ+), we obtain
k:sk≤T
snk−1,s
≤ {(2K + 1)δn + 2γn,T } ‖f0,Tn ‖ → 0, n→ +∞,
what was to be proved. The theorem is proved.
Let us make one remark. For the random walks, the Skorokhod’s method is well known, allowing one to
reduce the investigation of the sums of the type (3.1) to the case L = 1. This method can be applied in the
context of current paper, also. Namely, the reasoning, similar to the one used in the proof of Theorem 1,
Chapter 5.3 [2], provides the following result (the proof is omitted).
Proposition 1. Let the sequence of functionals {φn = φn(Xn)} of the type (3.1) be given, and, for every n,
the process Xn possesses the Markov property at the time moments
, i ∈ Z+. Consider the functionals
n (Xn)
k:s≤k/n<t
, 0 ≤ s < t,
where
Ψn,k(x) ≡ E
k + 1
, . . . , Xn
k + L− 1
)) ∣∣∣Xn
, x ∈ X.
Let functions Fn(·) be non-negative and satisfy condition 1 of Theorem 1, then the functionals φs,tn have a
limit distribution if and only if the functionals χs,tn have a limit distribution, and the limit distributions of the
functionals φs,tn , χ
n are equal as soon as they exist.
It is worth to note that the Proposition 1 does not lead to simplification of the initial problem in the context
of current paper. The number of values of process Xn, contained in a one summand for the functional φn (that
is, number L), is not involved significantly into the proof of the main theorem. We will see later that the main
problem in the application of the Theorem consists in verification of the condition 2 of uniform convergence
of characteristics; the characteristics of the functionals φn and χn, obviously, coincide.
In the following two chapters, the examples of application of Theorem 1 are given.
10 YURI N.KARTASHOV, ALEXEY M.KULIK
4. The local time of a random walk at a point.
Let the processesXn be constructed w.r.t. one-dimensional random walk that belongs to the normal domain
of attraction of an α-stable law, α ∈ (1, 2] (see Examples 1,2). We assume the centering sequence an to be
equal to zero, and set the random broken lines Xn by equality (2.4).
Consider, for arbitrary z∗ ∈ R, the functionals φn = φn(Xn) of the type (3.1) with L = 2, Fn(x, y) =
|y−x|
1I(x−z∗)(y−z∗)<0 +
(1Ix 6=z∗,y=z∗ + 1Ix=z∗,y 6=z∗)
. For every s < t, s, t ∈ { j
, j ∈ Z+}, with probability 1
the following equality takes place
(4.1) φs,tn (Xn) = lim
1IXn(r)∈(z∗−ε,z∗+ε)\{z∗} dr, 0 ≤ s < t.
Therefore the functionals φn can be naturally interpreted as the censored local times for the broken lines Xn
at the point z∗ (the censoring operation consists in removing horizontal parts of the broken lines). Theorem
3.1 allows one to obtain the following limit result.
Proposition 2. Let the distribution of the jump ξ1 of the random walk be concentrated on Z and aperiodic.
Then the conditions of Theorem 1 hold true and φs,tn (Xn) converge by distribution to φ
s,t(X) = P (ξ1 6=
0) · Ls,t(X, z∗), where L(X, z∗) is the local time of the limit α-stable process X at the point z∗.
Proof. The condition for Xn to provide Markov approximation for X holds true (see Example 2). Condition
1 of the Theorem holds with δn = 2n
−1 since either the increment of the process Xn in the neighboring knots
is equal to zero or the absolute value of this increment is not less then n−
α . Let us show that the characteristics
of functionals φn converge uniformly to the function
(4.2) f s,t(x) = P (ξ1 6= 0)
∫ t−s
pr(z∗ − x) dr,
where pr(·) is the density of distribution X(r) under condition X(0) = 0; this provides conditions 2,3 of the
Theorem.
In order to shorten notation we take z∗ = 0. Denote P
i = P (Sk = i), Pj = P
j = P (ξ1 = j), i, j ∈ Z. We
have that
f s,tn (x) = n
j 6=0
i∈(xn
α −j,xn
P ki +
+ P k
notation i ∈ (a, b) in the case a > b means that b < i < a. Using the appropriate version of the Gnedenko’s
local limit theorem (see [18], Theorem 4.2.1), one can write
(4.3) εk ≡ sup
∣∣∣∣k
αP ki − p1
)∣∣∣∣→ 0, k → +∞.
Hence
f s,tn (x) =
j 6=0
i∈(xn
α −j,xn
(4.4) +
α − j
+ Ξn(x),
where
(4.5) |Ξn(x)| ≤
[nt]∑
and Ξn ⇒ 0, n→ +∞ via the Toeplitz’s theorem.
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 11
The density p1 is uniformly continuous over R, hence, using the same arguments, one can show that, up to
a summand that uniformly converges to zero, the value of f s,tn (x) equals
j 6=0
i∈(xn
α −j,xn
(4.6) =
P (ξ1 6= 0)
P (ξ1 6= 0)
in the latter equality, we have used that the process X is self-similar, that is, pr(x) = r
α p1(r
αx), r > 0.
The sum in the right hand part of (4.6) is exactly the integral sum for the integral in the right hand part of
(4.2), the functions {pr(·), r ≥ r0} are uniformly continuous for arbitrary r0 > 0 and supx pr(x) ≤ Cr−
α . This
immediately provides the required uniform convergence of fn to f . The proposition is proved.
The similar result can be proved for ξk with non-lattice distribution, for which there exists a bounded
distribution density of Sn0 for some n0 (the proof is omitted).
The result of Proposition 2 and its analog for non-lattice random walks is not essentially new; one can obtain
it applying either Proposition 1 and the technique, exposed in §§III.2, III.3 [3], or the reasonings, similar to
those used in the proof of Theorem 3 [9]. Our reason to give this example consists, on the one hand, in
describing the way of application of Theorem 1 in a simple situation where an appropriate local limit theorem
is available, and on the other hand, in emphasizing the following interesting fact, that is not reflected in a
literature available for us. For a ”good” random walks (lattice or essentially non-lattice), their local times at
the point, defined by the natural equality (4.1), converge by distribution exactly to the local time of the limit
process at the same point, as soon as the broken lines corresponding to the random walk does not contain
horizontal sections.
5. Difference approximations of diffusion processes.
Consider the sequence {Zn} of difference approximations of diffusion process Z (see Example 3, equalities
(2.5),(2.6)). The sequence {Zn} provides Markov approximation for Z, that allows one to apply Theorem 1
while considering the question on the limit behavior of the functionals of type (3.1) for {Zn}.
One of possible way to proceed here is to apply the estimates based on an appropriate local limit theorem,
like it was made in the previous chapter. In order to make this paper reasonably short, we do not give the
detailed exposition of this subject here (see the separate paper [19]). In this chapter, we give a simple corollary
of Theorem 1, that provides invariance principle for certain ”canonic” additive functionals, that are related to
the Doob’s decomposition of |Zn(·)|.
Let us consider the objects introduced in Example 3 with m = d = 1 and a, b, {ξn} satisfying conditions
introduced there. Put
(5.1) φs,tn (Zn) ≡
k∈(sn,tn]
Zn( k−1n )Zn(
Zn( k−1n )=0
ψn are corresponding broken lines.
Proposition 3. The processes ψn converge by distribution in C(T,R) to the local time
φs,t ≡ lim
1I|Z(r)|<εb
2(Z(r)) dr
of the diffusion process Z at the point 0.
Proof. Since the diffusion coefficient is non-degenerate, Z possesses continuous transition density pt(x, y)
and the standard estimate supx pt(x, y) ≤
C(y)√
holds true. This implies existence of the local time of Z at
12 YURI N.KARTASHOV, ALEXEY M.KULIK
the point 0. This local time is a W -functional with the characteristics f0,t(x) = b2(0)
ps(x, 0) ds, that is,
condition 3 of Theorem 1 holds. Straightforward calculations prove the equality
(5.2) |Zn(t)| − |Zn(s)| = φ0,tn (Zn) +
[nt]−1∑
where s ∈ 1
Z+, sign (0) = 0. This provides that
f s,tn (x) = E [|Zn(t)||Zn(s) = x]− |x| −
[nt]−1∑
sign (Zn
) ∣∣∣Zn(s) = x
Processes Zn converge weakly to Z, function a(x)sign (x) has unique jump at point x = 0 and P (Z(r) = 0) = 0
for every r > 0. Hence the standard reasonings provide that (we omit the details)
(5.3) f s,tn (x)⇒
E [|Z(t)||Z(s) = x]− |x| − E
a(Zr)sign (Zr) dr
∣∣∣Z(s) = x
This proves condition 2 of Theorem 1, since the right hand side of (5.3) is exactly the characteristics of the
local time φ due to Ito-Tanaka formula.
In order to provide condition 1, let us, for a while, suppose additionally that the coefficients a, b are bounded.
We apply the standard ”cutting” procedure: on each step of approximation, together with the process Zn,
we consider the process Z̃n, constructed by the same scheme from a sequence of i.i.d.r.v. {ξ̃n}, satisfying
conditions ‖ξ̃n‖ ≤ n
2 and ξn = ξ̃n for ‖ξn‖ ≤ n
2 . For such Z̃n, condition 1 of theorem holds with
δ(Fn) ≤ n−1 max
|a(x)| + n
|b(x)|,
and the other conditions of theorem for Z̃n remain to hold true. This proves the statement of Proposition 3
for {Z̃n}. On the other hand, for arbitrary T ∈ R+
Zn|[0,T ] 6= Z̃n|[0,T ]
1− 2+δ
= o(1), n→ +∞,
and therefore the statement of Proposition 3 holds true for {Zn}. At last, the additional assumption that the
coefficients a, b are bounded, can be removed via a standard localization procedure. The proposition is proved.
Remark 6. Let a = 0, b = 1, P (ξk = ±1) = 12 (that is, Zn corresponds to the Bernoulli’s random walk), then
functional (5.1) can be represented at the form
(5.4) φ̃s,tn =
# {k ∈ [sn, tn) : Zn(k) = 0} .
The functional (5.4) is widely used in a literature as the difference analogue of the local time at the point
zero for lattice random walks. Proposition 3 shows that the functional (5.1) is a natural difference analogue of
the local time both for random walks and, more generally, for difference approximations of diffusion processes
without any restrictions on the distribution of the sequence {ξk}.
6. Invariance principle for additive functionals of Markov chains
In previous two chapters we have considered more or less particular examples illustrating possible ways to
provide the main condition of Theorem 1 (condition 2). In this chapter we introduce general sufficient condition
of weak convergence of additive functionals, constructed on the sequence of Markov chains, that is formulated
in terms of the transition probabilities of these chains and the functions Fn involved in representation (3.1).
This condition is obtained as an application of Theorem 1, and the main assumption here is that the local limit
theorem (condition 4 of Theorem 2 below) takes place in an appropriate form. For recurrent Markov chains
this condition, together with a natural condition of weak convergence of ”symbols” of additive functionals
(exact formulation is given below), is sufficient for convergence of characteristics, and the estimates here are
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 13
similar to (4.4) – (4.6) (see Theorem 3 below). For transient chains these estimates are not powerful enough,
since in this case the estimate (4.5) does not provide that Ξn is negligible. One possible way to overcome this
difficultly is to apply a more strong version of local limit theorem, for instance, to claim explicitly the rate
of convergence εk → 0 in (4.3). Such an approach restricts the range of possible applications, therefore we
introduce another one, that is concerned with a uniform condition on the modulus of continuity of processes
Xn (condition 5 of Theorem 2) and a ”dimensional” condition on the symbols of functionals (condition 6),
adjusted one with another with an appropriate way (condition 7).
We assume that a σ-finite measures ν, νn on X are given such that
P (X(t) ∈ dy|X(s) = x) = pt−s(x, y)ν(dy), 0 ≤ s < t, x, y ∈ X,
∈ dy|Xn
= pn,k(x, y)νn(dy), i ∈ Z+, k ∈ N, x, y ∈ X.
The measurable functions pt, pn,k are interpreted as the transition probability densities for X,Xn w.r.t. mea-
sures ν, νn.
We assume the W -functional φ = φ(X) with the characteristics f to be given. It is known (see [1], Chapter
6) that
s,t = L2 − lim
0,ε(X(r)) dr,
and therefore
f s,t(x) = lim
pr(x, y)
f0,ε(y)ν(dy) dr.
We assume that, as ε→ 0+, the measures 1
f0,εdν converge weakly (i.e., on every bounded continuous function)
to a finite measure µ, the characteristics f can be represented in the form
(6.1) f s,t(x) =
∫ t−s
pr(x, y)µ(dy) dr, and
pr(x, y)µ(dy)
dr < +∞, T ∈ R+.
We also consider the sequence of the functionals φn = φn(Xn) of the type (3.1) with L = 1 and Fn =
(the case L > 1 can be considered similarly and we omit it in order to shorten notation). The characteristics
of φn has the form
f s,tn (x) =
pn,k(x, y)µn(dy), 0 ≤ s < t, x ∈ X,
where µn(dy) ≡ gn(y)νn(dy) are the ”symbols” of the functionals φn.
Theorem 2. Assume the following conditions to hold true.
(1) Trajectories of the processes Xn are continuous, and the sequence {Xn} possesses Markov approxima-
tion of X.
(2) 1
supx gn(x) → 0, n→ +∞.
(3) For arbitrary t0 > 0, the function (t, x, y) 7→ pt(x, y) is uniformly continuous on [t0,+∞) × X2, and
for arbitrary y ∈ X
x 6∈B(y,R)
pt(x, y) → 0, R → +∞
(here and below B(x,R) ≡ {x ∈ X|ρ(x, y) < R}). Furthermore, there exist constants γ > 0, Cγ > 0
such that
x,y∈X
pt(x, y) ≤ Cγt−γ , t > 0.
(4) There exist sequences {αn}, {βn} ⊂ R+ tending to zero, such that
x,y∈X
|pn,k(x, y)− p k
(x, y)| ≤ (αn + βk)
, n, k ∈ N.
14 YURI N.KARTASHOV, ALEXEY M.KULIK
(5) There exist constants δ > 0, Cδ > 0 such that, for arbitrary T > 0,
x∈X,n∈N
t,s∈[0,T ],|t−s|≥ 1
ρ(Xn(t), Xn(s))
|t− s|δ
]Cδ ∣∣∣X(0) = x
 < +∞.
(6) Measures µn are finite and converge weakly to measure µ. There exist constants θ > 0, Cθ, cθ > 0 such
µn(B(x,R)) ≤ CθRθ, x ∈ X, n ∈ N, R > cθn−δ
(note that the latter condition provides that µ(B(x,R)) ≤ CθRθ, x ∈ X, R > 0).
(7) The constants γ, δ, θ, Cδ satisfy the relations
δθ + 1 > γ, Cδ > 2θ + 2.
Then (Xn, ψn(Xn)) ⇒ (X,φ(X)) in a sense of convergence in distribution in C(R+,X)×C(T,R+) (ψn are
the random broken lines corresponding to the functionals φn).
Proof. In order to prove the Theorem, it is sufficient to show that, for every T ∈ R+,
(6.2) f s,tn (x) ⇒
s≤t≤T,x∈X
f s,t(x), n→ +∞.
Indeed, the sequence {Xn} provides Markov approximation for X (condition 1), and condition 1 of Theorem 1
is provides by condition 2 of Theorem 2. Having (6.2) proved, we provide condition 2 of Theorem 1. Condition
3 of this theorem is provided by (6.1) and uniform continuity of the density p. At last, condition 5 of Theorem
2 provides weak convergence of Xn to X in C(R
+,X), that allows one to apply Theorem 1 and Remark 5.
Before proving (6.2), let us make some auxiliary estimates. Denote
δ,n(Xn) = sup
v,w∈[s,t],|v−w|≥ 1
ρ(Xn(v), Xn(w))
|v − w|δ ,
n,A =
Xn(r) ∈ B(Xn(s), A(r − s)δ), r ∈
note that {Hs,tδ,n(Xn) < A} ⊂ D
n,A. Also denote α = maxn αn, β = maxk βk, δn =
supx |gn(x)|
, B1 =
maxn δn, B2(T ) =
Cθ(Cγ+α+β)
1+δθ−γ T
1+δθ−γ. For arbitrary A > cθ, T ∈ R+, consider the functionals φs,tn,A =
φs,tn 1IHs,t
(Xn)<A
, s ≤ t ≤ T .
Lemma 2. 1. E
n,A|Xn(s) = x
≤ B1 +B2(T )Aθ.
|Xn(s) = x
≤ 3B1(B1 +B2(T )Aθ) + 2(B1 +B2(T )Aθ)2.
3. Let p ∈
1, 2Cδ−2
Cδ+2θ
(recall that 1 < 2Cδ−2
Cδ+2θ
due to condition 7 of the Theorem). Then
x∈X,n∈N,s≤t≤T
)p |Xn(s) = x
< +∞.
Proof. Using condition 4 of the Theorem and then condition 6, we obtain, for t, s ∈ 1
Z+, the estimate
n,A|Xn(s) = x
φs,tn 1IDs,t
|Xn(s) = x
gn(x)
n(t−s)−1∑
x,A( kn )
pn,k(x, y)µn(dy) ≤
≤ δn +
Cγ + α+ β
n(t−s)−1∑
≤ δn +
Cγ + α+ β
n(t−s)−1∑
)γ−δθ
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 15
that immediately proves the first statement of the Lemma. The second statement can be obtained from the
first one via the estimate similar to (3.10) with the use of the inequality
1IHs,t
(Xn)<A
≤ 1IHs,r
(Xn)<A1IHr,t
(Xn)<A
that holds true for arbitrary r ∈ (s, t).
Applying statement 2 and Hölder inequality we obtain
φs,tn
)p |Xn(s) = x
φs,tn
(Xn)∈[N−1,N)|Xn(s) = x
(φs,tn )
21IHT
(Xn)<N
|Xn(s) = x
P (HTδ,n(Xn) ≥ N − 1)
] 2−p
B3(T ) +B4(T )N
2 ·B5(T ) [(N − 1) ∨ 1]−
here and below Bi(T ), i = 3, 4, . . . denotes a constant, that can be expressed explicitly through T and the
constants introduced in the formulation of the Theorem, but an explicit expression is not needed in our
consideration. Since θp− 2−p
Cδ < −1 by the choice of p, this proves the statement 3. The lemma is proved.
Let us proceed with the proof of (6.2). Choose non-increasing Lipschitz function Ψ : R+ → [0, 1] such that
Ψ([0, 1]) = {1},Ψ([2,+∞)) = {0}, and set
Ψr(x, y) = Ψ(r
−1 · ρ(x, y)), r > 0, x, y ∈ X, Ψ0 ≡ 1.
Note that, for arbitrary r0 > 0, the function (r, x, y) 7→ Ψr(x, y) is uniformly continuous on [r0,+∞)× X2.
For fixed s ≤ t ≤ T,A ∈ R+ we decompose φs,tn as φs,tn = η
n,A + ζ
n,A, where
n,A =
A( kn−s)
Xn(s), Xn
We have that, on the set D
n,A, for k such that s ≤ kn < t,
Xn(0), Xn
A( kn−s)
Xn(s), Xn
hence {φs,tn = η
n,A} ⊃ D
n,A and
(6.3) {ζs,tn,A 6= 0} ⊂ Ω\D
n,A ⊂ {H
δ,n ≥ A}.
Let p be the same as in statement 3 of Lemma 2. Then it follows from (6.3) and inequality 0 ≤ ζs,tn,A ≤ φs,tn
(6.4) E
n,A|Xn(s) = x
(φs,tn )
p|Xn(s) = x
δ,n ≥ A|Xn(s) = x)
] p−1
p ≤ B6(T )A−δ
Similarly, one can write φs,t = η
A + ζ
A , where η
ΨA(r−s)δ(X(s), X(r))dφ
s,r ,
(6.5) E
A |X(s) = x
≤ B6(T )A−δ
We have ∣∣∣E
n,A|Xn(s) = x
A |X(s) = x
]∣∣∣ =
∣∣∣∣∣∣
gn(x)
]n(t−s)[−1∑
pk,n(x, y)ΨA( kn )
δ (x, y)µn(dy)−
∫ t−s
pr(x, y)ΨArδ(x, y)µ(dy) dr
∣∣∣∣∣∣
≤ δn +∆1n(x,A, s, t) + ∆2n(x,A, s, t) + ∆3n(x,A, s, t),
16 YURI N.KARTASHOV, ALEXEY M.KULIK
where ]z[≡ min{N ∈ Z, N ≥ z},
∆1n(x,A, s, t) =
∣∣∣∣∣∣
]n(t−s)[−1∑
[pk,n(x, y)− p k
(x, y)]Ψ
A( kn )
δ (x, y)µn(dy)
∣∣∣∣∣∣
∆2n(x,A, s, t) =
∣∣∣∣∣∣
]n(t−s)[−1∑
(x, y)Ψ
A( kn)
δ(x, y)µn(dy)−
∫ t−s
pr(x, y)ΨArδ(x, y)µn(dy) dr
∣∣∣∣∣∣
∆3n(x,A, s, t) =
∫ t−s
pr(x, y)ΨArδ (x, y)[µn(dy)− µ(dy)] dr
∣∣∣∣ .
Denote ∆in(A, T ) = supx∈X,s≤t≤T ∆
n(x,A, s, t), i = 1, 2, 3. Since Ψr(x, y) ∈ [0, 1] and {Ψr(x, y) 6= 0} ⊂ {y ∈
B(x, 2r)},
∆1n(A, T ) ≤
]nT [−1∑
[αn + βk]
x, 2A
(6.6) ≤ Cθ(2A)θ ·
]nT [−1∑
[αn + βk]
)δθ−γ
→ 0, n→ +∞
by Toeplitz theorem.
The function (r, x, y) 7→ pr(x, y)Ψr(x, y) is uniformly continuous over [r0,+∞)×X2 for any r0 > 0, therefore
an estimate analogous to (6.6) provides that
x∈X,s≤t≤T
∣∣∣∣∣∣
]n(t−s)[−1∑
k=[r0n]+1
(x, y)Ψ
A( kn)
δ (x, y)µn(dy)−
∫ t−s
pr(x, y)ΨArδ(x, y)µn(dy) dr
∣∣∣∣∣∣
(note that maxn µn(X) < +∞ since µn weakly converge to µ). The same arguments provide that
lim sup
∆2n(A, T ) ≤
≤ lim sup
[r0n]∑
 = B7(A, T )(r0)δθ−γ+1.
Since r0 > 0 is arbitrary, this implies that
(6.7) ∆2n(A, T ) → 0, n→ +∞.
At last, the weak convergence of µn to µ and the first part of condition 3 provide that, for every t,
In(A, t) ≡ sup
pt(x, y)ΨArδ(x, y)[µn(dy)− µ(dy)]
∣∣∣∣→ 0, n→ +∞.
Since In(A, t) ≤ Cγt−γ · Cθ(2Atδ)θ, the Lebesgue theorem of dominated convergence provides that
(6.8) ∆3n(A, T ) → 0, n→ +∞.
It follows from the estimates (6.4) – (6.8) that
lim sup
x∈X,s≤t≤T
∣∣f s,tn (x)− f s,t(x)
∣∣ ≤ 2B6(T )A−δ
p , A > cθ.
Taking A→ +∞ we obtain (6.2), that completes the proof. The theorem is proved.
In order to make our exposition complete, let us formulate a version of Theorem 2 for the recurrent case.
Theorem 3. Let conditions 1 – 4 of Theorem 2 hold true and γ < 1. Also let µn converge weakly to µ, and
Xn converge to X by distribution in C(R
+,X).
Then (Xn, ψn(Xn)) ⇒ (X,φ(X)) in a sense of convergence in distribution in C(R+,X)× C(T,R+).
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 17
The proof, with slight changes, repeats the proof of Theorem 2, and is omitted. Note that, under conditions
of Theorem 3, the convergence of finite-dimensional distributions of φn can be provided with the use of the
technique, mentioned in the Introduction, that was proposed by I.I.Gikhman and is based on studying of limit
behavior of difference equations for characteristic functions of φs,tn (see for instance the proof of Theorem 3
[9]). In the transient case, treated in Theorem 2, this technique can not be applied since the uniform estimates,
analogous to (4.4) – (4.6), are not available in this case.
At last, let us give an example of application of Theorem 2. To shorten exposition we omit the proofs of
some technical details.
Example 4. Let X = Rd, d ≥ 2 and Xn, X be as in Example 1. Let K ⊂ Rd be a compact set, for which the
surface measure λK is well defined by equality
λK(·) ≡ w − lim
λd(· ∩Kε)
λd(Kε)
where w − lim means the limit in the sense of weak convergence of measures, λd is Lebesgue measure on Rd,
Kε ≡ {x|dist(x,K) ≤ ε}. Assume that the condition
(6.9) λd(Kε) ≥ const · εβ, ε > 0
holds with some β < 2. In particular, the set K can be smooth (or, more generally, Lipschitz) surface of
codimension 1 or fractal with its Haussdorf-Besikovich dimension greater then d− 2.
It not hard to verify that µ ≡ λK is W -measure (see [1], Chapter 8.1 for the terminology), and therefore
corresponds to some W -functional φ of the Wiener process X . This functional is naturally interpreted as the
local time of Wiener process at the set K, and can be written as φs,t =
λK(Xr) dr.
We consider the functionals φn(Xn) of the form
k∈[sn,tn)
1I{Xn( k
)∈K 1√
and apply Theorem 2 in order to prove convergence of the distributions in C(R+,Rd)× C(T,R+)
(6.10) (Xn, ψn(Xn)) ⇒ (X,φ(X))
(ψn are the broken lines corresponding to φn).
Condition 1 holds true due to Example 1, condition 2 is provided by condition (6.9) (by this condition,
supx gn(x) ≤ const · n
2 ). Condition 3 holds with pt(x, y) = (2πt)
2 exp{− 1
‖y− x‖2
} and γ = d
. Condition
(6.9) implies condition 6 with θ = d− β.
We assume that the random walk Sn is either aperiodic on some lattice hZ
d or is strongly non-lattice (i.e.,
Sn0 has bounded distribution density for some n0). Under this assumption, condition 4 holds with αn ≡ 0,
ν = λd and νn equal to counting measures on
d in lattice case or λd in strongly non-lattice case.
It remains to provide conditions 5, 7. We have γ−1
= d−2
2(d−β) <
. Choose some δ ∈
and consider
α > 0 such that
> δ and α > 2θ + 2. Suppose that
(6.11) E‖ξk‖αRd < +∞.
Then applying Burkholder inequality we obtain that
(6.12) E‖Xn(t)−Xn(s)‖αRd ≤ const · |t− s|
2 , |t− s| ≥ 1√
, x ∈ Rd.
Repeating the standard proof of the Kolmogorov’s theorem on existence of continuous modification (see, for
instance [20], p. 44,45), one can deduce from (6.12) that, for ς < α, ϑ <
t,s∈[0,T ],|t−s|≥ 1
‖Xn(t)−Xn(s)‖Rd
|t− s|ϑ
< +∞.
18 YURI N.KARTASHOV, ALEXEY M.KULIK
Finally, choosing ϑ = δ, ς > 2θ + 2 we obtain that conditions 5,7 hold with Cθ = ς . Applying Theorem 2,
we obtain weak convergence (6.10) under additional moment condition (6.11). One can remove this condition
using the ”cutting” procedure, described in the proof of the Proposition 3.
Let us remark that for the lattice random walks the result, exposed in Example 4, was obtained in [5] by a
technique, essentially different from the one proposed here. Convergence (6.10) in continuous case, as far as it
is known to authors, is a new result.
References
[1] Dynkin E.B. Markov processes, M.: Fizmatgiz, 1963 (in Russian).
[2] Skorokhod A.V., Slobodeniuk M.P. Limit theorems for random walks, Kiev: Naukova dumka, 1970 (in Russian).
[3] Borodin A.N., Ibragimov I.A. Limit theorems for the functionals of random walks, Proc. of the Mathematical Institute of R.
Acad. Sci, vol. 195. St.-P.: Nauka, 1994 (in Russian).
[4] Revesz P. Random walk in random and nonrandom environments, World Sci. Publ. Co., Inc., Teaneck, NJ, 1990.
[5] Bass R.F., Khoshnevisan D. Local times on curves and uniform invariance principles, Prob. Theory Rel. Fields 92, 1992, p.
465 – 492.
[6] Cherny A.S., Shiryaev A.N., Yor M. Limit behavior of the ”horizontal-vertical” random walk and some extensions of the
Donsker-Prokhorov invariance principle. Probability theory and its applications, vol. 47, 3, 2002, p. 498 – 517.
[7] Gikhman I.I. Some limit theorems for the number of intersections of a boundary of a given domain by a random function,
Sci. notes of Kiev Un-ty, 1957, vol. 16, 10, p. 149 – 164 (in Ukrainian).
[8] Gikhman I.I. Asymptotic distributions for the number of intersections of a boundary of a domain by a random function,
Visnyk of Kiev Un-ty, serie astron., athem and mech., 1958, v. 1, 1, p. 25 – 46 (in Ukrainian).
[9] Portenko N.I. Integral equations and limit theorems for additive functionals of Markov processes, robability theory and its
applications, 1967, v. 12, 3, p. 551 – 558 (in Russian).
[10] Portenko N.I. The development of I.I.Gikhman’s idea concerning the methods for investigating local behavior of diffusion
processes and their weakly convergent sequences, Probab. Theory and Math. Stat., 1994, 50, p. 7 – 22.
[11] Kulik A.M. Markov Approximation of stable processes by random walks, vol.12(28) 2006, .1-2, p. 87 – 93.
[12] Feller W. An introduction to probability theory and its applications, Vol II, M.: Mir, 1984 (Russian, translated from
W.Feller, An introduction to probability theory and its applications, John Wiley & Sons, New York, 1971).
[13] Skorokhod A.V. Studies in theory of stochastic processes, Kiev, Kiev Univ-ty publishing house, 1961 (in Russian).
[14] Jacod J., Shiryaev A. Limit theorems for stochastic processes,Springer, Berlin, 1987.
[15] Kurtz T.G., Protter Ph. Weak limit theorems for stochastic integrals and SDE’s, Annals of Probability, 1991, vol. 19, 3, p.
1035 – 1070.
[16] Yamada T., Watanabe S. On the uniqueness of solutions of stochastic differential equations, J. Math. Kyoto Univ., 1971,
vol. 11, p. 156 – 167.
[17] Androshchuk T.O., Kulik A.M. Limit theorems for oscillatory functionals of a Markov process. Theory of stochastic proc-
cesses, vol. 11(27), p. 3 – 13.
[18] Ibragimov I.A., Linnik Yu.V. Linnik, Independent and stationary related variables, M.: Nauka, 1965 (in Russian).
[19] Kulik A.M. Difference approximation for local times of multidimensional diffusions, arXiv:math/0702175
[20] Skorokhod A.V. Lections on theory of stochastic processes, Kyiv: Lybid, 1990 (in Ukrainian).
E-mail address: kulik@imath.kiev.ua
http://arxiv.org/abs/math/0702175
	1. Introduction
	2. Markov approximation.
	3. Main theorem
	4. The local time of a random walk at a point.
	5. Difference approximations of diffusion processes.
	6. Invariance principle for additive functionals of Markov chains
	References

  We consider a sequence of additive functionals {\phi_n}, set on a sequence of
Markov chains {X_n} that weakly converges to a Markov process X. We give
sufficient condition for such a sequence to converge in distribution,
formulated in terms of the characteristics of the additive functionals, and
related to the Dynkin's theorem on the convergence of W-functionals. As an
application of the main theorem, the general sufficient condition for
convergence of additive functionals in terms of transition probabilities of the
chains X_n is proved.

Introduction
Let a sequence of processes Xn = Xn(·) be given, converging in distribution (in some sense, e.g., in a
sense of convergence of finite-dimensional distributions, distributions in spaces C or D, etc.) to a limit process
X = X(·). Also let the family of functionals φn of the processes Xn be given. Assume that they are additive
in an appropriate sense with respect to time variable. The general question, considered in the present paper,
is what an information about the limit behavior of the distributions of functionals φn can be obtained in a
situation where the processesXn, X possess certain Markov properties. The starting point in our considerations
is provided by the comparatively simple, but important particular case of the problem outlined above, in which
all the processes Xn coincide. In this situation, φn are a functionals of the same process X , and if X is Markov
process and φn are W -functionals (see [1], Chapter 6), then their limit behavior, according to the well known
theorem by E.B.Dynkin ([1], Theorem 6.4), is determined by the limit behavior of their characteristics (that
is, their expectations).
In the present paper we consider the processes Xn that differ one from another. The class of sequences
of processes Xn, considered in the framework of our approach, contains sequences of Markov chains with
appropriately normalized time, embedded into C or D (for example, by means of standard operations of
linearization or construction of graduated processes), and weakly convergent to Markov process X . Important
partial case is provided by random broken lines (or random step functions) Xn, constructed by a random walk
in Rd and weakly convergent to a homogenous stable process X (particularly, to the Brownian motion).
We show that, under some structural assumption about processes Xn, X (the condition is that the sequence
{Xn} provides Markov approximation for the process X), the full analogue of the Dynkin’s theorem takes
place: if the characteristics of functionals φn converge weakly to the characteristics of W -functional φ of the
limit process X , then the distributions of φn converge to the distribution of φ. Our method of proof is based
on L2-estimates for the distance between additive functionals, similar to those given in Lemma 6.5 [1]. The
proof of these estimates is concerned with a preliminary construction of processes Xn, X on one probability
space in such a way, that the functionals φn, φ, associated initially with a different processes, are interpreted
as a functionals of one two-component process. The (some kind of) Markov property of the two-component
process is essential for the estimates, analogous to those given in Lemma 6.5 [1]; the structural assumption
mentioned above is just the claim for such a property to hold true in an appropriate form.
The method, proposed by authors, allows one to reduce the problem of studying of asymptotic behavior
of the distributions of additive functionals to a priori more simple problem of studying of their means. In
our opinion, it provides a good addition to the available methods of studying the limit behavior of additive
functionals both for the important partial case of random walks (we do not give the detailed review here,
2000 Mathematics Subject Classification. Primary 60J55; Secondary 60F17.
Key words and phrases. additive functional, characteristics of additive functional, Markov approximation.
http://arxiv.org/abs/0704.0508v1
2 YURI N.KARTASHOV, ALEXEY M.KULIK
referring the reader to monographs [2],[3],[4], papers [5],[6] and reviews there), and for general Markov chains.
Among the latter, it is necessary to mention the method that is based on the passing to the limit in the difference
equations that describe characteristic functions of additive functionals of Markov chains, and ascends to the
works of I.I.Gikhman at 50-ies (see [7],[8], also [9] and the survey paper [10]).
The structure of the article is following. In Chapter 2, we introduce the notion of Markov approximation
and give examples that illustrate it. In Chapter 3, the main theorem of the article is introduced and proved.
In Chapters 4,5, the two elementary examples of application of this theorem are given. In Chapter 6, the main
theorem is applied to the proof of a general sufficient condition for weak convergence of additive functionals,
set on the sequence of Markov chains, that is formulated in terms of transition probabilities of the chains.
2. Markov approximation.
Further we assume that the processes Xn, X are defined on R
+ and have a locally compact metric phase
space (X, ρ). We say that the process X possesses the Markov property at the time moment s ∈ R+ w.r.t.
filtration {Gt, t ∈ R+}, if X is adapted to this filtration and for each k ∈ N, t1, . . . , tk > s there exists a
stochastic kernel {Pst1...tk(x,A), x ∈ X, A ∈ B(Xk)} such that
(2.1) E[1IA((X(t1), . . . , X(tk)))|Gs] = Pst1...tk(X(s), A) a.s., A ∈ B(Xk).
The measure Pst1...tk(x, ·) has a natural interpretation as the finite-dimensional distribution of X at the points
t1, . . . , tk, conditioned by {X(s) = x}; we denote below Pst1...tk(x, ·) = P ((X(t1), . . . , X(tk)) ∈ ·|X(s) = x).
Remark 1. In some cases, (2.1) implies the following functional analogue of (2.1):
(2.2) E[1I·(X |∞s )|Gs] = E[1I·(X |∞s )|X(s)],
where X |∞s denotes the trajectory of the process X on the time interval [s,+∞), considered as an element of
appropriate functional space. For instance, if the Kolmogorov’s sufficient condition for existence of continuous
modification holds true both for unconditional and conditional distributions of X , then (2.2) holds with X |∞s
considered as an element of C([s,+∞),X).
Everywhere below we assume that the process X possesses the Markov property w.r.t. its canonic filtration
at every point s ∈ R+ and for the processesXn the same property holds true at every point of the type in , i ∈ Z+
(the choice of the denominator here is quite arbitrary; it is possible to put any expression N(n) → ∞, n→ ∞
instead of n, but we avoid to do this in order to shorten the notation).
The next definition is introduced in [11].
Definition 1. The sequence {Xn} provides Markov approximation for the process X , if for arbitrary γ >
0, T < +∞ there exists K(γ, T ) ∈ N and a sequence of two-componential processes {Ŷn = (X̂n, X̂n)}, defined
on another probability space, such that
(i) X̂n
=Xn, X̂
n d=X ;
(ii) the process Ŷn, together with the processes X̂n, X̂
n, possesses the Markov property at the points
iK(γ,T )
, i ∈ N w.r.t. filtration {F̂nt = σ(Ŷn(s), s ≤ t)};
(iii) lim sup
 sup
i≤ Tn
K(γ,T )
iK(γ,T )
, X̂n
iK(γ,T )
 < γ.
Remark 2. Condition (ii) implies that, for i, k ∈ N, t1, . . . , tk > iK(γ,T )n , (x, y) ∈ X
2, the marginal distributions
(Ŷn(t1), . . . , Ŷn(tk)) ∈ ·|Ŷn( iK(γ,T )n ) = (x, y)
are equal to P
(Xn(t1), . . . , Xn(tk)) ∈ ·|Xn( iK(γ,T )n ) = x
and P
(X(t1), . . . , X(tk)) ∈ ·|X
iK(γ,T )
respectively.
Let us give some examples that illustrate Definition 1.
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 3
Example 1. Let {ξk} be a sequence of i.i.d random vectors in Rd with E‖ξk‖2+δRd < +∞ for some δ > 0.
Assume {ξk} to have zero mean and identity for their covariance matrix. Let us introduce the sequence of
processes Xn (”random broken lines”) on R
(2.3) Xn(t) =
Sk−1√
+ (nt− k + 1)
− Sk−1√
, t ∈
k − 1
, k ∈ N,
where Sn =
k=1 ξk. Then Xn converge by distribution in C(R
+,Rd) to the Brownian motion X in Rd.
It is shown in [11] that the sequence {Xn} provides Markov approximation for the process X (part I. of
Theorem 1 [11]). On the other hand, in the same paper (part II. of the same Theorem) the following effect
is revealed. Let us denote by K(γ, T ) the minimal constant K(γ, T ) such that there exists a process Ŷn
satisfying conditions (i)-(iii) of Definition 1. Then, in all the cases except one trivial case ξk ∼ N (0, I), for
each fixed T > 0 the convergence K(γ, T ) → +∞, γ → 0+ takes place. In other words, while the accuracy of
approximation of the Brownian motion X by the random walk Xn becomes better (this accuracy is described
by the parameter γ), the Markov properties of the pair of processes (X,Xn) necessarily become worse (these
properties are characterized by K(γ, T )).
Example 2. Let {ξk} be i.i.d random variables, belonging to the normal domain of attraction for α-stable
distribution L, α ∈ (0, 2). By the definition, this means that
α [Sn − an] ⇒ L, an =
0, α ∈ (0, 1)
nEξ1, α ∈ (1, 2)
n2E sin ξ1
, α = 1
([12], Chapter XVII.5). In order to shorten the notation, we assume that an ≡ 0 and consider processes Xn
on R+ of the type
(2.4) Xn(t) = n
αSk−1 + (nt− k + 1)
αSk − n−
αSk−1
, t ∈
k − 1
, k ∈ N.
Then Xn converge by distribution in D(R
+) to the homogeneous process with independent increments X in
R, for which X(1)−X(0) d=L (we call such process a process an α-stable one).
It is shown in [11] (Theorem 2) that the sequence {Xn} provides Markov approximation for the process X .
Furthermore, in this situation, on the contrary to the previous example, K(γ, T ) = 1 for all γ, T . This means
that, in this case, the Markov properties do not become worse while accuracy of approximation improves.
Remark 3. The last example shows that the property of Markov approximation does imply, in general, the
convergence of distributions of the processes Xn to the distribution of X in C = C(R
+,X) even if Xn has
continuous trajectories. The same can be said about convergence in D = D(R+,X) (we omit the corresponding
example).
Let us remark that the approach, introduced in the present paper, is closely related to the Skorokhod’s
method of embedding of random walk into Wiener process by means of of appropriate sequence of stopping
moments ([13]), widely used in literature. The basic idea is the same: we have to construct two processes on
the same probability space, with the pair keeping Markov or martingale properties. However, the Skorokhod’s
method, while being quite efficient for one-dimensional random walks that approximate Wiener process, is
much less appropriate in a multi-dimensional situation or for stable domain of attraction. Examples 1 and 2
show that the claim for the Markov approximation to hold true is not restrictive, at least for all basic classes
of random walks with no regard to the dimension of the phase space or to the type of limit distribution.
The following example shows that the property of Markov approximation is ”stable” in the following sense.
This property is preserved under construction of a new pair (Zn, Z) from the pair (Xn, X), possessing this
property, in some regular way (e.g., as a solution of a family of stochastic equations).
4 YURI N.KARTASHOV, ALEXEY M.KULIK
Example 3. Let Xn, X be as in Example 1, functions a : R
m → Rm, b : Rd → Rd×m be Lipschitz and
b∗(x)b(x) > 0, x ∈ Rm (the sign ∗ denotes the operation of taking of the adjoint matrix). Define
(2.5) Zn
k + 1
, Zn(0) = z,
) ≡ [Xn(k+1n )−Xn(
)]. Then ([14], [15]) Zn converge by distribution in C(R
+,Rm) to the process Z,
defined by SDE
(2.6) dZ(t) = a(Z(t))dt + b(Z(t))dX(t), Z(0) = z,
where X is the Brownian motion in Rd. It is natural to call the sequence Zn the difference approximation of
the diffusion process Z.
Let us show that the sequence {Zn} provides Markov approximation for the process Z. For arbitrary γ, T ,
we construct a pair (X̂n, X̂
n), corresponding to processes Xn, X and satisfying conditions of Definition 1 (such
construction is possible due to Example 1).
Let us construct the processes Ẑn, Ẑ
n as the functionals of the processes X̂n, X̂
n by equalities (2.5),(2.6) with
Xn replaced by X̂n and X replaced by X̂
n (note that (2.6) has unique strong solution, hence this procedure
is correct). By the construction, the pair (Ẑn, Ẑ
n) satisfies condition (i) of Definition 1. It is easy to verify
that the Markov condition (ii) for the pair (X̂n, X̂
n) holds in the functional form (2.2) with Ŷn|∞s considered
as an element of C([s,+∞),Rd × Rd) (see Remark 1). Hence, the pair (Ẑn, Ẑn) also satisfies condition (ii) of
Definition 1. Let us write
∆(γ) = lim sup
 sup
i≤ Tn
K(γ,T )
iK(γ, T )
, Ẑn
iK(γ, T )
and show that
(2.7) ∆(γ) → 0+, γ → 0 + .
Note that (2.7) immediately implies Markov approximation: for arbitrary δ > 0 we chose, using (2.7), γ = γ(δ)
such that inequalities γ < δ and ∆(γ) < δ hold. Then the pair (Ẑn, Ẑ
n), constructed by the scheme described
above, satisfy Definition 1 with the constant γ replaced by δ (note that, under this construction, the value
K(δ, T ) ≡ KZ(δ, T ) for the pair (Ẑn, Ẑn) is expressed through the same value for the pair (X̂n, X̂n) by
KZ(δ, T ) = KX(γ(δ), T )).
Now assume that (2.7) does not hold, then there exist constant c > 0 and sequence γk → 0+, nk → +∞
such that
(2.8)
K(γk, T )
→ 0, P
 sup
i≤ Tnk
K(γk,T )
iK(γk, T )
iK(γk, T )
 > c.
Consider the sequence of four-component processes (X̂nk , X̂
nk , Ẑnk , Ẑ
nk). Every component of this sequence is
weakly compact in C(R+,Rd) or C(R+,Rm), hence the whole sequence is also weakly compact in C(R+,Rd×
d ×Rm ×Rm). Consider arbitrary limit point (X̂∗, X̂∗, Ẑ∗, Ẑ∗) (in a sense of convergence by distribution) of
this sequence. It follows from (2.8) that
(2.9) P (Z∗ 6= Z∗) > 0.
It follows from Theorem 2.2 [15] (see also Chapter 9.5 [14]) that the processes Z∗, Z
∗ satisfy SDE (2.6) with X
replaced by X∗, X
∗. However, the SDE (2.6) possesses the property of pathwise uniqueness (see [16]), and the
property (iii) of the pair (Xnk , X̂
nk) implies that the processes X∗, X
∗ coincide a.s. Therefore, the processes
Z∗, Z
∗ also coincide a.s., that contradicts to (2.9) and show that our assumption that ∆(γ) 6→ 0+, γ → 0+ is
false.
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 5
The examples given above show that the claim for the Markov approximation to hold is not very restrictive,
and is provided in a typical situations. On the other hand, this claim is strong enough to provide one the
opportunity to obtain an analog of the Dynkin’s theorem; this will be shown in the next chapter.
3. Main theorem
We consider the functionals of the type
(3.1) φs,tn (Y )
k:s≤k/n<t
k + 1
, . . . , Y
k + L− 1
, 0 ≤ s < t,
where the functions Fn(·) are nonnegative, L is a fixed integer. Together with the functionals φn, that are
”stepwise” functions w.r.t. every time variable, we consider random broken lines, related to these functions:
n = φ
n + (ns− j + 1)φ
n + (nt− k + 1)φ
n , s ∈
j − 1
, t ∈
k − 1
We interpret the random broken lines ψn as a random elements in space C(T,R
+), where T
= {(s, t)|0 ≤ s ≤
If process Y possesses Markov property w.r.t. the filtration, associated with this process, at the points of
the type s = i
, i ∈ Z+, then, for functional φn, its characteristic fn is naturally defined by the formula
(3.2) f s,tn (x)
= E[φs,tn (Y )|Y (s) = x], s =
, i ∈ Z+, t > s, x ∈ X.
Note that the functional (3.1) is a function of values of Y at finite number of time moments, thus the mean
value in (3.2) is well defined as the integral over the family {Pst1...tk(x, ·), t1, . . . , tk > s, k ∈ N} of conditional
finite-dimensional distributions of the process Y .
The main result of this chapter is given in the following theorem.
Theorem 1. Assume that there exist the sequence Xn that provides Markov approximation for the homoge-
neous Markov process X and the sequence {φn ≡ φn(Xn)} of the functionals of the type (3.1). Let the following
conditions hold true:
(1) The functions Fn(·) are bounded and uniformly tend to zero:
δ(Fn)
= sup{Fn(x1, . . . , xL)|x1, . . . , xL ∈ X} → 0, n→ ∞.
(2) There exists a function f , that appears to be a characteristics (in a sense of Chapter 6 [1]) of some
W -functional φ = φ(X) of the limiting Markov process X, such that, for each T ,
,t∈(s,T )
∥∥f s,tn (·)− f s,t(·)
∥∥→ 0, n→ ∞,
where ‖g(·)‖ ≡ sup
|g(x)|.
(3) The limiting function f is uniformly continuous with respect to variable x, that is, for arbitrary T
0≤s≤t<T
∣∣f s,t(x′)− f s,t(x′′)
∣∣→ 0, |x′ − x′′| → 0.
ψn(Xn) ⇒ φ(X) ≡ {φs,t(X), (s, t) ∈ T},
where ψn are the random broken lines corresponding to the functionals φn and convergence is understood in a
sense of C(T,R+).
Remark 4. Conditions 1,2 are analogous to those of the Dynkin’s theorem: condition 2 is exactly the condition
for the characteristics to converge, condition 1 corresponds to the assumption that the prelimit functionals are
W -functionals. In the present situation, of course, we can not say that φn are W -functionals, particulary, φn
are not continuous with respect to temporary variable. Condition 1 means exactly that the values of jumps
6 YURI N.KARTASHOV, ALEXEY M.KULIK
are negligible while n→ ∞. Condition 3, though not very restrictive, is specific, and is caused by necessity to
consider functionals, set over different processes.
Remark 5. If Xn ⇒ X in C or in D (this condition is not provided by the conditions of the Theorem, see
Remark 3), then, as one can easily see from the proof, (Xn, ψn(Xn)) ⇒ (X,φ(X)) in C × C(T,R+) or in
D× C(T,R+), respectively.
Note that the result of the theorem also holds for the Markov process X that is not homogeneous w.r.t.
time variable; the claim for the limit Markov process to be homogeneous is imposed in order to shorten the
notation only. This remark concerns also the most of the results stated below.
Proof of the theorem. The general scheme of the proof is close to the one, proposed in [17] in order to
prove the analogue of the Dynkin’s theorem for the family of functionals of a single Markov process, for which
the properties of additivity, continuity and homogeneity may fail, but the violations become negligible while
n→ ∞.
First let us show that the finite-dimensional distributions of φn converge to the corresponding distributions
of φ. Let the constants γ, T be fixed and X̂n, X̂
n be processes satisfying conditions (i)-(iii) of Definition 1
with these constants. For these processes, one can consider the functionals φn(X̂n), φ(X̂
n); obviously, their
distributions and characteristics coincide with those for φn(Xn), φ(X). In order to shorten notation, we denote
further φn = φn(X̂n), φ = φ(X̂
n),K = K(γ, T ),Ft = F̂nt ≡ σ(X̂n(s), X̂n(s), s ≤ t).
It follows from the condition (iii) and the definition of characteristics that, for arbitrary t ∈
(3.3) E
,t|FKi
n |FKi
almost surely.
Lemma 1. For 0 ≤ s ≤ t ≤ T , the following estimate holds:
lim sup
n (X̂n)− φs,t(X̂)
∥∥f0,T
∥∥G(f, γ, T ) + 4
∥∥f0,T
∥∥2 ,
where G(f, γ, T ) = sup
0≤s≤t≤T,|x′−x′′|<γ
|f s,t(x′)− f s,t(x′′)|.
Proof. We will prove the statement of lemma for s = 0, t = T ; in general case the proof is exactly the same.
Consider the partition of the axis R+ by points of the type Ki
, i ∈ N. Denote Mn = [nTK ] + 1,
(i−1)K
,( iK
n , ∆̃
(i−1)K
T , i = 1,Mn.
We have that
φ0,Tn − φ0,T
∆ni − ∆̃ni
∆ni ∆̃
j = Σ
1 + 2Σ
where
(∆ni )
(∆̃ni )
2 − 2
∆ni ∆̃
1≤i<l≤Mn
∆ni ∆
1≤i<j≤Mn
∆ni ∆̃
1≤j<k≤Mn
∆̃nj ∆̃
1≤j<i≤Mn
∆ni ∆̃
Let us estimate the expectations Σn1 ,Σ
2 separately. Since the increments ∆
i , ∆̃
i are non-negative, the first
sum can be estimated by the sum of the first two terms:
(3.4) Σn1 ≤
(∆ni )
(∆̃ni )
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 7
The expectation of the first term in (3.4) can be estimated via the definition of φn:
(∆ni )
2 ≤ E
i=1,Mn
) Mn∑
∆ni ≤ Kδnf0,Tn
X̂n(0)
≤ Kδn
∥∥f0,Tn
∥∥→ 0, n→ +∞,
where δn ≡ δ(Fn). Convergence to zero of the expectation of the second term in (3.4) is provided by the
arguments, analogous to those used in [1] Chapter 6: on the one hand, by the continuity of functional φ,∑Mn
i=1(∆̃
2 → 0 by probability; on the other hand,
i=1(∆̃
2 is dominated by the variable (φ0,T )2; the
expectation of this variable, due to Lemma 6.4 [1], does not exceed 2
∥∥f0,T
∥∥2 <∞. Therefore, E
i=1(∆̃
0 due to the Lebesgue theorem on dominated convergence. Hence, lim sup
EΣn1 ≤ 0.
The expectation of Σn2 is equal
EΣn2 = E
1≤i<l≤Mn
∆ni ∆
1≤i<j≤Mn
∆ni ∆̃
1≤j<k≤Mn
∆̃nj ∆̃
1≤j<i≤Mn
∆ni ∆̃
(3.5) = E
Mn−1∑
n − φ
Mn−1∑
n − φ
We estimate the second term in (3.5), using property (3.3). Since ∆̃ni is measurable w.r.t. FKi
, the following
estimate holds:
Mn−1∑
n − φ
Mn−1∑
∆̃ni E
n − φ
Mn−1∑
− f Kin ,T
Mn−1∑
n − f
∣∣∣+ E
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣ ≤
(3.6) ≤ ‖f0,T‖ sup
,t∈(s,T )
∥∥f s,tn (·)− f s,t(·)
∥∥+ E
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣
(in the last inequality, we have used that
∑Mn−1
i=1 ∆̃
i ≤ φ0,T and Eφ0,T ≤ ‖f0,T‖). The first term in (3.6)
tends to zero. In order to estimate the second term, we put Ωγ,T =
i≤ Tn
, X̂n
(recall
that P (Ωγ,T ) < γ due to the claim (iii) of Definition 1). We have
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣ ≤ Eφ
G(f, γ, T )1IΩ\Ωγ,T+
(3.7) + E
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣ 1IΩγ,T .
The first term in (3.7) can be estimated by ‖f0,T‖G(f, γ, T ). The second term is estimated by Cauchy
inequality:
Mn−1∑
∣∣∣∣f
− f Kin ,T
))∣∣∣∣ 1IΩγ,T ≤
∥∥f0,T
∥∥Eφ0,T 1IΩγ,T ≤
∥∥f0,T
∥∥ [E(φ0,T )2
2 [P (Ωγ,T )]
∥∥f0,T
∥∥2√2γ
8 YURI N.KARTASHOV, ALEXEY M.KULIK
(here, the Lemma 6.4 [1] was applied). Summing up the above relations, we deduce that
(3.8) lim sup
Mn−1∑
n − φ
∥∥f0,T
∥∥G(f, γ, T ) +
∥∥f0,T
∥∥2√2γ.
Now, let us proceed with the estimation of the first item in (3.5). Straightforward use of the property
(3.3) is impossible here, since the variable ∆ni is a functional of values of the process X̂n at the points
, Ki+1
, . . . Ki+L
, that is, it is not measurable with respect to FKi
. Without loss of generality, one can
assume that K ≥ L (otherwise one can make the same procedure with the constant K replaced by K · L).
Then the variable ∆ni is measurable with respect to FK(i+1)
. The functionals φn, φ are additive at points of
the type j
. Applying (3.3) and condition 1 of the Theorem, we obtain the following relation
Mn−1∑
n − φ
Mn−1∑
K(i+1)
n − φ
K(i+1)
Mn−1∑
K(i+1)
K(i+ 1)
K(i+1)
K(i+ 1)
(3.9) ≤ Kδn
∣∣f0,Tn
∣∣+ E
Mn−1∑
K(i+1)
K(i+ 1)
K(i+1)
K(i+ 1)
The first term in (3.9) tends to zero. The second term in (3.9) is estimated in the same way with the second
term in (3.5), with one necessary change. We cannot apply Lemma 6.4 [1] in order to estimate the second
moment φ0,Tn , therefore this estimate must be obtained separately. This can be done in a following way:
E(φ0,Tn )
2 = E
(∆ni )
2 + 2E
1≤i<j≤Mn
∆ni ∆
j = E
(∆ni )
2 + 2E
1≤i≤Mn
∆ni φ
(∆ni )
2 + 2E
1≤i≤Mn
∆ni [φ
iK/n,(i+1)K/n
n + φ
(i+1)K/n,T
n ] ≤
(∆ni )
2 + 2KδnE
1≤i≤Mn
∆ni + 2E
1≤i≤Mn
∥∥f0,Tn
(3.10) ≤
(2K + 1)δn + 2‖f0,Tn ‖
n ≤ (2K + 1)δn
∥∥f0,Tn
∥∥+ 2
∥∥f0,Tn
∥∥2 ,
all transitions here are analogous to those given above, and thus are not discussed in details. Repeating literally
the estimates for the second term in (3.5), we obtain the estimate
(3.11) lim sup
Mn−1∑
n − φ
∥∥f0,T
∥∥G(f, γ, T ) +
∥∥f0,T
∥∥2√2γ.
It follows from (3.8),(3.11) that lim sup
[2Σn2 ] ≤ 4
∥∥f0,T
∥∥G(f, γ, T ) + 4
∥∥f0,T
∥∥2. This, combined with the
estimate lim sup
[Σn1 ] ≤ 0 proved before, provides the needed statement. The lemma is proved.
Now, we can complete the proof of the convergence of finite-dimensional distributions of φn to those of φ.
In order to shorten notation we consider the one-dimensional distributions only; in general case considerations
are completely the same.
Take arbitrary s, t, s < t. In order to prove weak convergence φs,tn (Xn) to φ
s,t(X), it is sufficient to show
that, for arbitrary bounded Lipschitz function g,
(3.12) lim sup
∣∣Eg(φs,tn (Xn))− Eg(φs,t(X))
∣∣ = 0.
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 9
Let g be fixed, consider a pair of processes X̂n, X̂
n, corresponding (in a sence of Definition 1) to T = t and
given positive γ. By construction, φs,tn (Xn)
=φs,tn (X̂n), φ
s,t(X)
=φs,t(X̂n). Applying Lemma 1, we obtain
lim sup
∣∣Eg(φs,tn (Xn))− Eg(φs,t(X))
∣∣ ≤ lim sup
∣∣∣g(φs,tn (X̂n))− φs,t(X̂n)
∣∣∣ ≤
≤ Lip(g) lim sup
∣∣∣φs,tn
− φs,t
)∣∣∣ ≤ 2Lip(g)
‖f0,t‖G(f, γ, t) +
2γ ‖f0,t‖2,
here Lip(g) denotes the Lipshits constant for g. Condition 3 of the Theorem provides that G(f, γ, t) → 0, γ →
0+. Therefore, since γ > 0 is arbitrary, (3.12) follows from the estimate given above.
Since sups,t |ψs,tn − φs,tn | ≤ δn → 0, the finite-dimensional distributions of φn converge to corresponding
distributions of φ. Thus, the only thing left to show in order to prove the Theorem, is that the family of
distributions of ψn is dense in C(T,R
+). The values of the functions ψn at the point s, t differ from the values
at the closest knots of partition s∗, t∗ ∈ 1nZ+ at most on δn, and ψn are monotone as the functions of the time
variables. Hence, in order to prove the required statement, it is sufficient to show that, for arbitrary sequence
of partitions
Sn = {sn0 = 0 < sn1 < · · · < snk < . . . } ⊂ 1nZ+, n ∈ N
with σn ≡ maxk(snk −snk−1) → 0, n→ +∞
and arbitrary T ∈ R+,
k:sk≤T
snk−1,s
→ 0, n→ +∞.
Set γn,T = sup0<t−s<σn,t<T ‖f
n ‖, note, that γn,T → 0, n→ +∞ due to continuity of the limit characteristics
f and uniform convergence of fn ⇒ f . In the same way with (3.10) we obtain the estimate
(3.13) E
snk−1,s
≤ {(2K + 1)δn + 2γn,T }Eφ
snk−1,s
Summing up the estimates (3.13) w.r.t. k (recall that φs,tn = ψ
n when s, t ∈ 1nZ+), we obtain
k:sk≤T
snk−1,s
≤ {(2K + 1)δn + 2γn,T } ‖f0,Tn ‖ → 0, n→ +∞,
what was to be proved. The theorem is proved.
Let us make one remark. For the random walks, the Skorokhod’s method is well known, allowing one to
reduce the investigation of the sums of the type (3.1) to the case L = 1. This method can be applied in the
context of current paper, also. Namely, the reasoning, similar to the one used in the proof of Theorem 1,
Chapter 5.3 [2], provides the following result (the proof is omitted).
Proposition 1. Let the sequence of functionals {φn = φn(Xn)} of the type (3.1) be given, and, for every n,
the process Xn possesses the Markov property at the time moments
, i ∈ Z+. Consider the functionals
n (Xn)
k:s≤k/n<t
, 0 ≤ s < t,
where
Ψn,k(x) ≡ E
k + 1
, . . . , Xn
k + L− 1
)) ∣∣∣Xn
, x ∈ X.
Let functions Fn(·) be non-negative and satisfy condition 1 of Theorem 1, then the functionals φs,tn have a
limit distribution if and only if the functionals χs,tn have a limit distribution, and the limit distributions of the
functionals φs,tn , χ
n are equal as soon as they exist.
It is worth to note that the Proposition 1 does not lead to simplification of the initial problem in the context
of current paper. The number of values of process Xn, contained in a one summand for the functional φn (that
is, number L), is not involved significantly into the proof of the main theorem. We will see later that the main
problem in the application of the Theorem consists in verification of the condition 2 of uniform convergence
of characteristics; the characteristics of the functionals φn and χn, obviously, coincide.
In the following two chapters, the examples of application of Theorem 1 are given.
10 YURI N.KARTASHOV, ALEXEY M.KULIK
4. The local time of a random walk at a point.
Let the processesXn be constructed w.r.t. one-dimensional random walk that belongs to the normal domain
of attraction of an α-stable law, α ∈ (1, 2] (see Examples 1,2). We assume the centering sequence an to be
equal to zero, and set the random broken lines Xn by equality (2.4).
Consider, for arbitrary z∗ ∈ R, the functionals φn = φn(Xn) of the type (3.1) with L = 2, Fn(x, y) =
|y−x|
1I(x−z∗)(y−z∗)<0 +
(1Ix 6=z∗,y=z∗ + 1Ix=z∗,y 6=z∗)
. For every s < t, s, t ∈ { j
, j ∈ Z+}, with probability 1
the following equality takes place
(4.1) φs,tn (Xn) = lim
1IXn(r)∈(z∗−ε,z∗+ε)\{z∗} dr, 0 ≤ s < t.
Therefore the functionals φn can be naturally interpreted as the censored local times for the broken lines Xn
at the point z∗ (the censoring operation consists in removing horizontal parts of the broken lines). Theorem
3.1 allows one to obtain the following limit result.
Proposition 2. Let the distribution of the jump ξ1 of the random walk be concentrated on Z and aperiodic.
Then the conditions of Theorem 1 hold true and φs,tn (Xn) converge by distribution to φ
s,t(X) = P (ξ1 6=
0) · Ls,t(X, z∗), where L(X, z∗) is the local time of the limit α-stable process X at the point z∗.
Proof. The condition for Xn to provide Markov approximation for X holds true (see Example 2). Condition
1 of the Theorem holds with δn = 2n
−1 since either the increment of the process Xn in the neighboring knots
is equal to zero or the absolute value of this increment is not less then n−
α . Let us show that the characteristics
of functionals φn converge uniformly to the function
(4.2) f s,t(x) = P (ξ1 6= 0)
∫ t−s
pr(z∗ − x) dr,
where pr(·) is the density of distribution X(r) under condition X(0) = 0; this provides conditions 2,3 of the
Theorem.
In order to shorten notation we take z∗ = 0. Denote P
i = P (Sk = i), Pj = P
j = P (ξ1 = j), i, j ∈ Z. We
have that
f s,tn (x) = n
j 6=0
i∈(xn
α −j,xn
P ki +
+ P k
notation i ∈ (a, b) in the case a > b means that b < i < a. Using the appropriate version of the Gnedenko’s
local limit theorem (see [18], Theorem 4.2.1), one can write
(4.3) εk ≡ sup
∣∣∣∣k
αP ki − p1
)∣∣∣∣→ 0, k → +∞.
Hence
f s,tn (x) =
j 6=0
i∈(xn
α −j,xn
(4.4) +
α − j
+ Ξn(x),
where
(4.5) |Ξn(x)| ≤
[nt]∑
and Ξn ⇒ 0, n→ +∞ via the Toeplitz’s theorem.
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 11
The density p1 is uniformly continuous over R, hence, using the same arguments, one can show that, up to
a summand that uniformly converges to zero, the value of f s,tn (x) equals
j 6=0
i∈(xn
α −j,xn
(4.6) =
P (ξ1 6= 0)
P (ξ1 6= 0)
in the latter equality, we have used that the process X is self-similar, that is, pr(x) = r
α p1(r
αx), r > 0.
The sum in the right hand part of (4.6) is exactly the integral sum for the integral in the right hand part of
(4.2), the functions {pr(·), r ≥ r0} are uniformly continuous for arbitrary r0 > 0 and supx pr(x) ≤ Cr−
α . This
immediately provides the required uniform convergence of fn to f . The proposition is proved.
The similar result can be proved for ξk with non-lattice distribution, for which there exists a bounded
distribution density of Sn0 for some n0 (the proof is omitted).
The result of Proposition 2 and its analog for non-lattice random walks is not essentially new; one can obtain
it applying either Proposition 1 and the technique, exposed in §§III.2, III.3 [3], or the reasonings, similar to
those used in the proof of Theorem 3 [9]. Our reason to give this example consists, on the one hand, in
describing the way of application of Theorem 1 in a simple situation where an appropriate local limit theorem
is available, and on the other hand, in emphasizing the following interesting fact, that is not reflected in a
literature available for us. For a ”good” random walks (lattice or essentially non-lattice), their local times at
the point, defined by the natural equality (4.1), converge by distribution exactly to the local time of the limit
process at the same point, as soon as the broken lines corresponding to the random walk does not contain
horizontal sections.
5. Difference approximations of diffusion processes.
Consider the sequence {Zn} of difference approximations of diffusion process Z (see Example 3, equalities
(2.5),(2.6)). The sequence {Zn} provides Markov approximation for Z, that allows one to apply Theorem 1
while considering the question on the limit behavior of the functionals of type (3.1) for {Zn}.
One of possible way to proceed here is to apply the estimates based on an appropriate local limit theorem,
like it was made in the previous chapter. In order to make this paper reasonably short, we do not give the
detailed exposition of this subject here (see the separate paper [19]). In this chapter, we give a simple corollary
of Theorem 1, that provides invariance principle for certain ”canonic” additive functionals, that are related to
the Doob’s decomposition of |Zn(·)|.
Let us consider the objects introduced in Example 3 with m = d = 1 and a, b, {ξn} satisfying conditions
introduced there. Put
(5.1) φs,tn (Zn) ≡
k∈(sn,tn]
Zn( k−1n )Zn(
Zn( k−1n )=0
ψn are corresponding broken lines.
Proposition 3. The processes ψn converge by distribution in C(T,R) to the local time
φs,t ≡ lim
1I|Z(r)|<εb
2(Z(r)) dr
of the diffusion process Z at the point 0.
Proof. Since the diffusion coefficient is non-degenerate, Z possesses continuous transition density pt(x, y)
and the standard estimate supx pt(x, y) ≤
C(y)√
holds true. This implies existence of the local time of Z at
12 YURI N.KARTASHOV, ALEXEY M.KULIK
the point 0. This local time is a W -functional with the characteristics f0,t(x) = b2(0)
ps(x, 0) ds, that is,
condition 3 of Theorem 1 holds. Straightforward calculations prove the equality
(5.2) |Zn(t)| − |Zn(s)| = φ0,tn (Zn) +
[nt]−1∑
where s ∈ 1
Z+, sign (0) = 0. This provides that
f s,tn (x) = E [|Zn(t)||Zn(s) = x]− |x| −
[nt]−1∑
sign (Zn
) ∣∣∣Zn(s) = x
Processes Zn converge weakly to Z, function a(x)sign (x) has unique jump at point x = 0 and P (Z(r) = 0) = 0
for every r > 0. Hence the standard reasonings provide that (we omit the details)
(5.3) f s,tn (x)⇒
E [|Z(t)||Z(s) = x]− |x| − E
a(Zr)sign (Zr) dr
∣∣∣Z(s) = x
This proves condition 2 of Theorem 1, since the right hand side of (5.3) is exactly the characteristics of the
local time φ due to Ito-Tanaka formula.
In order to provide condition 1, let us, for a while, suppose additionally that the coefficients a, b are bounded.
We apply the standard ”cutting” procedure: on each step of approximation, together with the process Zn,
we consider the process Z̃n, constructed by the same scheme from a sequence of i.i.d.r.v. {ξ̃n}, satisfying
conditions ‖ξ̃n‖ ≤ n
2 and ξn = ξ̃n for ‖ξn‖ ≤ n
2 . For such Z̃n, condition 1 of theorem holds with
δ(Fn) ≤ n−1 max
|a(x)| + n
|b(x)|,
and the other conditions of theorem for Z̃n remain to hold true. This proves the statement of Proposition 3
for {Z̃n}. On the other hand, for arbitrary T ∈ R+
Zn|[0,T ] 6= Z̃n|[0,T ]
1− 2+δ
= o(1), n→ +∞,
and therefore the statement of Proposition 3 holds true for {Zn}. At last, the additional assumption that the
coefficients a, b are bounded, can be removed via a standard localization procedure. The proposition is proved.
Remark 6. Let a = 0, b = 1, P (ξk = ±1) = 12 (that is, Zn corresponds to the Bernoulli’s random walk), then
functional (5.1) can be represented at the form
(5.4) φ̃s,tn =
# {k ∈ [sn, tn) : Zn(k) = 0} .
The functional (5.4) is widely used in a literature as the difference analogue of the local time at the point
zero for lattice random walks. Proposition 3 shows that the functional (5.1) is a natural difference analogue of
the local time both for random walks and, more generally, for difference approximations of diffusion processes
without any restrictions on the distribution of the sequence {ξk}.
6. Invariance principle for additive functionals of Markov chains
In previous two chapters we have considered more or less particular examples illustrating possible ways to
provide the main condition of Theorem 1 (condition 2). In this chapter we introduce general sufficient condition
of weak convergence of additive functionals, constructed on the sequence of Markov chains, that is formulated
in terms of the transition probabilities of these chains and the functions Fn involved in representation (3.1).
This condition is obtained as an application of Theorem 1, and the main assumption here is that the local limit
theorem (condition 4 of Theorem 2 below) takes place in an appropriate form. For recurrent Markov chains
this condition, together with a natural condition of weak convergence of ”symbols” of additive functionals
(exact formulation is given below), is sufficient for convergence of characteristics, and the estimates here are
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 13
similar to (4.4) – (4.6) (see Theorem 3 below). For transient chains these estimates are not powerful enough,
since in this case the estimate (4.5) does not provide that Ξn is negligible. One possible way to overcome this
difficultly is to apply a more strong version of local limit theorem, for instance, to claim explicitly the rate
of convergence εk → 0 in (4.3). Such an approach restricts the range of possible applications, therefore we
introduce another one, that is concerned with a uniform condition on the modulus of continuity of processes
Xn (condition 5 of Theorem 2) and a ”dimensional” condition on the symbols of functionals (condition 6),
adjusted one with another with an appropriate way (condition 7).
We assume that a σ-finite measures ν, νn on X are given such that
P (X(t) ∈ dy|X(s) = x) = pt−s(x, y)ν(dy), 0 ≤ s < t, x, y ∈ X,
∈ dy|Xn
= pn,k(x, y)νn(dy), i ∈ Z+, k ∈ N, x, y ∈ X.
The measurable functions pt, pn,k are interpreted as the transition probability densities for X,Xn w.r.t. mea-
sures ν, νn.
We assume the W -functional φ = φ(X) with the characteristics f to be given. It is known (see [1], Chapter
6) that
s,t = L2 − lim
0,ε(X(r)) dr,
and therefore
f s,t(x) = lim
pr(x, y)
f0,ε(y)ν(dy) dr.
We assume that, as ε→ 0+, the measures 1
f0,εdν converge weakly (i.e., on every bounded continuous function)
to a finite measure µ, the characteristics f can be represented in the form
(6.1) f s,t(x) =
∫ t−s
pr(x, y)µ(dy) dr, and
pr(x, y)µ(dy)
dr < +∞, T ∈ R+.
We also consider the sequence of the functionals φn = φn(Xn) of the type (3.1) with L = 1 and Fn =
(the case L > 1 can be considered similarly and we omit it in order to shorten notation). The characteristics
of φn has the form
f s,tn (x) =
pn,k(x, y)µn(dy), 0 ≤ s < t, x ∈ X,
where µn(dy) ≡ gn(y)νn(dy) are the ”symbols” of the functionals φn.
Theorem 2. Assume the following conditions to hold true.
(1) Trajectories of the processes Xn are continuous, and the sequence {Xn} possesses Markov approxima-
tion of X.
(2) 1
supx gn(x) → 0, n→ +∞.
(3) For arbitrary t0 > 0, the function (t, x, y) 7→ pt(x, y) is uniformly continuous on [t0,+∞) × X2, and
for arbitrary y ∈ X
x 6∈B(y,R)
pt(x, y) → 0, R → +∞
(here and below B(x,R) ≡ {x ∈ X|ρ(x, y) < R}). Furthermore, there exist constants γ > 0, Cγ > 0
such that
x,y∈X
pt(x, y) ≤ Cγt−γ , t > 0.
(4) There exist sequences {αn}, {βn} ⊂ R+ tending to zero, such that
x,y∈X
|pn,k(x, y)− p k
(x, y)| ≤ (αn + βk)
, n, k ∈ N.
14 YURI N.KARTASHOV, ALEXEY M.KULIK
(5) There exist constants δ > 0, Cδ > 0 such that, for arbitrary T > 0,
x∈X,n∈N
t,s∈[0,T ],|t−s|≥ 1
ρ(Xn(t), Xn(s))
|t− s|δ
]Cδ ∣∣∣X(0) = x
 < +∞.
(6) Measures µn are finite and converge weakly to measure µ. There exist constants θ > 0, Cθ, cθ > 0 such
µn(B(x,R)) ≤ CθRθ, x ∈ X, n ∈ N, R > cθn−δ
(note that the latter condition provides that µ(B(x,R)) ≤ CθRθ, x ∈ X, R > 0).
(7) The constants γ, δ, θ, Cδ satisfy the relations
δθ + 1 > γ, Cδ > 2θ + 2.
Then (Xn, ψn(Xn)) ⇒ (X,φ(X)) in a sense of convergence in distribution in C(R+,X)×C(T,R+) (ψn are
the random broken lines corresponding to the functionals φn).
Proof. In order to prove the Theorem, it is sufficient to show that, for every T ∈ R+,
(6.2) f s,tn (x) ⇒
s≤t≤T,x∈X
f s,t(x), n→ +∞.
Indeed, the sequence {Xn} provides Markov approximation for X (condition 1), and condition 1 of Theorem 1
is provides by condition 2 of Theorem 2. Having (6.2) proved, we provide condition 2 of Theorem 1. Condition
3 of this theorem is provided by (6.1) and uniform continuity of the density p. At last, condition 5 of Theorem
2 provides weak convergence of Xn to X in C(R
+,X), that allows one to apply Theorem 1 and Remark 5.
Before proving (6.2), let us make some auxiliary estimates. Denote
δ,n(Xn) = sup
v,w∈[s,t],|v−w|≥ 1
ρ(Xn(v), Xn(w))
|v − w|δ ,
n,A =
Xn(r) ∈ B(Xn(s), A(r − s)δ), r ∈
note that {Hs,tδ,n(Xn) < A} ⊂ D
n,A. Also denote α = maxn αn, β = maxk βk, δn =
supx |gn(x)|
, B1 =
maxn δn, B2(T ) =
Cθ(Cγ+α+β)
1+δθ−γ T
1+δθ−γ. For arbitrary A > cθ, T ∈ R+, consider the functionals φs,tn,A =
φs,tn 1IHs,t
(Xn)<A
, s ≤ t ≤ T .
Lemma 2. 1. E
n,A|Xn(s) = x
≤ B1 +B2(T )Aθ.
|Xn(s) = x
≤ 3B1(B1 +B2(T )Aθ) + 2(B1 +B2(T )Aθ)2.
3. Let p ∈
1, 2Cδ−2
Cδ+2θ
(recall that 1 < 2Cδ−2
Cδ+2θ
due to condition 7 of the Theorem). Then
x∈X,n∈N,s≤t≤T
)p |Xn(s) = x
< +∞.
Proof. Using condition 4 of the Theorem and then condition 6, we obtain, for t, s ∈ 1
Z+, the estimate
n,A|Xn(s) = x
φs,tn 1IDs,t
|Xn(s) = x
gn(x)
n(t−s)−1∑
x,A( kn )
pn,k(x, y)µn(dy) ≤
≤ δn +
Cγ + α+ β
n(t−s)−1∑
≤ δn +
Cγ + α+ β
n(t−s)−1∑
)γ−δθ
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 15
that immediately proves the first statement of the Lemma. The second statement can be obtained from the
first one via the estimate similar to (3.10) with the use of the inequality
1IHs,t
(Xn)<A
≤ 1IHs,r
(Xn)<A1IHr,t
(Xn)<A
that holds true for arbitrary r ∈ (s, t).
Applying statement 2 and Hölder inequality we obtain
φs,tn
)p |Xn(s) = x
φs,tn
(Xn)∈[N−1,N)|Xn(s) = x
(φs,tn )
21IHT
(Xn)<N
|Xn(s) = x
P (HTδ,n(Xn) ≥ N − 1)
] 2−p
B3(T ) +B4(T )N
2 ·B5(T ) [(N − 1) ∨ 1]−
here and below Bi(T ), i = 3, 4, . . . denotes a constant, that can be expressed explicitly through T and the
constants introduced in the formulation of the Theorem, but an explicit expression is not needed in our
consideration. Since θp− 2−p
Cδ < −1 by the choice of p, this proves the statement 3. The lemma is proved.
Let us proceed with the proof of (6.2). Choose non-increasing Lipschitz function Ψ : R+ → [0, 1] such that
Ψ([0, 1]) = {1},Ψ([2,+∞)) = {0}, and set
Ψr(x, y) = Ψ(r
−1 · ρ(x, y)), r > 0, x, y ∈ X, Ψ0 ≡ 1.
Note that, for arbitrary r0 > 0, the function (r, x, y) 7→ Ψr(x, y) is uniformly continuous on [r0,+∞)× X2.
For fixed s ≤ t ≤ T,A ∈ R+ we decompose φs,tn as φs,tn = η
n,A + ζ
n,A, where
n,A =
A( kn−s)
Xn(s), Xn
We have that, on the set D
n,A, for k such that s ≤ kn < t,
Xn(0), Xn
A( kn−s)
Xn(s), Xn
hence {φs,tn = η
n,A} ⊃ D
n,A and
(6.3) {ζs,tn,A 6= 0} ⊂ Ω\D
n,A ⊂ {H
δ,n ≥ A}.
Let p be the same as in statement 3 of Lemma 2. Then it follows from (6.3) and inequality 0 ≤ ζs,tn,A ≤ φs,tn
(6.4) E
n,A|Xn(s) = x
(φs,tn )
p|Xn(s) = x
δ,n ≥ A|Xn(s) = x)
] p−1
p ≤ B6(T )A−δ
Similarly, one can write φs,t = η
A + ζ
A , where η
ΨA(r−s)δ(X(s), X(r))dφ
s,r ,
(6.5) E
A |X(s) = x
≤ B6(T )A−δ
We have ∣∣∣E
n,A|Xn(s) = x
A |X(s) = x
]∣∣∣ =
∣∣∣∣∣∣
gn(x)
]n(t−s)[−1∑
pk,n(x, y)ΨA( kn )
δ (x, y)µn(dy)−
∫ t−s
pr(x, y)ΨArδ(x, y)µ(dy) dr
∣∣∣∣∣∣
≤ δn +∆1n(x,A, s, t) + ∆2n(x,A, s, t) + ∆3n(x,A, s, t),
16 YURI N.KARTASHOV, ALEXEY M.KULIK
where ]z[≡ min{N ∈ Z, N ≥ z},
∆1n(x,A, s, t) =
∣∣∣∣∣∣
]n(t−s)[−1∑
[pk,n(x, y)− p k
(x, y)]Ψ
A( kn )
δ (x, y)µn(dy)
∣∣∣∣∣∣
∆2n(x,A, s, t) =
∣∣∣∣∣∣
]n(t−s)[−1∑
(x, y)Ψ
A( kn)
δ(x, y)µn(dy)−
∫ t−s
pr(x, y)ΨArδ(x, y)µn(dy) dr
∣∣∣∣∣∣
∆3n(x,A, s, t) =
∫ t−s
pr(x, y)ΨArδ (x, y)[µn(dy)− µ(dy)] dr
∣∣∣∣ .
Denote ∆in(A, T ) = supx∈X,s≤t≤T ∆
n(x,A, s, t), i = 1, 2, 3. Since Ψr(x, y) ∈ [0, 1] and {Ψr(x, y) 6= 0} ⊂ {y ∈
B(x, 2r)},
∆1n(A, T ) ≤
]nT [−1∑
[αn + βk]
x, 2A
(6.6) ≤ Cθ(2A)θ ·
]nT [−1∑
[αn + βk]
)δθ−γ
→ 0, n→ +∞
by Toeplitz theorem.
The function (r, x, y) 7→ pr(x, y)Ψr(x, y) is uniformly continuous over [r0,+∞)×X2 for any r0 > 0, therefore
an estimate analogous to (6.6) provides that
x∈X,s≤t≤T
∣∣∣∣∣∣
]n(t−s)[−1∑
k=[r0n]+1
(x, y)Ψ
A( kn)
δ (x, y)µn(dy)−
∫ t−s
pr(x, y)ΨArδ(x, y)µn(dy) dr
∣∣∣∣∣∣
(note that maxn µn(X) < +∞ since µn weakly converge to µ). The same arguments provide that
lim sup
∆2n(A, T ) ≤
≤ lim sup
[r0n]∑
 = B7(A, T )(r0)δθ−γ+1.
Since r0 > 0 is arbitrary, this implies that
(6.7) ∆2n(A, T ) → 0, n→ +∞.
At last, the weak convergence of µn to µ and the first part of condition 3 provide that, for every t,
In(A, t) ≡ sup
pt(x, y)ΨArδ(x, y)[µn(dy)− µ(dy)]
∣∣∣∣→ 0, n→ +∞.
Since In(A, t) ≤ Cγt−γ · Cθ(2Atδ)θ, the Lebesgue theorem of dominated convergence provides that
(6.8) ∆3n(A, T ) → 0, n→ +∞.
It follows from the estimates (6.4) – (6.8) that
lim sup
x∈X,s≤t≤T
∣∣f s,tn (x)− f s,t(x)
∣∣ ≤ 2B6(T )A−δ
p , A > cθ.
Taking A→ +∞ we obtain (6.2), that completes the proof. The theorem is proved.
In order to make our exposition complete, let us formulate a version of Theorem 2 for the recurrent case.
Theorem 3. Let conditions 1 – 4 of Theorem 2 hold true and γ < 1. Also let µn converge weakly to µ, and
Xn converge to X by distribution in C(R
+,X).
Then (Xn, ψn(Xn)) ⇒ (X,φ(X)) in a sense of convergence in distribution in C(R+,X)× C(T,R+).
INVARIANCE PRINCIPLE FOR ADDITIVE FUNCTIONALS OF MARKOV CHAINS 17
The proof, with slight changes, repeats the proof of Theorem 2, and is omitted. Note that, under conditions
of Theorem 3, the convergence of finite-dimensional distributions of φn can be provided with the use of the
technique, mentioned in the Introduction, that was proposed by I.I.Gikhman and is based on studying of limit
behavior of difference equations for characteristic functions of φs,tn (see for instance the proof of Theorem 3
[9]). In the transient case, treated in Theorem 2, this technique can not be applied since the uniform estimates,
analogous to (4.4) – (4.6), are not available in this case.
At last, let us give an example of application of Theorem 2. To shorten exposition we omit the proofs of
some technical details.
Example 4. Let X = Rd, d ≥ 2 and Xn, X be as in Example 1. Let K ⊂ Rd be a compact set, for which the
surface measure λK is well defined by equality
λK(·) ≡ w − lim
λd(· ∩Kε)
λd(Kε)
where w − lim means the limit in the sense of weak convergence of measures, λd is Lebesgue measure on Rd,
Kε ≡ {x|dist(x,K) ≤ ε}. Assume that the condition
(6.9) λd(Kε) ≥ const · εβ, ε > 0
holds with some β < 2. In particular, the set K can be smooth (or, more generally, Lipschitz) surface of
codimension 1 or fractal with its Haussdorf-Besikovich dimension greater then d− 2.
It not hard to verify that µ ≡ λK is W -measure (see [1], Chapter 8.1 for the terminology), and therefore
corresponds to some W -functional φ of the Wiener process X . This functional is naturally interpreted as the
local time of Wiener process at the set K, and can be written as φs,t =
λK(Xr) dr.
We consider the functionals φn(Xn) of the form
k∈[sn,tn)
1I{Xn( k
)∈K 1√
and apply Theorem 2 in order to prove convergence of the distributions in C(R+,Rd)× C(T,R+)
(6.10) (Xn, ψn(Xn)) ⇒ (X,φ(X))
(ψn are the broken lines corresponding to φn).
Condition 1 holds true due to Example 1, condition 2 is provided by condition (6.9) (by this condition,
supx gn(x) ≤ const · n
2 ). Condition 3 holds with pt(x, y) = (2πt)
2 exp{− 1
‖y− x‖2
} and γ = d
. Condition
(6.9) implies condition 6 with θ = d− β.
We assume that the random walk Sn is either aperiodic on some lattice hZ
d or is strongly non-lattice (i.e.,
Sn0 has bounded distribution density for some n0). Under this assumption, condition 4 holds with αn ≡ 0,
ν = λd and νn equal to counting measures on
d in lattice case or λd in strongly non-lattice case.
It remains to provide conditions 5, 7. We have γ−1
= d−2
2(d−β) <
. Choose some δ ∈
and consider
α > 0 such that
> δ and α > 2θ + 2. Suppose that
(6.11) E‖ξk‖αRd < +∞.
Then applying Burkholder inequality we obtain that
(6.12) E‖Xn(t)−Xn(s)‖αRd ≤ const · |t− s|
2 , |t− s| ≥ 1√
, x ∈ Rd.
Repeating the standard proof of the Kolmogorov’s theorem on existence of continuous modification (see, for
instance [20], p. 44,45), one can deduce from (6.12) that, for ς < α, ϑ <
t,s∈[0,T ],|t−s|≥ 1
‖Xn(t)−Xn(s)‖Rd
|t− s|ϑ
< +∞.
18 YURI N.KARTASHOV, ALEXEY M.KULIK
Finally, choosing ϑ = δ, ς > 2θ + 2 we obtain that conditions 5,7 hold with Cθ = ς . Applying Theorem 2,
we obtain weak convergence (6.10) under additional moment condition (6.11). One can remove this condition
using the ”cutting” procedure, described in the proof of the Proposition 3.
Let us remark that for the lattice random walks the result, exposed in Example 4, was obtained in [5] by a
technique, essentially different from the one proposed here. Convergence (6.10) in continuous case, as far as it
is known to authors, is a new result.
References
[1] Dynkin E.B. Markov processes, M.: Fizmatgiz, 1963 (in Russian).
[2] Skorokhod A.V., Slobodeniuk M.P. Limit theorems for random walks, Kiev: Naukova dumka, 1970 (in Russian).
[3] Borodin A.N., Ibragimov I.A. Limit theorems for the functionals of random walks, Proc. of the Mathematical Institute of R.
Acad. Sci, vol. 195. St.-P.: Nauka, 1994 (in Russian).
[4] Revesz P. Random walk in random and nonrandom environments, World Sci. Publ. Co., Inc., Teaneck, NJ, 1990.
[5] Bass R.F., Khoshnevisan D. Local times on curves and uniform invariance principles, Prob. Theory Rel. Fields 92, 1992, p.
465 – 492.
[6] Cherny A.S., Shiryaev A.N., Yor M. Limit behavior of the ”horizontal-vertical” random walk and some extensions of the
Donsker-Prokhorov invariance principle. Probability theory and its applications, vol. 47, 3, 2002, p. 498 – 517.
[7] Gikhman I.I. Some limit theorems for the number of intersections of a boundary of a given domain by a random function,
Sci. notes of Kiev Un-ty, 1957, vol. 16, 10, p. 149 – 164 (in Ukrainian).
[8] Gikhman I.I. Asymptotic distributions for the number of intersections of a boundary of a domain by a random function,
Visnyk of Kiev Un-ty, serie astron., athem and mech., 1958, v. 1, 1, p. 25 – 46 (in Ukrainian).
[9] Portenko N.I. Integral equations and limit theorems for additive functionals of Markov processes, robability theory and its
applications, 1967, v. 12, 3, p. 551 – 558 (in Russian).
[10] Portenko N.I. The development of I.I.Gikhman’s idea concerning the methods for investigating local behavior of diffusion
processes and their weakly convergent sequences, Probab. Theory and Math. Stat., 1994, 50, p. 7 – 22.
[11] Kulik A.M. Markov Approximation of stable processes by random walks, vol.12(28) 2006, .1-2, p. 87 – 93.
[12] Feller W. An introduction to probability theory and its applications, Vol II, M.: Mir, 1984 (Russian, translated from
W.Feller, An introduction to probability theory and its applications, John Wiley & Sons, New York, 1971).
[13] Skorokhod A.V. Studies in theory of stochastic processes, Kiev, Kiev Univ-ty publishing house, 1961 (in Russian).
[14] Jacod J., Shiryaev A. Limit theorems for stochastic processes,Springer, Berlin, 1987.
[15] Kurtz T.G., Protter Ph. Weak limit theorems for stochastic integrals and SDE’s, Annals of Probability, 1991, vol. 19, 3, p.
1035 – 1070.
[16] Yamada T., Watanabe S. On the uniqueness of solutions of stochastic differential equations, J. Math. Kyoto Univ., 1971,
vol. 11, p. 156 – 167.
[17] Androshchuk T.O., Kulik A.M. Limit theorems for oscillatory functionals of a Markov process. Theory of stochastic proc-
cesses, vol. 11(27), p. 3 – 13.
[18] Ibragimov I.A., Linnik Yu.V. Linnik, Independent and stationary related variables, M.: Nauka, 1965 (in Russian).
[19] Kulik A.M. Difference approximation for local times of multidimensional diffusions, arXiv:math/0702175
[20] Skorokhod A.V. Lections on theory of stochastic processes, Kyiv: Lybid, 1990 (in Ukrainian).
E-mail address: kulik@imath.kiev.ua
http://arxiv.org/abs/math/0702175
	1. Introduction
	2. Markov approximation.
	3. Main theorem
	4. The local time of a random walk at a point.
	5. Difference approximations of diffusion processes.
	6. Invariance principle for additive functionals of Markov chains
	References
