Chương 1. Quá trình Markov


Đặng Hùng Thắng

Quá trình ngẫu nhiên và tính toán ngẫu nhiên.
NXB Đại học quốc gia Hà Nội 2007,
Tr 5 - 63.


Từ khoá: Quá trình ngẫu nhiên, Quá trình Markov, Xích Markov, Trạng thái hữu
han, Trạng thái vô hạn đếm được.



Tài liệu trong Thư viện điện tử ĐH Khoa học Tự nhiên có thể sử dụng cho mục
đích học tập và nghiên cứu cá nhân. Nghiêm cấm mọi hình thức sao chép, in ấn
phục vụ các mục đích khác nếu không được sự chấp thuận của nhà xuất bản và
tác giả.






Chương 1
Quá trình Markov
1.1 XíchMarkov 5

1.2 Phân loại trạng thái xích Markov . . . . . . . . . 20
1.3 QuátrìnhMarkov 34
1.3.1 Trường hợp không gian trạng thái hữu hạn . . . . 36
1.3.2 Trường hợp không gian trạng thái vô hạn đếm được 42
1.3.3 Trường hợp tổng quát . . . . . . . . . . . . . . . . 54
1.4 Bàitập 58
1.1 Xích Markov
Xét một hệ nào đó được quan sát tại các thời điểm rời rạc 0, 1, 2, Giả sử
các quan sát đó là X
0
,X
1
, , X
n
, Khi đó ta có một dãy các đại lượng ngẫu
nhiên (ĐLNN) (X
n
) trong đó X
n
lg thái của hệ tại thời điểm n. Giả thiết
rằng mỗi X
n
,n=0, 1, là một ĐLNN rời rạc. Ký hiệu E là tập giá trị của
các (X
n
). Khi đó E là một tập hữu hạn hay đếm được, các phần tử của nó
được ký hiệu là i, j, k Ta gọi E là không gian trạng thái của dãy.
6 Chương 1. Quá trình Markov
Định nghĩa 1.1. Ta nói rằng dãy các ĐLNN (X
n

) là một xích Markov nếu
với mọi n
1
< <n
k
<n
k+1
và với mọi i
1
,i
2
, i
k+1
∈ E
P {X
n
k+1
= i
k+1
|X
n
1
= i
1
.X
n
2
= i
2
, X

n
k
= i
k
}
= P {X
n
k+1
= i
k+1
|X
n
k
= i
k
}.
Ta coi thời điểm n
k+1
là tương lai, n
k
là hiện tại còn n
1
, ,n
k−1
là quá
khứ. Như vậy, xác suất có điều kiện của một sự kiện B nào đó trong tương
lai nếu biết hiện tại và quá khứ của hệ cũng giống như xác suất có điều kiện
của B nếu chỉ biết trạng thái hiện tại của hệ. Đó chính là tính Markov của
hệ. Đôi khi tính Markov của hệ còn phát biểu dưới dạng: Nếu biết trạng thái
hiện tại của hệ thì quá khứ và tương lai độc lập với nhau.

Giả sử P {X
m+n
= j|X
m
= i} là xác suất để xích tại thời điểm m ở trạng
thái i sau n bước, tại thời điểm m + n chuyển sang trạng thái j. Đây là một
con số nói chung phụ thuộc vào i, j, m, n. Nếu đại lượng này không phụ thuộc
m ta nói xích là thuần nhất. Trong giáo trình này ta chỉ xét xích Markov
thuần nhất.
Ký hiệu
P
ij
= P {X
n+1
= j|X
n
= i}
P
ij
(n)=P{X
m+n
= j|X
m
= i}.
Ta gọi (P
ij
,i,j ∈ E) là xác suất chuyển sau một bước hay xác suất chuyển
còn (P
ij
(n),i,j ∈ E) là xác suất chuyển sau n bước. Chú ý rằng


j∈E
P
ij
=1

j∈E
P
ij
(n)=1.
Phân bố của X
0
được gọi là phân bố ban đầu. Ta ký hiệu u
i
= P (X
0
= i).
Định lý 1.1. Phân bố đồng thời của (X
0
,X
1
, , X
n
) được hoàn toàn xác
định từ phân bố ban đầu và xác suất chuyển. Cụ thể ta có
P (X
0
= i
0
,X

1
= i
1
, , X
n
= i
n
)=u
i
0
P
i
0
i
1
P
i
n−1
i
n
.
1.1. Xích Markov 7
Thật vậy theo công thức nhân xác suất ta có
P (X
0
= i
0
,X
1
= i

1
, , X
n
= i
n
)=
= P (X
0
= i
0
)P (X
1
= i
1
|X
0
= i
0
) ×
× P (X
k
= i
k
|X
0
= i
0
, , X
k−1
= i

k−1
) ×
× P (X
n
= i
n
|X
0
= i
0
, , X
n−1
= i
n−1
).
Sử dụng tính Markov ta có
P (X
k
= i
k
|X
0
= i
0
, , X
k−1
= i
k−1
)=P (X
k

= i
k
|X
k−1
= i
k−1
)
= P
i
k−1
i
k
.
Thành thử
P (X
0
= i
0
,X
1
= i
1
, , X
n
= i
n
)=u
i
0
P

