Biến đổi Box Mull Muller – Wikipedia

lordneo

14 years ago

Trực quan hóa biến đổi Box Mull Muller – các điểm được tô màu trong ô vuông đơn vị (u1, u2), được vẽ dưới dạng hình tròn, được ánh xạ tới 2D Gaussian (z0, z1), được vẽ dưới dạng hình chữ thập. Các ô ở lề là các hàm phân phối xác suất của z0 và z1. Lưu ý rằng z0 và z1 không bị ràng buộc; chúng có vẻ là trong [-2.5,2.5] do sự lựa chọn của các điểm minh họa. Trong tệp SVG, di chuột qua một điểm để làm nổi bật nó và điểm tương ứng của nó.

Biến đổi Box kiếm Muller bởi George Edward Pelham Box và Mervin Edgar Muller, ^[1] là giả ngẫu nhiên phương pháp lấy mẫu số để tạo các cặp số ngẫu nhiên độc lập, tiêu chuẩn, phân phối bình thường (không kỳ vọng, phương sai đơn vị), được cung cấp một nguồn các số ngẫu nhiên phân bố đồng đều. Trên thực tế, phương pháp này lần đầu tiên được đề cập rõ ràng bởi Raymond E. A. C. Paley và Norbert Wiener vào năm 1934. ^[2]

Phép biến đổi Box Mull Muller thường được thể hiện dưới hai dạng. Mẫu cơ bản được đưa ra bởi Box và Muller lấy hai mẫu từ phân phối đồng đều trong khoảng [0, 1] và ánh xạ chúng thành hai mẫu chuẩn, phân phối chuẩn. Dạng cực lấy hai mẫu từ một khoảng khác nhau, [−1, +1] và ánh xạ chúng thành hai mẫu được phân phối bình thường mà không sử dụng các hàm sin hoặc cos.

Biến đổi Boxer Muller được phát triển như một phương pháp thay thế hiệu quả hơn về mặt tính toán cho phương pháp lấy mẫu biến đổi nghịch đảo. ^[3] Thuật toán ziggurat đưa ra một phương pháp hiệu quả hơn ^{[ cần trích dẫn ]} ]. Hơn nữa, phép biến đổi Boxer Muller có thể được sử dụng để vẽ từ mật độ Gaussian bivariate bị cắt ngắn. ^[4]

Dạng cơ bản [ chỉnh sửa ]

Giả sử U _{và U ₂ là các mẫu độc lập được chọn từ phân phối đồng đều trên khoảng đơn vị (0, 1). Để cho}

Z 0 = R cos ⁡ ( Θ ) = – ] ln ⁡ U 1 cos ⁡ ( 2 π U 2 displaystyle Z_ {0} = R cos ( Theta) = { sqrt {-2 ln U_ {1}}} cos (2 pi U_ {2}) ,} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/46e09d833afb2466f517e90dbc0e363cb0bcdf8a" aria-hidden="true" alt=" Z_0 = R cos ( Theta) = sqrt {-2 ln U_1} cos (2 pi U_2) , " width="16877.2" height="1439.2">

và

Z 1 = R sin ⁡ ( Θ ) = – ] ln ⁡ U 1 sin ⁡ ( 2 π U 2 ) { displaystyle Z_ {1} = R sin ( Theta) = { sqrt {-2 ln U_ {1}}} sin (2 pi U_ {2}). ,} [19659067] Z_1 = R sin ( Theta) = sqrt {-2 ln U_1} sin (2 pi U_2). , “/>

Sau đó Z ₀ và Z ₁ là các biến ngẫu nhiên độc lập với phân phối chuẩn thông thường.

Đạo hàm ^[5] dựa trên tính chất của hệ thống Cartesian hai chiều, trong đó tọa độ X và Y được mô tả bởi hai biến ngẫu nhiên độc lập và phân phối thông thường, các biến ngẫu nhiên cho R ² và (hiển thị ở trên) trong tọa độ cực tương ứng cũng độc lập và có thể được biểu thị bằng

R 2 = – 2 ⋅ ln ⁡ U 1 ^ {2} = – 2 cdot ln U_ {1} ,} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/702928cf2d25505446185f796a9dcfa0f0d5034b" aria-hidden="true" alt=" R ^ 2 = -2 cdot ln U_1 , " width="6855.1" height="1295.7">

và

Θ = 2 π U 2 . { displaystyle Theta = 2 pi U_ {2}. } <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/145ac177710afd925efaae9ae8ba6c594b35b20b" aria-hidden="true" alt=" Theta = 2 pi U_2. , " width="4769.1" height="1080.4">

