BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

KHOA TOÁN

NGUYỄN THỊ HẰNG

XÍCH MARKOV VÀ
ỨNG DỤNG TRONG VẤN ĐỀ TRỘN BÀI

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

Hà Nội – Năm 2017


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

KHOA TOÁN

XÍCH MARKOV VÀ
ỨNG DỤNG TRONG VẤN ĐỀ TRỘN BÀI
Chuyên ngành: Toán ứng dụng

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. TRẦN VĨNH ĐỨC

Hà Nội – Năm 2017


2.1.1

Ký hiệu chu trình . . . . . . . . . . . . . . . . 23

2.1.2

Sinh hoán vị ngẫu nhiên . . . . . . . . . . . . 24

2.1.3

Tính chẵn lẻ của hoán vị

. . . . . . . . . . . 25

2.2 Sự đổi chỗ ngẫu nhiên . . . . . . . . . . . . . . . . . 27
i


Khóa luận tốt nghiệp Đại học

MỤC LỤC

2.2.1

Chặn trên và ghép đôi . . . . . . . . . . . . . 28

2.2.2

Chặn trên qua thời điểm dừng mạnh . . . . . 30


Đặc biệt,tôi xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc tới
TS. Trần Vĩnh Đức, người đã trực tiếp hướng dẫn, chỉ bảo tận tình
giúp đỡ để tôi có thể hoàn thành khóa luận này.
Hà Nội, tháng 5 năm 2017
Sinh viên

Nguyễn Thị Hằng

2


GIỚI THIỆU
1. Lý do chọn đề tài
Việc tráo bài chủ yếu là một phương pháp để giảm khả năng gian
lận của một ai đó bằng cách thao túng thứ tự của quân bài để đạt
được lợi thế. Vậy tráo bài như vậy bao nhiêu lần để bộ bài đạt đến
sự ngẫu nhiên cần thiết là vấn đề ta sẽ nghiên cứu trong bài luận
này.

2. Mục đích nghiên cứu
Ta vận dụng tính dừng của xích Markov để tính toán số lần tráo
bài để bộ bài ngẫu nhiên.
Rèn luyện tư duy nghiên cứu khoa học và nâng cao trình độ nhận
thức của bản thân.

3. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: Xích Markov và ứng dụng.
Phạm vi nghiên cứu: Cách tráo bài ngẫu nhiên.

3

Một xích Markov hữu hạn là một quá trình mà sự chuyển động
của các phần tử của một tập hữu hạn Ω được xác định như sau:
tại x ∈ Ω, vị trí tiếp theo có phân bố xác suất P (x, ·). Đặc biệt
hơn, một dãy dãy các ngẫu nhiên(X0, X1, ...) là một xích Markov
với không gian trạng thái Ω và ma trận chuyển P nếu ∀x, y ∈ Ω, với
t ≥ 1 và Ht−1 = ∩t−1
s=0 {Xs = xs } thỏa mãn P(Ht−1 ∩ {Xt = x}) > 0,
ta có
P{Xt+1 = y | Ht−1 ∩ {Xt = x}} = P{Xt+1 = y | Xt = x} = P (x, y).
(1.1)
Phương trình (1.1) được gọi là tính chất Markov, có nghĩa là xác
suất có điều kiện đi từ trạng thái x vào trạng thái y là như nhau, ta
không quan tâm dãy x0, x1, ...xt−1 là các trạng thái đứng trước x.
Ví dụ sau đây giải thích tại sao ma trận P , |Ω| × |Ω| phần tử thỏa
mãn mô tả của chuyển động.
Xét hàng thứ x của ma trận P có phân bố P (x, ·). Do P là ngẫu
5


Khóa luận tốt nghiệp Đại học

CHƯƠNG 1. XÍCH MARKOV

nhiên, trong nó chứa tất cả các phần tử không âm và
P (x, y) = 1,

∀x ∈ Ω.

y∈Ω


