طريقة الاحتمالات الشرطية

تعتمد العديد من البراهين الاحتمالية على النحو التالي: فهي تُعرّف ضمنيًا متغيرًا عشوائيًا Q ، وتُبيّن أن (أ) القيمة المتوقعة لـ Q لا تتجاوز (أو لا تقل) عن قيمة عتبة معينة، و(ب) في أي نتيجة تكون فيها Q لا تتجاوز (أو لا تقل) عن هذه العتبة، تكون النتيجة ناجحة. ثم يُشير (أ) إلى وجود نتيجة تكون فيها Q لا تتجاوز (أو لا تقل) عن العتبة، وهذا و(ب) يُشيران إلى وجود نتيجة ناجحة. (في المثال أعلاه، Q هو عدد مرات ظهور الذيل، والذي يجب أن يكون على الأقل العتبة 1.5. في العديد من التطبيقات، Q هو عدد الأحداث "السيئة" (ليست بالضرورة منفصلة) التي تحدث في نتيجة معينة، حيث يُقابل كل حدث سيئ طريقة واحدة لفشل التجربة، ويكون العدد المتوقع للأحداث السيئة التي تحدث أقل من 1).

في هذه الحالة، وللحفاظ على احتمال الفشل الشرطي أقل من 1، يكفي الحفاظ على القيمة المتوقعة الشرطية لـ Q أقل (أو أعلى) من العتبة. ولتحقيق ذلك، بدلاً من حساب احتمال الفشل الشرطي، تحسب الخوارزمية القيمة المتوقعة الشرطية لـ Q وتتابع وفقًا لذلك: عند كل عقدة داخلية، يوجد فرع تكون قيمته المتوقعة الشرطية على الأكثر (أو على الأقل) من القيمة المتوقعة الشرطية للعقدة؛ تنتقل الخوارزمية من العقدة الحالية إلى هذا الفرع، وبالتالي تحافظ على القيمة المتوقعة الشرطية أقل (أو أعلى) من العتبة.

في بعض الحالات، يُستخدم حدٌّ دقيقٌ مناسبٌ يُسمى المُقدِّر التشاؤمي ، كبديلٍ عن القيمة المتوقعة الشرطية الدقيقة للكمية Q. المُقدِّر التشاؤمي هو دالةٌ للحالة الراهنة، ويجب أن يكون حدًّا أعلى (أو أدنى) للقيمة المتوقعة الشرطية لـ Q بالنظر إلى الحالة الراهنة، كما يجب أن يكون غير متزايد (أو غير متناقص) في قيمته المتوقعة مع كل خطوة عشوائية من التجربة. عادةً، يُمكن حساب مُقدِّر تشاؤمي جيد من خلال تحليل منطق البرهان الأصلي بدقة.

بالنظر إلى أي رسم بياني غير موجه G = ( V , E )، فإن مسألة القطع الأقصى هي تلوين كل رأس من رؤوس الرسم البياني بأحد لونين (مثلاً الأسود أو الأبيض) بحيث يتم تعظيم عدد الحواف التي تكون نهاياتها بألوان مختلفة. (لنفترض أن هذه الحافة مقطوعة ).

معضلة القطع الأقصى: في أي رسم بياني G = ( V , E )، يمكن قطع ما لا يقل عن | E |/2 من الحواف.

برهان احتمالي. لوّن كل رأس بالأسود أو الأبيض برمي قطعة نقدية متوازنة. بالحساب، لأي ضلع e في E ، احتمال قطعه هو 1/2. بالتالي، بحسب خطية التوقع ، فإن العدد المتوقع للأضلاع المقطوعة هو | E |/2. إذن، يوجد تلوين يقطع على الأقل | E |/2 ضلعًا. وهو المطلوب إثباته.

لتطبيق طريقة الاحتمالات الشرطية، نبدأ بنمذجة التجربة العشوائية كسلسلة من الخطوات العشوائية الصغيرة. في هذه الحالة، من الطبيعي اعتبار كل خطوة بمثابة اختيار لون لرأس معين (وبالتالي يوجد | V | خطوة).

بعد ذلك، استبدل الاختيار العشوائي في كل خطوة باختيار حتمي، وذلك للحفاظ على الاحتمالية الشرطية للفشل، بالنظر إلى الرؤوس الملونة حتى الآن، أقل من 1. (هنا يعني الفشل أنه في النهاية يتم قطع أقل من | E |/2 من الحواف.)

في هذه الحالة، يصعب حساب الاحتمال الشرطي للفشل. في الواقع، لم يحسب البرهان الأصلي احتمال الفشل مباشرةً؛ بل اعتمد على إثبات أن العدد المتوقع للحواف المقطوعة لا يقل عن | E |/2.