Bởi vì R ² là bình phương của định mức của tiêu chuẩn biến thông thường bivariate ( X Y, ), nó có phân phối chi bình phương với hai bậc tự do. Trong trường hợp đặc biệt của hai bậc tự do, phân phối chi bình phương trùng với phân bố hàm mũ và phương trình cho R ² ở trên là một cách đơn giản để tạo ra biến thiên theo hàm mũ cần thiết.

Dạng cực [ chỉnh sửa ]

Hai giá trị phân bố đồng đều, u và v được sử dụng để tạo ra giá trị = R ²được phân phối đồng đều như vậy. Các định nghĩa về sin và cos sau đó được áp dụng cho dạng cơ bản của phép biến đổi Box Mull Muller để tránh sử dụng các hàm lượng giác.

Dạng cực được đề xuất đầu tiên bởi J. Bell ^[6] và sau đó được sửa đổi bởi R. Knop. ^[7] Trong khi một số phiên bản khác nhau của phương pháp cực đã được mô tả, phiên bản của R. Knop sẽ được mô tả ở đây vì nó được sử dụng rộng rãi nhất, một phần do được đưa vào Công thức toán số .

Đã cho u và v phân phối độc lập và thống nhất trong khoảng thời gian đóng [−1, +1]đặt s = R ² = u ² + v ². (Rõ ràng

R = s { displaystyle scriptstyle R = { sqrt {s}}}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e50e115e7784dbf50bc65edf9e1a94ae1a73c28e" aria-hidden="true" alt=" scriptstyle R = sqrt {s} " width="2008.9" height="936.9">$ ) . Nếu s = 0 hoặc s ≥ 1 loại bỏ u và v và thử một cặp khác [ u v ). Bởi vì u và v được phân phối đồng đều và vì chỉ các điểm trong vòng tròn đơn vị đã được thừa nhận, các giá trị của s sẽ được phân phối đồng đều trong khoảng thời gian mở ( 0, 1) cũng vậy. Cái sau có thể được nhìn thấy bằng cách tính hàm phân phối tích lũy cho s trong khoảng (0, 1). Đây là khu vực của một vòng tròn có bán kính

s { displaystyle scriptstyle { sqrt {s}}}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a41099430a8cc26566c1c11a5155f2cedcf2fc7c" aria-hidden="true" alt=" scriptstyle sqrt {s} " width="921.4" height="936.9">$ được chia cho

π [19659127] { displaystyle scriptstyle pi}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bb2635a9b35ac9dfcc9fed1229d49f5355bd3a8d" aria-hidden="true" alt=" scriptstyle pi " width="405.5" height="578.1">$ . Từ đó, chúng ta thấy hàm mật độ xác suất có giá trị không đổi 1 trên khoảng (0, 1). Tương tự như vậy, góc θ chia cho

2 π { displaystyle scriptstyle 2 pi}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ca1c97b2aba7cb514f08126df3889034ba5927b4" aria-hidden="true" alt=" scriptstyle 2 pi " width="759.4" height="721.6">$ được phân bố đồng đều trong khoảng [01)vàđộclậpvới s .

Bây giờ chúng tôi xác định giá trị của s với giá trị của U ₁ và

θ / ( 2 π ) { displaystyle scriptstyle theta / (2 pi)}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98067e94723827cfc412f06eb4b506afe83bc185" aria-hidden="true" alt=" scriptstyle theta / (2 pi) " width="1996.2" height="936.9">$ với U ₂ ở dạng cơ bản. Như được hiển thị trong hình, các giá trị của

cos ⁡ θ = cos ⁡ 2 U 2 { displaystyle scriptstyle cos theta = cos 2 pi U_ {2}}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8454069b95bf2685b26b9e597caa3e2e267a55e2" aria-hidden="true" alt=" scriptstyle cos theta = cos 2 pi U_2 " width="4710.9" height="793.3">$ và

sin ⁡ θ = sin ⁡ 2 π { displaystyle scriptstyle sin theta = sin 2 pi U_ {2}}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d64a13bcc01da7101303eca350fe5a53564858d6" aria-hidden="true" alt=" scriptstyle sin theta = sin 2 pi U_2 " width="4555.4" height="793.3">$ ở dạng cơ bản có thể được thay thế bằng các tỷ số

cos ⁡ θ = u / R = u ] s { displaystyle scriptstyle cos theta = u / R = u / { sqrt {s}}}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5375f4c6b1ba089ebccbabfb7765ea28c1de0383" aria-hidden="true" alt=" scriptstyle cos theta = u / R = u / sqrt {s} " width="5522.6" height="936.9">$ và

