فجوة الارتباط

في البرمجة العشوائية ، فجوة الارتباط هي نسبة أسوأ حالة بين التكلفة عندما تكون المتغيرات العشوائية مرتبطة بالتكلفة عندما تكون المتغيرات العشوائية مستقلة . ^{[ 1 ]}

كمثال، ^{[ 1 ]}^{: 6} لننظر في مسألة التحسين التالية. يريد معلم معرفة ما إذا كان سيحضر إلى الفصل أم لا. يوجد n طالبًا محتملاً. لكل طالب، هناك احتمال بنسبة 1/ n لحضوره الفصل. إذا حضر طالب واحد على الأقل، فيجب على المعلم الحضور وتكون تكلفته 1. إذا لم يحضر أي طالب، فيمكن للمعلم البقاء في المنزل وتكون تكلفته 0. هدف المعلم هو تقليل تكلفته. هذه مسألة برمجة عشوائية، لأن القيود غير معروفة مسبقًا - فقط احتمالاتها معروفة. الآن، هناك حالتان فيما يتعلق بالارتباط بين الطلاب:

الحالة رقم 1: الطلاب غير مترابطين: يقرر كل طالب ما إذا كان سيحضر إلى الفصل أم لا عن طريق رمي عملة معدنية باحتمالية $1/n$ بشكل مستقل عن الآخرين. التكلفة المتوقعة في هذه الحالة هي $1-(1-1/n)^{n}\approx 1-1/e$ .
الحالة الثانية: الطلاب مرتبطون: يتم اختيار طالب واحد عشوائيًا ويحضر إلى الفصل، بينما يبقى الآخرون في المنزل. لاحظ أن احتمال حضور كل طالب لا يزال $1/n$ لكن التكلفة الآن هي 1.

فجوة الارتباط هي التكلفة في الحالة رقم 2 مقسومة على التكلفة في الحالة رقم 1، وهي $e/(e-1)$ .

^{[ 1 ]} أثبت أن فجوة الارتباط محدودة في عدة حالات. على سبيل المثال، عندما تكون دالة التكلفةدالة مجموعة شبه معيارية(كما في المثال أعلاه)، فإن فجوة الارتباط تكون على الأكثر $e/(e-1)$ (لذا فإن المثال أعلاه يمثل أسوأ حالة).

يُشير الحد الأعلى لفجوة الارتباط إلى حد أعلى للخسارة الناتجة عن تجاهل الارتباط. على سبيل المثال، لنفترض أن لدينا مسألة برمجة عشوائية ذات دالة تكلفة شبه معيارية. نحن نعرف الاحتمالات الحدية للمتغيرات، لكننا لا نعرف ما إذا كانت مرتبطة أم لا. إذا تجاهلنا الارتباط وحلّينا المسألة كما لو كانت المتغيرات مستقلة، فإن الحل الناتج هو $(e-1)/e$ -تقريب للحل الأمثل.

التطبيقات

تم استخدام فجوة الارتباط لتقييد خسارة الإيرادات عند استخدام التسعير الأمثل وفقًا لنظرية بايز بدلاً من المزاد الأمثل وفقًا لنظرية بايز . ^{[ 2 ]}

انظر أيضاً

مراجع

1 2 3 أغراوال، شيبرا؛ دينغ، ييتشوان؛ صابري، أمين؛ يي، يينيو (2010). "التحسين العشوائي القوي ضد الارتباط". وقائع الندوة السنوية الحادية والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة . ص 1087. arXiv : 0902.1792 . doi : 10.1137/1.9781611973075.88 . ISBN 978-0-89871-701-3.
↑ يان، تشيتشي (2011). "تصميم الآليات عبر فجوة الارتباط". وقائع الندوة السنوية الثانية والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة . ص 710. arXiv : 1008.1843 . doi : 10.1137/1.9781611973082.56 . ISBN 978-0-89871-993-2.

[adsy10-1] 1 2 3 أغراوال، شيبرا؛ دينغ، ييتشوان؛ صابري، أمين؛ يي، يينيو (2010). "التحسين العشوائي القوي ضد الارتباط". وقائع الندوة السنوية الحادية والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة . ص 1087. arXiv : 0902.1792 . doi : 10.1137/1.9781611973075.88 . ISBN 978-0-89871-701-3.

[y10-2] يان، تشيتشي (2011). "تصميم الآليات عبر فجوة الارتباط". وقائع الندوة السنوية الثانية والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة . ص 710. arXiv : 1008.1843 . doi : 10.1137/1.9781611973082.56 . ISBN 978-0-89871-993-2.

[ 1 ]

[ 2 ]