Một số mô hình xếp hàng và ứng dụng

ợi ......................................................................... Error! Bookmark not defined. 2.1.4 Phân loại Kendall .......................................................................... Error! Bookmark not defined. 2.1.5 Mục tiêu của phân tích hàng đợi ................................................... Error! Bookmark not defined. 2.2 Một số mô hình xếp hàng cơ bản ......................................................... Error! Bookmark not defined. 2.2.1 Mô hình xếp hàng sinh – chết tổng quát ....................................... Error! Bookmark not defined. 2.2.2 Mô hình hàng đợi M/M/1 .............................................................. Error! Bookmark not defined. a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined. b. Thời gian khách hàng chờ đợi ............................................................ Error! Bookmark not defined. c. Thời gian bận rộn ............................................................................... Error! Bookmark not defined. d. Quá trình dời đi .................................................................................. Error! Bookmark not defined. e. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. 2.2.3. Mô hình hàng đợi M/M/s ............................................................. Error! Bookmark not defined. a. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined. 3 b. Thời gian bận rộn ............................................................................... Error! Bookmark not defined. c. Quá trình dời đi .................................................................................. Error! Bookmark not defined. d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. 2.2.4. Mô hình hàng đợi hữu hạn M/M/s/K ........................................... Error! Bookmark not defined. a. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. 2.2.5. Mô hình hàng đợi M/G/1 ............................................................. Error! Bookmark not defined. a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined. b. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined. c. Thời gian bận rộn ............................................................................... Error! Bookmark not defined. d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. 2.2.6. Mô hình hàng đợi G/M/1 ............................................................. Error! Bookmark not defined. a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined. b. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined. c. Chu kỳ bận rộn ................................................................................... Error! Bookmark not defined. d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined. CHƢƠNG 3: .................................................................................................. Error! Bookmark not defined. ỨNG DỤNG .................................................................................................. Error! Bookmark not defined. 3.1 Mô phỏng một số mô hình xếp hàng bằng Matlab............................... Error! Bookmark not defined. 3.1.1 Mô phỏng hàng đợi M/M/1 ........................................................... Error! Bookmark not defined. 3.2 Ứng dụng của mô hình xếp hàng trong bài toán ra quyết định. ........... Error! Bookmark not defined. a) Xét ba bài toán sau: ............................................................................ Error! Bookmark not defined. b) Hàm giá: ............................................................................................ Error! Bookmark not defined. KẾT LUẬN .................................................................................................... Error! Bookmark not defined. TÀI LIỆU THAM KHẢO ............................................................................. Error! Bookmark not defined. 4 MỞ ĐẦU Lý thuyết xếp hàng đã đƣợc nghiên cứu và ứng dụng rộng rãi trên thế giới trong nhiều lĩnh vực ngành nghề khác nhau nhƣ bƣu chính viễn thông, hàng không, đƣờng sắt, kiểm soát lƣu lƣợng giao thông, đánh giá hiệu năng hệ thống máy tính, y tế và chăm sóc sức khỏe, không lƣu, bán vé Trong nhiều hệ thống phục vụ, các khách hàng (costumer) phải dùng chung tài nguyên, phải chờ để đƣợc phục vụ và đôi khi bị từ chối phục vụ. Lý thuyết quá trình xếp hàng (queueing process) xác định và tìm các phƣơng án tối ƣu để hệ thống phục vụ là tốt nhất. Trong nửa đầu của thế kỷ 20 lý thuyết xếp hàng đã đƣợc ứng dụng để nghiên cứu thời đợi trong các hệ thống điện thoại. Ngày nay lý thuyết xếp hàng còn có nhiều ứng dụng trong các lĩnh vực khác nhau nhƣ trong mạng máy tính, trong việc quản lý xí nghiệp, quản lý giao thông và trong các hệ phục vụ khác Ngoài ra lý thuyết xếp hàng cũng còn là cơ sở toán học để nghiên cứu và ứng dụng trong nhiều bài toán kinh tế nhƣ đầu tƣ, kiểm kê, rủi ro của bảo hiểm, thị trƣờng chứng khoán Chuỗi Markov là quá trình xếp hàng với thời gian rời rạc đã đƣợc xem xét trong giáo trình xác suất thống kê. Quá trình sinh tử cũng là quá trình xếp hàng, trong đó sinh biểu thị sự đến và tử biểu thị sự rời hàng của hệ thống. Đối với lý thuyết xếp hàng ta quan tâm đến các số đo hiệu năng, đó là các giá trị trung bình khi quá trình đạt trạng thái dừng bao gồm: độ dài hàng đợi trung bình của hàng, độ dài hàng đợi trung bình của hệ thống, thời gian đợi trung bình của hàng (trễ của hàng) và thời gian đợi trung bình của hệ thống (trễ của hệ thống). Để tính các đại lƣợng này ta có thể sử dụng phƣơng pháp giải phƣơng trình tích phân dạng Wiener – Hopf hoặc phƣơng pháp khảo sát chuỗi Markov nhúng. Từ đó suy ra các công thức tính các phân bố ổn định cho các loại hàng M/M/k, M/M/k/N; Công thức tổng quát tính các giá trị trung bình này cho các hàng G/G/1 và công thức cụ thể cho các hàng đặc biệt M/M/1, M/D/1 và M/𝐸𝑘 /1 Luận văn này tìm hiểu về một số mô hình xếp hàng cơ bản và ứng dụng của nó. Nội dung của luận văn này gồm ba chƣơng. Chƣơng 1: Kiến thức chuẩn bị. Chƣơng này trình bày về một số phân bố xác suất liên quan nhƣ: Phân bố Poisson, phân bố mũ. Những định nghĩa, định lý về xích Markov, phân loại trạng thái xích Markov, quá trình Markov gồm trƣờng hợp không gian trạng thái hữu hạn và không gian trạng thái vô hạn đếm đƣợc. 5 Chƣơng 2: Một số mô hình xếp hàng. Trình bày về một số mô hình xếp hàng cơ bản gồm: Mô hình hệ thống xếp hàng Markov đơn giản gồm mô hình xếp hàng Birth- and – Death tổng quát, trình bày cụ thể mô hình hàng đợi M/M/1, M/M/s và mô hình hàng đợi hữu hạn M/M/s/K. Mô hình chuỗi Markov nhúng trình bày tổng quát về chuỗi Markov nhúng cụ thể là mô hình hàng đợi M/G/1 và G/M/1. Chƣơng 3: Ứng dụng Chƣơng này tìm hiểu về một vài ứng dụng đơn giản của mô hình xếp hàng bao gồm: Mô phỏng một số mô hình bằng Matlab và ứng dụng của mô hình xếp hàng trong bài toán ra quyết định. Dù đã có nhiều cố gắng nhƣng do thời gian và khả năng có hạn nên các vấn đề trong luận văn vẫn chƣa đƣợc trình bày sâu sắc và không thể tránh khỏi những sai sót. Em rất mong đƣợc sự góp ý xây dựng của thầy cô và các bạn. Em xin chân thành cảm ơn! 6 CHƢƠNG 1 KIẾN THỨC CHUẨN BỊ Trong chƣơng này em xin trình bày về một sốphân bốxác suất liên quan là phân bố Poisson, phân bố mũvà một số định nghĩa, định lý về xích Markov gồm hai trƣờng hợp là không gian trạng thái hữu hạn và không gian trạng thái vô hạn đếm đƣợc để chuẩn bị kiến thức cho các chƣơng tiếp theo của khóa luận. 1.1 Phân bố Poisson và phân bố mũ 1.1.1 Phân bố Poisson Định nghĩa.Biến ngẫu nhiên rời rạc X nhận các giá trị từ 0, 1, 2, gọi là phân phối Poisson với tham số λ nếu: 𝑃 𝑋 = 𝑘 = 𝑒−𝜆𝜆𝑘 𝑘! 𝑘 = 0, 1, 2, . Ký hiệu: X ~ Poisson(λ) Kỳ vọng: 𝐸 𝑥 = 𝑘 𝜆𝑘𝑒−𝜆 𝑘! ∞ 𝑘=0 = 𝜆𝑘𝑒−𝜆 𝑘 − 1 ! ∞ 𝑘=1 Phƣơng sai : D(X) = 𝐸 𝑋 − 𝜇 2 = λ Do đó, chúng ta có thể viết: X ~ Poisson (µ). Mô hình Poisson: Giả sử chúng ta quan tâm đến số lần xảy ra của một sự kiện A trong một khoảng thời gian hoặc không gian liên tục có chiều dài w; với điều kiện là số lần xảy ra trong những khoảng không giao nhau là độc lập nhau, và xác suất xuất hiện A nhiều hơn một lần trong khoảng đó là rất bé. Hơn nữa, “cƣờng độ” xuất hiện A là không thay đổi, tức là số lần xuất hiện trung bình của A trong một khoảng chỉ phụ thuộc vào độ dài của khoảng đó. Với các điều kiện trên, nếu gọi X là BNN chỉ số lần xuất hiện A trong một khoảng chiều dài w thì ngƣời ta chứng minh đƣợc rằng X tuân theo luật phân phối Poisson với tham số λ = mw, trong đó m là một hằng số dƣơng chỉ “cƣờng độ” xuất hiện của A. 7 Thí dụ, số cuộc điện thoại gọi đến trong một phút tại một trạm nào đó; sốlỗi trên một trang giấy trong một quyển sách dầy; số đơn đặt hàng gửi tới một cơ sở trong một tháng, Biến ngẫu nhiên chỉ số lần xuất hiện nêu trên đã đƣợc nhà toán học Simeon D. Poisson nghiên cứu và hình thành phân phối Poisson. Ngoài ra, phân phối Poisson còn đƣợc dùng để tính xấp xỉ phân phối nhịthức B(n;p) khi n lớn và p khá gần 0 hoặc gần 1. Định lý Poisson. Giả sử trong một dãy n phép thử độc lập, một biến cố A xuất hiện với xác suất 𝑝𝑛 trong mỗi phép thử. Nếu khi 𝑛 → ∞ mà 𝑝𝑛 → 0 sao cho 𝑛. 𝑝𝑛 = 𝜆 (λ là một hằng số dƣơng) thì với mọi 𝑘 ∈ {0,1,2, , 𝑛}, chúng ta có: lim 𝑛→∞ 𝐶𝑛 𝑘𝑝𝑛 𝑘 1 − 𝑝𝑛 𝑛−𝑘 = 𝜆𝑘 𝑘! 𝑒−𝜆 Hệ quả: Nếu 𝑋~𝐵(𝑛, 𝑝), với 𝑛 > 30 và (𝑛𝑝 < 5 𝑕𝑎𝑦 𝑛 1 − 𝑝 < 5) thì chúng ta có thể xem như 𝑋~𝑃𝑜𝑖𝑠𝑠𝑜𝑛 (𝑛𝑝) Định lí: Cho hai biến ngẫu nhiên X và Y độc lập. Nếu 𝑋~𝑃𝑜𝑖𝑠𝑠𝑜𝑛 (𝜇) và 𝑌~𝑃𝑖𝑜𝑠𝑠𝑜𝑛 (𝜆) thì biến ngẫu nhiên 𝑋 + 𝑌~𝑃𝑜𝑖𝑠𝑠𝑜𝑛 (𝜇 + 𝜆). 1.1.2 Phân bố mũ: Định nghĩa: Hàm mật độ xác suất của một phân phối mũ có dạng như sau: 𝑓 𝑥, 𝜆 = 𝜆𝑒 −𝜆𝑥 , 𝑥 ≥ 0 0 , 𝑥 < 0 Trong đó λ là tham số của phân bố, thƣờng đƣợc gọi là tham số tỉ lệ. Phân bố đƣợc hỗ trợ dựa trên khoảng [0; ∞). Nếu một biến ngẫu nhiên X có phân phối này, ta viết: 𝑋~𝐸𝑥𝑝𝑜𝑛𝑒𝑛𝑡𝑖𝑎𝑙 (𝜆). Đặc tả: 8 Một cách khác để định nghĩa hàm mật độ xác suất của một phân phối mũ nhƣ sau: 𝑓 𝑥, 𝜆 = 1 𝜆 𝑒−𝑥/𝜆 , 𝑥 ≥ 0 0 ,𝑥 < 0 Trong đó 𝜆 > 0 là một tham số của phân bố và có thể đƣợc coi là nghịch đảo của tham số tỉ lệ đƣợc định nghĩa ở trên. Trong đặc tả, λ là một tham số sống sót theo nghĩa: nếu một biến ngẫu nhiên X là khoảng thời gian mà một hệthống sinh học hoặc cơ học M cho trƣớc sống sót đƣợc và 𝑋~𝐸𝑥𝑝𝑜𝑛𝑒𝑛𝑡𝑖𝑎𝑙 (𝜆)thì 𝐸 𝑋 = 𝜆. Nghĩa là khoảng thời gian sống sót kì vọng của M là λ đơn vị thời gian. Tính chất: + Giá trị trung bình và phương sai: Giá trị trung bình hay giá trị kì vọng của một biến ngẫu nhiên phân phối mũ X với tham số tỉ lệ λ đƣợc cho bởi công thức: 𝐸 𝑋 = 1 𝜆 Phƣơng sai của X là: 1 𝜆2 + Tính không nhớ: Một tính chất quan trọng của phân phối mũ là nó không nhớ. Nghĩa là nếu một biến ngẫu nhiên T có phân phối mũ xác suất điều kiện của nó phải thỏa mãn: 𝑃(𝑇 > 𝑠 + 𝑡/𝑇 > 𝑡) = 𝑃 𝑇 > 𝑠 ,∀ 𝑠, 𝑡 ≥ 0 1.2. 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à X0, X1, ..., Xn, ... Khi đó ta có một dãy các đại lƣợng ngẫu nhiên (ĐLNN) (Xn) trong đó Xn là trạng thái của hệ tại thời điểm n. Giả thiết rằng mỗi Xn, n = 0,1,... là một ĐLNN rời rạc. Ký hiệu E là tập giá trị của các (Xn). 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. 9 Định nghĩa 1.2.1.Ta nói rằng dãy các ĐLNN (Xn) là một xích Markov nếu với mọi n1< ... < nk< nk+1 và với mọi i1, i2, ..., ik+1∈ E, ta có: 𝑃 𝑋𝑛𝑘+1 = 𝑖𝑘+1/𝑋𝑛1 = 𝑖1 , 𝑋𝑛2 = 𝑖2, , 𝑋𝑛𝑘 = 𝑖𝑘 = 𝑃 𝑋𝑛𝑘+1 = 𝑖𝑘+1/𝑋𝑛𝑘 = 𝑖𝑘 . Ta coi thời điểm nk+1 là tƣơng lai, nk là hiện tại còn n1, ..., nk -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ử 𝑃 𝑋𝑚+𝑛 = 𝑗/𝑋𝑚 = 𝑖 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. Ký hiệu: 𝑃𝑖𝑗 = 𝑃 𝑋𝑛+1 = 𝑗 /𝑋𝑛 = 1 , 𝑃𝑖𝑗 𝑛 = 𝑃 𝑋𝑚+𝑛 = 𝑗/𝑋𝑚 = 𝑖 . Ta gọi (𝑃𝑖𝑗 , 𝑖, 𝑗 ∈ 𝐸) là xác suất chuyển sau một bƣớc hay xác suất chuyển còn (𝑃𝑖𝑗 𝑛 , 𝑖, 𝑗 ∈ 𝐸) là xác suất chuyển sau n bƣớc. Chú ý rằng: 𝑃𝑖𝑗𝑗 ∈𝐸 = 1, 𝑃𝑖𝑗 𝑛 = 1𝑗∈𝐸 . Phân bố của X0 đƣợc gọi là phân bố ban đầu. Ta ký hiệu 𝑢𝑖 = 𝑃(𝑋0 = 𝑖). Định lý 1.2.1.Phân bố đồng thời của (X0, X1, ..., Xn) đượ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ó: 𝑃 𝑋0 = 𝑖0, 𝑋1 = 𝑖1, , 𝑋𝑛 = 𝑖𝑛 = 𝑢𝑖0𝑃𝑖0𝑖1 𝑃𝑖𝑛−1𝑖𝑛 . Nhƣ vậy phân bố đồng thời của 𝑋0, , 𝑋𝑛 đƣợc xác định bởi phân bố ban đầu và xác suất chuyển. Định lý 1.2.2.(Phương trình C - K (Chapman-Kolmogorov)): 𝑃𝑖𝑗 (n + m) = 𝑃𝑖𝑘𝑘 ∈𝐸 (n) 𝑃𝑘𝑗 (m). 10 Trong trƣờng hợp E có d phần tử, ta ký hiệu𝑃 = (𝑃𝑖𝑗 ), 𝑃(𝑛) = (𝑃ij(n))là các ma trận vuông cấp 𝑑 × 𝑑. 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: 𝑃(𝑛 + 𝑚) = 𝑃(𝑛)𝑃(𝑚). Vì P = P(1) nên bằng quy nạp ta dễ thấy: 𝑃(𝑛) = 𝑃𝑛 . Gọi 𝑢𝑖 𝑛 = 𝑃 𝑋𝑛 = 𝑖 . Ký hiệu vecto 𝑈 𝑛 = (𝑢1(𝑛), , 𝑢𝑑 𝑛 )là vector hàng d - chiều mô tả phân bố của 𝑋𝑛, 𝑈 = 𝑢 0 = (𝑢1, 𝑢2, , 𝑢𝑑)là vector hàng d - chiều mô tả phân bố ban đầu (Phân bố của𝑋0). Định lý 1.2.3.Ta có: 𝑈 𝑚 + 𝑛 = 𝑈 𝑚 𝑃𝑛 . Định nghĩa 1.2.2.Phân bố ban đầu 𝑈 = (𝑢𝑖), 𝑖 ∈ 𝐸 được gọi là phân bố dừng nếu ta có 𝑈(𝑛) = 𝑈 với mọi n tức là 𝑢𝑖 𝑛 = 𝑢𝑖 ∀𝑖 ∈ 𝐸 , ∀𝑛. Khi đó dãy (𝑋𝑛 ) có cùng phân bố. Từ định lý 1.2.3 ta suy ra 𝑈 = (𝑢𝑖) là phân bố dừng nếu và chỉ nếu: • 1. 𝑢𝑖 ≥ 0 và 𝑢𝑖 = 1𝑖∈𝐸 , • 2. 𝑢𝑖 = 𝑢𝑖𝑃𝑖𝑗 𝑖∈𝐸 ∀𝑗 ∈ 𝐴. Định lý 1.2.4.Giả sử (𝑋𝑛 ) 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 𝑃 = (𝑃𝑖𝑗 ) và ma trận xác suất chuyển sau n bước là𝑃 𝑛 = 𝑃𝑖𝑗 (𝑛). 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 𝑛→ ∞ 𝑃𝑖𝑗 𝑛 = 𝜋𝑗 Giới hạn này không phụ thuộc i ∈ E. khi đó: • 1. 𝜋𝑗𝑗 ∈𝐸 ≤ 1 và πj = 𝜋𝑖𝑃𝑖𝑗𝑖 ∈𝐸 . • 2. Hoặc πj = 0 với mọi j ∈ E, hoặc 𝜋𝑗𝑗 ∈𝐸 = 1. 11 • 3. Nếu 𝜋𝑗𝑗 ∈𝐸 = 1 thì U = (π1, π2, ...) là phân bố dừng và phân bố dừng là duy nhất. Nếu πj = 0 với mọi j ∈ E thì phân bố dừng không tồn tại. Ý nghĩa của phân bố giới hạn là nhƣ sau: Gọi 𝑢𝑖(𝑛) = 𝑃(𝑋𝑛 = 𝑖). Ký hiệu vector 𝑈(𝑛) = (𝑢1(𝑛),𝑢2(𝑛), . . . )là vector hàng d - chiều mô tả phân bố của 𝑋𝑛 . Ta có: P(Xn = j) = 𝑃𝑗 ∈𝐸 (X0 = i)𝑃𝑖𝑗 (n). Do đó: lim𝑛→ ∞ 𝑃 𝑋𝑛 = 𝑗 = 𝑃 𝑋0 = 𝑖 𝑗 ∈𝐸 lim𝑛→ ∞ 𝑃𝑖𝑗 (𝑛) = 𝑃 𝑋0 = 𝑖 𝑗 ∈𝐸 𝜋𝑗 = 𝜋𝑗 . Định nghĩa 1.2.3.Giả sử (𝑋𝑛 ) 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 𝑃 = 𝑃𝑖𝑗 (𝑛)và ma trận xác suất chuyển sau n bước là 𝑃(𝑛) = 𝑃𝑖𝑗 (𝑛). 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) = πj . Giới hạn này không phụ thuộc i ∈ E và 𝜋𝑗𝑗 ∈𝐸 = 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. Vậy phân bố 𝑈(𝑛) của 𝑋𝑛hội tụ tới phân bố giới hạn π. Khi n khá lớn ta có (𝑋𝑛 = 𝑗) ≈ 𝜋𝑗. Theo định lý 1.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. Định lý 1.2.5.Cho (𝑋𝑛 ) 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à 𝑃(𝑛) = (𝑃𝑖𝑗 (n)).Khi đó có tồn tại phân bố giới hạn π = (π1, ..., πd ) với 𝜋𝑗 > 0 ∀𝑗 ∈ 𝐸 khi và chỉ khi xích là chính quy theo nghĩa: Tồn tại 𝑛0sao cho: 𝑃𝑖𝑗 𝑛0 > 0, ∀𝑖, 𝑗 ∈ 𝐸. 1.2.1. Phân loại trạng thái xích Markov 12 Định nghĩa 1.2.4.Ta nói rằng trạng thái i đến được trạng thái j và ký hiệu là 𝑖 → 𝑗 nếu tồn tại 𝑛 ≥ 0 sao cho 𝑃𝑖𝑗 (𝑛) > 0. (Ta quy ước 𝑃𝑖𝑖 0 = 1, 𝑃𝑖𝑗 (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 𝑖 → 𝑗và 𝑗 → 𝑖. Trong trường hợp đó ta viết 𝑖 ↔ 𝑗. Định nghĩa 1.2.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. Định nghĩa 1.1.6.Ký hiệu 𝑓𝑖𝑖 𝑛 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à: 𝑓𝑖𝑖 (n) = P(Xn = i, 𝑋𝑛−1 ≠ i, ..., 𝑋1 ≠ i|X0 = i) và ký hiệu: 𝑓𝑖𝑖 ∗ = 𝑓𝑖𝑖 ∞ 𝑛=1 (𝑛). Định lý 1.2.6.Trạng thái i là hồi quy khi và chỉ khi: 𝑃𝑖𝑖(𝑛) ∞ 𝑛=1 = ∞. Định lý 1.2.7.Nếu i ↔ j và j hồi quy thì i hồi quy. Chứng minh: Theo giả thiết tồn tại 𝑚, 𝑛 sao cho𝑃𝑖𝑖 (n) > 0, 𝑃𝑗𝑖 (m) > 0. Với mỗi số nguyên dƣơng h từ phƣơng trình C-P suy ra: 𝑃𝑖𝑖 (n + h + m) ≥ 𝑃𝑖𝑗 (n)𝑃𝑗𝑗 (h)𝑃𝑗𝑖 (m). Vậy: 𝑃𝑖𝑖 ∞ 𝑕=1 (n + h + m) ≥ 𝑃𝑗 (n)𝑃𝑗𝑖 (m) 𝑃𝑗𝑗 ∞ 𝑕=1 (h) = ∞. Vậy i hồi quy. Định lý 1.2.8. Ký hiệu 𝑄𝑖𝑖 là xác suất để hệ xuất phát từ i quay lại i vô số lần, 𝑄𝑖𝑗 là xác suất để hệ xuất phát từ i đi qua j vô số lần. Khi đó: • (i) Nếu i hồi quy thì 𝑄𝑖𝑖 = 1, nếu i không hồi quy thì 𝑄𝑖𝑖 = 0. 13 • (ii) Nếu i hồi quy 𝑖 ↔ 𝑗thì𝑄𝑖𝑗 = 1. Nói riêng, với xác suất một hệ xuất phát từ i sau một số hữu hạn bước sẽ đi qua j. Định lý 1.2.9.Cho (𝑋𝑛 ) là xích tối giản không hồi quy. Khi đó với mọi i, j: 𝑃𝑖𝑗 𝑛 < ∞ ∞ 𝑛=1 . Nói riêng lim𝑛→ ∞ 𝑃𝑖𝑗 = 0 và xích không tồn tại phân bố dừng. Định lý 1.2.10.Cho (𝑋𝑛 ) là xích tối giản hồi quy không có chu kỳ. Khi đó với mọi i, j ta có: lim𝑛→ ∞ 𝑃𝑖𝑗 (n) = 1 𝜇 𝑗 ở đó: µ𝑗 = 𝑘𝑓𝑗𝑗 ∞ 𝑘=1 (k). Định nghĩa 1.2.7.Trạng thái hồi quy i được gọi là trạng thái hồi quy dương nếu 𝜇𝑖 < ∞ và được gọi là trạng thái hồi quy không nếu µ𝑖 = ∞. Định lý 1.2.11.Giả sử 𝑖 → 𝑗. Nếu i hồi quy dương thì j hồi quy dương. Nếu i hồi quy không thì j hồi quy không. Định lý 1.2.12.Giả sử (𝑋𝑛) là xích tối giản không có chu kỳ với không gian trạng thái đếm được E. Khi đó sẽ xảy ra một trong ba khả năng sau đây: • 1)Mọi trạng thái là không hồi quy. Khi đó với mọi i, j ta có: 𝑙𝑖𝑚𝑛→ ∞ 𝑃𝑖𝑗 (n) = 0. Xích không có phân bố dừng. • 2) Mọi trạng thái là hồi quy không. Khi đó với mọi i, j ta có: 𝑙𝑖𝑚𝑛→ ∞ 𝑃𝑖𝑗 = 0. Xích không có phân bố dừng. • 3) Mọi trạng thái là hồi quy dương. Khi đó với mọi i, j, ta có: 14 𝑙𝑖𝑚𝑛→ ∞ 𝑃𝑖𝑗 = πj> 0 và𝜋 = (𝜋1, 𝜋2, . . . ) là phân bố giới hạn (và cũng là phân bố dừng) của xích. Định lý 1.2.13.Giả sử (𝑋𝑛 ) là xích tối giản không có chu kỳ với không gian trạng thái hữu hạn E = {1, 2, ..., d}. Khi đó mọi trạng thái đều hồi quy dương và xích có phân bố giới hạn 𝜋 = (𝜋1, 𝜋2 , . . . , 𝜋𝑑 ). Phân bố này cũng là phân bố dừng duy nhất của xích. Định lý 1.2.14.Giả sử 𝑋𝑛 là xích tối giản với không gian trạng thái E đếm được. Khi đó: • 1.Với mỗi 𝑖, 𝑗 ∈ 𝐸: 𝑙𝑖𝑚𝑛→ ∞ 𝑛 −1 𝑃𝑖𝑗 (𝑘) 𝑛 𝑘=1 = 1 𝜇 𝑗 . Nói cách khác dãy 𝑃𝑖𝑗 𝑛 hội tụ theo trung bình Cesaro tới πj = 1 𝜇 𝑖 không phụ thuộc i. • 2.Dãy 𝜋 = (𝜋𝑗 ) thoả mãn: a) 𝜋𝑗 ∞ 𝑗=1 ≤ 1, b) 𝜋𝑗 = 𝜋𝑖𝑃𝑖𝑗 ∞ 𝑖=1 . Định lý 1.2.15.Cho (𝑋𝑛 ) là xích Markov tối giản. Khi đó: • 1. Nếu E hữu hạn có d phần tử thì (𝜋1, . . . , 𝜋𝑑) là phân bố dừng duy nhất. • 2. Chỉ có các khả năng sau: a) Mọi trạng thái của E là không hồi quy b) Mọi trạng thái của E là hồi quy không c) Mọi trạng thái của E là hồi quy dương. • 3. Nếu E là vô hạn đếm được thì xích có phân bố dừng khi và chỉ khi mọi trạng thát của E là hồi quy dương. Trong trường hợp này phân bố dừng là duy nhất. 1.3. Quá trình Markov 15 Xét họ các ĐLNN rời rạc (𝑋𝑡), t ≥ 0 với tập chỉ số t là các số thực không âm 𝑡 ∈ [0, ∞). Ký hiệu 𝐸 = 𝑋𝑡 Ω là tập giá trị của 𝑋𝑡 . 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 𝑙à 𝑖, 𝑗, 𝑘. . .. Ta gọi (𝑋𝑡) là một quá trình ngẫu nhiên với không gian trạng thái E . Định nghĩa 1.3.1. Ta nói rằng (𝑋𝑡) là một quá trình Markov nếu với mọi 𝑡1 < . . . < 𝑡𝑘 < 𝑡và với mọi 𝑖1 , 𝑖2, . . . 𝑖𝑛 , 𝑖 ∈ 𝐸 ∶ P{Xt = i|𝑋𝑡1 = i1, 𝑋𝑡2= i2..., 𝑋𝑡𝑘= ik} = P{Xt = i|𝑋𝑡𝑘 = ik}. 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ứ 𝑋𝑢 ,𝑢 𝑡 là độc lập với nhau." Giả sử: P{𝑋𝑡+𝑠 = j|Xs = i} là xác suất để xích tại thời điểm s ở trạng thái i sau một khoảng thời gian t, tại thời điểm t + h chuyển sang trạng thái j. Đây là một con số nói chung phụ thuộc vào i, j, t, s. Nếu đại lƣợng này không phụ thuộc s ta nói xích là thuần nhất. Ký hiệu: 𝑃𝑖𝑗 (t) = P{𝑋𝑡+𝑠 = j|Xs = i}. Ta gọi 𝑃𝑖𝑗 𝑡 là xác suất chuyển của hệ từ trạng thái i sang trạng thái j sau một khoảng thời gian t . Ký hiệuP(t) = (𝑃𝑖𝑗 (t), i, j → E). P(t) là một ma trận hữu hạn hay vô hạn chiều. Chú ý rằng: • i)𝑃𝑖𝑗 (t) ≥ 0. • ii) 𝑃𝑖𝑗 (𝑡)𝑗 ∈𝐸 = 1. Phân bố của 𝑋0 đƣợc gọi là phân bố ban đầu. Ta ký hiệu 𝑢𝑖 = 𝑃(𝑋0 = 𝑖). Định lý 1.3.1.Phân bố hữu hạn chiều của quá trình (𝑋𝑡) được hoàn toàn xác định từ phân bố ban đầu và xác suất chuyển. Cụ thể với 𝑡1 < 𝑡2 < . . . < 𝑡𝑛 phân bố đồng thời của (𝑋𝑡1 , ..., 𝑋𝑡𝑛 ) được tính theo công thức sau: 16 P(𝑋𝑡1= i1, ..., 𝑋𝑡𝑛 = in) = = 𝑢𝑖𝑃𝑖𝑖1 𝑡1 𝑃𝑖1𝑖2𝑖 ∈𝐸 𝑡2 − 𝑡1 𝑃𝑖𝑛−1𝑖𝑛 (𝑡𝑛 − 𝑡𝑛−1). Định lý 1.3.2.( Phương trình Chap - Kolmogorov): 𝑃𝑖𝑗 (t + s) = 𝑃𝑖𝑘 (𝑡)𝑃𝑘𝑗 (𝑠)𝑘 ∈𝐸 . 1.3.1. Trƣờng hợp không gian trạng thái hữu hạn Giả sử E = {1, 2,..., d}. Khi đó từ phƣơng trình C - K P(t), t > 0 là một họ các ma trận thoả mãn đẳng thức sau: 𝑃(𝑡 + 𝑠) = 𝑃(𝑡)𝑃(𝑠). Nói cách khác họ (P(t), t > 0) lập thành một nửa nhóm các ma trận. Từ nay về sau ta sẽ luôn giả thiết thêm rằng: 1.𝑃𝑖𝑗 (0) = δij. 2.lim𝑛→ ∞ 𝑃𝑖𝑗 (𝑡)= δij. Ở đây 𝛿𝑖𝑗 là ký hiệu Kronecke: δij = 1 𝑘𝑕𝑖 𝑖 = 𝑗 0 𝑘𝑕𝑖 𝑖 ≠ 𝑗 Định lý 1.3.3.Hàm ma trận P(t) là một hàm liên tục và tồn tại: 𝑃′ (0) = 𝑙𝑖𝑚𝑕→ 0+ 𝑃 𝑡 −𝐼 𝑕 . Định lý 1.3.4.Cho quá trình Markov với nửa nhóm P(t), t > 0 các xác suất chuyển. Gọi A là ma trận cực vi của nửa nhóm. Khi đó ta có: 𝑃′ 𝑡 = 𝑃 𝑡 𝐴 , ↔ 𝑃𝑖𝑗 ′ = 𝑃𝑖𝑘 𝑡 𝑎𝑘𝑗 − 𝑃𝑖𝑗 𝑦 𝑎𝑗𝑘 ≠𝑗 . (1.3.1) và 𝑃′ 𝑡 = 𝐴𝑃(𝑡) , ↔ 𝑃′ 𝑖𝑗 𝑡 = 𝑃𝑘𝑗 𝑎𝑖𝑘𝑘 ≠𝑖 − 𝑃𝑖𝑗 (𝑦)𝑎𝑖 . (1.3.2) 17 với𝑎𝑖𝑗 là cƣờng độ chuyển từ trạng thái i sang trạng thái j và 𝑎𝑖 là cƣờng độ thoát khỏi trạng thái i của hệ. Phƣơng trình (1.3.1) gọi là phƣơng trình thuận và phƣơng trình (1.3.2) gọi là phƣơng trình ngƣợc Kolmogorov. Định lý 1.3.5.Cho quá trình Markov tối giản (𝑋𝑡) với không gian trạng thái E = 1, 2,..., d hữu hạn và ma trận xác suất chuyểnP(t) = 𝑃𝑖𝑗 (t). Khi đó với mỗi 𝑖, 𝑗 ∈ 𝐸 tồn tại giới hạn hữu hạn: 𝑙𝑖𝑚 𝑡→ ∞ 𝑃𝑖𝑗 𝑡 = 𝜋𝑗 chỉ phụ thuộc j không phụ thuộc i. Thêm vào đó 𝜋 = (𝜋1, 𝜋2, . . . , 𝜋𝑑 ) là phân bố xác suất duy nhất thoả mãn phương trình: 𝜋 = 𝜋𝑃(𝑡),∀𝑡 > 0. 1.3.2. Trƣờng hợp không gian trạng thái vô hạn đếm đƣợc Định lý 1.3.6. (1)Với mọi i ≠ j, giới hạn: 𝑃𝑖𝑗 ′(0) = lim 𝑡→ ∞ 𝑃𝑖𝑗 (𝑡) 𝑡 = 𝑎𝑖𝑗