i
0
i
1
P
i
n−1
i
n
Định lý 1.2. (Phương trình C - K (Chapman-Kolmogorov))
P
ij
(n + m)=

k∈E
P
ik
(n)P
kj
(m).
Chứng minh. Theo công thức xác suất đầy đủ và tính Markov ta có
P
ij
(n + m)=P(X
n+m
= j|X
0
= i)
=


k∈E
P (X
n
= k|X
0
= i)P (X
n+m
= j|X
n
= k, X
0
= i)
=

k∈E
P
ik
(n)P
kj
(m).
Trong trường hợp E có d phần tử, ta ký hiệu P =(P
ij
),P(n)=(P
ij
(n))
là các ma trận vuông cấp d ×d. P được gọi là ma trận xác suất chuyển, P (n)
được gọi là ma trận xác suất chuyển sau n bước. Khi đó từ phương trình
Chapman-Kolmogorov tương đương với
P (n + m)=P(n)P (m).
8 Chương 1. Quá trình Markov

Vì P = P (1) nên bằng quy nạp ta dễ thấy
P (n)=P
n
.
Gọi u
i
(n)=P(X
n
= i). Ký hiệu vecto U(n)=(u
1
(n), , u
d
(n)) là vector
hàng d - chiều mô tả phân bố của X
n
, U = U(0) = (u
1
,u
2
, , u
d
) là vector
hàng d - chiều mô tả phân bố ban đầu (phân bố của X
0
).
Định lý 1.3. Ta có
U(m + n)=U(m)P
n
.
Nói riêng

U(n)=UP
n
.
Chứng minh. Thật vậy, theo công thức xác suất đầy đủ ta có
u
j
(m + n)=P(X
n+m
= j)=
d

i=1
P (X
m
= i)P (X
n+m
= j|X
m
= i)
=
d

i=1
u
i
(m)P
ij
(n).
Ví dụ 1.1. Cho (ξ
n

),n=0, 1, 2, là dãy các ĐLNN độc lập, cùng phân bố.
Giả sử P(ξ
n
= i)=a
i
,i ∈ Z. Đặt X
n
=
n

i=1
ξ
i
. Khi đó (X
n
) là một xích
Markov với không gian trạng thái Z.
P {X
n+1
= i
n+1
|X
0
= i
0
.X
1
= i
1
, X

n
= i
n
}
= P {X
n
+ ξ
n+1
= i
n+1
|ξ
0
= i
0
,ξ
1
= i
1
− i
0
, , ξ
n
= i
n
− i
n−1
}
= P {ξ
n+1
= i

n+1
− i
n
} = P {X
n+1
= i
n+1
|X
n
= i
n
}.
Vậy thì (X
n
) là một xích Markov với không gian trạng thái Z. Xác suất
chuyển là P
ij
= a
i−j
.
1.1. Xích Markov 9
Ví dụ 1.2. (Mô hình Ehrenfest) Ta có hai bình A, B và có d quả cầu đánh
số 1, 2, d. Tại thời điểm ban đầu có a quả cầu trong A và d−a quả cầu trong
B. Tại mỗi thời điểm n ta chọn ngẫu nhiên một số trong tập {1, 2, d}. Khi
đó quả cầu mang chỉ số được chọn sẽ được chuyển từ bình đang chứa nó sang
bình kia. Ký hiệu X
n
là số quả cầu trong bình A tại thời điểm n. Hiển nhiên
(X
n

) là xích Markov. Ta hãy tính xác suất chuyển P (X
n+1
= j|X
n
= i).Vì
A chứa i quả cầu nên với xác suất i/d ta sẽ chọn được quả cầu từ A. Khi đó
quả cầu này được chuyển sang B.VậyP (X
n+1
= i −1|X
n
= i)=i/d. Tương
tự với xác suất 1 − i/d sẽ chọn được quả cầu của B và quả cầu này sẽ được
chuyển vào A.VậyP (X
n+1
= i +1|X
n
= i)=1−i/d. Thành thử
P
ij
=









i

d
nếu j = i −1
d − i
d
nếu j = i +1
0 nếu j = i +1,j = i − 1.
(1.1)
Mô hình này được nhà vật lý nổi tiếng Ehrenfest đưa ra năm 1907 nhằm mô
tả sự truyền nhiệt giữa hai vật thể.
Ví dụ 1.3. Ta nghiên cứu một vấn đề xã hội nào đó chẳng hạn vấn đề nghiện
hút. Ta ký hiệu trạng thái 0 là không nghiện và trạng thái 1 là nghiện. Đơn
vị thời gian là một quý (3 tháng). Thống kê nhiều năm cho thấy xác suất
để một người không nghiện sau một quý vẫn không nghiện là 0,99 và xác
suất để một người nghiện sau một quý vẫn tiếp tục nghiện là 0,88. Như vậy
trạng thái của một người (nghiện hay không nghiện) được mô tả bởi một xích
Markov với hai trạng thái E = {0, 1} với ma trận xác suất chuyển như sau
P =