sin ⁡ θ = v / R = v / s { displaystyle scriptstyle sin theta = v / R = v / { sqrt {s}}}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6190ca5e4c906826786c8ce696ea3b9ca11aefa" aria-hidden="true" alt=" scriptstyle sin theta = v / R = v / sqrt {s} " width="5321.8" height="936.9">$ tương ứng. Ưu điểm là tính toán các hàm lượng giác trực tiếp có thể tránh được. Điều này hữu ích khi các hàm lượng giác đắt hơn để tính toán hơn so với phép chia duy nhất thay thế cho từng hàm.

Giống như dạng cơ bản tạo ra hai độ lệch chuẩn thông thường, phép tính thay thế này cũng vậy.

z 0 = – 2 ln ⁡ U 1 cos ⁡ ] 2 π U 2 ) = – 2 ln ⁡ 19659226] u s ) = u ⋅ – 2 ln ⁡ { displaystyle z_ {0} = { sqrt {-2 ln U_ {1}}} cos (2 pi U_ {2}) = { sqrt {-2 ln s}} left ({ frac {u} { sqrt {s}}} right) = u cdot { sqrt { frac {-2 ln s} {s}}}} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e40643ede00b3902399f6ec449eed868a7edb734" aria-hidden="true" alt=" z_0 = sqrt {- 2 ln U_1} cos (2 pi U_2) = sqrt {-2 ln s} left ( frac {u} { sqrt {s}} right) = u cdot sqrt { frac {-2 ln s} {s}} " width="26629.2" height="2874.4">

và

z 1 = – 2 ln ⁡ U 1 sin ⁡ ] 2 π U 2 ) = – 2 ln ⁡ 19659226] v s ) = v ⋅ – 2 ln ⁡ . { displaystyle z_ {1} = { sqrt {-2 ln U_ {1}}} sin (2 pi U_ {2}) = { sqrt {-2 ln s }} left ({ frac {v} { sqrt {s}}} right) = v cdot { sqrt { frac {-2 ln s} {s}}}.} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5c7c0d13474cc0cdf0b4893a2ad8595f8b51d852" aria-hidden="true" alt=" z_1 = sqrt {-2 ln U_1} sin (2 pi U_2) = sqrt {-2 ln s} left ( frac {v} { sqrt {s}} right) = v cdot sqrt { frac {-2 ln s} {s}}. " width="26710.7" height="2874.4">

Đối chiếu hai hình thức [ chỉnh sửa ]

] Phương pháp cực khác với phương pháp cơ bản ở chỗ nó là một kiểu lấy mẫu từ chối. Nó loại bỏ một số số ngẫu nhiên được tạo ra, nhưng có thể nhanh hơn phương pháp cơ bản vì nó đơn giản hơn để tính toán (với điều kiện là trình tạo số ngẫu nhiên tương đối nhanh) và mạnh hơn về số lượng. ^[8] Nó tránh sử dụng các hàm lượng giác, có thể tốn kém trong một số môi trường máy tính ^{[ cần trích dẫn ]}. Nó loại bỏ 1 – $π$ / 4 21,46% trong tổng số các cặp số ngẫu nhiên được phân phối đồng đều được tạo ra, tức là loại bỏ 4 / $π$ – 1 27,3

Dạng cơ bản yêu cầu hai phép nhân, 1/2 logarit, 1/2 căn bậc hai và một hàm lượng giác cho mỗi phương sai thông thường. ^[9] Trên một số bộ xử lý, cosine và sin của cùng một đối số có thể được tính song song sử dụng một hướng dẫn duy nhất. Đáng chú ý đối với các máy dựa trên Intel, người ta có thể sử dụng lệnh biên dịch chương trình biên dịch fsincos hoặc lệnh expi (thường có sẵn từ C như một hàm nội tại), để tính toán phức tạp

exp ⁡ ( i z ) = e i z = ] ⁡ z + i sin ⁡ z { displaystyle exp (iz) = e ^ {iz} = cos z + i sin z, ,} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/155b08d9d1897e1de951c73317a5b44ad488131d" aria-hidden="true" alt=" { displaystyle exp (iz) = e ^ {iz} = cos z + i sin z, ,} " width="12952.3" height="1367.4">

và chỉ cần tách các phần thực và tưởng tượng.

Lưu ý: Để tính toán rõ ràng dạng cực phức, sử dụng các thay thế sau ở dạng tổng quát,

Hãy

