Tài liệu Xích markov, du động ngẫu nhiên và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐẶNG THỊ THỎA XÍCH MARKOV, DU ĐỘNG NGẪU NHIÊN VÀ ỨNG DỤNG Chuyên ngành: Lý thuyết xác suất và thống kê toán học Mã số: 60460106 LUẬN VĂN THẠC SỸ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH ĐẶNG HÙNG THẮNG HÀ NỘI- 2015 Mục lục Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Xích Markov 1.1 4 6 Xích Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Các định nghĩa . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Ma trận chuyển . . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . 9 Xích Markov hấp thụ . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 Dạng chính tắc . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 Xác suất hấp thụ . . . . . . . . . . . . . . . . . . . . . 11 1.2.3 Ma trận cơ bản . . . . . . . . . . . . . . . . . . . . . . 12 1.2.4 Thời gian tiến tới hấp thụ . . . . . . . . . . . . . . . . 13 1.2.5 Xác suất hấp thụ . . . . . . . . . . . . . . . . . . . . . 14 Xích Markov egođic . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.1 Xích Markov chính quy . . . . . . . . . . . . . . . . . 16 1.3.2 Vectơ cố định . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.3 Trạng thái cân bằng . . . . . . . . . . . . . . . . . . . 22 1.3.4 Ví dụ về xích Egođic . . . . . . . . . . . . . . . . . . . 24 1.4 Định lí giới hạn cơ bản cho xích chính quy . . . . . . . . . . . 26 1.5 Thời gian trung bình chuyển qua cho xích Egođic . . . . . . . 29 1.2 1.3 1 1.5.1 Thời gian trung bình chuyển qua lần đầu tiên . . . . . 29 1.5.2 Thời gian trung bình quay lại . . . . . . . . . . . . . . 31 1.5.3 Ma trận trung bình lần đầu tiên đi qua và ma trận trung bình quay lại . . . . . . . . . . . . . . . . . . . . 32 1.5.4 Ma trận cơ bản . . . . . . . . . . . . . . . . . . . . . . 34 1.5.5 Sử dụng ma trận cơ bản để tính ma trận thời gian trung 1.5.6 bình chuyển qua lần đầu tiên . . . . . . . . . . . . . . 37 Định lí giới hạn trung tâm cho xích Markov . . . . . . 40 2 Du động ngẫu nhiên 2.1 2.2 41 Du động ngẫu nhiên trong không gian Ơ’clit . . . . . . . . . . 41 2.1.1 Du động ngẫu nhiên trên đường thẳng thực . . . . . . 42 2.1.2 Du động ngẫu nhiên tổng quát . . . . . . . . . . . . . 43 2.1.3 Sự quay lại và sự quay lại lần đầu tiên . . . . . . . . . 44 2.1.4 Xác suất hồi quy . . . . . . . . . . . . . . . . . . . . . 47 2.1.5 Kỳ vọng của số lần ở vị trí cân bằng . . . . . . . . . . 51 Luật arcsin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3 Ứng dụng 60 3.1 Mô hình Ehrenfest được dùng để giải thích sự khuếch tán khí ga 60 3.2 Di truyền . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.3 Kinh tế . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.3.1 Mô hình phân chia thị trường . . . . . . . . . . . . . . 63 3.3.2 Mô hình quản lý tiến mặt . . . . . . . . . . . . . . . . 68 3.3.3 Mô hình kiểm kê . . . . . . . . . . . . . . . . . . . . . 70 3.3.4 Mô hình phục vụ đám đông . . . . . . . . . . . . . . . 72 3.4 Đường đi của người say rượu . . . . . . . . . . . . . . . . . . 74 3.5 Sự phá sản của người chơi cờ bạc . . . . . . . . . . . . . . . . 79 3.5.1 80 Sự phá sản của người chơi cờ bạc . . . . . . . . . . . . 2 3.5.2 3.6 Đối phương của người chơi giàu vô tận . . . . . . . . . Xã hội học 82 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . 86 3 LỜI NÓI ĐẦU Đầu thế kỷ XX, A.A. Markov(14/6/1856 - 20/7/1922)- nhà Toán học và Vật Lý nổi tiếng người Nga đã đưa ra một mô hình toán học để mô tả chuyển động của các phần tử chất lỏng trong một bình kín. Về sau mô hình này được phát triển và sử dụng trong nhiều lĩnh vực khác như cơ học, sinh học, y học, kinh tế,vv . . . và được mang tên là quá trình Markov. Xích Markov là trường hợp riêng của quá trình Markov( khi ta có thể đánh số được các trạng thái). Luận văn này đề cập tới xích Markov, du động ngẫu nhiên và ứng dụng. Bố cục luận văn gồm ba chương, phần kết luận và danh mục tài liệu tham khảo. Chương một trình bày về xích Markov: các định nghĩa cơ bản, ma trận chuyển, các ví dụ và các trường hợp riêng của xích Markov, xích Markov hấp thụ, xích egođic, xích chính quy. Chương hai sẽ trình bày về du động ngẫu nhiên, các đặc điểm của nó và luật arcsin. Chương ba sẽ trình bày các ứng dụng của xích Markov và du động ngẫu nhiên trong thực tế. Luận văn này được thực hiện dưới sự hướng dẫn của GS.TSKH Đặng Hùng Thắng. Toàn thể ban lãnh đạo và các thầy cô trong khoa Toán - Cơ Tin học, trường Đại học Khoa học Tự nhiên - Đại học Quốc Gia Hà nội đã giúp tôi có thêm nhiều kiến thức để có thể hoàn thành luận văn và khóa học một cách tốt đẹp. Các thầy cô phòng Sau Đại học đã tạo những điều kiện thuận lợi giúp tôi hoàn thành các thủ tục bảo vệ luận văn cũng như học tập. 4 Các thầy và các bạn trong seminar Lý thuyết xác suất và thống kê toán học về những góp ý để tôi có thể hoàn thành luận văn này. Tôi xin chân thành cảm ơn tất cả những sự giúp đỡ và đóng góp quý giá ấy. Tôi rất mong nhận được những ý kiến đóng góp của quý thầy cô và các bạn. Hà Nội, tháng 11 năm 2014 Đặng Thị Thỏa 5 Chương 1 Xích Markov 1.1 Xích Markov 1.1.1 Các định nghĩa Giả thiết ta nghiên cứu sự tiến triển theo thời gian của một hệ vật lý hoặc sinh thái nào đó. Ký hiệu X(t) là ví trí của hệ tại thời điểm t. Tập hợp các vị trí có thể có của hệ được gọi là không gian trạng thái. Giả sử trước thời điểm t trong tương lai t > s hệ ở trạng thái j với xác suất là bao nhiêu? Nếu xác suất này chỉ phụ thuộc vào s, t, i, j thì điều này có nghĩa là: sự tiến triển của hệ trong tương lai chỉ phụ thuộc vào hiện tại và độc lập với quá khứ. Đó là tính Markov. Hệ có tính chất này được gọi là quá trình Markov. Ta kí hiệu E là tập gồm các giá trị của X(t) và gọi E là không gian trạng thái của X(t). Nếu X(t) có tính Markov và E đánh số được thì X(t) được gọi là xích Markov. Thêm vào đó, nếu t = 0, 1, 2, 3, . . . thì ta có khái niệm xích Markov với thời gian rời rạc, còn nếu t ∈ (0, +∞) thì ta có định nghĩa xích Markov có thời gian liên tục. 6 Về phương diện toán học, tính Markov có thể định nghĩa như sau: Định nghĩa 1.1.1. Ta nói rằng X(t) có tính Markov nếu: P {X(tn+1 ) = j|X(t0 ) = i0 , . . . , X(tn−1 ) = in−1 , X(tn ) = i} = P {X(tn+1 ) = j|X(tn ) = i} với bất kì t0 < t1 < . . . < tn < tn+1 < . . . và i0 , . . . , in−1 , i, j ∈ E. Ta xem tn là hiên tại, tn+1 là tương lai, (t0 , . . . , tn−1 ) là quá khứ. Vì thế biểu thức trên chính là tính Markov của X(t). Đặt P (s, i, t, j) = P (X(t) = j|X(s) = i), (s < t). Đó chính là xác suất có điều kiện để hệ (quá trình) tại thời điểm s ở trạng thái i, đến thời điểm t chuyển sang trại thái j. Vì thế ta gọi là xác suất chuyển của hệ ( hay quá trình). Nếu xác suất chuyển chị phụ thuộc vào (t − s), tức là P (s, i, t, j) = P (s + h, i, t + h, j) thì ta nói hệ (quá trình) thuần nhất theo thời gian. 1.1.2 Ma trận chuyển Giả sử Xn ở hàng thứ nhất của ma trận P trong ví dụ 1.1.3 ở trên mô tả xác suất của biến thể hiện trạng thái thời tiết mưa. Tương tự hàng hai và hàng ba tương ứng với thời tiết đẹp trời và có tuyết rơi. Ma trận vuông như vậy gọi là ma trận xác suất chuyển hay ma trận chuyển. Giả sử Xn ; n = 0, 1, 2, . . . là xích rời rạc vầ thuần nhất. Nói một cách chính xác là: giả sử (Ω, A, P ) là không gian xác suất, Xn : Ω → Elà biến (đại lượng)ngẫu nhiên nhận giá trị trong tập đếm được E. E là không gian trạng thái, các phần tử của nó được kí hiệu là i, j, k, . . .. Khi đó, tính Markov và 7 tính thuần nhất của Xn có nghĩa là: pij = P {X(tn+1 ) = j|X(tn ) = i} = P {X(tn+1 ) = j|X(t0 ) = i0 . . . , X(tn−1 ) = in−1 , X(tn ) = i} không phụ thuộc vào n. P = (pij ) được gọi là ma trận xác suất chuyển sau 1 bước hay gọi tắt là ma trận chuyển. Tổng quát thì ta có định lý sau: Định lý 1.1.1. Nếu P là ma trận chuyển của xích Markov. Phần tử pij của ma trận Pn là xác suất của xích bắt đầu từ trạng thái i sang trạng thái j sau (n) n bước là pij : (n) pij = X (n−1) pik pkj k∈E Chứng minh. Để chứng minh biểu thức của đính lý này ta lập luận như sau: Hệ xuất phát từ trạng thái i và chuyển sang trạng thái j sau n bước là kết quả của việc hệ xuất phát từ trạng thái i, sau một bước chuyển sang trạng thái k, sau n − 1 bước tiếp theo chuyển sang trạng thái j. Từ công thức xác suất đầy đủ và tính Markov ta có: (n) pij = = P {Xn+1 = j|X0 = i} X P (Xn = j|X0 = i, X1 = k).P (X1 = k|X0 = i) k∈E = X P (Xn = j|X1 = k).P (X1 = k|X0 = i) k∈E = X (n−1) pik pkj k∈E Định lí được chứng minh. Định lý 1.1.2. Cho P là ma trận chuyển của xích Markov và u là véctơ xác suất miêu tả phân bố ban đầu. Khi đó xác suất của xích ở trạng thái i sau n 8 bước là phần tử thứ i của véctơ: u(n) = uP n 1.1.3 Các ví dụ Các ví dụ sau về xích Markov sẽ được sử dụng trong suốt các bài tập của chương. Ví dụ 1.1.1. Tổng thống Mỹ kể cho một người A về việc có hoặc không tranh cử trong cuộc tuyển cử tới. Nếu A thay dổi câu trả lời và chuyển tiếp tới B và B là người chuyển tiếp cho C,vv... luôn luôn chuyển tiếp cho một người mới. Ta đặt xác suất là a với một người thay đổi câu trả lời từ có sang không khi truyền thông điệp cho một ng tiếp theo và xác suất là b mà người đó thay đổi từ không sang có. Ta chọn các trạng thái của thông điệp là có hoặc không. Ma trận chuyển như sau: Y es P= Y es No  1−a  No  a 1−b b  Ví dụ 1.1.2. Mỗi một con ngựa bất kì chạy trong một cuộc đua ba con ngựa có ba trường hợp xảy ra với xác suất chiến thắng, nhì và thứ ba lần lượt là 1/2,1/4 và 1/4, độc lập với các kết quả trước đó. Chúng ta có thể có quá trình kiểm tra độc lập nhưng cũng có thể tính toán thông qua lý thuyết của xích Markov. Ma trận chuyển: W W  .5   P = P  .5  S .5 9 P S .25 .25    .25 .25   .25 .25 Tài liệu tham khảo [1] Nguyễn Duy Tiến (2000), Các mô hình xác suất và ứng dụng, NXB Đại học Quốc gia Hà nội. [2] Đặng Hùng Thắng (1998), Mở đầu về lý thuyết xác suất và các ứng dụng, Nhà xuất bản Giáo dục, Hà Nội. [3] Lawrence C. Evans, An Introduction to stochastic differential equations