Mô hình đơn giản của tìm kiếm Brownian với quay lại ngẫu nhiên đến vị
trí ban đầu được giới thiệu bởi Evans and Majumdar [19]. Sau đó nó được
mở rộng nghiên cứu theo nhiều cách khác nhau, với nhiều cách quay lại ngẫu
nhiên, đa dạng từ hệ đơn hạt cho đến hệ nhiều hạt. Ví dụ nó có thể quay lại
ngẫu nhiên đến vị trí nào đó tốt hơn vị trí ban đầu (có thể chọn ngẫu nhiên).
Trong bài báo [22] năm 2015 trên tạp chí Physical Review E, các tác giả
Satya N. Majumdar, Sanijb Sabhapandit and Gregory Schehr giới thiệu mô
hình bước đi ngẫu nhiên trong lưới Z1 với sự quay lại (reset đến) vị trí cực
đại bởi xác suất cố định r. Chiến lược này có thể xem như kết hợp giữa tìm
kiếm tất định và tìm kiếm ngẫu nhiên. Trong chiến lược tìm kiếm chỉ tất định
nếu mỗi vị trí được thăm mà không được đánh dấu thì nó sẽ bị lãng quên.
Nhưng trong chiến lược mới này, nó có thể được thăm lại đồng thời ta cũng
có thể đi đến những vị trí mới (bởi quay lại vị trí cực đại). Mô hình này có thể
tương tự đến quá trình động vật tìm kiếm thức ăn. Trong thời gian tìm thức
ăn, động vật thường di chuyển theo một bước đi ngẫu nhiên [23]-[24]. Một
cách tự nhiên, những động vật thông minh (có trí nhớ) thường nhớ lại những
chỗ đã từng đi, do vậy nó sẽ thăm lại những nơi đã đến vì khả năng có thức ăn
có thể cao hơn nơi chưa từng đến. Giả sử thiết lập trên lưới Z1, động vật bên
cạnh di chuyển ngẫu nhiên theo bước đi ngắn, có thể thăm lại với xác suất cố Mô hình đơn giản của tìm kiếm Brownian với quay lại ngẫu nhiên đến vị
trí ban đầu được giới thiệu bởi Evans and Majumdar [19]. Sau đó nó được
mở rộng nghiên cứu theo nhiều cách khác nhau, với nhiều cách quay lại ngẫu
nhiên, đa dạng từ hệ đơn hạt cho đến hệ nhiều hạt. Ví dụ nó có thể quay lại
ngẫu nhiên đến vị trí nào đó tốt hơn vị trí ban đầu (có thể chọn ngẫu nhiên).
Trong bài báo [22] năm 2015 trên tạp chí Physical Review E, các tác giả
Satya N. Majumdar, Sanijb Sabhapandit and Gregory Schehr giới thiệu mô
hình bước đi ngẫu nhiên trong lưới Z1 với sự quay lại (reset đến) vị trí cực
đại bởi xác suất cố định r. Chiến lược này có thể xem như kết hợp giữa tìm
kiếm tất định và tìm kiếm ngẫu nhiên. Trong chiến lược tìm kiếm chỉ tất định
nếu mỗi vị trí được thăm mà không được đánh dấu thì nó sẽ bị lãng quên.
Nhưng trong chiến lược mới này, nó có thể được thăm lại đồng thời ta cũng
có thể đi đến những vị trí mới (bởi quay lại vị trí cực đại). Mô hình này có thể
tương tự đến quá trình động vật tìm kiếm thức ăn. Trong thời gian tìm thức
ăn, động vật thường di chuyển theo một bước đi ngẫu nhiên [23]-[24]. Một
cách tự nhiên, những động vật thông minh (có trí nhớ) thường nhớ lại những
chỗ đã từng đi, do vậy nó sẽ thăm lại những nơi đã đến vì khả năng có thức ăn
có thể cao hơn nơi chưa từng đến. Giả sử thiết lập trên lưới Z1, động vật bên
cạnh di chuyển ngẫu nhiên theo bước đi ngắn, có thể thăm lại với xác suất cố
BỘ GIÁO DỤC
VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------
Nguyễn Văn Quyết
MỘT SỐ ĐỊNH LÝ GIỚI HẠN
CHO BƯỚC ĐI NGẪU NHIÊN CÓ TRÍ NHỚ
LUẬN VĂN THẠC SĨ TOÁN HỌC
Hà Nội – 2020
BỘ GIÁO DỤC
VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------
Nguyễn Văn Quyết
MỘT SỐ ĐỊNH LÝ GIỚI HẠN
CHO BƯỚC ĐI NGẪU NHIÊN CÓ TRÍ NHỚ
Chuyên ngành: Toán giải tích
Mã số: 8 46 01 02
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TSKH. ĐOÀN THÁI SƠN
Hà Nội - 2020
LỜI CAM ĐOAN
Tôi xin cam đoan những gì viết trong luận văn là do sự tìm tòi, học hỏi của
bản thân và sự hướng dẫn tận tình của thầy Đoàn Thái Sơn và thầy Cấn Văn
Hảo. Mọi kết quả nghiên cứu cũng như ý tưởng của tác giả khác, nếu có đều
được trích dẫn cụ thể. Đề tài luận văn này cho đến nay chưa được bảo vệ tại
bất kì một hội đồng bảo vệ luận văn thạc sĩ nào và cũng chưa hề được công bố
trên bất kì một phương tiện nào. Tôi xin chịu trách nhiệm về những lời cam
đoan.
Hà Nội, tháng 10 năm 2020
Học viên
Nguyễn Văn Quyết
3
LỜI CẢM ƠN
Đầu tiên, tôi xin được tỏ lòng biết ơn sâu sắc nhất của mình tới PGS.TSKH.
Đoàn Thái Sơn và TS. Cấn Văn Hảo, hai người thầy đã trực tiếp hướng dẫn
và giúp đỡ tôi tìm ra đề tài luận văn cũng như định hình hướng nghiên cứu.
Luận văn này được hoàn thành dưới sự hướng dẫn tận tình trong một thời gian
dài của hai thầy. Các thầy đã luôn quan tâm, giúp đỡ, động viên tôi trong suốt
quá trình học tập và nghiên cứu.
Tôi xin chân thành cảm ơn Trung tâm Quốc tế Đào tạo và Nghiên cứu Toán
học, Viện Toán học đã hỗ trợ tài chính giúp tôi hoàn thành hai năm học thạc
sỹ. Bên cạnh đó, trong quá trình học tập, nghiên cứu và thực hiện Luận văn,
tôi còn nhận được nhiều sự quan tâm, góp ý, hỗ trợ quý báu của các thầy cô,
anh chị và bạn bè trong và ngoài Viện Toán học.
Tôi cũng xin trân trọng cảm ơn sự giúp đỡ và tạo điều kiện thuận lợi về
môi trường học tập của nơi đào tạo là Viện Toán học và cơ sở đào tạo là Học
viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt
Nam trong suốt quá trình thực hiện Luận văn này.
Đặc biệt, tôi xin cảm ơn gia đình, người thân và bạn bè đã luôn sát cánh,
động viên và khích lệ tôi trong suốt quá trình học tập và nghiên cứu.
4
Danh mục các hình vẽ, đồ thị
Hình 3.1: Minh họa hai quá trình X và X̂ được xây dựng từ bước đi ngẫu
nhiên đơn giản Z và tập J với hai thời điểm reset t1 , t2 ..............................40
Hình 3.2: Đồ thị so sánh kết quả của chúng ta và của bài báo [22].................54
Hình 3.3: Kết quả thực nghiệm dáng điệu của
M
√n
n
và
Xn
√
n
với n = 106 ...........54
Mục lục
Lời cam đoan
2
Lời cảm ơn
3
Danh mục các hình vẽ, đồ thị
4
Mục lục
6
Mở đầu
7
1 Giới thiệu
10
1.1 Sơ lược một số kết quả chính . . . . . . . . . . . . . . . . . .
10
1.2 Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . .
14
1.2.1 Bước đi ngẫu nhiên dừng . . . . . . . . . . . . . . . . .
14
1.2.2 Quá trình tái tạo . . . . . . . . . . . . . . . . . . . . . .
17
2 Bước đi ngẫu nhiên có trí nhớ cố định
21
2.1 Mô hình toán học . . . . . . . . . . . . . . . . . . . . . . . .
21
2.2 Các định lý giới hạn cho Mn và Xn . . . . . . . . . . . . . . .
25
2.2.1 Tính chất của τ và Kn . . . . . . . . . . . . . . . . . . .
25
2.2.2 Các định lý giới hạn cho Mn và Xn . . . . . . . . . . . .
30
3 Bước đi ngẫu nhiên có trí nhớ suy giảm
34
3.1 Một hiệu chỉnh của (Xn )n≥0 . . . . . . . . . . . . . . . . . . .
36
3.2 Dáng điệu tiệm cận của E[Xn ] và E[Mn ] . . . . . . . . . . . .
40
3.2.1 Pha dưới 0 < a < 1 . . . . . . . . . . . . . . . . . . . .
44
5
6
3.2.2 Điểm chuyển pha a = 1 . . . . . . . . . . . . . . . . . .
48
3.2.3 Pha trên a > 1 . . . . . . . . . . . . . . . . . . . . . . .
55
Kết luận và kiến nghị
62
Tài liệu tham khảo
63
7
MỞ ĐẦU
Tìm kiếm là một trong những quá trình cơ bản và quan trọng mà ta có thể
bắt gặp mọi lúc mọi nơi [1, 2, 3, 4]. Chẳng hạn động vật tìm kiếm thức ăn,
con người tìm kiếm đồ vật bị mất hay tìm kiếm ai đó trong đám đông. Gần
đây, vấn đề tìm kiếm thu hút sự quan tâm lớn của các cộng đồng vật lý, toán
học, khoa học máy tính [5]. Một cách tự nhiên là phải đưa ra các chiến lược
tìm kiếm hiệu quả. Thông thường nó có thể hoặc là tất định hoặc là ngẫu
nhiên. Trong chiến lược tất định, người tìm kiếm sử dụng những luật tất định
(không thay đổi theo thời gian), ví dụ máy xén cỏ, robot lau nhà,. . . Ngược
lại, chiến lược tìm kiếm ngẫu nhiên có luật tiến hóa theo ngẫu nhiên. Chiến
lược tìm kiếm phụ thuộc vào mỗi vấn đề xác định nhưng đều hướng đến một
thuật toán tìm kiếm tối ưu. Chiến lược nổi bật trong số chúng đó là chiến lược
gián đoạn mà trộn cả: bước đi ngắn (đến lân cận nào đó) khi ta tìm kiếm một
mục tiêu và bước đi dài (nhảy đến vị trí nào đó) khi không tìm thấy mục tiêu
nhưng ta nhảy đến một nơi khác [6, 7, 8]. Các bước đi ngắn được mô hình
đặc trưng bởi sự khuếch tán hoặc bước đi ngẫu nhiên (bước tới các vị trí liền
kề). Ngược lại, bước đi dài thường ít xảy ra, và mang một ý nghĩa kí ức nhất
định. Ví dụ khi động vật tìm kiếm thức sau một thời gian dài mà không hiệu
quả, chúng nên quay lại một vị trí nào đó trong quá khứ và tiếp tục. Tương
tự khi ta tìm kiếm một chiếc chìa khóa bị mất mà không thấy, ta nên quay
lại tìm từ một vị trí đã từng tìm kiếm để kiểm tra lại. Một ví dụ quan trọng
khác trong mô phỏng máy tính của một hệ năng lượng. Nó bắt đầu từ cấu hình
ban đầu và cố gắng tìm đến vị trí năng lượng tối thiểu toàn cục. Tuy nhiên ở
nhiệt độ thấp, hệ có thể tắc vào tối thiểu địa phương ở thời gian dài. Để tăng
tốc độ tìm kiếm, nó nên dừng quá trình và quay lại cấu hình ban đầu. Trong
khoa học máy tính, các thuật toán nổi tiếng như Page-rank hay các thuật toán
8
ngẫu nhiên thường có thể bị rơi vào tắc nghẽn và nó thường phải khởi động
lại thuật toán [9]-[13]. Chiến lược bước đi dài có thể được mô hình phụ thuộc
vào từng ứng dụng xác định [4], chẳng hạn quay lại Poissonian đến cấu hình
ban đầu, quay lại không Poissonian, hay quay lại sử dụng trí nhớ trong quá
khứ. Một phương thức bước đi dài quan trọng đó là quay lại một vị trí xác
định với một xác xuất hữu hạn. Khi ta tìm kiếm không thành công bởi bước
đi ngắn thì để tốt hơn ta nên khởi động lại quá trình hơn là tiếp tục. Sự ảnh
hưởng của phương thức quay lại ngẫu nhiên được nghiên cứu đa dạng trong
[14]-[17].
Mô hình đơn giản của tìm kiếm Brownian với quay lại ngẫu nhiên đến vị
trí ban đầu được giới thiệu bởi Evans and Majumdar [19]. Sau đó nó được
mở rộng nghiên cứu theo nhiều cách khác nhau, với nhiều cách quay lại ngẫu
nhiên, đa dạng từ hệ đơn hạt cho đến hệ nhiều hạt. Ví dụ nó có thể quay lại
ngẫu nhiên đến vị trí nào đó tốt hơn vị trí ban đầu (có thể chọn ngẫu nhiên).
Trong bài báo [22] năm 2015 trên tạp chí Physical Review E, các tác giả
Satya N. Majumdar, Sanijb Sabhapandit and Gregory Schehr giới thiệu mô
hình bước đi ngẫu nhiên trong lưới Z1 với sự quay lại (reset đến) vị trí cực
đại bởi xác suất cố định r. Chiến lược này có thể xem như kết hợp giữa tìm
kiếm tất định và tìm kiếm ngẫu nhiên. Trong chiến lược tìm kiếm chỉ tất định
nếu mỗi vị trí được thăm mà không được đánh dấu thì nó sẽ bị lãng quên.
Nhưng trong chiến lược mới này, nó có thể được thăm lại đồng thời ta cũng
có thể đi đến những vị trí mới (bởi quay lại vị trí cực đại). Mô hình này có thể
tương tự đến quá trình động vật tìm kiếm thức ăn. Trong thời gian tìm thức
ăn, động vật thường di chuyển theo một bước đi ngẫu nhiên [23]-[24]. Một
cách tự nhiên, những động vật thông minh (có trí nhớ) thường nhớ lại những
chỗ đã từng đi, do vậy nó sẽ thăm lại những nơi đã đến vì khả năng có thức ăn
có thể cao hơn nơi chưa từng đến. Giả sử thiết lập trên lưới Z1 , động vật bên
cạnh di chuyển ngẫu nhiên theo bước đi ngắn, có thể thăm lại với xác suất cố
9
định khác 0 đến vị trí cực đại hoặc cực tiểu hiện tại. Tuy nhiên, động vật khi
già đi thường có trí nhớ suy giảm theo thời gian, nghĩa là xác suất chúng thăm
lại nơi từng đến sẽ giảm dần theo theo thời gian. Hiện tượng thú vị này yêu
cầu chúng ta cần đưa ra một nghiên cứu mới về mô hình bước đi ngẫu nhiên
có trí nhớ có thể thay đổi theo thời gian. Đặc biệt, chúng ta cần quan tâm liệu
tốc độ suy giảm trí nhớ ảnh hưởng như thế nào đến hoạt động tìm kiếm này.
Trong Luận văn này, chúng tôi sẽ nghiên cứu mô hình bước đi ngẫu nhiên
có trí nhớ cố định và trí nhớ có thể suy giảm theo thời gian. Trong bài báo
[22], các tác giả đã tính toán dáng điệu tiệm cận của các giá trị kì vọng và
phương sai bởi phương thức hàm sinh với các kỹ thuật tính toán giải tích rất
phức tạp. Trong Chương 2, chúng tôi sẽ xây dựng một cách tiếp cận khác
nhằm hoàn chỉnh nghiên cứu mô hình này. Từ đó, chúng tôi đạt được các kết
quả mà các tác giả đưa ra và đồng thời thu được các định lý giới hạn quan
trọng như luật mạnh của số lớn và định lý giới hạn trung tâm thông thường. Ở
Chương 3, chúng tôi sẽ đề xuất mô hình hoàn chỉnh cho bước đi ngẫu nhiên
có trí nhớ giảm dần theo thời gian. Chúng ta sẽ thấy sự chuyển pha theo tốc
độ suy giảm của trí nhớ của dáng điệu tiệm cận của kì vọng của bước ngẫu
nhiên. Chương 1 được dành để trình bày sơ lược mô hình và kết quả cũng như
các kiến thức chuẩn bị.
CHƯƠNG 1
GIỚI THIỆU
1.1
Sơ lược một số kết quả chính
Trong Luận văn này, chúng ta nghiên cứu về mô hình bước ngẫu nhiên
có trí nhớ. Cụ thể ở Chương 2, chúng ta nghiên cứu mô hình bước đi ngẫu
nhiên có trí nhớ trên Z1 được đề xuất trước đó vào năm 2015 [22]. Các tác giả
nghiên cứu mô hình bước đi ngẫu nhiên mà người đi bộ đang không ở vị trí
cực đại thì có khả năng reset về vị trí cực đại với xác suất cố định r, sang trái
hoặc phải với cùng xác suất
1−r
2 .
Ngược lại khi đang ở vị trí cực đại, người đi
bộ chỉ bước sang trái hoặc phải với xác suất 12 . Họ chỉ ra rằng khi 0 < r < 1
thì kì vọng và phương sai của biến ngẫu nhiên vị trí Xn và của biến ngẫu
nhiên vị trí cực đại Mn tăng trưởng tuyến tính theo thời gian với tốc độ lần
lượt là các hằng số v(r) và D(r) (xem trong công thức (2.1.5),(2.1.6)):
v(r) =
r(1 − r)
√
,
r − 2r2 + 2r − r2
và
h
i
p
D(r) = (2 − 2r − 5r + 3r ) + (2 − r − r + 2r ) r(2 − r)
2
3
2
×p
3
(1 − r)r2
r(2 − r)[r − 2r2 +
p
.
r(2 − r)]3
Bằng cách tiếp cận từ lý thuyết quá trình tái tạo, đầu tiên chúng ta kiểm chứng
lại ước lượng của kì vọng và phương sai, đồng thời từ đó xây dựng các định lý
10
11
giới hạn như luật mạnh của số lớn và định lý giới hạn trung tâm thông thường
cho cả Xn và Mn (cụ thể trong Định lý 2.2.1) ta có
Luật mạnh của số lớn và kỳ vọng:
Mn h.c.c
−−→ v(r)
n
và
Xn h.c.c
−−→ v(r),
n
khi n → ∞, và
E[Mn ]
E[Xn ]
= lim
= v(r),
n→∞
n→∞
n
n
lim
với v(r) cho bởi (2.1.5).
Định lý giới hạn trung tâm và phương sai:
Mn − µ0 λn d
√
→
− N (0, D(r)) và
n
Xn − µ0 λn d
√
→
− N (0, D(r)),
n
khi n → ∞ và
Var[Mn ]
Var[Xn ]
= lim
= D(r),
n→∞
n→∞
n
n
lim
với D(r) cho bởi (2.1.6).
Ở Chương 3 của Luận văn, ta nghiên cứu mô hình bước đi ngẫu nhiên có
trí nhớ suy giảm theo thời gian. Lúc này ở thời điểm n, xác suất reset về vị trí
cực đại là rn = min{ nra , 12 }. Chúng ta chỉ ra rằng dáng điệu tiệm cận kì vọng
của các biến ngẫu nhiên vị trí và vị trí cực đại thay đổi theo giá trị của a. Cụ
thể, trong Định lý 3.0.1 ta có
Dáng điệu tiệm cận của E[Xn ] và E[Mn ]:
E[Xn ]
= FX (a, r)
n→∞ ϕa (n)
lim
và
E[Mn ]
= FM (a, r).
n→∞ ψa (n)
lim
Khi 0 < a < 1:
ϕa (n) = ψa (n) = n1−a/2 ,
và
√
FX (a, r) = FM (a, r) =
2r
.
2−a
12
Tại a = 1:
ϕa (n) = ψa (n) =
√
n,
và
r
FX (a, r) = 2r2
2
B(3/2, r),
π
và
r
FM (a, r) = (2r2 + r)
2
B(3/2, r).
π
Khi a > 1:
3
2 −a
n
ϕa (n) = log n
1
và
ψa (n) =
khi 1 < a < 23 ,
khi a = 32 ,
khi a > 32 ,
√
n,
và
FX (a, r) = λ2 (a, r) − λ3 (a, r) + λ4 (a, r),
và
FM (a, r) = λ1 (a, r) + λ5 (a, r),
với λ1 (a, r), λ2 (a, r), . . . , λ5 (a, r) là các hằng số trong Bổ đề 3.2.8.
Chúng ta thấy rằng khi 0 < a < 1, dáng điệu tiệm cận kì vọng của Mn và
Xn cùng cỡ, cùng hàm tỷ lệ. Nhưng tại a = 1, chúng cùng cỡ và khác hàm
tỷ lệ. Còn khi a > 1 dáng điệu tiệm cận của E[Xn ] nhỏ hơn hẳn của E[Mn ].
Do vậy mô hình bước đi ngẫu nhiên có trí nhớ suy giảm xảy ra hiện tượng
chuyển pha theo giá trị của a. Hơn thế nữa, chúng ta thu được dáng điệu tiệm
13
cận của các hàm tỷ lệ:
p
r
∼ v(r)
2
pr
∼ v(r)
q2
2
π
FM (a, r) ∼ q
2
π
√
2r
√2r
khi a = 0, r → 0,
khi a → 0, r → 0,
khi a = 1, r → 0,
khi a → 1+ , r → 0,
khi a = 1, r → ∞,
khi a → 1− , r → ∞.
và
0
FX (a, r) =
0
khi a = 1, r → 0,
khi a → 1+ , r → 0,
pr
2 ∼ v(r)
p r ∼ v(r)
FX (a, r) ∼ √ 2
2r
√
2r
khi a = 0, r → 0,
khi a → 0, r → 0,
khi a = 1, r → ∞,
khi a → 1− , r → ∞.
Bây giờ ta thấy lại rằng trong trường hợp trí nhớ cố định 0 < r < 1,
D(r → 0) = 12 . Từ đó suy ra phương sai của Mn và Xn cùng cỡ tuyến tính
nhưng khác hệ số tỷ lệ với trường hợp r = 0 (với hệ số tỷ lệ DM (0) = 1−2/π
và DX (0) = 1), nghĩa là r = 0 là một điểm kỳ dị. Trong bài báo [22], các
tác giả nghiên cứu sự chuyển pha tại điểm kỳ dị r = 0 này thông qua một mô
hình tương đương với trường hợp a = 1 và đưa ra các hàm tỷ lệ (xem công
thức (124),(132) của [22]):
E[Mn ]
√
n
n→∞
FM (r) = lim
p
√
1
= √ [(r + 1/2)erf( r) + r/π exp(−r)]
2r
14
và
p
√
1
= √ [(r − 1/2)erf( r) + r/π exp(−r)].
2r
R
z
Trên đây hàm erf(z) = √2π 0 exp(−u2 )du.
E[Xn ]
√
n
n→∞
FX (r) = lim
Dựa vào dáng điệu tiệm cận của các hàm tỷ lệ trên khi r → 0 và r → ∞
(xem công thức (125) và (133)), các tác giả suy ra các hàm tỷ lệ này nội suy
trơn giữa hai trường hợp rn = r = 0 và rn > 0, r → ∞. Từ nghiên cứu cách
tiếp cận của bài báo cùng các kết quả lý thuyết và thực nghiệm, chúng ta chỉ
ra rằng công thức tường minh của các hàm tỷ lệ trong bài báo đưa ra là chưa
chính xác (cụ thể trong Nhận xét 3.2.7). Bên cạnh đó, công thức tường minh
của FM (1, r) và FX (1, r) mà chúng ta xây dựng trong điểm chuyển pha a = 1
được nghiệm đúng bởi mô phỏng.
1.2
Kiến thức chuẩn bị
Trong phần này, chúng ta sẽ giới thiệu một số kiến thức và kết quả cơ
bản cần thiết về lý thuyết bước đi ngẫu nhiên và lý thuyết quá trình tái tạo.
Bên cạnh đó, một số tính chất cần thiết sẽ được sử dụng cho các kết quả ở
những chương tiếp theo cũng sẽ được đề cập đến.
1.2.1
Bước đi ngẫu nhiên dừng
Cho (Xk )k≥1 là một dãy biến ngẫu nhiên độc lập cùng phân phối (i.i.d.).
Chúng ta xét một bước ngẫu nhiên (Sn )n≥0 có gia số (Xk )k≥1 cho bởi S0 = 0
và Sn = Sn−1 + Xn với n ≥ 1.
Trước hết ta có một bổ đề về sự hội tụ của các dãy con ứng với các thời
điểm ngẫu nhiên của một dãy biến ngẫu nhiên hội tụ.
Bổ đề 1.2.1. Cho (Yn )n≥0 là một dãy biến ngẫu nhiên và (Nt )t≥0 là một
dãy tăng các chỉ số.
15
h.c.c
h.c.c
(i) Giả sử Yn −−→ Y
khi n → ∞ và Nt −−→ ∞
khi t → ∞. Khi đó
thì
h.c.c
YNt −−→ Y
khi t → ∞.
p
h.c.c
(ii) Giả sử Yn −−→ Y
khi n → ∞ và Nt →
− ∞
khi t → ∞. Khi đó,
p
− Y khi t → ∞.
YNt →
Chứng minh. Với (i), ta đặt A = {ω : Yn (ω) 9 Y (ω)}, B = {ω : Nt (ω) 9
∞} and C = {ω : YNt (ω) (ω) 9 Y (ω)}. Khi đó, C ⊆ A ∪ B, và ta thu được
(i).
Để chứng minh (ii), ta sẽ chỉ ra rằng mỗi dãy con của (YNt )t≥0 có một
dãy con hội tụ hầu chắc chắn. Thật vậy, giả sử (Ntk )k≥0 là một dãy con của
(Nt )t≥0 . Theo giả thiết ta có Ntk cũng hội tụ theo xác suất đến ∞. Do đó, tồn
tại một dãy con (Ntkj )j≥0 hội tụ hầu chắc chắn. Kết hợp điều này với giả thiết
h.c.c
h.c.c
Yn −−→ Y khi n → ∞ và (i) suy ra YNtk −−→ Y khi j → ∞. Do vậy ta kết
j
p
luận YNt →
− Y khi t → ∞.
Định lý 1.2.2. Xét bước ngẫu nhiên (Sn )n≥0 với gia số i.i.d. (Xk )k≥1 . Giả sử
h.c.c
rằng Nt −−→ ∞ khi t → ∞. Khi đó, nếu E[|X1 |] < ∞ và E[X1 ] = µ, thì
SNt h.c.c
−−→ µ
Nt
Hơn thế nữa, nếu
Nt h.c.c
t −−→
khi t → ∞.
(1.2.1)
θ ∈ (0, ∞) khi t → ∞, thì
SNt h.c.c
−−→ µθ
t
khi t → ∞.
(1.2.2)
Chứng minh. Bởi luật mạnh của số lớn và Bổ đề 1.2.1 ta có phần đầu chứng
minh. Biến đổi đại số, ta có phần thứ hai
SNt
SNt − µNt Nt
Nt h.c.c
=
×
+µ
−−→ µθ,
t
Nt
t
t
khi t → ∞.
16
Tiếp theo, chúng ta có định lí giới hạn trung tâm của bước ngẫu nhiên với
thời gian ngẫu nhiên.
Định lý 1.2.3. [[25], Định lý Anscombe]. Xét bước ngẫu nhiên (Sn )n≥0 với
gia số i.i.d. (Xk )k≥1 . Giả sử rằng E[X] = 0 và Var[X] = σ 2 ∈ (0, ∞). Xét
dãy thời điểm ngẫu nhiên (Nt )t≥0 thỏa mãn
Nt p
→
− θ
t
khi t → ∞.
(1.2.3)
Khi đó,
(i)
SNt d
√ →
− N (0, 1) khi t → ∞,
σ Nt
(1.2.4)
SNt d
√ →
− N (0, 1) khi t → ∞.
σ tθ
(1.2.5)
(ii)
Chúng ta gọi là N là một thời gian dừng đối với dãy tăng của các σ-đại
số (Fn )n≥1 (chẳng hạn Fn = σ(X1 , X2 , . . . , Xn ), F0 = {∅, Ω}), nếu với mọi
n ≥ 1 thì
{N = n} ∈ Fn .
Bây giờ ta thu được các đẳng thức quan trọng cho moment bậc 1 và moment
bậc 2 của tổng dừng.
Định lý 1.2.4. [[29], Định lý 1.5.3]. Xét bước ngẫu nhiên (Sn )n≥0 với gia số
i.i.d. (Xk )k≥1 . Nếu E[X1 ] = µ và E[N ] < ∞ thì
E[SN ] = µE[N ].
(1.2.6)
Hơn nữa, nếu σ 2 = Var[X1 ] < ∞ thì
E[(SN − N µ)2 ] = σ 2 E[N ].
(1.2.7)
17
1.2.2
Quá trình tái tạo
Xét bước ngẫu nhiên (Sn )n≥0 với gia số i.i.d. (Xk )k≥1 . Nếu (Xi )i≥1 là các
biến ngẫu nhiên không âm, thì ta cũng gọi (Sn )n ≥ 0 là một quá trình tái tạo
(renewal process). Chúng ta đặt
Nt = max{n ≥ 1 : Sn ≤ t},
là số lần tái tạo của quá trình trong đoạn [0, t].
Bây giờ ta có một số kết quả cơ bản đầu tiên:
Khẳng định 1. [[29], Định lý 2.3.1]. Nếu X1 ≥ 0 và tồn tại a > 0 sao cho
P(X1 ≥ a) > 0 thì
(i) P(Nt < ∞) = 1 ;
(ii) E[Ntr ] < ∞ với mọi r > 0 ;
(iii) Tồn tại s0 > 0 thỏa mãn E[esNt ] < ∞ với mọi s < s0 .
Một mối liên hệ quan trọng mà một số chứng minh sẽ sử dụng đó là quan
hệ ngược giữa quá trình tái tạo và quá trình đếm,
{Nt ≥ n} = {Sn ≤ t}.
Tuy nhiên, Nt không phải là một thời gian dừng (stopping time). Thay vào
đó, chúng ta có thể xét dãy thời gian vượt đầu tiên (νt )t≥0 (first passage time
process), định nghĩa bởi
νt = min{n : Sn > t}.
Khi đó, νt là một thời gian dừng với mọi t > 0. Ngoài ra,
νt = Nt + 1,
và vì vậy Khẳng định 1 cũng đúng cho dãy (νt )t≥1 .
18
Bây giờ chúng ta sẽ giới thiệu đến các định lý giới hạn quan trọng như luật
mạnh của số lớn, định lý giới hạn trung tâm của cho quá trình đếm tái tạo.
Các định lý này được đưa ra bởi Doob (1948), Feller (1941) và Hatori (1959),
Smith (1954).
Đầu tiên, chúng ta nhận xét rằng khi t → ∞,
h.c.c
Nt −−→ ∞,
h.c.c
νt −−→ ∞.
Định lý 1.2.5. [Luật mạnh của số lớn cho quá trình đếm]. Giả sử 0 < µ =
E[X1 ] < ∞. Khi đó, khi t → ∞,
(i)
Nt h.c.c 1
−−→ ,
t
µ
(1.2.8)
N r
1
t
→ r.
E
t
µ
(1.2.9)
(ii) và với mọi r > 0,
Chứng minh. Bởi định nghĩa, ta có
SNt ≤ t < Sνt
và
SNt
t
Sν Nt + 1
≤
< t
.
Nt
Nt
ν t Nt
Sử dụng Định lý 1.2.2, ta chứng minh được cả chặn trên và chặn dưới của
t
Nt
đều hội tụ hầu chắc chắn đến µ khi t → ∞, điều này suy ra
t h.c.c
−−→ µ.
Nt
Để chứng minh (ii), chúng ta sẽ chỉ ra
Nt r
t
t≥1
là khả tích đều với mọi
r > 0. Hơn nữa, νt = Nt + 1, và do đó, ta cần chỉ ra
n ν r o
t
là họ khả tích đều với mọi r > 0.
t
t≥1
(1.2.10)
19
Ta sẽ chứng minh tính chất cộng tính dưới của quá trình (νt )t≥1 . Trước hết, ta
thấy để đạt được mức (t + s) thì phải đạt đến mức t. Khi điều này hoàn thành
thì quá trình bắt đầu làm lại. Vì Sνt > t nên khoảng cách còn lại cần đi nhiều
nhất là s, do vậy thời gian cần đi bị chặn bởi biến ngẫu nhiên đồng phân phối
với νs . Nghĩa là,
νt+s ≤ νt + min{k − νt : Sk − Sνt > s}
0
= νt + νs ,
0
với νs cùng phân phối với νs .
Bây giờ với n ≥ 1 là số nguyên bất kỳ. Bởi lập luận đệ quy chúng ta có
νn ≤ ν1,1 + . . . + ν1,n ,
với (ν1,k )k≥1 là đồng phân phối với ν1 . Kết hợp với bất đẳng thức Minkowski
thu được
kνn kr ≤ nkν1 kr .
Cuối cùng bởi νt ≤ ν[t]+1 nên ta có với mọi t ≥ 1,
ν[t]+1
νt
≤2
,
t
[t] + 1
và do vậy
Do đó,
ν[t]+1
νt
kr ≤ 2kν1 kr < ∞.
k kr ≤ 2k
t
[t] + 1
νt p
t
t≥1
là họ khả tích đều với mọi p < r. Bởi r là bất kì, dương
nên ta suy ra (1.2.10) và (ii).
Nhận xét 1.2.6. Trong chứng minh trên ta sử dụng tính chất nếu một họ biến
ngẫu nhiên bị chặn theo Lp với 1 < p < ∞ thì họ biến ngẫu nhiên đó là khả
tích đều.
Cuối cùng, chúng ta có định lý giới hạn trung tâm cho quá trình đếm tái
tạo:
- Xem thêm -