Luận văn Thạc sĩ Toán học: Một số định lý giới hạn cho bước đi ngẫu nhiên có trí nhớ

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:68

Thêm vào BST

Báo xấu

38
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong luận văn này, các tác giả 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 "Random walk with random resetting to the maximum position", 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số định lý giới hạn cho bước đi ngẫu nhiên có trí nhớ

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO 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 VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO 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ị ˆ được xây dựng từ bước đi ngẫu Hình 3.1: Minh họa hai quá trình X và X 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 M Xn Hình 3.3: Kết quả thực nghiệm dáng điệu của √n n và √ 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 1−r hoặc phải với cùng xác suất 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)): r(1 − r) v(r) = √ , r − 2r2 + 2r − r2 và h p i 2 3 2 3 D(r) = (2 − 2r − 5r + 3r ) + (2 − r − r + 2r ) r(2 − r) (1 − r)r2 ×p p . r(2 − r)[r − 2r2 + 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 Xn h.c.c −−→ v(r) và −−→ v(r), n n khi n → ∞, và E[Mn ] E[Xn ] lim = lim = v(r), n→∞ n n→∞ n 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 Xn − µ0 λn d √ → − N (0, D(r)) và √ → − N (0, D(r)), n n khi n → ∞ và Var[Mn ] Var[Xn ] lim = lim = D(r), n→∞ n n→∞ n 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 ] E[Mn ] lim = FX (a, r) và lim = FM (a, r). n→∞ ϕa (n) n→∞ ψa (n) Khi 0 < a < 1: ϕa (n) = ψa (n) = n1−a/2 , và √ 2r FX (a, r) = FM (a, r) = . 2−a
12 Tại a = 1: √ ϕa (n) = ψa (n) = n, và r 2 FX (a, r) = 2r2 B(3/2, r), π và r 2 FM (a, r) = (2r2 + r) B(3/2, r). π Khi a > 1:  3 n 2 −a khi 1 < a < 23 ,      ϕa (n) = log n khi a = 32 ,    1 khi a > 32 ,  và √ ψa (n) = 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    2 ∼ v(r) khi a = 0, r → 0,   pr   ∼ v(r) khi a → 0, r → 0, q2      2  khi a = 1, r → 0, π FM (a, r) ∼ q 2     π khi a → 1+ , r → 0,  √ 2r khi a = 1, r → ∞,     √2r   khi a → 1− , r → ∞.  và  0 khi a = 1, r → 0, FX (a, r) = 0 khi a → 1+ , r → 0,  pr 2 ∼ v(r) khi a = 0, r → 0,       p r ∼ v(r)  khi a → 0, r → 0, FX (a, r) ∼ √ 2    2r khi a = 1, r → ∞, √     2r 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 ] 1 √ p FM (r) = lim √ n = √ [(r + 1/2)erf( r) + r/π exp(−r)] n→∞ 2r
14 và E[Xn ] 1 √ p FX (r) = lim √= √ [(r − 1/2)erf( r) + r/π exp(−r)]. n n→∞ 2r z Trên đây hàm erf(z) = √2π 0 exp(−u2 )du. R 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 → ∞. h.c.c p (ii) Giả sử Yn −−→ Y khi n → ∞ và Nt → − ∞ khi t → ∞. Khi đó, p YNt → − Y khi t → ∞. 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 −−→ µ khi t → ∞. (1.2.1) Nt Nt h.c.c Hơn thế nữa, nếu t −−→ θ ∈ (0, ∞) khi t → ∞, thì SNt h.c.c −−→ µθ khi t → ∞. (1.2.2) t 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 → − θ khi t → ∞. (1.2.3) t Khi đó, (i) SNt d √ → − N (0, 1) khi t → ∞, (1.2.4) σ Nt (ii) SNt d √ → − N (0, 1) khi t → ∞. (1.2.5) σ tθ 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 h.c.c Nt −−→ ∞, ν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 −−→ , (1.2.8) t µ (ii) và với mọi r > 0, N r 1 t E → r. (1.2.9) t µ 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 t 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 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 Nt r Để chứng minh (ii), chúng ta sẽ chỉ ra 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. (1.2.10) t t≥1
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 ν[t]+1 ≤2 , t [t] + 1 và do vậy νt ν[t]+1 k kr ≤ 2k kr ≤ 2kν1 kr < ∞. t [t] + 1 νt p Do đó, 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: