طريقة مارساجليا القطبية

طريقة مارساجليا القطبية [ 1 ^{] هي طريقة} أخذ عينات الأرقام شبه العشوائية لتوليد زوج من المتغيرات العشوائية الطبيعية القياسية المستقلة . ^{[ 2 ]}

تُستخدم المتغيرات العشوائية الطبيعية القياسية بشكل متكرر في علوم الحاسوب ، والإحصاءات الحسابية ، وعلى وجه الخصوص، في تطبيقات طريقة مونت كارلو .

تعتمد الطريقة القطبية على اختيار نقاط عشوائية ( س ، ص ) في المربع −1 < س < 1 ، −1 < ص < 1 حتى         

${\displaystyle 0<s=x^{2}+y^{2}<1,\,}$

ثم إرجاع الزوج المطلوب من المتغيرات العشوائية الطبيعية كـ

${\displaystyle x{\sqrt {\frac {-2\ln(s)}{s}}}\,,\ \ y{\sqrt {\frac {-2\ln(s)}{s}}},}$

أو، على نحو مماثل،

${\displaystyle {\frac {x}{\sqrt {s}}}{\sqrt {-2\ln(s)}}\,,\ \ {\frac {y}{\sqrt {s}}}{\sqrt {-2\ln(s)}},}$

أين${\displaystyle x/{\sqrt {s}}}$و${\displaystyle y/{\sqrt {s}}}$يمثل جيب التمام وجيب الزاوية التي يصنعها المتجه ( x , y ) مع المحور x .

يمكن تلخيص النظرية الأساسية على النحو التالي:

إذا ^{كان المتغير} u موزعًا توزيعًا منتظمًا في الفترة 0  ≤ u < 1، فإن النقطة (cos(2π u ), sin(2π u )) موزعة توزيعًا منتظمًا على محيط الدائرة x² + y² = 1، وبضرب تلك النقطة بمتغير عشوائي مستقل ρ يكون توزيعه        

${\displaystyle \Pr(\rho <a)=\int _{0}^{a}re^{-r^{2}/2}\,dr}$

سينتج عنه نقطة

${\displaystyle \left(\rho \cos(2\pi u),\rho \sin(2\pi u)\right)}$

والتي يتم توزيع إحداثياتها بشكل مشترك كمتغيرين عشوائيين طبيعيين قياسيين مستقلين.

تعود هذه الفكرة إلى لابلاس ، الذي ينسب إليه غاوس الفضل في اكتشاف ما سبق ذكره.

${\displaystyle I=\int _{-\infty }^{\infty }e^{-x^{2}/2}\,dx}$

بأخذ الجذر التربيعي لـ

${\displaystyle I^{2}=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }e^{-(x^{2}+y^{2})/2}\,dx\,dy=\int _{0}^{2\pi }\int _{0}^{\infty }re^{-r^{2}/2}\,dr\,d\theta .}$

يُظهر التحويل إلى الإحداثيات القطبية أن θ موزعة بانتظام (بكثافة ثابتة) من 0 إلى 2π، وأن المسافة القطرية r لها كثافة

${\displaystyle re^{-r^{2}/2}.\,}$

( r ^{2 له توزيع} مربع كاي المناسب .)

تُسمى هذه الطريقة لإنتاج زوج من المتغيرات الطبيعية المعيارية المستقلة عن طريق إسقاط نقطة عشوائية شعاعيًا على محيط الوحدة إلى مسافة تُعطى بواسطة الجذر التربيعي لمتغير كاي تربيع 2، الطريقة القطبية لتوليد زوج من المتغيرات العشوائية الطبيعية.

تطبيق مباشر لهذه الفكرة،

${\displaystyle x={\sqrt {-2\ln(u_{1})}}\cos(2\pi u_{2}),\quad y={\sqrt {-2\ln(u_{1})}}\sin(2\pi u_{2})}$

يُطلق عليه اسم تحويل بوكس-مولر ، والذي يتم فيه عادةً توليد متغير كاي على النحو التالي:

${\displaystyle {\sqrt {-2\ln(u_{1})}},}$

لكن هذا التحويل يتطلب دوال اللوغاريتم والجذر التربيعي والجيب وجيب التمام. في بعض المعالجات، يمكن حساب جيب وجيب تمام نفس الوسيط بالتوازي باستخدام تعليمة واحدة. ^{[ 3 ]} ومن الجدير بالذكر أنه بالنسبة للأجهزة التي تعمل بمعالجات إنتل، يمكن استخدام تعليمة التجميع fsincos أو تعليمة expi (المتوفرة مثلاً في لغة D) لحساب الأعداد المركبة.

${\displaystyle \operatorname {expi} (z)=e^{iz}=\cos(z)+i\sin(z),\,}$

وافصل ببساطة الأجزاء الحقيقية عن الأجزاء الخيالية.

ملاحظة: لحساب الصيغة القطبية المركبة بشكل صريح، استخدم الاستبدالات التالية في الصيغة العامة،

يترك${\displaystyle r={\sqrt {-2\ln(u_{1})}}}$و${\displaystyle z=2\pi u_{2}.}$ثم

${\displaystyle \ re^{iz}={\sqrt {-2\ln(u_{1})}}e^{i2\pi u_{2}}={\sqrt {-2\ln(u_{1})}}\left[\cos(2\pi u_{2})+i\sin(2\pi u_{2})\right].}$

في المقابل، تُغني الطريقة القطبية هنا عن حساب جيب التمام وجيب الزاوية. فبدلاً من ذلك، بحل المعادلة لإيجاد نقطة على دائرة الوحدة ، يمكن استبدال هاتين الدالتين بإحداثيات س و ص مُعَيَّرة إلى${\displaystyle {\sqrt {x^{2}+y^{2}}}}$نصف القطر. على وجه الخصوص، يتم إسقاط نقطة عشوائية ( x , y ) داخل دائرة الوحدة على محيط الوحدة عن طريق تحديد ${\displaystyle s=x^{2}+y^{2}}$وتشكيل النقطة

${\displaystyle \left({\frac {x}{\sqrt {s}}},{\frac {y}{\sqrt {s}}}\right),\,}$

وهي عملية أسرع من حساب جيب التمام وجيب الزاوية. يرى بعض الباحثين أن استخدام عبارة if الشرطية (لرفض نقطة خارج دائرة الوحدة) قد يُبطئ البرامج على المعالجات الحديثة المزودة بتقنية التجزئة والتنبؤ بالتفرع. ^{[ 4 ]} كما تتطلب هذه العملية حوالي 27% تقييمات إضافية لمولد الأرقام العشوائية الأساسي (فقط${\displaystyle \pi /4\approx 79\%}$(تقع جميع النقاط المتولدة داخل دائرة الوحدة).

ثم يتم إسقاط تلك النقطة العشوائية على المحيط شعاعيًا على المسافة العشوائية المطلوبة بواسطة

${\displaystyle {\sqrt {-2\ln(s)}},\,}$

باستخدام نفس قيمة s لأن قيمة s مستقلة عن النقطة العشوائية على المحيط وهي نفسها موزعة بشكل منتظم من 0 إلى  1.