لنفترض أن المتغير العشوائي Q هو عدد الحواف المقطوعة. للحفاظ على احتمال الفشل الشرطي أقل من 1، يكفي أن يكون التوقع الشرطي لـ Q مساويًا أو أعلى من العتبة | E |/2. وذلك لأنه طالما أن التوقع الشرطي لـ Q يساوي على الأقل | E |/2، فلا بد من وجود نتيجة قابلة للتحقيق حيث يكون Q على الأقل | E |/2، وبالتالي فإن احتمال الوصول إلى مثل هذه النتيجة موجب. وللحفاظ على التوقع الشرطي لـ Q عند | E |/2 أو أعلى، ستقوم الخوارزمية، في كل خطوة، بتلوين الرأس قيد الدراسة لتعظيم التوقع الشرطي الناتج لـ Q. وهذا يكفي، لأنه لا بد من وجود ابن يكون توقعه الشرطي على الأقل مساويًا للتوقع الشرطي للحالة الحالية (وبالتالي على الأقل | E |/2).

بافتراض أن بعض الرؤوس ملونة بالفعل، فما هو التوقع الشرطي؟ باتباع منطق البرهان الأصلي، فإن التوقع الشرطي لعدد الحواف المقطوعة هو

عدد الحواف التي تم تلوين نقاط نهايتها بألوان مختلفة حتى الآن

+ (1/2)*( عدد الحواف التي تحتوي على نقطة نهاية واحدة على الأقل لم يتم تلوينها بعد ).

تُلوّن الخوارزمية كل رأس لزيادة قيمة التوقع الشرطي المذكور أعلاه إلى أقصى حد. وهذا يضمن بقاء التوقع الشرطي عند | E |/2 أو أعلى، وبالتالي يضمن بقاء احتمال الفشل الشرطي أقل من 1، مما يضمن بدوره نتيجة ناجحة. وبحساب بسيط، تُبسط الخوارزمية إلى ما يلي:

1. لكل رأس u في V (بأي ترتيب): 2. ضع في اعتبارك الرؤوس المجاورة الملونة بالفعل لـ u . 3. من بين هذه الرؤوس، إذا كان عدد الرؤوس السوداء أكثر من عدد الرؤوس البيضاء، فقم بتلوين u باللون الأبيض. 4. وإلا، فاللون الأسود هو اللون المناسب.

بفضل اشتقاقها، تضمن هذه الخوارزمية الحتمية قطع نصف حواف الرسم البياني المعطى على الأقل. وهذا يجعلها خوارزمية تقريبية بنسبة 0.5 لمسألة القطع الأقصى .

إحدى طرق صياغة نظرية توران هي التالية:

أي رسم بياني G = ( V , E ) يحتوي على مجموعة مستقلة بحجم لا يقل عن | V |/( D +1 )، حيث D = 2| E |/| V | هو متوسط ​​درجة الرسم البياني.

لنفترض العملية العشوائية التالية لإنشاء مجموعة مستقلة S :

1. قم بتهيئة S لتكون المجموعة الفارغة . 2. لكل رأس u في V بترتيب عشوائي: 3. إذا لم يكن هناك جيران لـ u في S ، فأضف u إلى S. 4. أعد S.

من الواضح أن العملية تحسب مجموعة مستقلة. أي رأس u يُؤخذ في الاعتبار قبل جميع جيرانه سيُضاف إلى S. وبالتالي، إذا رمزنا لدرجة u بـ d ( u ) ، فإن احتمال إضافة u إلى S هو على الأقل 1/( d ( u )+1). وبحسب خاصية الخطية للتوقع ، فإن الحجم المتوقع لـ S هو على الأقل

${\displaystyle \sum _{u\in V}{\frac {1}{d(u)+1}}~\geq ~{\frac {|V|}{D+1}}.}$

(تنتج المتباينة أعلاه لأن 1/( x + 1) دالة محدبة في x ، لذا فإن الطرف الأيسر يكون في أدنى قيمة له، بشرط أن يكون مجموع الدرجات ثابتًا عند 2| E | ، عندما يكون كل d ( u ) = D = 2| E |/| V |.)

في هذه الحالة، تتكون العملية العشوائية من | V | خطوة. في كل خطوة، تُؤخذ في الاعتبار رأس u لم يُؤخذ في الاعتبار بعد، ويُضاف u إلى S إذا لم يُضَف أي من جيرانه بعد. لنفترض أن المتغير العشوائي Q هو عدد الرؤوس المُضافة إلى S. يُبين البرهان أن E [ Q ] ≥ | V |/( D +1).

سنستبدل كل خطوة عشوائية بخطوة حتمية تحافظ على القيمة المتوقعة الشرطية لـ Q عند أو أعلى من | V |/( D +1). سيضمن هذا نتيجة ناجحة، أي نتيجة يكون فيها حجم المجموعة المستقلة S على الأقل | V |/( D +1)، محققًا بذلك الحد المنصوص عليه في نظرية توران.

بافتراض إتمام الخطوات t الأولى، لنرمز بـ S ^{( t )} إلى الرؤوس المضافة حتى الآن. ولنرمز بـ R ^{( t )} إلى الرؤوس التي لم تُضَف بعد، والتي ليس لها جيران في S ^{( t )} . وبالنظر إلى الخطوات t الأولى، ووفقًا للمنطق الوارد في البرهان الأصلي، فإن أي رأس w في R ^{( t ) لديه احتمال شرطي لا يقل عن 1/(} d ( w )+1) للإضافة إلى S ، وبالتالي فإن القيمة المتوقعة الشرطية لـ Q هي على الأقل 1/( d ( w)+1).