0, 99 0, 01
0, 12 0, 88

Giả sử lúc đầu có 17% số người nghiện. Như vậy phân bố ban đầu là U(0) =
(0, 83, 0, 17). Sang quý hai, theo định lý 1.3 phân bố số người nghiện và không
nghiện sẽ là
U(1) = U(0)P =(0.83, 0.17)

0, 99 0, 01
0, 12 0, 88

=(0, 845, 0, 155).

10 Chương 1. Quá trình Markov
Sang quý ba nữa phân bố số người không nghiện và nghiện sẽ là
U(2) = U(1)P =(0.845, 0.155)

0, 99 0, 01
0, 12 0, 88

=(0, 855, 0, 145)
tức là lúc này có 14,5% số người nghiện.
Ví dụ 1.4. Giả sử ta có d cửa hàng ký hiệu là 1, 2, d cùng bán một sản
phẩm nào đó. Khách hàng có thể chọn mua sản phẩm ở một trong d cửa hàng
này tuỳ theo sở thích của họ và trong từng tháng họ không thay đổi chỗ mua
hàng. Gọi X
n
là cửa hàng mà khách hàng chọn mua sản phẩm ở tháng thứ
n. Đây là một xích Markov có d trạng thái, xác suất chuyển P
ij
có nghĩa là
xác suất để khách hàng, hiện tại đang mua hàng tại cửa hàng i sang tháng
sau chuyển sang mua ở cửa hàng j. Xét d =3và ma trận xác suất chuyển
là
P =



0, 800 0, 100 0, 100
0, 070 0, 900 0, 030
0, 083 0, 067 0, 850




Giả sử tháng giêng cửa hàng 1 chiếm 20% khách hàng, cửa hàng 2 chiếm
50% khách hàng và cửa hàng 3 chiếm 30% khách hàng. Như vậy phân bố ban
đầu là U(0) = (0, 2, 0, 5, 0, 3). Sang tháng 2 phân bố khách hàng trong 3 cửa
hàng sẽ là U(1) = U(0)P =(0, 22, 0, 49, 0, 29). Sang tháng 3 phân bố khách
hàng trong 3 cửa hàng sẽ là U(2) = U(1) P =(0, 234, 0, 483, 0, 283). Tiếp tục
quá trình như vậy ta có thể tính ở tháng 12 phân bố khách hàng trong 3 cửa
hàng sẽ là U(11) = (0, 270, 0, 459, 0, 271) tức là trong tháng 12 cửa hàng 1
chiếm 27% khách hàng, cửa hàng 2 chiếm 45,9% khách hàng và cửa hàng 3
chiếm 27,1% khách hàng.
Ví dụ 1.5. Cho (X
n
) là một xích Markov có 2 trạng thái E = {0, 1} với ma
trận xác suất chuyển là
P =

1 − aa
b 1 − b

1.1. Xích Markov 11
trong đó a, b > 0, 0 <a+ b<1. Ta hãy tìm biểu thức của ma trận xác suất
chuyển sau n bước P(n).Tacó
P
00
(n +1)=P (X
n+1
=0|X
0
=0)
= P (X

n
=0|X
0
=0)P (X
n+1
=0|X
n
= 0)+
+ P (X
n
=1|X
0
=0)P (X
n+1
=0|X
n
=1)
= P
00
(n)(1 −a)+(1−P
00
(n))b. (1.2)
Nếu ký hiệu u
n
= P
00
(n),q =1−a −b từ (1.2) ta có công thức truy hồi sau
u
n+1
= u

n
(1 − a)+(1−u
n
)b =(1−a −b)u
n
+ b = qu
n
+ b.
Chú ý rằng u
0
=1, từ công thức truy hồi trên dễ thấy
u
n
= q
n
+
b(1 − q
n
)
1 − q
=(1− a −b)
n
+
b
a + b
(1 − (1 − a − b)
n
)
hay
P

00
(n)=
b
a + b
+(1− a − b)
n
a
a + b
.
Suy ra
P
01
(n)=1−P
00
(n)=
a
a + b
− (1 − a − b)
n
a
a + b
.
Tương tự ta có
P
10
(n +1)=P (X
n+1
=0|X
0
=1)

= P (X
n
=0|X
0
=1)P (X
n+1
=0|X
n
= 0)+
+ P (X
n
=1|X
0
=1)P (X
n+1
=0|X
n
=1)
= P
10
(n)(1 −a)+(1−P
10
(n))b. (1.3)
Nếu ký hiệu v
n
= P
00
(n),q =1− a −b từ (1.3) ta có công thức truy hồi sau
v
n+1

= v
n
(1 − a)+(1−v
n
)b =(1−a −b)v
n
+ b = qv
n
+ b.
Chú ý rằng v
0
=0, từ công thức trên ta thu được
v
n
=
b(1 − q
n
)
(1 − q)
=
b
a + b
(1 − (1 − a − b)
n
).
12 Chương 1. Quá trình Markov
Suy ra
P
10
(n)=