thì (X0 , X1, ...) là một xích Markov với ma trận chuyển P . Chú ý
rằng hàng đầu tiên của ma trận P là phân phối có điều kiện của
Xt+1 cho bởi Xt = e, khi đó hàng thứ hai là phân phối có điều kiện
của Xt+1 cho bởi Xt = w.
Giả thiết rằng con ếch đã ở lá phía đông vào ngày chủ nhật. Khi
nó tỉnh dậy vào ngày thứ hai, thì xác suất p chuyển sang lá phía
6


Khóa luận tốt nghiệp Đại học

CHƯƠNG 1. XÍCH MARKOV

tây và lá phía đông có xác suất là 1 − p. Do đó,
P{X1 = e|X0 = e} = 1 − p,

P{X1 = w|X0 = e} = p.

(1.3)

Ngày thứ ba như thế nào? Xem xét hai khả năng như X1 , ta thấy
rằng
P{X2 = e|X0 = e} = (1 − p)(1 − p) + pq

(1.4)

P{X2 = w|X0 = e} = (1 − p)p + p(1 − q).

(1.5)



CHƯƠNG 1. XÍCH MARKOV

thuộc vào p và q) khi t → ∞. Bất kỳ phân phối hữu hạn π nào đều
thỏa mãn π = πP , điều đó dẫn đến
π(e) =

q
,
p+q

π(w) =

p
.
p+q

Nếu ta xác định
t

= µt (e) −

q
,
p+q

thì với định nghĩa của µt+1 , dãy (
t+1

t)

p+q

(1.9)

đối với mọi phân phối ban đầu bất kì. Như vậy, µt tiến tới π khi
t → ∞.
Những tính toán mà chúng ta vừa làm đối với một xích hai trạng
thái sẽ được khái quát lên một xích Markov hữu hạn bất kỳ. Nói
riêng, phân phối tại thời điểm t có thể được xác định bởi phép nhân
ma trận. Cho (X0 , X1, ...) là xích Markov hữu hạn với không gian
trạng thái Ω và ma trận chuyển P , giả sử vectơ hàng µt là phân
phối của Xt :
µt (x) = P{Xt = x},

∀x ∈ Ω.

Từ điều kiện có thể có ở trên, cho trạng thái t + 1, ta thấy rằng

µt+1(y) =

µt (x)P (x, y) với mọi y ∈ Ω.

P {Xt = x}P (x, y) =
x∈Ω

x∈Ω

8



Px {Xt = y} = (δx P t )(y) = P t (x, y).
Có nghĩa, xác suất của sự chuyển động trong t bước từ x đến y được
cho bởi phần tử ở hàng (x, y) của ma trận P t . Ta gọi đó là xác xuất
chuyển t - bước.
Chú ý 1.1.1. Một phân phối xác suất µ trong Ω sẽ đồng nhất với
một vectơ hàng. Cho bất kì A ⊂ Ω, ta viết
µ(x).

π(A) =
x∈A

Với x ∈ Ω, hàng phần tử của ma trận P có được từ x sẽ kí hiệu là
P (x, ·).
9


Khóa luận tốt nghiệp Đại học

1.2

CHƯƠNG 1. XÍCH MARKOV

Biểu diễn ánh xạ ngẫu nhiên

Hình 1.3: Hành trình ngẫu nhiên trên Z10 là tuần hoàn, do mỗi bước đi từ trạng
thái chẵn đến trạng thái lẻ hoặc ngược lại. Hành trình ngẫu nhiên trên Z9 là phi
tuần hoàn.

Ví dụ 1.2.1. (Hành trình ngẫu nhiên trên n-chu trình)
Cho Ω = Zn = {0, 1, 2, ..., n − 1}, tập các số dư mođun n. Xét

đồng hồ. Nếu đồng xu xuất hiện mặt sấp thì hành trình chuyển động
một bước ngược chiều kim đồng hồ.
Mệnh đề 1.2.1. Mọi ma trận chuyển trên một không gian trạng
thái hữu hạn đều có một biểu diễn ánh xạ ngẫu nhiên.

10


Khóa luận tốt nghiệp Đại học

1.3

CHƯƠNG 1. XÍCH MARKOV

Tính tối giản và phi tuần hoàn

