Vấn đề xấp xỉ ngẫu nhiên và ứng dụng

TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ T3 - 2010 Bản quyền thuộc ĐHQG-HCM Trang 5 VẤN ĐỀ XẤP XỈ NGẪU NHIÊN VÀ ỨNG DỤNG Nguyễn Văn Thu (1), Hồng Văn Bắc (2) (1) Trường Đại học Quốc tế, ĐHQG-HCM (2) Trường THPT Đức Trọng, tỉnh Lâm Đồng (Bài nhận ngày 08 tháng 11 năm 2009, hồn chỉnh sửa chữa ngày 22 tháng 11 năm 2010) TĨM TẮT: Xấp xỉ ngẫu nhiên là một cơng cụ vơ cùng quan trọng của giải tích số. Trong bài này chúng tơi sẽ trình bày tổng quát về xấp xỉ ngẫu nhiên đồng thời cũng nêu ra một phương pháp đặc biệt của xấp xỉ ngẫu nhiên, đĩ là phương pháp Robbins - Monro. Từ khĩa: xấp xỉ ngẫu nhiên, phương pháp Robbins – Monro. 1. CÁC VÍ DỤ THỰC TẾ a. Để biết độ cứng của hợp kim đồng - sắt ở nhiệt độ 5000C người ta thường xét khoảng thời gian x và ( )Y x là độ cứng tương của hợp kim. Vấn đề đặt ra là tìm các giá trị của x mà hợp kim cĩ độ cứng trung bìnhα . Biết rằng các loại hợp kim khác nhau ứng với độ cứng khác nhau. b. Ta xét độ nhạy của một chất nổ khi bị va chạm. Một phương pháp thong thường ta thả cho nĩ rơi tự do từ một độ cao xác định. Đối với một số chất nổ thì độ cao này thì phát nổ mỗi loại chất nổ làm cho nổ khi được thả. c. Tương tự, trong việc kiểm tra thuốc trừ sâu, ta cũng phải xác định giới hạn của các loại thuốc đối với các loại cơn trùng và mức độ sử dụng sao cho phù hợp để đạt kết quả cao trong sử dụng. 2. XẤP XỈ NGẪU NHIÊN Các tình huống trong ví dụ rất thực tế và cụ thể ở trên cĩ thể vận dụng tốn học để giải quyết như sau. Chọn ngẫu nhiên một giá trị 1x , sau đĩ quan sát giá trị 1( )y x của biến ngẫu nhiên 1( )Y x với kỳ vọng { }1( ) ( )M x E Y x= . Trong đĩ E là kí hiệu kỳ vọng tốn học và M là một hàm tăng chưa biết dạng chính xác. Ta cũng chọn một dãy các số dương na giảm dần theo n , ví dụ chọn n c a n = , trong đĩ c là hằng số dương tuỳ ý. Vấn đề đặt ra là xác định giá trị của θ sao cho ( )M θ α= . Ta thiết lập hệ thức đệ quy để tìm các giá trị x cho các thí nghiệm tiếp theo: [ ]1 ( ) .n n ncx x y x n α+ = − − (1) Giả sử ta làm được thí nghiệm thứ n và đã biết được nx cũng như giá trị ( )ny x . Sử dụng (1) ta cĩ thể xác định giá trị cụ thể của x để sử dụng cho lần thí nghiệm thứ 1n + . Ta sẽ kiểm tra hệ thức đệ quy này. Với trường hợp đơn giản nhất. Xét 0α = thì (1) cĩ dạng 1 ( )n n n c x x y x n + = − (2) Science & Technology Development, Vol 13, No.T3- 2010 Trang 6 Bản quyền thuộc ĐHQG-HCM Nếu ( ) 0ny x > thì 1n nx x+ < và nếu ( ) 0ny x . Nếu ( )ny x là dương thì giảm giá trị của x cho lần thí nghiệm thứ 1n + và ngược lại. Ta sẽ nghiên cứu một ứng dụng của xấp xỉ ngẫu nhiên, đĩ là phương pháp Robbins - Monro được trình bày sau đây. 3. PHƯƠNG PHÁP ROBBINS - MONRO 3.1. Giải tích thích ứng - Khơng thích ứng Trong việc kiểm tra thuốc trừ sâu, ta nhận thấy hiện tượng là cĩ hoặc khơng cĩ loại cơn trùng mà thuốc cĩ tác dụng. Do đĩ, vấn đề là để xác định phù hợp chủng loại và liều lượng mà thích ứng cho từng loại cơn trùng. Về mặt tốn học, các vấn đề này được giải quyết như sau. Xét Z là biến ngẫu nhiên với hàm phân bố M . Nếu x là số thực và ( )Y x là biến ngẫu nhiênsao cho: ( ) 1Y x = nếu Z x≤ 0= nếu Z x> Thì [ ] [ ] [ ] [ ] [ ] ( ) ( ) 1 ( ), ( ) 0 1 ( ), ( ) 1. ( ) 0. 1 ( ) ( ). P Y x P Z x M x P Y x P Z x M x E Y x M x M x M x = = ≤ = = = > = − = + − = Bây giờ ( )Y x là một quan sát thích ứng đối với số lượng x (khối lượng thuốc trừ sâu chẳng hạn). Vấn đề là để xác định giá trị của x cho sự thích ứng α . Ta cĩ định lí sau: Định lí 1. Giả sử M là một hàm phân phối và α là một số thực ứng với một số thực θ thoả mãn ( )M θ α= ; giả sử M khả vi tại θ và ( ) 0M θ′ > . Xét 1x là một số thực và n là một số nguyên dương. Nếu ( )1 1n n nX X Y n α+ = − − (1) trong đĩ nY là một nghiệm ngẫu nhiên sao cho [ ] [ ] 1 2 1 1 1 2 1 1 1| ,..., , ,..., ( ) 0| ,..., , ,..., 1 ( ) n n n n n n n n P Y X X X Y Y M X P Y X X X Y Y M X − − = = = = − Thì 2lim ( ) 0 n E X θ →∞ − = , dẫn đến dãy biến ngẫu nhiên { }nX hội tụ đến θ theo bình phương trung bình và do đĩ hội tụ theo xác suất. Gợi ý chứng minh: Đặt ( )2n nE Xξ θ= − , ta chỉ cần chứng minh lim 0 n n ξ →∞ = . Cĩ một phương pháp để giải quyết vấn đề thích ứng – khơng thích ứng là phương pháp xấp xỉ ngẫu nhiên. 3.2. Xấp xỉ ngẫu nhiên một chiều Bây giờ ta xét câu hỏi của tình huống tổng quát trong đĩ Y khơng bị hạn chế nhận giá trị 1 hoặc 0 mà cĩ thể nhận bất kì giá trị nào Định lí 2 (Dvoretzky). Giả sử { } { } { }, ,n n nα β γ là các dãy số thực khơng âm sao cho lim 0 n n α →∞ = (1) TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ T3 - 2010 Bản quyền thuộc ĐHQG-HCM Trang 7 1 nβ ∞ < ∞∑ (2) 1 nγ ∞ = ∞∑ (3) Xét θ là một số thực và nT là các phép biến đổi đo được sao cho ( ) [ ]1,..., max ,(1 )| |n n n n n nT X X Xθ α β θ γ− ≤ + − − (4) với mọi 1,..., nX X . Xét 1X và ( 1, 2,...)nY n = là các biến ngẫu nhiên và định nghĩa 1 1 1( ,..., ) ( ,..., ), 1.n n n n nX T X X Y X X n+ = − ∀ ≥ (5) Thì các điều kiện { }21E X < ∞ . { }2 1 n n E Y ∞ = < ∞∑ (6) và { }1| ,..., 0n nE Y X X = (7) với xác suất 1 với mọi n , suy ra lim 0 1n n P X →∞  = =   (8) Chứng minh: Khơng mất tính tổng quát, ta cĩ thể chọn 0θ = . 1. Từ (4) và (6) suy ra rằng ( )2nE X < ∞ với mọi n . 2. Đặt ( )s n là dấu của ( ) [ ]1, ...,n n nT X X X   nếu cả 2 thừa số là khác 0, và ( ) 1s n = nếu một trong hai thừa số bằng 0. Viết ( , ) ( ), (1, ) n n n j m m n s j Y n Y = ′= =∏ ∏ ∏ .Thì 1 nY ∞ ′∑ hội tụ với xác suất 1 bởi (6) và (7). Viết ( , ) . n j j m Z m n Y = ′=∑ Với 00, 0, ( , )Mδ ε δ ε∀ > ∀ > ∃ sao cho , sup ( , ) / 2. 48 M m n m n P Z m n δ ε ≤ ≤    > <     (9) 3. Đặt ( , 1) 1d m m − = , 1 ( , ) (1 ) n j j m d m n β + = = +∏ với n m≥ . Xét tổng 1 1( , ) ( , ) n j j m S m n d j n Y + − = ′=∑ bằng với [ ]1 2(( 2),( 1)) ( , ) ( 1, ) ( , ) n n j m Z m j d j n d j n Y d mn − − + ′ − − − + −∑ (( 2), ( 1)) ( , ) nZ m n d n n Y ′+ − − + (10) Khi ( , ) ( 1, )d j n d j n≥ + chúng ta thấy rằng giá trị tuyệt đối của (10) khơng lớn hơn 1 2 sup (( 2), ( 1)) ( ( , )) m j n n j Z m j d m n Y − ≤ ≤     − − +     Science & Technology Development, Vol 13, No.T3- 2010 Trang 8 Bản quyền thuộc ĐHQG-HCM Do đĩ từ (2) và (9) ta cĩ được rằng với 0, 0δ ε> > tồn tại một 00 0( , ) ( , )M Mδ ε δ ε≥ sao cho ( , ) 3 / 2d m ∞ < với 00m M≥ và 00 00 , , sup ( , ) , sup ( , ) 1 / 2. 48 8 M m n M m n m n m n P Z m n S m nδ δ ε ≤ ≤ ≤ ≤     −     (11) Ta suy ra điều phải chứng minh. Định lí 3 (Dvoretzky) Cho{ } { }1 1( ,..., , ( ,..., )n n n nX X X Xα β và { }1( ,..., )n nX Xγ là những dãy hàm khơng âm của biến số thực 1,..., nX X sao cho hàm 1( ,..., )n nX Xα là bị chặn đều và 1lim ( ,..., ) 0n n n X Xα →∞ = hội tụ đều với mọi 1,..., nX X ; (1) hàm 1( ,..., )n nX Xβ là đo được và 1 1 ( ,..., )n nX Xβ ∞ ∑ là bị chặn đều và hội tụ đều trong 1,..., nX X ; (2) và 1 1 0, ( ,..., ) 0: 0, n n n L X Xγ γ ∞ ∀ > ∃ ≥ =∑ (3) và 1 1 1( ,..., ) max{ ( ,..., ),[1 ( ,..., )] | | }n n n n n n n nT X X X X X X Xθ α β θ γ− ≤ + − − (4) cố định đều với mọi dãy 1,..., nX X thoả mãn 1,2,... sup n n X L = < , trong đĩ L là số dương tuỳ ý, (5) ở đây 1( ,..., )nT X X là phép biến đổi đo được sao cho 1 1( ,..., ) ( ), 1n n n n nX T X X Y X n+ = + ≥ (6) và 21( )E X < ∞ (7) 2 1 ( )nE Y ∞ < ∞∑ ; (8) với xác suất 1 { }1| , ..., 0.n nE Y X X = (9) Thì { }lim 1n n P X θ →∞ = = (10) và 2lim ( ) 0.n n E X θ →∞ − = (11) Chứng minh: Lấy 0θ = và ,δ ε là những số dương tuỳ ý. Để chứng minh (10) ta cần chứng minh nĩ thoả mãn { }, 1nP X nδ ε − (12) Lấy 0 ( , )M M δ ε≥ là đủ lớn thoả, với , / 8nn M α δ≥ < . Lấy L đủ lớn thoả L δ> và { } 22 1 . 32jj m LMax E X M ε ≤ ≤ < (13) Chúng ta lấy L ở đây là thoả mãn với (3). Nĩ cũng thoả mãn rằng { }1 / 4 1 / 2.jj MP Max X L ε≤ ≤ ≤ > − (14) TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ T3 - 2010 Bản quyền thuộc ĐHQG-HCM Trang 9 Giả sử rằng 4 điều kiện sau được thoả mãn liên hệ (1) của định lí 1. (15) / 4mX δ≤ với một vài m M≥ . (16) 1 / 4, 1mX j kδ+ ≥ ≤ ≤ . (17) 1 / 4m kX δ+ + ≤ . (18) trong đĩ 1 k≤ ≤ ∞ . Khi k = ∞ , (17) đúng khi 1j ≥ và (18) là rổng (là rõ ràng khi chứng minh xong mà k ≠ ∞ ). Bởi vì / 8nα δ< khi n M≥ và bởi vì (15), (16), (17) dẫn đến ( ) (0 1)m j m j m jT X j kα+ + +> ≤ ≤ − (19) ( ) ( )1 ( ) (0 1)m j m j m jsign X sign T X j k+ + + += ≤ ≤ − (20) Áp dụng (4) ( với 0γ = ) ta cĩ 1mX + nằm giữa 0 và ( )(1 )m m ms m X Yβ+ + (21) Lập lại lập luận này, khi 1 j k≤ ≤ thì m jX + nằm giữa 0 và ( 1) ( 2)... ( ) ( , 1) ms m j s m j s m d m m j X+ − + − + − ( 1)... ( 1) ( 1, 1) ms m j s m d m m j Y+ + − − + + − 2 1( 1) ( 1, 1) m j m js m j d m j m j Y Y+ − + −+ + − + − + − + (22) Giá trị tuyệt đối của (22) khơng lớn hơn ( , 1) ( 1, 1) .mX d m m j S m m j+ − + + + − (23) Vì vậy , 1 .m jX j k+ ≤ ≤ (24) Để chứng minh (12) ta chỉ cần chỉ ra rằng các kiều kiện sau khơng thể xảy ra cả hai. Liên hệ với (11) và (14) của (15), (25) / 4mX δ> với tất cả m M≥ . (26) Để chứng minh (11). Xét 1 lim jjk α≤ <∞= . Xét N là số nguyên. Bởi vì (10), ta chỉ phải chứng minh rằng ( ){ }2lim (| | ) 0n n E X k + →∞ − = ở đây ( ) ( ){ }| | max | | , 0n nX k X k+− = − . 3.3. Xấp xỉ cho quá trình tiệm cận chính quy Trong phần này sẽ nghiên cứu dãy các biến ngẫu nhiên, nhưng chỉ tập trung vào các điều kiện yếu trên các hệ số lập. Định lí 4(a) (Comer). Xét { }nX là một dãy xác định như dưới đây và 1X là một biến ngẫu nhiên sao cho ( )2 21E X Vθ− < < ∞ , ở đây θ và V là các số thực. Giả sử rằng (i) [ ]1 0( )n n n n nX X a Y X Y+ ′= − − , ở đây 0Y là số thực bất kì và ( )n nY X là biến ngẫu nhiên sao cho [ ]( ) | ( )n n nE Y X X M X= . (ii) 0( )n n n M X YL d u X θ − ≤ = ≤ − với mọi n , ở đây L và u là những số thực thoả mãn L u< . Khơng mất tính tổng quát giả sử rằng 0 0Y = . (iii) 1 na ∞ ′ = ∞∑ , ở đây { }na′ là dãy số dương. Science & Technology Development, Vol 13, No.T3- 2010 Trang 10 Bản quyền thuộc ĐHQG-HCM (iv) lim 0n n a a →∞ ′ ′= ≥ . (v) 10 a u ′≤ ≤ . (vi) ( ) ( )n n n nZ Y X M X= − và M là lien tục tại θ với (0) 0M = . (vii) 2 2nE Z k  =  , ở đây k là số thực dương bất kì. Thì 1 2 2lim ( ) /n n E X k Lθ →∞  − ≤  và 1 2 2lim sup n n ukE Y k L→∞    ≤ +   . Chứng minh: Từ (iv) và (v) luơn tồn tại một số N sao cho 1na u′ . Do đĩ [ ] ( ) ( ) { } ( ) ( ) 1 1 1 2 22 2 2 1 22 2 2 0 1 1 1 1, ( ), (1 )( ) ( 1), (1 ) , (1 ) 2(1 ) | || | (1 ) n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n a u a d a L n N X X a Z a d X X a d X a Z n X a d X a Z E X a L E X a E Z a L a E Z X a L E X a E Z θ θ θ θ θ θ θ θ θ θ θ + + + + ′ ′ ′ ′ − = − − − − ′ ′ − = − − − ≥ ′ ′ − ≤ − − + ′ ′ − ≤ − − + ′ ′+ − − ′≤ − − + 1 1 2 22 2 1 1 2 22 2 1 1 1 2 22 2 2(1 )( ) ( ) , ( ) (1 ) ( ) ( ) ( ) / , . n n n n n n n n n n n a L a EZ E X E X a L E X a k E X a L E X k L n N θ θ θ θ θ +               ′ ′    + − −      ′ ′   − ≤ − − +       ′   = − − − − ≥         (1) Lấy 0ε > thì ta giả sử trái với giả thiết rằng ( )2 / .nE X k Lθ ε− ≥ + Lấy .n N> Thay vào (1) ta cĩ ( ) ( ) 1 1 2 22 2 1n n nE X E X a Lθ θ ε+    ′− ≤ − −    , thì 1 1( ) 1 ( ) 1 ( ) 1 2 22 2 1 1 1 ( ) 1 2 22 2 ( ) ( ) ( ) , ( ) ( ) . n n n n n n N N N n n N n N E X E X L a E X E X L a ε ε ε ε ε θ θ ε θ θ ε − − − + −  ′   − ≤ − −        ′   − ≤ − −     ∑ ∑ ∑ ∑ (2) TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ T3 - 2010 Bản quyền thuộc ĐHQG-HCM Trang 11 Nhưng khi 1 na ∞ ′ = ∞∑ ta cĩ 1( ) 2 2( ) / n n N N L a E X k L ε ε θ′  ≥ − − ∑ (3) Thay (3) vào (2) ta được ( ) 1 2 2 ( ) / .nE X k Lε θ − ≤   Khi ( ) ( 1),n n n n n n n Y d X Z n Y u X Z θ θ = − + ≥ ≤ − + và 1 1 2 22 2( ) / .nEY u E X k uk L kθ   ≤ − + ≤ +    Định lí 4(b)(Comer). Giả sử cĩ các điều kiện (i) đến (iv) của định lí 4(a) (i) Xét ( ) , 1 1| , ,...,n m n n m n mE Z Z Z Zµ − − −= , ở đây 1m ≥ và 1n m≥ + . (ii) Tồn tại một dãy các số thực { }mξ sao cho 1 2 2 , ( ) , 1n m mE mµ ξ  ≤ ≥  và 1n m≥ + và lim 0m m ξ →∞ = . Thì tồn tại một hàm g của a′ sao cho ( ) [ ] 2 2 2 limsup ( ), lim ( ) ( ) n n n n m E X g a E Y Z u g a θ →∞ →∞ ′− ≤ ′− ≤ và 0 lim ( ) 0, (0) 0. a g a g ′→ ′ → = Định lí 4(c). Giả sử cĩ các điều kiện của định lí 4(a) và 4(b). Thêm vào (i) 0na′ → khi n → ∞ ii) ( ) ( ) 0.n nX M Xθ− > Thì lim 1.n n P X θ →∞  = =   3.4. Lý thuyết mẫu nhỏ Vì các phương pháp đã trình bày ở các phần trước trong thực tế chỉ áp dụng đối với các vấn đề giải quyết một cỡ mẫu xác định, câu hỏi đặt ra là lí thuyết xấp xỉ tiệm cận tốt như thế nào đối với các trường hợp cụ thể. Trong tốn học, khài niệm tuyến tính rất quan trọng, ví dụ trong Kakutani là sự mở rộng của định lí điểm bất động Brauwer cĩ quan hệ gắn với vấn đề đặt ra. Vì vậy nĩ được giả thiết rằng ( )( ) ( )M X E y X= là một đường thẳng với phương sai của X được chọn là một hằng số. Science & Technology Development, Vol 13, No.T3- 2010 Trang 12 Bản quyền thuộc ĐHQG-HCM STOCHASTIC APPROXIMATIONS AND APPLICATIONS Nguyen Van Thu (1), Hoang Van Bac(2) (1) International University,VNU-HCM (2) Secondary School, Duc Trong, Lam Dong ABSTRACT: The purpose of this note is to present introductory ideas of stochastic approximation problems which stand for important aspects of numerical analysis. In particular, we illustrate by considering the Robbins – Monro method. Từ khĩa: Xấp xỉ ngẫu nhiên, phương pháp Robbins – Monro, biến ngẫu nhiên, hàm phân phối, nghiệm ngẫu nhiên, quá trình tiệm cận chính quy, mẫu nhỏ. TÀI LIỆU THAM KHẢO [1]. M.T. Wasan, Stochastic Approximation, Cambridge University Press, (1969). [2]. Vivek S. Borkar, Stochastic Approximation, Cambridge University Press, (2008).