b
a + b
− (1 − a − b)
n
b
a + b
P
11
(n)=1−P
10
(n)=
a
a + b
+(1−a −b)
n
b
a + b
.
Viết dưới dạng ma trận ta có
P (n)=
1
a + b

ba
ba

+
(1 − a − b)
n
a + b


a −a
−bb

.
Định nghĩa 1.2. Phân bố ban đầu U =(u
i
),i∈ E được gọi là phân bố dừng
nếu ta có U(n)=U với mọi n tức là u
i
(n)=u
i
∀i ∈ E,∀n. Khi đó dãy
(X
n
) có cùng phân bố.
Từ định lý 3 ta suy ra U =(u
i
) là phân bố dừng nếu và chỉ nếu
1. u
i
≥ 0 và

i∈E
u
i
=1
2. u
j
=


i∈E
u
i
P
ij
∀j ∈ E.
Ví dụ 1.6.
Cho (X
n
) là một xích Markov có 3 trạng thái E = {1, 2, 3} với ma trận xác
suất chuyển là
P =



1/31/31/3
1/41/21/4
1/61/31/2



Hãy tìm tất cả các phân bố dừng.
Đặt U =(x, y, z). Khi đó U là phân bố dừng khi và chỉ khi x, y, z là
nghiệm không âm của hệ sau














x/3+y/4+z/6=x
x/3+y/2+z/3=y
x/3+y/4+z/2=z
x + y + z =1.
1.1. Xích Markov 13
Từ phương trình thứ nhất và thứ hai của hệ khử z ta rút ra y =5x/3. Từ đó
z =3x/2. Thế vào phương trình (4) ta thu được x =6/25,y =10/25,z =
9/25.
Ví dụ 1.7.
Cho (X
n
) là một xích Markov có 2 trạng thái E = {0, 1} với ma trận xác
suất chuyển là
P =

1 − aa
b 1 − b

trong đó a, b > 0, 0 <a+ b<1 (xem ví dụ 1.5). Ta hãy tìm phân bố dừng.
Đặt U =(x,y). Khi đó U là phân bố dừng khi và chỉ khi x, y là nghiệm
không âm của hệ sau










(1 − a)x + by = x
ax +(1− b)y = y
x + y =1.
Phương trình (1) và (2) của hệ tương đương với ax = by hay x =
by
a
. Thế
vào phương trình (3) của hệ ta thu được
x =
b
a + b
,y =
a
a + b
.
Như sau này ta sẽ thấy phân bố dừng không phải bao giờ cũng tồn tại. Câu
hỏi đặt ra là: Với điều kiện nào thì tồn tại phân bố dừng? Phân bố dừng nếu
tồn tại thì có duy nhất không?
Định lý 1.4. Giả sử (X
n
) là xích Markov với không gian trạng thái E =
{1, 2, } với ma trận xác suất chuyển P =(P

ij
) và ma trận xác suất chuyển
sau n bước là P (n)=(P
ij
(n)). Giả sử rằng với mọi i, j ∈ E tồn tại giới hạn
lim
n→∞
P
ij
(n)=π
j
và giới hạn này không phụ thuộc i. Khi đó
14 Chương 1. Quá trình Markov
1.

j∈E
π
j
≤ 1 và π
j
=

i∈E
π
i
P
ij
.
2. Hoặc π
j

=0với mọi j ∈ E, hoặc

j∈E
π
j
=1.
3. Nếu

j∈E
π
j
=1thì U =(π
1
,π
2
, ) là phân bố dừng và phân bố dừng là
duy nhất. Nếu π
j
=0với mọi j ∈ E thì phân bố dừng không tồn tại.
Chứng minh. 1. Theo bổ đề Fatou ta có

j∈E
π
j
=

j∈E
lim
n→∞
P

ij
(n) ≤ lim inf
n→∞

j∈E
P
ij
(n)=1.
Sử dụng bổ đề Fatou và phương trình C-K ta có

i∈E
π
i
P
ij
=

i∈E
lim
n
P
ki
(n)P
ij
≤ lim inf
n→∞

i∈E
P
ki

(n)P
ij
= lim inf
n→∞
P
kj
(n +1)=π
j
.
Đặt s
j
= π
j
−

i∈E
π
i
P
ij
≥ 0 ∀j ∈ E.Tacó

j∈E
s
j
=

j∈E
π
j

−

j∈E

i∈E
π
i
P
ij
=

j∈E
π
j
−

i∈E

j∈E
π
i
P
ij
=

j∈E
π
j
−


i∈E
π
i

j∈E
P
ij
=

j∈E
π
j
−

i∈E
π
i
=0.
Vậy s
j
=0 ∀j ∈ E hay π
j
=

i∈E
π
i
P
ij
∀j ∈ E.

2. Ta có
π
j
=

i∈E
π
i
P
ij
=

i∈E
(

k∈E
π
k
P
ki
)P
ij
=

k∈E
π
k
(

i∈E

P
ki
P
ij
)=