Một xích P được gọi là tối giản nếu cho hai trạng thái bất kỳ
x, y ∈ Ω thì tồn tại một số nguyên t (có thể phụ thuộc vào x, y) sao
cho P t (x, y) > 0. Có nghĩa là nó có thể đi bất kỳ từ trạng thái này
đến trạng thái khác với ma trận xác suất chuyển dương.
Cho T (x) := {t ≥ 1 : P t (x, x) > 0} là tập các thời điểm mà xích
có thể quay trở lại trạng thái dương x. Chu trình của trạng thái x
được xác định bởi ước chung lớn nhất của τ (x).
Bổ đề 1.1. Nếu P tối giản được thì UCLN T (x) = U CLN T (y),
với mọi x, y ∈ Ω.
Cho một xích tối giản, chu trình của xích được xác định là chu
trình chung của tất cả các trạng thái. Xích được gọi là phi tuần hoàn
nếu tất cả các trạng thái có chu trình là 1. Nếu một xích không phi
tuần hoàn thì ta gọi là tuần hoàn.
Mệnh đề 1.3.1. Nếu P phi tuần hoàn và tối giản thì sẽ có một số

1/4






1/2




1/4





0

nếu k ≡ j + 1 (modn),
nếu k ≡ j

(modn),

nếu k ≡ j − 1 (modn),
trái lại.

Hành trình chậm ngẫu nhiên trên n chu trình là tối giản và phi
tuần hoàn với mọi n.

Hình 1.4: Đồ thị với tập đỉnh {1, 2, 3, 4, 5} và có 6 cạnh.

trình ngẫu nhiên đơn giản trên G là


0 1/2 1/2 0
0




 1/3 0 1/3 1/3 0 




P =  1/4 1/4 0 1/4 1/4 




 0 1/2 1/2 0
0 


0
0
1
0
0


x∼y

13

deg(x)
= deg(y).
deg(x)

(1.15)


Khóa luận tốt nghiệp Đại học

CHƯƠNG 1. XÍCH MARKOV

Để có được một xác suất, ta chuẩn hóa

y∈V

deg(y) = 2|E|. Ta có

được
π(y) =

deg(y)
,
2|E|

∀y ∈ Ω,

CHƯƠNG 1. XÍCH MARKOV

(i) tồn tại phân phối xác suất π trên Ω sao cho π = πP và π(x) >
0, ∀x ∈ Ω,
(ii) π(x) =

1
.
Ex (τx+ )

Tính duy nhất của phân phối dừng
Gọi hàm số h : Ω → R điều hòa tại x nếu
h(x) =

P (x, y)h(y).

(1.16)

y∈Ω

Một hàm số là điều hòa trên D ⊂ Ω nếu nó điều hòa tại mọi điểm
x ∈ D. Nếu coi h là một vectơ cột thì hàm đó được gọi là điều hòa
trên tất cả tập của Ω thỏa mãn phương trình ma trận P h = h.
Bổ đề 1.3. Giả sử P là tối giản. Một hàm số h điều hòa tại mọi
điểm của Ω là hằng số.
Hệ quả 1.1. Cho P là ma trận chuyển của xích Markov tối giản.
Khi đó tồn tại duy nhất phân phối xác suất π thỏa mãn π = πP .

1.6


ngược chiều kim đồng hồ với xác suất q = 1 − p.
1
Phân phối dừng là đều nếu π(k) = thì
n
π(j)P (j, k) = π(k − 1)p + π(k + 1)q =
j∈Zn

do π là phân phối dừng. Tuy nhiên nếu p =
π(k)P (k, k + 1) =

1
,
n

1
thì
2

p
q
= = π(k + 1)P (k + 1, k).
n n

Thời điểm nghịch đảo của xích Markov tối giản với ma trận chuyển
P và phân phối dừng π là xích có ma trận
P (x, y) :=

π(y)P (y, x)
.
π(x)

Ta nói x liên thông với y và viết x ↔ y khi và chỉ khi x → y và
y → x. Lớp tương đương ↔ được gọi là lớp liên thông. Với x ∈ Ω,
lớp liên thông của x được kí hiệu là [x].
Quan sát rằng khi P tối giản, tất cả các trạng thái của xích nằm
trong lớp liên thông đơn.
Bổ đề 1.4. Nếu x là trạng thái cơ bản và x → y thì y cũng là trạng
thái cơ bản.
Bổ đề 1.5. Mọi chuỗi hữu hạn đều có ít nhất một lớp cơ bản.
17


