Tài liệu 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 V N Đ X P X NG U NHIÊN VÀ T3 - 2010 NG D NG Nguy n Văn Thu (1), Hoà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, hoà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 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. Các tình hu ng trong ví d r t th c t và trên có th v n d ng toán h c ñ gi i quy t như sau. Ch n ng u nhiên m t giá tr sau ñó quan sát giá tr x1 , y ( x1 ) c a bi n ng u B n quy n thu c ĐHQG-HCM kỳ v ng M ( x) = E {Y ( x1 )} . Trong ñó E là kí hi u kỳ v ng toá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 an = an gi m d n theo n , ví d ch n c , trong ñó c là h ng s dương tuỳ ý. n 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: xn +1 = xn − c [ y( xn ) − α ]. (1) n Gi s ta làm ñư c thí nghi m th ñã bi t ñư c n và xn cũng như giá tr y ( xn ) . 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 n + 1 . Ta s 2. X P X NG U NHIÊN c th Y ( x1 ) v i nhiên a. Đ bi t ñ c ng c a h p kim ñ ng - s t ki m tra h th c ñ quy này. V i trư ng h p ñơn gi n nh t. Xét xn +1 = xn − α = 0 thì (1) có d ng c y( xn ) (2) n Trang 5 Science & Technology Development, Vol 13, No.T3- 2010 y ( xn ) > 0 thì xn +1 < xn và n u θ tho mãn M (θ ) = α ; gi s M kh vi t i y ( xn ) < 0 thì xn +1 > xn . N u y ( xn ) là θ và M ′(θ ) > 0 . Xét x1 là m t s th c và N u dương thì gi m giá tr c a x cho l n thí n là m t s nguyên dương. N u nghi m th n + 1 và ngư c l i. X n +1 = X n − 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 1 (Yn − α ) (1) n Yn là m t nghi m ng u nhiên trong ñó sao cho P[Yn = 1| X1 X2 ,..., Xn , Y1,...,Yn−1 ] = M ( Xn ) ng - Không thích P[Yn = 0| X1 X2 ,..., Xn , Y1,...,Yn−1 ] = 1− M ( Xn ) Trong vi c ki m tra thu c tr sâu, ta nh n Thì lim E ( X − θ ) = 0 , d n ñ n dãy 3.1. Gi i tích thích ng 2 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à bi n ng u nhiên {X n} h it ñ n θ theo bình ñ xác ñ nh phù h p ch ng lo i và li u lư ng phương trung bình và do ñó h i t theo xác mà thích ng cho t ng lo i côn trùng. V m t su t. G i toá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 ý ch ng ξn = E ( X n − θ ) 2 minh: Đ t , ta ch c n ch ng minh lim ξ n = 0 . n →∞ nhiênsao cho: Y ( x) = 1 n u Z ≤ x = 0 n u Z > x 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 Thì P [Y ( x) = 1] = P [ Z ≤ x ] = M ( x), P [Y ( x) = 0] = P [ Z > x ] = 1 − M ( x), E [Y ( x) ] = 1.M ( x) + 0. (1 − M ( x) ) = M ( x). 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 Bây gi Y ( x ) là m t quan sát thích 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 ñ i v i s lư ng cho s thích ng α . Ta có ñ nh lí sau: Đ nh lí 1. Gi s ph i và α Trang 6 M là m t hàm phân Đ nh lí 2 {α n } , {β n } , {γ n } (Dvoretzky). Gi là các dãy s th c không âm sao cho lim α n = 0 n →∞ s (1) là m t s th c ng v i m t s th c B n quy n thu c ĐHQG-HCM T P CHÍ PHÁT TRI N KH&CN, T P 13, S ∞ n ∑ βn < ∞ ∏ (m, n) = ∏ s( j ), Yn′ = ∏ (1, n)Yn (2) j =m 1 ∞ ∞ ∑γ n =∞ .Thì (3) n là m t s th c và Tn là các phép n Z (m, n) = ∑ Y j′. bi n ñ i ño ñư c sao cho j =m Tn ( X1,..., Xn ) −θ ≤m [αn,(1+βn)| Xn −θ | −γn] (4) ax X 1 ,..., X n . Xét m i X1 và V i ∀δ > 0, ∀ε > 0, ∃M 0 (δ , ε ) sao cho Yn ( n = 1, 2,...) là các bi n ng u nhiên và  δ    P  sup Z (m, n) >  < ε / 2. (9) 48  ,  Mmmn≤n  ≤  ñ nh nghĩa Xn+1 = Tn ( X1,..., Xn ) −Yn (X1,..., Xn ), ∀n ≥1. (5) 3. Đ t d ( m, m − 1) = 1 , { }<∞. 2 Thì các ñi u ki n E X 1 n +1 d (m, n) = ∏ (1 + β j ) v i n ≥ m . ∞ ∑ E {Y } < ∞ 2 n n =1 j =m (6) Xét t ng và E {Yn | X 1 ,..., X n } = 0 v i xác su t 1 v i m i n +1 S (m, n) = ∑ d ( j , n)Y j′−1 (7) j =m n , suy ra b ng v i P  lim X n = 0  = 1  n →∞  (8) n−1 Ch ng minh: Không m t tính t ng quát, ta có th ch n 1. T (4) 2. Đ t , ∑Z((m−2),( j −1))[d( j,n)−d( j +1,n)] −Y′ d(mn) n−2 j+m θ = 0. và (6) suy ra r ng 2 E (Xn ) < ∞ v i m i n . s (n) + Z ((m − 2), (n − 1))d (n, n) + Yn′ (10) là d u c a Tn ( X 1 ,..., X n )  [ X n ] n u c 2 th a s là   khác 0, và v i xác su t 1 b i (6) và (7). Vi t θ v i ∑Y ′ h i t 1 1 Xét T3 - 2010 s(n) = 1 n u m t trong hai th a s b ng 0. Vi t B n quy n thu c ĐHQG-HCM Khi d ( j , n ) ≥ d ( j + 1, n) chúng ta th y r ng giá tr tuy t ñ i c a (10) không l n hơn    sup Z ((m − 2), ( j − 1))  (d (m, n)) + Yn 2  j   m−1≤ j≤n  Trang 7 Science & Technology Development, Vol 13, No.T3- 2010 Do ñó t (2) và (9) ta có ñư c r ng v i δ > 0, ε > 0 t n t i m t M 00 (δ , ε ) ≥ M 0 (δ , ε ) Ta suy ra ñi u ph i ch ng minh. {γ n ( X 1 ,..., X n )} là nh âm c a bi n s th c α n ( X 1 ,..., X n ) là (11) β n ( X 1 ,..., X n ) hàm là ño ñư c và ∞ Cho {α n ( X 1 ,..., X n } , { β n ( X 1 ,..., X n )} và cho d ( m, ∞) < 3 / 2 v i m ≥ M 00 và   δ δ  P  sup Z (m, n) < , sup S (m, n) <  > 1 − ε / 2. 48 m,n 8 m  M 00 ≤,n ≤n M 00 ≤m≤n  m  Đ nh lí 3 (Dvoretzky) sao ng dãy hàm không X 1 ,..., X n sao cho hàm b ch n ñ u ∑β n ( X 1 ,..., X n ) là b ch n ñ u và h i t 1 X 1 ,..., X n ; ñ u trong (2) và ∀L > 0, ∃γ n ( X1,..., X n ) ≥ 0: ∞ ∑γ n = 0, (3) 1 và lim α n ( X 1 ,..., X n ) = 0 h i t ñ u v i m i n →∞ X 1 ,..., X n ; (1) và Tn ( X 1 ,..., X n ) − θ ≤ max{α n ( X 1 ,..., X n ),[1 + β n ( X 1 ,..., X n )] | X n − θ | −γ n } c ñ nh ñ u v i m i dãy mãn sup X n < L , trong ñó X 1 ,..., X n tho L là s dương n =1,2,... ñ i Tn ( X 1 ,..., X ) là phép bi n ño ñư c sao E ( X12 ) < ∞ ∞ ∑ E (Y 2 n (7) ) < ∞ ; (8) v i xác su t 1 E {Yn | X 1 ,..., X n } = 0. { Thì P lim X n n →∞ } = θ = 1 (10) lim E ( X n − θ ) 2 = 0. (11) n →∞ Trang 8 δ, ε là P { X n < δ , ∀n} > 1 − ε (12) L y M ≥ M 0 (δ , ε ) là ñ l n tho , v i n ≥ M , α n < δ / 8 . L y L ñ l n tho L > δ và Max E { X 2 } < j 1 và và nh ng s dương tuỳ ý. Đ ch ng minh (10) ta cho X n +1 = Tn ( X 1 ,..., X n ) + Yn ( X n ), n ≥ 1 (6) và θ =0 c n ch ng minh nó tho mãn ñây tuỳ ý, (5) Ch ng minh: L y (4) 1≤ j ≤ m (9) Chúng ta l y ε L2 32 M L . (13) ñây là tho mãn v i (3). Nó cũng tho mãn r ng { } P Max X j ≤ L / 4 > 1 − ε / 2. (14) 1≤ j ≤ M B n quy n thu c ĐHQG-HCM T P CHÍ PHÁT TRI N KH&CN, T P 13, S Gi s r ng 4 ñi u ki n sau ñư c tho mãn Liên h v i (11) và (14) c a (15), (25) X m > δ / 4 v i t t c m ≥ M . (26) liên h (1) c a ñ nh lí 1. (15) X m ≤ δ / 4 v i m t vài m ≥ M . (16) X m +1 ≥ δ / 4, 1 ≤ j ≤ k . (17) trong ñó ñúng khi 1≤ k ≤ ∞ . αn < δ / 8 khi n≥M N ch ng Khi k =∞, (17) j ≥ 1 và (18) là r ng (là rõ ràng khi ch ng minh xong mà Đ ch ng minh (11). Xét Xét X m + k +1 ≤ δ / 4 . (18) k ≠ ∞ ). T3 - 2010 1≤ j <∞ là s nguyên. B i vì (10), ta ch ph i minh { lim E ( (| X n | − k ) + ) n →∞ k = lim α j . (| X n | − k ) + B i vì 2 r ng }=0 ñây = max {(| X n | − k ) , 0} . 3.3. X p x cho quá trình ti m c n chính và b i vì (15), (16), quy (17) d n ñ n Trong ph n này s nghiên c u dãy các Tm + j ( X m + j ) > α m + j (0 ≤ j ≤ k − 1) (19) bi n ng u nhiên, nhưng ch t p trung vào các sign( Xm+ j+1 ) = sign(Tm+ j (Xm+ j )) (0 ≤ j ≤ k −1) ñi u ki n y u trên các h s l p. Đ nh lí 4(a) (Comer). Xét (20) Áp d ng (4) ( v i γ = 0) dãy xác ñ nh như dư i ñây và ta có X m+1 ng u nhiên sao cho n m gi a 0 và s(m)(1 + β m ) X m + Ym (21) L p l i l p lu n này, khi ñây θ (i) 1 ≤ j ≤ k thì và ñây s(m + j −1)s(m + j − 2)...s(m)d (m, m + j −1) Xm + s(m + j − 1)...s(m − 1)d (m + 1, m + j − 1)Ym +s(m + j −1)d (m + j −1, m + j −1)Ym+ j −2 +Ym+ j −1 (ii) m i n, ′ X n +1 = X n − an [Yn ( X n ) − Y0 ] , sao cho L ≤ dn = M ( X n ) − Y0 ≤u Xn −θ v i L và u là nh ng s th c tho ñây mãn L < u . Không m t tính t ng quát gi s r ng Y0 = 0 . ∞ (iii) Đ ch ng minh (12) ta ch c n ch ra r ng B n quy n thu c ĐHQG-HCM 2 nhiên Vì v y X m + j , 1 ≤ j ≤ k . (24) các ki u ki n sau không th x y ra c hai. E ( X1 − θ ) < V 2 < ∞ , E [Yn ( X ) | X n ] = M ( X n ) . (22) (23) X 1 là m t bi n V là các s th c. Gi s r ng ng u X m d ( m, m + j − 1) + S ( m + 1, m + j − 1) . là m t Y0 là s th c b t kì và Yn ( X n ) là bi n X m+ j n m gi a 0 và Giá tr tuy t ñ i c a (22) không l n hơn {X n} ∑ a′ = ∞ , n ñây ′ { an } là dãy s 1 dương. Trang 9 Science & Technology Development, Vol 13, No.T3- 2010 (iv) ′ lim an = a′ ≥ 0 . 1 lim  E ( X n − θ )2  2 ≤ k / L   n →∞ 1 . u (v) 0 ≤ a′ ≤ (vi) Z n = Yn ( X n ) − M ( X n ) và M là lien t c t i θ và n →∞ Ch ng minh: T (iv) và (v) luôn t n t i v i M (0) = 0 . (vii) E  Z  2 n dương =k ,  2 b t ′ N sao cho anu < 1 v i n > N . m ts k là s th c ñây kì. 1 2 uk lim sup  E Y   ≤ +k .    n →∞ L 2 n Do ñó Thì ′ ′ 0 < 1 − an u ≤ 1 − an d n ≤ 1 − an L < 1, n > N   ′ ′ X n +1 − θ = X n − θ − an [ Z n ] − an d n ( X n − θ ),   ′ ′ X n +1 − θ = (1 − an d n )( X n − θ ) − an Z n (n ≥ 1),  ′ ′ X n +1 − θ ≤ (1 − an d n ) X n − θ + an Z n ,   2 2 2 ′ ′ E X n +1 − θ ≤ (1 − an L) 2 E ( X n − θ ) + an 2 E ( Z n )   ′ ′ + 2(1 − an L)an E {| Z n || X n − θ |}   (1) 2 2 2 2 ′ ≤ (1 − an L) E ( X n − θ ) + an E ( Z n )   1 1  2 2 2 2 ′ ′  + 2(1 − an L)(an )  EZ n   E ( X n − θ )  ,     1 1   ′  ′  E ( X n +1 − θ ) 2  2 ≤ (1 − an L)  E ( X n − θ ) 2  2 + an k     1 1    ′     =  E ( X n − θ ) 2  2 − an L   E ( X n − θ ) 2  2 − k / L  , n ≥ N .     L y ε >0 thì ta gi s trái v i gi thi t r ng E ( X n −θ ) ≥ k / L + ε . L y n > N. 2 1 1 2 2 2 2 ′ Thay vào (1) ta có  E ( X n +1 − θ )  ≤  E ( X n − θ )  − an Lε , thì     n ( ε ) −1 ∑ 1  E ( X n +1 − θ )2  2 ≤   N n ( ε ) −1 ∑ 1  E ( X n − θ ) 2  2 − Lε   N 1 2 2 n ( ε ) −1 ∑ a′ . n N  ∑ a′ ,   n N 1 2  E ( X n (ε ) − θ )  ≤  E ( X N − θ )  − Lε     2 Trang 10 n ( ε ) −1     (2) B n quy n thu c ĐHQG-HCM T P CHÍ PHÁT TRI N KH&CN, T P 13, S ∞ Nhưng khi Thì t n t i m t hàm ∑ a′ = ∞ ta có n T3 - 2010 g c a a′ sao cho lim sup E ( X n − θ ) ≤ g (a′), 1 2 n (ε ) n →∞ 1 2 ′  Lε ∑ an ≥  E ( X N − θ )  − k / L  2 (3) lim E [ (Yn − Z n ) ] ≤ u 2 g (a′) 2 N m →∞ Thay (3) vào (2) ta ñư c và 1 2  E ( X − θ )2  ≤ k / L. n (ε )     lim g (a′) → 0, g (0) = 0. a ′→ 0 Đ 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 Yn = d n ( X n − θ ) + Z n (n ≥ 1), Yn ≤ u X n − θ + Z n và 1 (i) ′ an → 0 khi n → ∞ ii) Khi ( X n − θ ) M ( X n ) > 0. 1  EYn2  2 ≤ u  E ( X − θ )2  2 + k ≤ uk / L + k.     Thì P  lim X n = θ  = 1.  n→∞  3.4. Lý thuy t m u nh Đ nh lí 4(b)(Comer). Gi s có các ñi u ki n (i) ñ n (iv) c a ñ nh lí 4(a) các ph n trư c trong th c t ch áp d ng ñ i v i (i) Xét các v n ñ gi i quy t m t c m u xác ñ nh, câu µn , m = E ( Z n | Z n − m , Z n − m −1 ,..., Z1 ) , ñây (ii) T n t i m t dãy các s th c 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 m ≥ 1 và n ≥ m + 1 . {ξ m } sao toá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 cho 1 2  E ( µn ,m )  2 ≤ ξ m , m ≥ 1 và n ≥ m + 1   và Vì các phương pháp ñã trình bày lim ξ m = 0 . m →∞ B n quy n thu c ĐHQG-HCM 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 . Trang 11 Science & Technology Development, Vol 13, No.T3- 2010 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). Trang 12 [2]. Vivek S. Approximation, Borkar, Cambridge Stochastic University Press, (2008). B n quy n thu c ĐHQG-HCM