k∈E
π
k
P
kj
(2).
1.1. Xích Markov 15
Bằng quy nạp dễ thấy với mọi n
π
j
=

k∈E
π
k
P
kj
(n).
Vì chuỗi hội tụ đều đối với n nên
π
j
= lim
n→∞


k∈E
π
k
P
kj
(n)=

k∈E
π
k
lim
n→∞
P
kj
(n)=π
j

k∈E
π
k
Suy ra
π
j

1 −

k∈E
π
k


=0 ∀j ∈ E.
Vậy nếu

k∈E
π
k
< 1 thì π
j
=0 ∀j ∈ E.
3. Nếu

k∈E
π
k
=1thì từ khẳng định 1 ta suy ra π =(π
1
,π
2
, ) là phân
bố dừng. Ta chứng minh đây là phân bố dừng duy nhất. Thật vậy giả
sử U =(u
i
) là phân bố dừng. Lập luận tương tự như trên ta có
u
j
=

k∈E
u
k

P
kj
(n).
Vì chuỗi hội tụ đều đối với n nên
u
j
=

k∈E
u
k
lim
n→∞
P
kj
(n)=

k∈E
u
k
π
j
= π
j
.
Do đó nếu

j∈E
π
j

< 1 thì phân b ố dừng không tồn tại. Nếu

j∈E
π
j
=1thì
π =(π
1
,π
2
, ) là phân bố dừng duy nhất.
Định nghĩa 1.3. Giả sử (X
n
) là xích Markov với không gian trạng thái
E = {1, 2, } với ma trận xác suất chuyển P =(P
ij
) và ma trận xác suất
chuyển sau n bước là P(n)=P
ij
(n). Ta nói rằng xích có phân bố giới hạn
nếu với mọi i, j ∈ E tồn tại giới hạn
lim
n→∞
P
ij
(n)=π
j
.
Giới hạn này không phụ thuộc i ∈ E và


j∈E
π
j
=1. Nói cách khác, vecto giới
hạn π =(π
1
,π
2
, ) lập thành một phân bố xác suất trên E.
16 Chương 1. Quá trình Markov
Ý nghĩa của phân bố giới hạn là như sau: Gọi u
i
(n)=P (X
n
= i).Ký
hiệu vecto U(n)=(u
1
(n),u
2
(n), ) là vector hàng d-chiều mô tả phân bố
của X
n
.Tacó
P (X
n
= j)=

ß∈E
P (X
0

= i)P
ij
(n).
Do đó
lim
n→∞
P {X
n
= j} =

ß∈E
P {X
0
= i} lim
n→∞
P
ij
(n)
=

ß∈E
P {X
0
= i}π
j
= π
j
.
Vậy phân bố U(n) của X
n

hội tụ tới phân bố giới hạn π. Khi n khá lớn ta
có P (X
n
= j) ≈ π
j
.
Theo định lý 1.4 nếu phân bố giới hạn tồn tại thì phân bố dừng cũng
tồn tại và duy nhất. Hơn nữa hai phân bố này trùng nhau. Tuy nhiên điều
ngược lại không đúng tức là có những xích Markov có tồn tại phân bố dừng
nhưng không tồn tại phân bố giới hạn.
Ví dụ 1.8. Cho xích Markov (X
n
) có hai trạng thái với ma trận xác suất
chuyển là
P =

01
10

.
Ta có
P (2n)=

01
10

và
P (2n +1)=

01

10

.
Do đó không tồn tại lim
n→∞
P (n). Tuy nhiên dễ dàng kiểm tra được π =
(1/2, 1/2) là phân bố dừng duy nhất.
1.1. Xích Markov 17
Một trong những bài toán quan trọng trong nghiên cứu xích Markov là
tìm những điều kiện để đảm bảo sự tồn tại của phân bố giới hạn và sự tồn
tại của phân bố dừng. Dưới đây là một định lý như vậy.
Định lý 1.5. Cho (X
n
) là xích Markov với không gian trạng thái hữu hạn
E = {1, 2, , d} với ma trận xác suất chuyển sau n bước là P (n)=(P
ij
(n)).
Khi đó có tồn tại phân bố giới hạn π =(π
1
, , π
d
) với π
j
> 0 ∀j ∈ E khi và
chỉ khi xích là chính quy theo nghĩa: Tồn tại n
0
sao cho P
ij
(n
0

) > 0, ∀i, j ∈ E.
Chứng minh. Giả thiết xích là chính quy. Ta cố định j và đặt
m
j
(n) = min
i∈E
P
ij
(n)
M
j
(n) = max
i∈E
P
ij
(n).
Ta có
P
ij
(n +1)=

k
P
ik
P
kj
(n) ≥

k
P

ik
m
j
(n)=m
j
(n).
Suy ra m
j
(n +1)≥ m
j
(n). V ậy dãy (m
j
(n)),n =1, 2, là dãy tăng và bị
chặn trên bởi 1, do đó tồn tại giới hạn
lim
n
m
j
(n)=a
j
.
Lập luận tương tự dãy (M
j
(n)),n =1, 2, ) là dãy giảm bị chặn bởi 0,do
đó tồn tại giới hạn
lim
n
M
j
(n)=A

