تطبيق مونتي كارلو التكامل في التقديم

درسنا جميعًا الأساليب العددية في سياق الرياضيات. هذه طرق مثل التكامل ، الاستيفاء ، السلسلة ، وما إلى ذلك. هناك نوعان من الأساليب العددية: القطعية والعشوائية.

طريقة تكامل الوظيفة الحتمية النموذجية $$$و$ في النطاق $$$[a، b]$ يبدو مثل هذا: نحن نأخذ $$$ن + 1 دولا$ نقاط متباعدة بالتساوي $$$t_0 = a ، t_1 = a + \ frac {b - a} {n} ، \ ldots ، t_n - b$ ، حساب $$$و$ عند نقطة المنتصف $$$\ frac {t_i + t_ {i + 1}} {2}$ من كل فترة من الفواصل المحددة بواسطة هذه النقاط ، لخص النتائج واضربها بعرض كل فاصل $$$\ frac {b -a} {b}$ . لوظائف مستمرة بما فيه الكفاية $$$و$ مع زيادة $$$ن$ سوف تتلاقى النتيجة مع القيمة الصحيحة.


الطريقة الاحتمالية أو طريقة مونت كارلو لحساب ، أو بشكل أدق ، تقدير تقريبي للتكامل $$$و$ في النطاق $$$[a، b]$ يشبه هذا: دع $$$X_1 ، \ ldots ، X_n$ - نقاط مختارة عشوائيا في الفاصل $$$[a، b]$ . ثم $$$Y = (b - a) \ frac {1} {n} \ sum_ {i = 1} ^ {n} f (X_i)$ هي قيمة عشوائية متوسطها جزء لا يتجزأ $$$\ int _ {[[a، b]} f$ . لتطبيق هذه الطريقة ، نستخدم مولد الأرقام العشوائية الذي يولد $$$ن$ نقاط في الفاصل $$$[a، b]$ نحن نحسب في كل $$$و$ ، متوسط ​​النتائج واضرب في $$$ب أ دولا$ . هذا يعطينا القيمة التقريبية للتكامل ، كما هو موضح في الشكل أدناه. $$$\ int _ {- 1} ^ {1} \ sqrt {1 - x ^ 2} dx$ مع 20 عينة تقريبًا النتيجة الصحيحة تساوي $$$\ frac {\ pi} {2}$ .


بالطبع ، في كل مرة نحسب فيها هذه القيمة التقريبية ، سنحصل على نتيجة مختلفة. يعتمد تباين هذه القيم على شكل الوظيفة. $$$و$ . إذا كنا توليد نقاط عشوائية $$$x_i$ بشكل غير متساو ، ثم نحن بحاجة إلى تغيير طفيف الصيغة. ولكن بفضل استخدام التوزيع غير المتكافئ للنقاط ، نحصل على ميزة كبيرة: إجبار التوزيع غير المتكافئ على إعطاء الأفضلية للنقاط $$$x_i$ حيث $$$f (x)$ كبير ، يمكننا تقليل تباين القيم التقريبية بشكل كبير. ويسمى مبدأ أخذ العينات غير الموحد أخذ العينات بالأهمية .


منذ العقود الماضية ، حدث انتقال واسع النطاق من المقاربات الحتمية إلى المقاربات العشوائية في أساليب التقديم ، وسندرس المناهج العشوائية المستخدمة في حل معادلات التقديم. للقيام بذلك ، نستخدم المتغيرات العشوائية والتوقعات الرياضية والتباين. نحن نتعامل مع قيم منفصلة ، لأن أجهزة الكمبيوتر منفصلة في الطبيعة. تتعامل الكميات المستمرة مع دالة الكثافة الاحتمالية ، لكن في المقالة لن نفكر فيها. سنتحدث عن وظيفة الكتلة الاحتمالية. PMF لديه اثنين من الخصائص:

1. لكل منهما $$$s \ في S$ هناك $$$p (s) \ geq 0$ .
2. $$$\ sum_ {s \ in S} p (s) = 1$

الخاصية الأولى تسمى عدم السلبية. والثاني يسمى "الحياة الطبيعية". حدسي ، هذا $$$S$ يمثل مجموعة من نتائج بعض التجارب ، و $$$p (s)$ هو نتيجة الاحتمال $$$s$ وهو عضو $$$S$ . النتيجة هي مجموعة فرعية من مساحة الاحتمال. احتمال وجود نتيجة هو مجموع عناصر PMF لهذه النتيجة ، منذ ذلك الحين

$$

$$Pr \ {E \} = \ sum_ {s \ in S} p (s)$$

المتغير العشوائي هو دالة ، عادة ما يتم الإشارة إليها بحرف كبير ، والذي يضع أرقامًا حقيقية في مساحة الاحتمال:

$$

$$X: S \ rightarrow \ boldsymbol {R}.$$

لاحظ أن الوظيفة $$$X$ - هذا ليس متغيرًا ، لكنه دالة ذات قيم حقيقية. هي أيضا ليست عشوائية ، $$$X (s)$ هو رقم حقيقي منفصل لأي نتيجة $$$s \ في S$ .

متغير عشوائي يستخدم لتحديد النتائج. على سبيل المثال ، العديد من النتائج $$$s$ من اجل ذلك $$$X (s) = 1$ ، إذا كان ht و th هما مجموعة الخطوط التي تشير إلى "النسور" أو "ذيول" ، إذن

$$

$$E = {s \ in S: X (s) = 1}$$

و

$$

$$= {ht، th}$$

إنها نتيجة مع الاحتمال $$$\ frac {1} {2}$ . نكتبها كما $$$Pr \ {X = 1 \} = \ frac {1} {2}$ . نحن نستخدم المسند $$$X = 1 دولا$ كمدخل مختصرة للنتيجة التي تحددها المسند.

دعنا نلقي نظرة على جزء من الشفرة يحاكي تجربة موصوفة في الصيغ المعروضة أعلاه:

headcount = 0 if (randb()): // first coin flip headcount++ if (randb()): // second coin flip headcount++ return headcount 

هنا نشير بواسطة ranb() بوظيفة منطقية ترجع إلى نصف الحالات. كيف يرتبط التجريد لدينا؟ تخيل الكثير $$$S$ جميع عمليات الإعدام المحتملة للبرنامج ، مع الإعلان عن ranb نفس القيم التي تم إرجاعها بواسطة ranb ، ranb . هذا يعني أن هناك أربعة عمليات إعدام محتملة للبرنامج حيث يستدعي مكالمات ranb() جهازي TT و TF و FT و FF. من تجربتنا الخاصة ، يمكننا أن نقول إن هذه الإنجازات الأربعة محتملة بنفس الدرجة ، أي أن كل منها يحدث في حوالي ربع الحالات.

الآن أصبح القياس أكثر وضوحًا. تعد عمليات الإعدام العديدة المحتملة لأحد البرامج والاحتمالات المرتبطة بها مساحة للاحتمال. متغيرات البرنامج التي تعتمد على المكالمات ranb هي متغيرات عشوائية. آمل أن كل شيء واضح لك الآن.

دعونا مناقشة القيمة المتوقعة ، وتسمى أيضا المتوسط. هذا هو في الأساس مجموع ناتج PMF ومتغير عشوائي:

$$

$$E [X] = \ sum_ {s \ in S} p (s) X (s)$$

تخيل أن ح "النسور" و "ذيول". لقد قمنا بالفعل بتغطية ht و th. هناك أيضا سمو وترينيداد وتوباغو. لذلك ، ستكون القيمة المتوقعة كما يلي:

$$

$$E [X] = p (hh) X (hh) + p (ht) X (ht) + p (th) X (th) + p (tt) X (tt)$$

$$

$$= \ frac {1} {4}. 2 + \ frac {1} {4}. 1 + \ frac {1} {4}. 1 + \ frac {1} {4} .0$$

$$

$$= 1 \ text {QED}$$

قد تتساءل من أين جاءت $$$X$ . هنا قصدت أنه يجب علينا تعيين معنى $$$X$ بنفسك. في هذه الحالة ، قمنا بتعيين h إلى 1 و t إلى 0. $$$X (hh)$ يساوي 2 لأنه يحتوي على 2 $$$ح$ .

دعنا نتحدث عن التوزيع. توزيع الاحتمالات هو دالة تعطي احتمالات نتائج مختلفة لحدث ما.

عندما نقول أن متغير عشوائي $$$X$ لديه التوزيع $$$و$ ثم يجب أن تشير $$$X \ sim f$ .

تشتت القيم المتراكمة حولها $$$X$ يسمى التشتت ويعرف على النحو التالي:

$$

$$\ boldsymbol {Var} [X] = E [(X - \ bar {X}) ^ 2]$$

حيث $$$\ bar {X}$ متوسط $$$X$ .

$$$\ sqrt {\ boldsymbol {Var}}$ دعا الانحراف المعياري . متغيرات عشوائية $$$X$ و $$$Y$ تسمى مستقلة إذا:

$$

$$Pr \ {X = x \ text {and} Y = y \} = Pr \ {X = x \}. Pr \ {Y = y \}$$

خصائص مهمة للمتغيرات العشوائية المستقلة:

1. $$$E [XY] = E [X] E [Y]$
2. $$$\ boldsymbol {Var} [X + Y] = \ boldsymbol {Var} [X] + \ boldsymbol {Var} [Y]$

عندما بدأت بقصة عن الاحتمال ، قارنت الاحتمالات المستمرة والمنفصلة. درسنا احتمال منفصل. الآن دعنا نتحدث عن الفرق بين الاحتمالات المستمرة والمتقطعة:

1. القيم مستمرة. وهذا هو ، الأرقام لا حصر لها.
2. تتطلب بعض جوانب التحليل دقة في الرياضيات مثل قابلية القياس .
3. سيكون لدينا مساحة الاحتمال لانهائية. بدلاً من PMF ، يجب أن نستخدم دالة كثافة الاحتمال (PDF).

خصائص PDF:

1. لكل منهما $$$s \ في S$ لدينا $$$p (s) \ geq 0$
2. $$$\ int_ {s \ in S} p (s) = 1$

ولكن إذا كان التوزيع $$$S$ بالتساوي ، ثم يتم تعريف قوات الدفاع الشعبي مثل هذا:


مع احتمال مستمر $$$E [X]$ المعرفة على النحو التالي:

$$

$$E [X]: = \ int_ {s \ in S} p (s) X (s)$$

قارن الآن تعاريف PMF و PDF:

$$

$$\ mathbb {PMF} \ rightarrow p_y (t) = Pr \ {Y = t \} \ text {for} t \ in T$$

$$

$$\ mathbb {PDF} \ rightarrow Pr \ {a \ leq X \ leq b \} = \ int_a ^ bp (r) dr$$

في حالة الاحتمال المستمر ، يُطلق على المتغيرات العشوائية اسم النقاط العشوائية . لأنه إذا $$$S$ هو الفضاء الاحتمال ، و $$$Y: S \ rightarrow T$ عرض في مساحة مختلفة من $$$\ mathbb {R}$ ثم يجب أن ندعو $$$Y$ نقطة عشوائية ، وليس متغير عشوائي. مفهوم كثافة الاحتمال ينطبق هنا ، لأننا نستطيع أن نقول ذلك لأي $$$U \ subset T$ لدينا:


الآن دعونا نطبق ما تعلمناه على المجال. يحتوي المجال على ثلاثة إحداثيات: خطوط الطول والعرض ومكمل خطوط العرض. نحن نستخدم إضافة خطوط الطول والعرض فقط في $$$\ mathbb {R} ^ 2$ ، الإحداثيات الديكارتية ثنائية الأبعاد المطبقة على متغير عشوائي $$$S$ حولها الى $$$S ^ 2$ . نحصل على التفاصيل التالية:

$$

$$Y: [0، 1] \ times [0، 1] \ rightarrow S ^ 2: (u، v) \ rightarrow (\ cos (2 \ pi u) \ sin (\ pi v)، \ cos (\ pi v) \ sin (2 \ pi u) sin (\ pi v))$$

نبدأ بكثافة احتمال موحدة $$$ع$ في $$$[0، 1] \ times [0، 1]$ أو $$$p (u، v) = 1$ . انظر إلى صيغة كثافة الاحتمال الموحدة أعلاه. للراحة ، سوف نكتب $$$(x، y، z) = Y (u، v)$ .

لدينا فهم بديهي أنك إذا قمت بتحديد نقاط بالتساوي والعشوائي في مربع وحدة واستخدامها $$$و$ لتحويلها إلى نقاط على كرة وحدة ، سوف تتراكم بجوار القطب. هذا يعني أن كثافة الاحتمال التي تم الحصول عليها في $$$T$ لن تكون موحدة. هذا مبين في الشكل أدناه.


سنناقش الآن طرق تقريب القيمة المتوقعة لمتغير عشوائي مستمر وتطبيقه لتحديد التكاملات. هذا مهم لأنه في التقديم نحتاج إلى تحديد قيمة تكامل الانعكاس :

$$

$$L ^ {ref} (P، \ omega_o) = \ int _ {\ omega_i \ in S _ {+} ^ {2}} L (P، - \ omega_i) f_s (P، \ omega_i، \ omega_0) \ omega_i. \ boldsymbol {n} d \ omega_i،$$

لمختلف القيم $$$P$ و $$$\ omega_0$ . قيمة $$$\ أوميغا$ هو اتجاه ضوء الحادث. رمز توليد رقم عشوائي موزعة بشكل موحد في الفاصل الزمني $$$[0، 1]$ وأخذ الجذر التربيعي ، ينشئ قيمة في النطاق من 0 إلى 1. إذا استخدمنا PDF لذلك ، لأن هذه قيمة موحدة ، فإن القيمة المتوقعة ستكون متساوية $$$\ frac {2} {3}$ . أيضا هذه القيمة هي القيمة المتوسطة $$$f (x) = \ sqrt {x}$ في هذا الفاصل الزمني. ماذا يعني هذا؟

النظر في نظرية 3.48 من كتاب رسومات الحاسوب: المبادئ والممارسة. هي تقول إن $$$f: [a، b] \ rightarrow \ mathbb {R}$ هي وظيفة مع القيم الحقيقية ، و $$$X \ sim \ boldsymbol {U} (a، b)$ هو متغير عشوائي موحد في الفاصل $$$[a، b]$ ثم $$$(b-a) f (x)$ متغير عشوائي له القيمة المتوقعة:

$$

$$E [(b-a) f (x)] = \ int_a ^ b f (x) dx.$$

ماذا يقول لنا هذا؟ هذا يعني أنه يمكنك استخدام خوارزمية عشوائية لحساب قيمة التكامل إذا قمنا بتنفيذ الكود عدة مرات ومتوسط ​​النتائج .

في الحالة العامة ، نحصل على قيمة معينة $$$C$ ، كما هو الحال في التكامل الموضح أعلاه ، والذي يحتاج إلى تحديد ، وبعض الخوارزمية العشوائية التي تُرجع قيمة تقريبية $$$C$ . هذا المتغير العشوائي لكمية ما يسمى مقدّر . يعتبر المُقدر خاليًا من التشويه إذا كانت قيمته المتوقعة $$$C$ . في الحالة العامة ، يفضل المقيمون الذين لا يشوهون التشوهات.

لقد ناقشنا بالفعل احتمالات منفصلة ومستمرة. ولكن هناك نوع ثالث ، يسمى الاحتمالات المختلطة ويستخدم في التقديم. تنشأ هذه الاحتمالات بسبب النبضات في وظائف التوزيع الخاصة بالانتثار ثنائي الاتجاه ، أو النبضات الناتجة عن مصادر الإضاءة النقطية. يتم تعريف هذه الاحتمالات في مجموعة مستمرة ، على سبيل المثال ، في الفاصل الزمني $$$[0، 1]$ لكن غير محدد بدقة بواسطة وظيفة PDF. النظر في البرنامج التالي:

 if uniform(0, 1) > 0.6 : return 0.3 else : return uniform(0, 1) 

في ستين بالمائة من الحالات ، سيعود البرنامج 0.3 ، وفي الـ 40٪ المتبقية ، سيعيد قيمة موزعة بالتساوي $$$[0، 1]$ . قيمة الإرجاع هي متغير عشوائي مع كتلة احتمال 0.6 عند 0.3 ، ويتم تحديد PDF في جميع النقاط الأخرى على النحو $$$d (x) = 0.4 دولا$ . يجب أن نحدد ملف PDF على النحو التالي:


بشكل عام ، المتغير العشوائي المتغير المختلط هو الذي توجد له مجموعة محددة من النقاط في منطقة تعريف PDF ، والعكس بالعكس ، نقاط موزعة بشكل موحد حيث لم يتم تعريف PMF.