${\displaystyle |S^{(t)}|~+~\sum _{w\in R^{(t)}}{\frac {1}{d(w)+1}}.}$

لنفترض أن Q ^{( t )} تشير إلى الكمية المذكورة أعلاه، والتي تسمى مقدرًا متشائمًا للتوقع الشرطي.

أظهر البرهان أن المُقدِّر المتشائم يكون مبدئيًا على الأقل | V |/( D +1). (أي أن Q ⁽⁰⁾ ≥ | V |/( D +1)). ستتخذ الخوارزمية كل خيار للحفاظ على المُقدِّر المتشائم من التناقص، أي بحيث يكون Q ^{( t +1)} ≥ Q ^{( t )} لكل قيمة من قيم t . وبما أن المُقدِّر المتشائم هو حد أدنى للتوقع الشرطي، فإن هذا سيضمن بقاء التوقع الشرطي أعلى من | V |/( D +1)، مما يضمن بدوره بقاء الاحتمال الشرطي للفشل أقل من 1.

ليكن u هو الرأس الذي تعتبره الخوارزمية في الخطوة التالية (( t +1)-st).

إذا كان للعنصر u جارٌ في المجموعة S ، فلن يُضاف u إلى S، وبالتالي (بفحص Q ^{( t )} ) يبقى المُقدِّر المتشائم دون تغيير. أما إذا لم يكن للعنصر u جارٌ في المجموعة S ، فسيُضاف u إلى S.

بحسب الحساب، إذا تم اختيار u عشوائيًا من الرؤوس المتبقية، فإن الزيادة المتوقعة في المُقدِّر المتشائم غير سالبة. [ الحساب: بافتراض اختيار رأس في R ^{( t )} ، فإن احتمال حذف حد معين 1/( d ( w )+1) من مجموع المُقدِّر المتشائم هو على الأكثر ( d ( w )+1)/| R ^{( t )} |، وبالتالي فإن الانخفاض المتوقع في كل حد من حدود المجموع هو على الأكثر 1/| R ^{( t )} |. يوجد R ^{( t )} حدًا في المجموع. لذا، فإن الانخفاض المتوقع في المجموع هو على الأكثر 1. في الوقت نفسه، يزداد حجم S بمقدار 1.]

وبالتالي، يجب أن يكون هناك خيار ما لـ u يمنع المقدر المتشائم من التناقص.

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

فيما يلي، يشير N ^{( t )} ( u ) إلى جيران u في R ^{( t )} (أي جيران u الذين ليسوا في S ولا يوجد لهم جار في S ).

1. قم بتهيئة S لتكون المجموعة الفارغة. 2. طالما يوجد رأس u لم يتم أخذه في الاعتبار بعد وليس له جار في S : 3. أضف رأسًا u إلى S حيث u يُقلل من قيمة${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}}$. 4. إرجاع S.

لكي تنجح طريقة الاحتمالات الشرطية، يكفي أن تحافظ الخوارزمية على قيمة المُقدِّر المتشائم ثابتةً (أو ثابتةً، حسب الاقتضاء). ليس من الضروري أن تُعظِّم الخوارزمية (أو تُصغِّرها). هذا يُتيح بعض المرونة في اشتقاق الخوارزمية. تُوضِّح الخوارزميتان التاليتان هذا الأمر.

1. قم بتهيئة S لتكون المجموعة الفارغة. 2. طالما يوجد رأس u في الرسم البياني ليس له جار في S : 3. أضف رأسًا كهذا u إلى S ، حيث يقلل u من d ( u ) (الدرجة الأولية لـ u ). 4. إرجاع S.

1. قم بتهيئة S لتكون المجموعة الفارغة. 2. بينما الرسم البياني المتبقي ليس فارغًا: 3. أضف رأسًا u إلى S ، حيث يكون لـ u أقل درجة في الرسم البياني المتبقي . 4. احذف u وجميع جيرانها من الرسم البياني.5. إرجاع S.

يتم تحليل كل خوارزمية باستخدام نفس المُقدِّر التشاؤمي كما في السابق. مع كل خطوة من خطوات أي من الخوارزميتين، تكون الزيادة الصافية في المُقدِّر التشاؤمي هي

${\displaystyle 1-\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}},}$

حيث يشير N ^{( t )} ( u ) إلى جيران u في الرسم البياني المتبقي (أي في R ^{( t )} ).

بالنسبة للخوارزمية الأولى، تكون الزيادة الصافية غير سالبة لأنه، باختيار u ،

${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d(u)+1){\frac {1}{d(u)+1}}=1}$،

حيث d ( u ) هي درجة u في الرسم البياني الأصلي.

أما بالنسبة للخوارزمية الثانية، فإن الزيادة الصافية غير سالبة لأنه، باختيار u ،

${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d'(u)+1){\frac {1}{d'(u)+1}}=1}$،

حيث d′ ( u ) هي درجة u في الرسم البياني المتبقي.