j
.
Ta có m
j
(n) ≤ P
ij
(n) ≤ M
j
(n) do đó định lý được chứng minh nếu ta chỉ ra
a
j
= A
j
. Ký hiệu r = min
i,j
P
ij
(n
0
) > 0.TacóP
ik
(n
0
) ≥ r.1 ≥ P
jk
(n) nên
P
ik
(n
0

) ≥ rP
jk
(n) ∀i, thành thử
P
ij
(n
0
+ n)=

k
P
ik
(n
0
)P
kj
(n)
=

k
(P
ik
(n
0
) − rP
jk
(n)) P
kj
(n)+r


k
P
jk
(n)P
kj
(n)
≥ m
j
(n)

k
(P
ik
(n
0
) − rP
jk
(n)) + rP
jj
(2n)
= m
j
(n)(1 −r)+rP
jj
(2n).
18 Chương 1. Quá trình Markov
Vì bất đẳng thức này đúng với mọi i nên ta có
m
j
(n

0
+ n) ≥ m
j
(n)(1 − r)+rP
jj
(2n).
Tương tự ta có
M
j
(n
0
+ n) ≤ M
j
(n)(1 − r)+rP
jj
(2n).
Suy ra
M
j
(n
0
+ n) − m
j
(n
0
+ n) ≤ (1 − r)(M
j
(n) − m
j
(n)) . (1.4)

