Một số dạng luật mạnh số lớn trong lí thuyết trò chơi xác suất

TAÏP CHÍ ÑAÏI HOÏC SAØI GOØN Soá 20 - Thaùng 4/2014 61 MỘT SỐ DẠNG LUẬT MẠNH SỐ LỚN TRONG LÍ THUYẾT TRÒ CHƠI XÁC SUẤT ĐỖ THẾ SƠN(*) LÊ HỒNG SƠN(**) TÓM TẮT Bài báo cung cấp một số dạng luật mạnh số lớn trong khuôn khổ lí thuyết trò chơi xác suất của Shafer và Vovk (2001). Các dạng luật mạnh số lớn trong lí thuyết trò chơi được thiết lập với hàng rào bậc hai có sẵn. Từ khoá: luật mạnh số lớn, lí thuyết, xác suất, trò chơi xác suất ABSTRACT The paper presents some versions of the strong law of large numbers in the framework of the game-theoretic probability of Shafer and Vovk (2001). Game-theoretic versions of the strong law of large numbers are established under the availability of the quadratic hedge. Keywords: the strong law of large numbers, theory, probability, probability game 1. GIỚI THIỆU* Trong khuôn khổ của lí thuyết trò chơi xác suất, việc chứng minh các nước đi của Thực tế (Reality) tuân theo luật mạnh số lớn (LMSL) trong trường hợp các nước đi này b chặn là khá dễ dàng. Tuy nhiên, khi các nước đi của Thực tế không b chặn, việc chứng minh trở nên phức tạp hơn. Bên cạnh đó, tương ứng với một số dạng phổ biến nhất của LMSL trong lí thuyết xác suất cần phải được nghiên cứu trong lí thuyết trò chơi xác suất (nếu có). Bài báo cung cấp một số dạng LMSL trong trò chơi dự báo không bị chặn (unbounded forecasting game) đã được giới thiệu trong chương 4 của [1]. Tiếp theo, khi hạn chế nước đi của Thực tế trong trò chơi dự báo không b chặn là các số thực dương, (*)ThS, Trường ĐH Công nghiệp TP Hồ Chí Minh, Cơ sở Thanh Hóa. (**)TS, Khoa Giáo dục đại cương, Trường ĐH Sư phạm Kĩ thuật Vinh. chúng tôi đưa ra một giao thức mới, gọi là trò chơi dự báo không bị chặn một phía (One-sided unbounded forecasting game). Sau đó, chúng tôi chứng minh một số kết quả dạng LMSL đối với giao thức này. 2. MỘT SỐ KHÁI NIỆM VÀ KẾT QUẢ SƠ BỘ Trong mục này, chúng tôi tóm tắt một số khái niệm cơ bản của trò chơi dự báo không b chặn. Sau đó, chúng tôi đưa ra hai kết quả dạng LMSL đối với trò chơi này. Xét trò chơi hoàn hảo thông tin giữa ba người: Dự báo (Forecaster), Hoài nghi (Skeptic) và Thực tế (Reality). Trước khi bắt đầu trò chơi, Hoài nghi công bố số vốn ban đầu của mình 0 1K  ( 0 0K D  trong mục 2 của [2]). Sau đó, ở mỗi vòng 1,2,...n  của trò chơi, người chơi lần lượt công bố các nước đi (move) của mình theo thứ tự: Dự báo, Hoài nghi và Thực tế. Tại mỗi vòng, đầu tiên Dự báo công bố nước đi nm và nv của mình, 62 chúng được hiểu lần lượt như là giá cho nước đi nx của Thực tế và giá cho bình phương độ lệch 2( )n nx m . Căn cứ vào các giá mà Dự báo đưa ra, Hoài nghi sau đó sẽ công bố số lượng nM và nV mà anh ta đặt cược lần lượt cho nx và 2( )n nx m . Cuối cùng, Thực tế công bố nước đi nx của mình. Số phải trả (payoff) cho Hoài nghi tại vòng thứ n là 2( ) [( ) ]n n n n n n nM x m V x m v    và số vốn (capital) của Hoài nghi khi kết thúc vòng thứ n được cập nhật là: 2 1: ( ) [( ) ]n n n n n n n n nK K M x m V x m v      . Giao thức của trò chơi dự báo không b chặn được viết như sau TRÒ CHƠI DỰ BÁO KHÔNG BỊ CHẶN (UNBOUNDED FORECASTING GAME) Người chơi: Dự báo, Hoài nghi, Thực tế Giao thức: 0 1K  . Dự báo công bố nm  và 0nv  . Hoài nghi công bố nM  và 0nV  . Thực tế công bố nx  . 2 1: ( ) [( ) ]n n n n n n n n nK K M x m V x m v      . Nhiệm vụ ràng buộc: Hoài nghi phải giữ nK không âm. Thực tế phải giữ nK không tiến đến vô cùng. Một chiến lược (strategy) 1{P }n nP  của Hoài nghi xác đ nh nM và nV dựa vào các nước đi trước của Dự báo và Thực tế, và nước đi hiện tại của Dự báo 1 1 1 2 2 2 1 1 1( , v , , , v , ,..., , v , , , v ) P n n n n n n nM M m x m x m x m   1 1 1 2 2 2 1 1 1( , v , , , v , ,..., , v , , , v ) P n n n n n n nV V m x m x m x m   P nK là số vốn tích lũy (cumulative) của Hoài nghi với chiến lược P sau vòng n, với 0 PK =0 . Chúng ta gọi một dãy hàm giá tr thực 1 1 1( ,v , ,..., , v , )n n n nS m x m x của các nước đi 1 1 1, v , ,..., , v ,n n nm x m x , n 0 là một quá trình vốn (capital process) nếu Pn nS K đối với một chiến lược P nào đó. Một dãy vô hạn 1 1 1 2 2 2( , v , , , v , ,....)m x m x  các nước đi của Dự báo và Thực tế được gọi là một đường đi (path). Tập tất cả các đường đi 1 1 1 2 2 2{ ( ,v , , , v , ,....), n 1}m x m x     gọi là không gian mẫu (sample space), tập con bất kỳ E  gọi là một biến cố (event). Chúng ta nói rằng Hoài nghi có thể buộc (force) biến cố E nếu tồn tại một chiến lược P của Hoài nghi sao cho ( ) 1, , n 0PnK        (1) và limsup ( )Pn n K   Chú ý rằng Hoài nghi có thể buộc biến cốE , tức là E xảy ra hầu chắc chắn (xem [1]). Một chiến lược P của Hoài nghi thỏa mãn (1) được gọi là thận trọng (prudent). Chúng ta cũng gọi hàm thực ( )n nh x m của hiệu các nước đi nx và nm là một hàng rào (hedge) nếu 0 (x m )n nh   . Cho hai biến cố ,E F  biến cố 63 E F được xác đ nh là cE F E F   . Chúng ta cũng nói rằng một quá trình A là dự báo được (predictable) nếu với mọi số nguyên 1n , 1 1 1 2 2 2 (m , , ,m , , ,...,m , , ) n n n n A v x v x v x không phụ thuộc vào n x . Một supermartingale T là một quá trình có dạng T S B  , với S là một quá trình vốn và B là một quá trình tăng (       1 ( ) ( ), n, n n B B ). Một quá trình  0B có thể xem là tăng nên bản thân một quá trình vốn S là một supermartingale. Một semimartingale là một quá trình có thể viết dưới dạng U T A  , với T là một supermartingale và A là một quá trình tăng dự báo được; quá trình A được gọi là compensator đối với U . Bây giờ chúng ta chứng minh đ nh lí dưới đây: Định lí 2.1. Trong trò chơi dự báo không b chặn, Hoài nghi có thể buộc 1 1 1 lim (x m ) 0 n n k k x n k v n n          . Trước khi chứng minh đ nh lí này, chúng ta thảo luận về ý nghĩa của đ nh lí và đặc trưng của giao thức trò chơi dự báo không b chặn. Trong giao thức của trò chơi dự báo không b chặn, chúng ta xét hàng rào phương sai (còn gọi là hàng rào bậc hai 2(x m ) (x m )n n n nh    ). Do đó, giao thức này được gọi chính xác là trò chơi dự báo không b chặn với hàng rào bậc hai. Trong trò chơi này, hàng rào bậc hai được cố đ nh sẵn đối với Hoài nghi còn các giá của hàng rào nv sẽ được Dự báo công bố ở mỗi vòng, trước khi Thực tế công bố nước đi của mình. Vì vậy, sẽ rất hữu ích nếu chúng ta thay hàng rào bậc hai bởi hàng rào tổng quát h còn giá của hàng rào là một hằng số dương cố đ nh (xem [3]). Đ nh lí 3.1 của [3] cho thấy rằng trong trò chơi dự báo không b chặn với hàng rào đơn 1( ) , 0h x x    thì Hoài nghi có thể buộc 0nx  , với 1 2 ... n n x x x x n     . Mặt khác, Mệnh đề 2.1 của [3] cũng khẳng đ nh rằng trong trò chơi dự báo không b chặn với hàng rào đơn ( ) , r 0rh x x  thì Hoài nghi không thể buộc 1 2 1/ ... 0n r x x x n     . Tuy nhiên, cả đ nh lí và mệnh đề này đều được phát biểu đối với trò chơi dự báo không b chặn với hàng rào đơn h , trong đó giá của hàng rào đơn h là hằng số dương (tức là: 0, 1nv v n    ). Do vậy, khi xem xét trò chơi dự báo không b chặn với hàng rào bậc hai, có hai câu hỏi chính mà chúng ta cần quan tâm là có thể thay n trong Đ nh lí 3.1 của [3] bằng n hay không và nếu có thể, thì chúng ta cần phải thêm điều kiện gì? Đ nh lí 2.1 đã đưa ra một câu trả lời cho hai câu hỏi trên. Việc tiếp theo của chúng ta bây giờ là đưa ra chứng minh cho Đ nh lí 2.1. Chứng minh. Không mất tính tổng quát, chúng ta giả sử rằng 0, nm n  . Đặt 1 n k n k x S k  , 0 0S  ; 1 n k n k v A k  , 1 k k v A k     . 64 Xét 2 2 1 1 1 2 n n k k k n n n k k k x x v U S A S kk          = 2 1 12 n n n n n x x v U S nn      = 2 1 ( ).n n n n n nU M x V x v    Trong đó, 1 1 1 2 2 n k n n k x M S n n k       và 1 nV n  . Suy ra, nU là một quá trình vốn, do đó nU cũng là một supermartingale. Từ 1 1 n k n n n k x x S S k n      Chúng ta có nS là một quá trình vốn, với 1 nM n  và 0nV  nên nS cũng là một supermartingale. Chú ý rằng 2 n n nS U A  , do đó nA là compensator đối với semimartingale 2 nS . Khi đó từ Bổ đề 4.7 của [1], nếu A   thì nS hội tụ h.c.c, tức là 1 1 n n k n k v x n k       hội tụ h.c.c, khi n . Kết hợp với bổ đề Kronecker, ta được: 1 1 1 lim x 0 n n k x n k v n n         . Trong các giáo trình về lí thuyết xác suất, tốc độ hội tụ của LMSL có thể được đánh giá bằng một dãy số ( )nb tăng dương ( 0 nb  ). Tuy nhiên, trong lí thuyết trò chơi xác suất, dãy số dương tăng trở nên đặc biệt hơn, như trong Đ nh lí 2.2 dưới đây. Định lí 2.2. Gọi 2 1 n n k k B v   , trong trò chơi dự báo không b chặn, Hoài nghi có thể buộc 1 n n v     và 2 1 1 1 lim ( ) 0 n n k k x n kn n v x m B B          . Chứng minh. Chú ý rằng, không mất tính tổng quát, chúng ta giả sử 0, nm n  . Xét quá trình vốn 1 n k n k k x S B  . Compensator của 2nS là 2 1 n k n k k v A B  . Từ hai bổ đề 4.6 và 4.7 của [1] kết hợp với bổ đề Kronecker, ta dễ dàng suy ra 1 1 lim 0 n k x kn x B   3. TRÒ CHƠI DỰ BÁO KHÔNG BỊ CHẶN MỘT PHÍA Với trò chơi dự báo không b chặn ở mục trước, chúng ta thấy rằng nước đi nx của Thực tế là một số thực bất kỳ. Trong mục này, chúng tôi hạn chế nước đi của Thực tế là các số thực dương và đưa ra giao thức trò chơi dự báo không bị chặn một phía với hàng rào bậc hai (One-sided unbounded forecasting game with quadric hedge). Sau đó, chúng tôi chứng minh một số kết quả dạng LMSL đối với giao thức này. Giao thức trò chơi dự báo không b 65 chặn một phía với hàng rào bậc hai được viết như sau: ONE-SIDED UNBOUNDED FORECASTING (OUF) Người chơi: Dự báo, Hoài nghi, Thực tế Giao thức: 0 1K  . Với 1,2,... :n  Dự báo công bố 0nm  và 0nv  . Hoài nghi công bố nM  và 0nV  . Thực tế công bố 0nx  . 2 1: ( ) [( ) ]n n n n n n n n nK K M x m V x m v      . Nhiệm vụ ràng buộc: Hoài nghi phải giữ nK không âm. Thực tế phải giữ nK không tiến đến vô cùng. Đ nh lí dưới đây được phát triển dựa vào Đ nh lí 4.4 của [2] phát biểu cho trò chơi dự báo không b chặn. Định lí 3.1. Đặt 1 n n k k B m   , giả sử rằng g là một hàm số dương tăng trên [0; ) với ( )g   . Trong OUF, Hoài nghi có thể buộc 1 n n m     và 1 1 1 lim ( ) 0. ( ) ( ) n n k k x n kn n v x m g B g B          Chứng minh. Đặt 1 ( ) n k k n k k x m U g B   , 0 0U  ; 1 ( ) n k n k k v A g B  , 1 (B ) k k k v A g     . Xét 2 2 1 1 1 ( ) 2 ( ) (B )( ) n n k k k k k n n n k k k kk x m x m v T U A U gg B            = 2 1 1 ( ) 2 ( ) ( )( ) n n n n n n n nn x m x m v T U g Bg B        = 2 1 ( ) [( ) ]n n n n n n n nT M x m V x m v      . với 1 1 1 2 2 ( ) ( ) ( ) n n k k n kn n k U x m M g B g B g B        và 1 ( ) n n V g B  . Do đó nT là một quá trình vốn, suy ra nT cũng là một supermartingale. Mặt khác 1 1 ( ) ( ) n k k n n n n k k n x m x m U U g B g B        , suy ra nU cũng là một quá trình vốn với 1 ( ) n n M g B  và 0nV  . Lưu ý rằng 2n n nU T A  nên nA là compensator đối với 2nU . Khi đó, theo Bổ đề 4.7 của [1], ta có 1 1( ) ( ) n n k k n kn k v x m g B g B        hội tụ h.c.c, khi n . 66 Kết hợp với bổ đề Kronecker, ta được 1 1 lim ( ) 0 ( ) n k k x kn x m g B    . Đ nh lí được chứng minh Như chúng ta đã biết trong lí thuyết xác suất, luật mạnh số lớn Kolmogorov đã được nghiên cứu với các biến ngẫu nhiên độc lập cùng phân phối. Trong trường hợp đó, kỳ vọng và phương sai của các biến ngẫu nhiên đó là những hằng số không phụ thuộc vào n. Tương ứng với điều đó, trong lí thuyết trò chơi xác suất, ta xét luật mạnh số lớn với các nước đi của Thực tế là những hằng số và thu được hệ quả dưới đây. Hệ quả 3.2. Trong OUF, giả sử rằng nm  , 2 nv  với mọi n, đặt 1 n n k k S x   . Khi đó, Hoài nghi có thể buộc lim n x S n    . Chứng minh. Trong Đ nh lí 3.1, lấy hàm 2( )g x x . Khi đó 2 2 2 2 2 2 1 1 1 1 ( ) n n n nn v g B n n                 , 1 1 1 1 (x m ) (x m ) ( ) n n k k k k k kn ng B       . Do đó 1 1 lim ( ) 0 n k x k x n      hay lim n x S n    . TÀI LIỆU THAM KHẢO 1. G. Shafer, V. Vovk, Probability and Finance: It's Only a Game! Wiley, 2001. 2. Kenshi Miyabe, Akimichi Takemura, Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability, Stochastic Process. Appl 122 (2012) 1-30. 3. M. Kumon, A. Takemura, K. Takeuchi, Game-theoretic versions of strong law of large numbers for unbounded variables, Stochastic 79 (5) (2007) 449-468. * Ngày nhận bài: 6/3/2014. Biên tập xong: 16/5/2014. Duyệt đăng: 22/5/2014