r = – 2 ln ⁡ ( u 1 ) [1965937] r = { sqrt {-2 ln (u_ {1})}}}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7cfcb5854b8383561fd45f19e70a8f85a9cb9bcd" aria-hidden="true" alt=" { displaystyle r = { sqrt {-2 ln (u_ {1})}}} " width="6872.1" height="2085">$ và [19659327] z = 2 π u 2 . { displaystyle z = 2 pi u_ {2}.}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e2b786079f38d943357a77df48ba50f0244dd91d" aria-hidden="true" alt=" { displaystyle z = 2 pi u_ {2}.} " width="4181.5" height="1080.4">$ Sau đó

r e i z = – 2 ln ⁡ ( u ]) e i 2 π u 2 = – 2 ln u 1 ) [ cos ⁡ ( 2 π u 2 ] + i sin ⁡ ( 2 π u 2 ) ] { displaystyle re ^ {iz} = { sqrt {-2 ln (u_ {1})}} e ^ {i2 pi u_ {2}} = { sqrt {-2 ln (u_ { 1})}} left [cos(2pi u_{2})+isin(2pi u_{2})right].} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d2c2194ab68d2d5d3ba8119f7691f8ccc4765846" aria-hidden="true" alt=" { displaystyle re ^ {iz} = { sqrt {-2 ln (u_ {1})}} e ^ {i2 pi u_ {2} } = { sqrt {-2 ln (u_ {1})}} left [cos(2pi u_{2})+isin(2pi u_{2})right].} " width="27999.7" height="2085">

Dạng cực yêu cầu 3/2 phép nhân, 1/2 logarit, 1/2 căn bậc hai và 1 / 2 chia cho mỗi phương sai bình thường. Hiệu quả là thay thế một phép nhân và một hàm lượng giác bằng một phép chia đơn và một vòng lặp có điều kiện.

Cần lưu ý rằng fsincos đã trở nên rất nhanh trong các kiến trúc CPU hiện đại, do đó tốc độ "lợi ích" của phương pháp lấy mẫu từ chối không còn thực tế nữa. Trong khi đó, phép chia dấu phẩy động theo s và vòng lặp có điều kiện, cả hai vẫn là một chi phí đáng kể trong thuật toán lấy mẫu từ chối, không có ở dạng cơ bản.

Cắt đuôi [ chỉnh sửa ]

Khi một máy tính được sử dụng để tạo ra một biến ngẫu nhiên thống nhất, chắc chắn sẽ có một số điểm không chính xác vì có thể bị giới hạn ở mức thấp hơn. 0. Nếu trình tạo sử dụng 32 bit cho mỗi giá trị đầu ra, số khác không nhỏ nhất có thể được tạo là

2 – 32 { displaystyle 2 ^ {- 32}} [19659394] 2 ^ {- 32} “/>. Khi

U 1 { displaystyle U_ {1}} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc9e7f892894bc50c32ce1b9f9a68a15562146ac" aria-hidden="true" alt=" U_ {1} " width="1137.4" height="1080.4">

và

