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
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
vấn đề đặt ra.
8 trang |
Chia sẻ: maiphuongdc | Lượt xem: 1578 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Vấn đề xấp xỉ ngẫu nhiên và ứng dụng, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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), 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Ế
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 toá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 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 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
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
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
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
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).
Các file đính kèm theo tài liệu này:
- van_de_xap_xi_ngau_nhien_va_ung_dung.pdf