Ta chứng minh quy nạp rằng với mọi k
M
j
(kn
0
+1)−m
j
(kn
0
+1)≤ (1 − r)
k
(M
j
(1) − m
j
(1)) . (1.5)
Thật vậy với k =1đúng (Cho n =1ở (1.4)). Giả sử đúng với k.Tacó
M
j
((k +1)n
0
+1)− m
j
((k +1)n
0
+1)
= M
j
(kn
0

+1+n
0
) − m
j
(kn
0
+1+n
0
)
≤ (1 − r)((M
j
(kn
0
+1)− m
j
(kn
0
+ 1))
≤ (1 − r)
k+1
(M
j
(1) − m
j
(1)) .
Cho k →∞trong (1.5) ta nhận được A
j
−a
j
≤ 0.VìA

j
−a
j
≥ 0 nên ta kết
luận A
j
= a
j
.
Đảo lại giả sử với mọi i, j ∈ E tồn tại lim
n
P
ij
(n)=π
j
> 0. Khi đó tồn
tại n
0
(i, j) sao cho P
ij
(n) > 0 ∀n>n
0
(i, j). Đặt n
0
= max
i,j
n
0
(i, j) ta có
P

ij
(n) > 0 ∀i, j ∈ E∀n>n
0
Ví dụ 1.9. Mỗi người dân trong một vùng nào đó có thể ở trong ba tầng lớp:
giàu, trung lưu và nghèo. Con cái của họ có thể ở trong một trong ba tầng lớp
nói trên với các xác suất khác nhau tuỳ thuộc vào việc họ đang ở trong tầng
lớp nào. Giả sử bằng thống kê ngưòi ta xác định được: Nếu một người giàu
thì với xác suất 0,448 con họ giàu, với xác suất 0,484 con họ trung lưu với
xác suất 0,068 con họ nghèo. Tương tự, với một người trung lưu thì xác suất
để con họ giàu, trung lưu hay nghèo tương ứng là 0,054. 0,699 và 0,247. Với
1.1. Xích Markov 19
một người nghèo thì xác suất để con họ giàu, trung lưu hay nghèo tương ứng
là 0,011, 0,503 và 0,486. Như vậy sự thay đổi trạng thái của một gia đình
trong xã hội từ thế hệ này qua thế hệ khác có thể mô tả bởi một xích Markov
ba trạng thái : 1(giàu), 2(trung lưu), 3(nghèo) với xác suất chuyển như sau
P =



0, 448 0, 484 0, 068
0, 054 0, 699 0, 247
0, 011 0, 503 0, 486



.
Xích Markov này là chính quy. Thành thử tồn tại phân bố giới hạn π =
(π
1
,π

2
,π
3
). Phân bố này chính là phân bố dừng duy nhất và được tìm bằng
cách giải hệ phương trình sau
(π
1
,π
2
,π
3
)P =(π
1
,π
2
,π
3
).
Giải ra ta tìm được π
1
=0, 067; π
2
=0, 624; π
3
=0, 369. Như vậy qua nhiều
thế hệ ở vùng dân cư nói trên sẽ có 6,7% người giàu, 62,4% trung lưu và
36.9% người nghèo.
Ví dụ 1.10. Xét xích Markov có d trạng thái E = {1, 2, , d} và ma trận
xác suất chuyển của nó là chính quy đồng thời là một ma trận kép nghĩa là


j∈E
P
ij
=

i∈E
P
ij
=1.
Theo định lý trên, phân phối giới hạn tồn tại. Ta hãy tìm phân bố giới hạn
đó.Ta nhận xét rằng phân bố đều π= (1/d, 1/d, , 1/d) là phân bố dừng. Thật
vậy đặt pi
j
=1/d ta có

k∈E
pi
k
P
kj
=1/d

k∈E
P
kj
=1/d = π
j
.
Vì phân bố dừng là duy nhất và phân bố giới hạn chính là phân bố dừng nên
ta kết luận rằng phân bố giới hạn là phân bố đều π =(1/d, 1/d, , 1/d) .

Chẳng hạn ta tung con xúc sắc liên tiếp một cách độc lập. Ký hiệu ξ
n
là
số chấm xuất hiện ở lần gieo thứ n, S
n
=

n
k=1
ξ
k
. S
n
là một xích Markov
20 Chương 1. Quá trình Markov
với không gian trạng thái E = {1, 2, }. Gọi X
n
là số dư khi chia S
n
cho
7. Khi đó X
n
cũng là một là một xích Markov với không gian trạng thái
E = {0, 1, 2, , 6}. Ma trận xác suất chuyển của X
n
là
P =














01/61/61/61/61/61/6
1/601/61/61/61/61/6
1/61/601/61/61/61/6
1/61/61/601/61/61/6
1/61/61/61/601/61/6
1/61/61/61/61/601/6
1/61/61/61/61/61/60














.
Xích Markov này chính quy vì ma trận xác suất chuyển sau 2 bước
P (2) = P
2
=













1/65/36 5/36 5/36 5/36 5/36 5/36
5/36 1/65/36 5/36 5/36 5/36 5/36
5/36 5/36 1/65/36 5/36 5/36 5/36
5/36 5/36 5/36 1/65/36 5/36 5/36
5/36 5/36 5/36 5/36 1/65/36 5/36
5/36 5/36 5/36 5/36 5/36 1/65/36
5/36 5/36 5/36 5/36 5/36 5/61/6














có tất cả các phần tử là số dương.
Vậy phân bố giới hạn là
π =(1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7 , 1/7).
1.2 Phân loại trạng thái xích Markov
Để giải quyết đầy đủ hơn bài toán về sự tồn tại của phân bố dừng cũng như
bài toán về sự tồn tại của phân bố giới hạn dẫn ta đến việc phân loại các
trạng thái của xích Markov như sau:
1.2. Phân loại trạng thái xích Markov 21
Định nghĩa 1.4. Ta nói rằng trạng thái i đến được trạng thái j và ký hiệu là
i → j nếu tồn tại n ≥ o sao cho P
ij
(n) > 0.(TaquyướcP
ii
(0) = 1,P
ij
(0) =
0 nếu i = j)
Hai trạng thái i và j được gọi là liên lạc được nếu i → j và j → i. Trong
trường hợp đó ta viết i ↔ j.
Bổ đề 1.1 (Tính chất bắc cầu). Nếu i → j, j → k thì i → k.
Thật vậy theo giả thiết tồn tại n, m sao cho
P

ij
(n) > 0,P
jk
(m) > 0.
Theo phương trình Chapman - Kolmogorov ta có
P
ik
(n + m)=

j∈E
P
ij
(n)P
jk
(m) ≥ P
ij
(n)P
jk
(m) > 0.
Từ bổ đề, dễ kiểm tra rằng quan hệ "liên lạc được" là một quan hệ tương
đương trên không gian trạng thái E. Theo quan hệ này không gian E được
phân hoạch thành các lớp rời nhau. Hai trạng thái bất kỳ cùng thuộc một
lớp thì liên lạc được với nhau, hai trạng thái khác lớp không thể liên lạc được
với nhau.
Định nghĩa 1.5. Xích Markov được gọi là tối giản nếu hai trạng thái bất kỳ
là liên lạc được. Có nghĩa là theo cách phân lớp trên thì E không thể phân
hoạch thành các lớp con nhỏ hơn.
Nếu xích không tối giản thì E được phân hoạch thành các lớp rời nhau
E = E
1

∪E
2
∪ ∪E
k
. Có thể xem mỗi E
k
là không gian trạng thái của xích
Markov tối giản. Như vậy việc nghiên cứu xích Markov có thể quy về việc
nghiên cứu các xích tối giản.
Ví dụ 1.11. Cho xích Markov với 5 trạng thái E = {1, 2, 3, 4, 5} với ma trận
xác suất chuyển là
P =

P
1
0
0 P
2

22 Chương 1. Quá trình Markov
trong đó
P
1
=

1/32/3
1/43/4

và
P

2
=



010
1/201/2
010



.
Khi đó
P (n)=P
n
=

P
n
1
0
0 P
n
2

.
Do đó E = E
1
∪ E
2

với E
1
= {1, 2},E
2
= {3, 4, 5}.
Ví dụ 1.12. Cho xích Markov với 4 trạng thái E = {1, 2, 3, 4} với ma trận
xác suất chuyển là
P
2
=





001/21/2
001/21/2
1/21/20 0
1/21/20 0





Xích này là tối giản. Thật vậy rõ ràng 1 ↔ 3, 1 ↔ 4, 2 ↔ 3, 2 ↔ 4.Tacó
1 → 3, 3 → 2 suy ra 1 → 2.Lạicó2 → 3, 3 → 1 suy ra 2 → 1.Vậy1 ↔ 2 .
Tương tự ta có 3 ↔ 4. Vậy hai trạng thái bất kỳ là liên lạc được do đó đây
là xích tối giản.
Định nghĩa 1.6. Chu kỳ của trạng thái i ký hiệu là d(i) là ước chung lớn
nhất của tất cả các số nguyên dương n ≥ 1 mà P

ii
(n) > 0. Nếu P
ii
(n)=0
với mọi n ≥ 1 thì ta quy ước đặt d(i)=0.
Định lý 1.6. Nếu i ↔ j thì d(i)=d(j). Vậy các trạng thái cùng một lớp có
cùng một chu kỳ d và ta gọi số d chung đó là chu kỳ của lớp.
Chứng minh. Do i ↔ j nên tồn tại k,l sao cho P
ij
(k) > 0,P
ji
(l) > 0. Theo
phương trình C-K ta có P
ii
(k + l)=

h∈E
P
ih
(k)P
hi
(l) ≥ P
ij
(k)P
ji
(l) > 0.
Vậy d(i)|k + l. Giả sử n ≥ 1 sao cho P
jj
(n) > 0. Sử dụng phương trình C-K
1.2. Phân loại trạng thái xích Markov 23

như trên ta có P
ii
(k + l + n) ≥ P
ij
(k)P
jj
(n)P
ji
(l) > 0.Vậyd(i)|k + l + n →
d(i)|n.Vậyd(i) |d(j). Tương tự d( j)|d(i). Thành thử d(i)=d(j).
Giả sử d là chu kỳ của một xích tối giản với không gian trạng thái E.
Nếu d =1ta nói rằng xích không có chu kỳ. Nếu d>1 thì có thể chứng
minh rằng E được phân hoạch thành d tập conE = C
0
∪ C
1
∪ ∪C
d−1
sao
cho sau một bước hệ sẽ chuyển từ một trạng thái thuộc C
k
sang một trạng
thái thuộc C
k+1
(quy ước C
d
= C
0
). Vì vậy mỗi tập con có thể lấy làm không
gian trạng thái của một xích Markov mới. Xích này tối giản và không có chu

kỳ. Tóm lại chúng ta có thể quy việc nghiên cúu xích Markov tổng quát về
việc nghiên cứu xích tối giản, không có chu kỳ.
Định nghĩa 1.7. Ký hiệu f
ii
(n) là xác suất để hệ xuất phát từ i lần đầu tiên
quay lại i ở thời diểm n. Nghĩa là
f
ii
(n)=P (X
n
= i, X
n−1
= i, , X
1
= i|X
0
= i)
và ký hiệu
f
∗
ii
=
∞

n=1
f
ii
(n)
là xác suất để hệ xuất phát từ i quay trở lại i sau một số hữu hạn bước. Nếu
f

∗
ii
=1ta nói i là trạng thái hồi quy (quay lại). Nếu trái lại f
∗
ii
< 1 ta nói i
là trạng thái không hồi quy.
Định lý cơ bản sau đây cho ta một tiêu chuẩn để xác định tính hồi quy
của một trạng thái.
Định lý 1.7. Trạng thái i là hồi quy khi và chỉ khi
∞

n=1
P
ii
(n)=∞. (1.6)
Chứng minh. Chứng minh sử dụng hai bổ đề sau
24 Chương 1. Quá trình Markov
Bổ đề 1.2. Ta có
P
ii
(n)=
n

k=0
f
ii
(k)P
ii
(n − k)

trong đó f
ii
(0) = 0.
Chứng minh bổ đề 1.2. Với mỗi 0 ≤ k ≤ n gọi E
k
là biến cố :" X
n
= i và
hệ lần đầu tiên quay lại i ở bước thứ k " ta có
P
ii
(n)=P (X
n
= i|X
0
= i)=
n

k=0
P (E
k
)P (X
n
= i|E
k
,X
0
=1)
=
n


k=0
f
ii
(k)P (X
n
= i|X
k
= i)=
n

k=0
f
ii
(k)P
ii
(n − k).
Bổ đề 1.3. (Aben)
(i) Nếu chuỗi

∞
k=0
a
k
= a hội tụ thì
lim
s→1
−
∞


k=0
a
k
s
k
=
∞

k=0
a
k
= a.
(ii) Nếu a
k
≥ 0 và lim
s→1
−

∞
k=0
a
k
s
k
= a<∞ thì
∞

k=0
a
k

= lim
s→1
−
∞

k=0
a
k
s
k
= a.
Ta bắt đầu chứng minh định lý. Xét các chuỗi luỹ thừa sau
P
ii
(s)=
∞

n=0
P
ii
(n)s
n
,,|s| < 1
F
ii
(s)=
∞

n=0
f

ii
(n)s
n
,,|s| < 1
Ta có
F
ii
(s)P
ii
(s)=
∞

n=0
c
k
s
k
, |s| < 1