U 2 { displaystyle U_ {2} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/590fa6a550fbe2866a28243a733d54245d218b9d" aria-hidden="true" alt=" U_ {2} " width="1137.4" height="1080.4">

bằng với phép biến đổi Box kèm Muller này tạo ra một biến ngẫu nhiên bình thường tương đương với

– 2 ln ⁡ ( 2 – 32 ) cos ⁡ ( 2 π 2 – 32 ] ≈ 6.66 { displaystyle { sqrt {-2 ln (2 ^ {- 32})}} cos (2 pi 2 ^ {- 32}) khoảng 6,66} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/40752fefebe561f4b7ad3a751f1f60d4745632ee" aria-hidden="true" alt=" sqrt {-2 ln (2 ^ {- 32})} cos (2 pi 2 ^ {- 32}) khoảng 6,66 " width="14251" height="2085">

Điều này có nghĩa là thuật toán sẽ không tạo ra các biến ngẫu nhiên nhiều hơn 6,66 độ lệch chuẩn so với giá trị trung bình. Điều này tương ứng với tỷ lệ của

2,74 × 10 – 11 { displaystyle 2.74 lần 10 ^ {- 11}} <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9a3f5f0d53bdb19d727d3f2440b2ec7de13b554" aria-hidden="true" alt=" 2.74 lần 10 ^ {- 11} " width="5362.2" height="1152.1">

bị mất do cắt ngắn.

Thực hiện [ chỉnh sửa ]

Biến đổi Box Tiêu chuẩn Muller tạo ra các giá trị từ phân phối chuẩn thông thường ( tức là độ lệch chuẩn bình thường) với trung bình 0 và độ lệch chuẩn 1 . Việc triển khai bên dưới trong C ++ tiêu chuẩn tạo ra các giá trị từ bất kỳ phân phối bình thường nào với giá trị trung bình

μ { displaystyle mu}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161" aria-hidden="true" alt=" mu " width="603.5" height="936.9">$ và phương sai

σ 2 [19659394] { displaystyle sigma ^ {2}}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/53a5c55e536acf250c1d3e0f754be5692b843ef5" aria-hidden="true" alt=" sigma ^ {2} " width="1026.8" height="1152.1">$ . Nếu

Z { displaystyle Z}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1cc6b75e09a8aa3f04d8584b11db534f88fb56bd" aria-hidden="true" alt=" Z " width="723.5" height="936.9">$ là độ lệch chuẩn bình thường, thì

X = Z σ μ { displaystyle X = Z sigma + mu}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cce5cc456b46bf59dc2c6374a2cc30f0246e1a5e" aria-hidden="true" alt=" X = Z sigma + mu " width="5309" height="1152.1">$ sẽ có phân phối bình thường với giá trị trung bình

μ { displaystyle mu}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161" aria-hidden="true" alt=" mu " width="603.5" height="936.9">$ và độ lệch chuẩn

σ { displaystyle sigma}

$<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59f59b7c3e6fdb1d0365a494b81fb9a696138c36" aria-hidden="true" alt=" sigma " width="572.5" height="721.6">$ . Lưu ý rằng vì trình tạo số ngẫu nhiên rand chưa được gieo hạt nên chuỗi giá trị tương tự sẽ luôn được trả về từ hàm createdGaussianNiri .

 #include    #include   #include    double   tạoGaussianNoir  ( double   mu  )   { 	 static   const   double   epsilon   =   std  ::  num_limits  ::  min  ();  	 static   const   double   hai_pi   =   2.0  *  3.14159 ] thread_local   double   z1 ;  	 thread_local   bool   tạo ;  	 tạo   =     	 if   (!  tạo ra )  	    trở lại   z1   *   sigma   +   ] gấp đôi   u1   u2 ;  	 do  	  { 	    u1   =   r và  ()   *   ( 1.0   /   RAND_MAX );  	    u2   =   rand ] *   ( 1.0   /   RAND_MAX );  	 }  	 trong khi   [  u1   ]);   	 gấp đôi   z0 ;  	 z0   =   sqrt  ( -  2.0   * [196594] ( u1 ))   *   cos  ( hai_pi   *   u2 );  	 z1 sqrt  ( -  2.0   *   log  ( u1 ))   *   sin    *   u2 );  	 trở lại   z0   *   sigma   +   mu ;    [ chỉnh sửa ]   Tài liệu tham khảo  [ chỉnh sửa ] 
  ^ [19659619] Hộp, G. E. P.; Muller, Mervin E. (1958). &quot;Lưu ý về việc tạo ra các sai lệch bình thường ngẫu nhiên&quot;.  Biên niên sử thống kê toán học .  29  (2): 610 Chiếc611. doi: 10.1214 / aoms / 1177706645. JSTOR 2237361.  
  ^   Raymond EAC Paley và Norbert Wiener  Fourier biến đổi trong miền phức,  New York: Hiệp hội toán học Mỹ (1934) §37.  
  ^  
  Platen,  Giải pháp số của phương trình vi phân ngẫu nhiên trang 11 Cách12  
  ^   Martino, L.; Luengo, Đ.; Míguez, J. (2012). &quot;Lấy mẫu hiệu quả từ các Gaussian bivariate cắt ngắn thông qua chuyển đổi Box-Muller&quot;.  Thư điện tử .  48  (24): 1533 19151534. CiteSeerX  10.1.1.716.8683 . doi: 10.1049 / el.2012.2816.  
  ^   Sheldon Ross,  Một khóa học đầu tiên về xác suất (2002), trang 279 Muff281  
  ^   Bell, James R (1968). &quot;Thuật toán 334: Độ lệch ngẫu nhiên bình thường&quot;.  Truyền thông của ACM .  11  (7): 498. doi: 10.1145 / 363397.363547.  
  ^   Knop, R. (1969). &quot;Ghi chú về thuật toán 334 [G5]: Độ lệch ngẫu nhiên bình thường&quot;.  Truyền thông của ACM .  12  (5): 281. doi: 10.1145 / 362946.362996.  
  ^   Everett F. Carter, Jr.,  Tạo và ứng dụng số ngẫu nhiên Forth Dimensions (1994), Tập. 16, Số 1 & 2.  
  ^   Lưu ý rằng việc đánh giá 2  $π$  U ₁ được tính là một phép nhân vì giá trị của 2  $π$  có thể được tính toán trước và được sử dụng nhiều lần.  
 
  Liên kết ngoài  [ chỉnh sửa ]