Khóa luận tốt nghiệp Đại học

CHƯƠNG 1. XÍCH MARKOV

Mệnh đề 1.7.1. Nếu π là phân phối dừng của ma trận chuyển hữu
hạn P thì π(y0 ) = 0 với mọi trạng thái không cơ bản y0 .

Mệnh đề 1.7.2. Phân phối dừng π của ma trận chuyển P là duy
nhất khi và chỉ khi nó là một lớp liên thông cơ bản duy nhất.

1.8

Ví dụ

1) Người chơi bạc phá sản
Xét một người chơi bạc, khi gieo đồng xu đồng chất và độc lập.
Nếu đồng xu xuất hện mặt ngửa thì người đó được 1$, nếu xuất
hiện mặt sấp thì người đó mất 1$. Cuộc chơi sẽ dừng lại nếu người
thắng được n$ hoặc người đó hết tiền.


Pk {Xτ = n} =
và

Chứng minh.
Giả sử gọi pk là xác suất mà người chơi kiếm được n$ trước khi
dừng cuộc chơi và lúc đầu người đó có k$. Ta có kết quả đồng thời
p0, p1, ..., pn. Rõ ràng p0 = 0 và pn = 1, khi đó
1
1
pk = pk−1 + pk+1, với 1 ≤ k ≤ n − 1.
2
2

(1.23)

Tại sao? Với xác suất 1/2 thì hành trình chuyển động đến k + 1.
Xác suất có điều kiện của chuyển động đến n trước 0, tức là bắt
đầu từ k + 1 là xác suất là pk+1. Tương tự như vậy với xác suất là
1/2, chuyển động tới k − 1 và xác suất có điều kiện đến n trước 0
của trạng thái k − 1 là pk−1.
Nghiệm của (1.23) là nghiệm của phương trình tuyến tính cho
bởi pk = k/n với 0 ≤ k ≤ n.
Với (1.22), viết fk tại thời điểm kì vọng Ek (τ ) và số dương k. Rõ
ràng f0 = fn = 0, hành trình bắt đầu tại thời điểm có khả năng xảy
ra. Cho 1 ≤ k ≤ n − 1, ta có
1
1
fk = (1 + fk+1) + (1 + fk−1).
2

và
k
.
n
Mọi quỹ đạo của xích này là không giảm. Một khi xích đạt đến
P{Xt+1 = k|Xt = k} =

trạng thái n (tương ứng với bộ sưu tập đầy đủ), nó được dừng ở đó.
Mệnh đề 1.8.2. Xét một nhà sưu tầm cố gắng thu nhập một bộ
các phiếu giảm giá. Giả sử mỗi phiếu giảm giá mới được chọn thống
nhất và độc lập từ bộ có n loại và cho τ (ngẫu nhiên) là tập các
phiếu giảm giá đầu tiên được sưu tầm . Thì
n

E(τ ) = n
k=1

20

1
.
k


Khóa luận tốt nghiệp Đại học

CHƯƠNG 1. XÍCH MARKOV

Chứng minh.
Kì vọng E(τ ) có được bằng cách viết τ như là một tổng của các

k=1

k=1

Mệnh đề 1.8.3. Cho τ là một biến ngẫu nhiên của bộ phiếu giảm
giá như trong mệnh đề 1.8.2 . Với mọi c > 0
n

P {τ > logn + cn } = P (

n

Ai ) ≤
i=1

P (Ai ).

(1.27)

i=1

Chứng minh. Cho Ai là biến cố sao cho loại phiếu thứ i không xuất
hiện giữa log n + cn loại phiếu giảm giá đầu tiên. Quan sát ta
thấy
P {τ > log n + cn } ≤ e−c .

(1.28)

Mỗi lượt sưu tầm mà không phải loại phiếu thứ i, nó có xác suất
là 1 − n−1 và nó là độc lập, thì vế phải của biểu thức 1.28 bị chặn