Tài liệu Xích markov và ứng dụng trong vấn đề trộn bài

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 Mục lục Lời cảm ơn 1 GIỚI THIỆU 3 1 XÍCH MARKOV 5 1.1 Xích Markov hữu hạn . . . . . . . . . . . . . . . . . . 5 1.2 Biểu diễn ánh xạ ngẫu nhiên . . . . . . . . . . . . . . 10 1.3 Tính tối giản và phi tuần hoàn . . . . . . . . . . . . 11 1.4 Hành trình ngẫu nhiên trên đồ thị . . . . . . . . . . . 12 1.5 Phân phối dừng . . . . . . . . . . . . . . . . . . . . . 13 1.6 Tính khả nghịch và thời điểm nghịch đảo . . . . . . . 15 1.7 Phân loại trạng thái của xích Markov . . . . . . . . . 17 1.8 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Trộn bài 22 2.1 Nhóm đối xứng . . . . . . . . . . . . . . . . . . . . . 22 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 2.2.3 Chặn trên . . . . . . . . . . . . . . . . . . . . 34 2.3 Trộn bài trang . . . . . . . . . . . . . . . . . . . . . . 35 KẾT LUẬN 42 TÀI LIỆU THAM KHẢO 43 ii Khóa luận tốt nghiệp Đại học MỤC LỤC 1 LỜI CẢM ƠN Trước khi trình bày nội dung chính của khóa luận, tôi xin bày tỏ lòng cảm ơn tới các thầy cô khoa Toán, trường Đại Học Sư Phạm Hà Nội 2, các thầy cô trong tổ bộ môn Toán Ứng Dụng cũng như các thầy cô tham gia giảng dạy đã tận tình truyền đạt những tri thức quý báu và tạo điều kiện thuận lợi để tôi hoàn thành tốt nhiệm vụ khóa học và khóa luận. Đặ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 Khóa luận tốt nghiệp Đại học MỤC LỤC 4. Phương pháp nghiên cứu Tổng hợp tài liệu, sắp xếp các vấn đề nghiên cứu một cách lôgic và có hệ thống. 5. Nội dung nghiên cứu Chương 1: Xích Markov hữu hạn Trình bày khái niệm Markov, các ví dụ cụ thể và các tính chất của xích Markov. Chương 2: Ứng dụng tính dừng của xích Markov vào trộn bài Hà Nội, 05/2017 Tác giả khóa luận Nguyễn Thị Hằng 4 Chương 1 XÍCH MARKOV 1.1 Xích Markov hữu hạn 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à X P (x, y) = 1, ∀x ∈ Ω. y∈Ω Ví dụ 1.1.1. Một con ếch sống trong một cái ao trên hai chiếc lá sen, phía đông và tây, trên mỗi lá sen có một đồng xu. Mỗi buổi sáng con ếch quyết định nhảy sang chiếc lá sen kia bằng việc tung đồng xu trên lá sen mà nó đang đứng. Sau khi tung đồng xu, nếu đồng xu xuất hiện mặt ngửa thì nó sẽ nhảy sang lá sen kia. Nếu đồng xu xuất hiện mặt sấp thì nó ở lại lá sen cũ. Hình 1.1: Bước nhảy ngẫu nhiên của con ếch, khi đồng tiền suất hiện mặt ngửa thì nhảy sang chiếc lá khác. Cho Ω = {e, ω} và (X0 , X1, ...) là dãy các lá sen mà con ếch đã ở vào ngày chủ nhật, thứ hai,... Gọi đồng xu ở chiếc lá phía đông và xuất hiện mặt ngửa có xác suất là p, khi đó đồng xu xuất hiện mặt ngửa ở chiếc lá phía tây có xác suất là q. Quy tắc các bước nhảy của con ếch thật đơn giản nếu ta đặt     P (e, e) P (e, w) 1−p p = , P = P (w, e) P (w, w) q 1−q (1.2) 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) và Ta có thể viết công thức như (1.4) và (1.5) một cách hệ thống hơn µt := (P{Xt = e|X0 = e}, P{Xt = w|X0 = e}). Giả thiết con ếch bắt đầu từ lá phía đông, giờ ta có thể viết µ0 = (1, 0), khi đó (1.3) trở thành µ1 = µ0 P . Nhân P vào vế phải của phân phối ta được µt = µt−1 P, ∀t ≥ 1. (1.6) Hơn nữa với phân phối µ0 đầu tiên bất kỳ µt = µ0 P t , (t ≥ 0). (1.7) Hình 1.2: Xác suất theo từng thời điểm (bắt đầu từ chiếc lá phía đông) với (a) p = q = 1/2, (b) p = 0.2 và q = 0.1, (c) p = 0.95 và q = 0.7. Các xác suất giới hạn tương ứng là 1/2, 1/3 và 14/33. Làm thế nào để hình dung về phân phối µt trong khoảng thời gian dài? Hình 1.2 cho thấy µt có thể có một giới hạn π (giá trị phụ 7 Khóa luận tốt nghiệp Đại học 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 4t = µt (e) − q , p+q ∀t ≥ 0, thì với định nghĩa của µt+1 , dãy (4t ) thỏa mãn 4t+1 = µt (e)(1 − p) + (1 − µt(e))(q) − q = (1 − p − q)4t. (1.8) p+q Ta kết luận rằng khi 0 < p < 1 và 0 < q < 1 , lim µt (e) = t→∞ q , p+q lim µt (w) = t→∞ p , 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) = X P {Xt = x}P (x, y) = x∈Ω X x∈Ω 8 µt (x)P (x, y) với mọi y ∈ Ω. Khóa luận tốt nghiệp Đại học CHƯƠNG 1. XÍCH MARKOV Viết lại công thức trên dưới dạng vectơ µt+1 = µt P, t ≥ 0, µt = µ0 P t , t ≥ 0. vì vậy (1.10) Vì chúng ta thường xét các xích Markov với ma trận chuyển giống nhau nhưng khác phân phối ban đầu, ta kí hiệu là Pµ là xác suất ban đầu và Eµ là kì vọng cho bởi µ0 = µ. Thông thường, phân phối đầu tiên sẽ tập trung vào việc xác định một trạng thái đơn x. Ta kí hiệu đó là δx   1 nếu y = x, δx (y) =  0 nếu y 6= x. Ta viết đơn giản Pδx = Px và Eδx = Ex . Ta đơn giản định nghĩa trên với (1.10) như sau 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 π(A) = X µ(x). 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 ma trận chuyển     1/2    P (j, k) = 1/2      0 nếu k ≡ j + 1 (modn), nếu k ≡ j − 1 (modn), (1.11) trái lại. Xích Markov liên hợp (Xt) được gọi là chuyển động ngẫu nhiên n hành trình. Các trạng thái có thể được hình dung như việc sắp xếp các điểm trên một đường tròn (hình 1.3). Ma trận chuyển trong (1.11), xích đó có thể được viết đơn giản và chi tiết hơn: Ở mỗi bước, đồng xu được gieo. Nếu đồng xu xuất hiện mặt ngửa thì hành trình chuyển động một bước theo chiều kim đồ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ố nguyên r sao cho P r (x, y > 0) với mọi x, y ∈ Ω. Giả sử một xích tối giản với 2 chu trình, ví dụ hành trình ngẫu nhiên đơn giản trên một chu trình chẵn (hình 1.3). Không gian trạng thái Ω có thể được phân thành hai lớp đó là chẵn và lẻ, sao cho xích làm di chuyển giữa các trạng thái trong các lớp bù nhau. Cho P có hai chu trình, giả sử x0 là một trạng thái chẵn. Xác suất phân phối của xích sau 2t bước, P 2t (x0, ·), là trạng thái chẵn, khi đó phân phối của xích sau 2t+1 bước ở trạng thái lẻ. Hiển nhiên rằng ta không thể hi vọng phân phối P t (x0, ·) hội tụ khi t → ∞. 11 Khóa luận tốt nghiệp Đại học CHƯƠNG 1. XÍCH MARKOV Ví dụ 1.3.1. Cho n chu trình. Ta nói hành trình ngẫu nhiên trên n chu trình được xác định ở ví dụ 1.2.1. Với mọi n ≥ 1, hành trình ngẫu nhiên trên n chu trình là tối giản. Hành trình ngẫu nhiên trên chu trình chẵn bất kì là tuần hoàn, do gcd{t : P t (x, x) > 0} = 2 (hình 1.3). Hành trình ngẫu nhiên trên chu trình lẻ là phi tuần hoàn. Ma trận chuyển Q của hành trình chậm ngẫu nhiên trên n chu trình là P (j, k) =    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. 1.4 Hành trình ngẫu nhiên trên đồ thị Cho đồ thị G = (V, E), ta có thể xác định được hành trình ngẫu nhiên đơn giản trong G từ xích Markov với không gian trạng thái V và ma trận chuyển. P (x, y) =   1/deg(x)  0 nếu y ∼ x nếu trái lại. (1.12) Ví dụ 1.4.1. Xét đồ thị G ở hình 1.4. Ma trận chuyển của hành 12 Khóa luận tốt nghiệp Đại học CHƯƠNG 1. XÍCH MARKOV 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 1.5 Phân phối dừng Định nghĩa Định nghĩa 1.1. Ta thấy ở ví dụ 1.1.1 cho thấy một phân phối π của Ω thỏa mãn π = πP, (1.13) là phân phối giới hạn của xích. Ta nói phân phối xác suất π thỏa mãn (1.13) là một phân phối dừng của xích Markov và µ0 = π thì µt = π, ∀t ≥ 0. Chú ý rằng ta cũng có thể viết (1.13) theo từng phần tử như sau X π(x)P (x, y), ∀y ∈ Ω. (1.14) π(y) = x∈Ω Ví dụ 1.5.1. Xét hành trình ngẫu nhiên trên đồ thị G = (V, E). Với bất kì đỉnh y ∈ V , X X deg(x) deg(x)P (x, y) = = deg(y). deg(x) x∼y x∈V 13 (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 được π(y) = deg(y) , 2|E| P y∈V deg(y) = 2|E|. Ta có ∀y ∈ Ω, π(y) tỉ lệ với bậc của nó và cũng là một phân phối dừng của hành 2 3 4 2 1 trình. Đồ thị hình (1.4) cho thấy π = ( , , , , ). Nếu G có 12 12 12 12 12 tính chất mọi đỉnh có cùng bậc d, ta gọi G là d - chính quy. Trong 1 , ∀y ∈ V là trường hợp 2|E| = d|V | và phân phối đều π(y) = |V | phân phối dừng. Các thời điểm chuyển động lặp lại lần đầu tiên Ta giả thiết cho xích Markov (X0 , X1, ...) trên không gian hữu hạn trạng thái Ω và ma trận chuyển P . Với x ∈ Ω, thời điểm đạt tới trạng thái x được xác định τx := min{t ≥ 0 : Xt = x}, đó là thời điểm đầu tiên xích trở về trạng thái x và có trạng thái là dương, ta xác định được τx+ := min{t ≥ 1 : Xt = x}. Khi đó X0 = x ta gọi τx+ là thời điểm lặp lại đầu tiên. Bổ đề 1.2. Cho trạng thái x và y bất kì của một xích tối giản thì Ex (τy+) < ∞. Tính tồn tại của phân phối dừng Mệnh đề 1.5.1. Cho P là ma trận chuyển của xích Markov tối giản. Vậy thì 14 Khóa luận tốt nghiệp Đại học 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) = 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 Tính khả nghịch và thời điểm nghịch đảo Giả sử xác suất π trên Ω thỏa mãn π(x)P (x, y) = π(y)P (y, x) ∀x, y ∈ Ω. (1.17) Mệnh đề 1.6.1. Cho P là ma trận chuyển của xích Markov với không gian trạng thái Ω. Phân phối π bất kì thỏa mãn phương trình (1.17) thì P có tính dừng. 15 Khóa luận tốt nghiệp Đại học CHƯƠNG 1. XÍCH MARKOV Kiểm tra tính chất trên thường là cách đơn giản để chứng tỏ một phân phối cụ thể là dừng. Hơn nữa, khi (1.17) cố định, π(x0)P (x0, x1) · · · P (xn−1, xn) = π(xn)P (xn , xn−1) · · · P (x1 , x0). (1.18) Ta có thể viết lại (1.18) dưới dạng Pπ {X0 = x0, ..., Xn = xn } = Pπ {X0 = xn, X1 = xn−1, ..., Xn = x0 }. (1.19) Nói cách khác, nếu xích (Xt) thỏa mãn (1.17) và có phân phối dừng ban đầu thì phân phối của (X0, X1 , .., Xn) cũng như phân phối của (Xn, Xn−1, ..., X0). Do đó xích thỏa mãn (1.17) được gọi là khả nghịch. Ví dụ 1.6.1. Xét hành trình chệch ngẫu nhiên trên n-chu trình: chuyển động theo chiều kim đồng hồ với xác suất p và chuyển động 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 X 1 π(j)P (j, k) = π(k − 1)p + π(k + 1)q = , n j∈Zn do π là phân phối dừng. Tuy nhiên nếu p 6= π(k)P (k, k + 1) = 1 thì 2 p q 6= = π(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 π(y)P (y, x) Pb(x, y) := . π(x) (1.20) Phương trình dừng π = πP có nghĩa là Pb là ma trận ngẫu nhiên. 16