خوارزمية الاحتمالات

الموسوعة الحرة

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

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

أمثلة

يوضح موقفان مختلفان الاهتمام بتعظيم احتمالية التوقف عند حدث محدد أخير.

  1. لنفترض أن سيارة معروضة للبيع لأعلى مزايد (أفضل "عرض").ن{\displaystyle n}يستجيب المشترون المحتملون ويطلبون معاينة السيارة. ويصر كل منهم على قرار فوري من البائع بقبول العرض أو رفضه. يُعرَّف العرض بأنه "مثير للاهتمام" ، ويُرمز له بالرقم 1 إذا كان أفضل من جميع العروض السابقة، وبالرقم 0 فيما عدا ذلك. ستشكل العروض سلسلة عشوائية من الأصفار والآحاد. العروض التي تحمل الرقم 1 فقط هي التي تهم البائع، الذي قد يخشى أن يكون كل عرض 1 لاحق هو الأخير. وبناءً على التعريف، فإن آخر عرض 1 هو أعلى عرض. وبالتالي، فإن تعظيم احتمالية البيع بناءً على آخر عرض 1 يعني تعظيم احتمالية البيع بأفضل سعر .
  2. قد يستخدم الطبيب، عند تطبيق علاج خاص، الرمز 1 للدلالة على نجاح العلاج، والرمز 0 في حال عدم نجاحه. يعالج الطبيب سلسلة من الحالات التالية:ن{\displaystyle n}يُعامل المرضى بنفس الطريقة، ويرغب في تقليل أي معاناة، ومعالجة كل مريض يستجيب للعلاج في التسلسل. إن التوقف عند الرقم 1 الأخير في مثل هذا التسلسل العشوائي من الأصفار والآحاد من شأنه أن يحقق هذا الهدف. وبما أن الطبيب ليس نبيًا، فإن الهدف هو زيادة احتمالية التوقف عند الرقم 1 الأخير إلى أقصى حد. (انظر الاستخدام الرحيم ).

التعريفات

لنفترض سلسلة منن{\displaystyle n}أحداث مستقلة . اربط بهذه السلسلة سلسلة أخرى من الأحداث المستقلةأنا1،أنا2،...،أنان{\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}} بقيم 1 أو 0. هنا أناك=1{\displaystyle \,I_{k}=1}ويُطلق على هذا النجاح اسم الحدث الذي تكون فيه الملاحظة رقم k مثيرة للاهتمام (كما يحددها صانع القرار)، وأناك=0{\displaystyle \,I_{k}=0}لغير المهم. هذه المتغيرات العشوائيةأنا1،أنا2،...،أنان{\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}تتم ملاحظتها بالتتابع، والهدف هو اختيار النجاح الأخير بشكل صحيح عند ملاحظته.

يتركصك=P(أناك=1){\displaystyle \,p_{k}=P(\,I_{k}\,=1)}ليكن احتمال أن يكون الحدث رقم k مثيرًا للاهتمام. وليكن كذلك qك=1-صك{\displaystyle \,q_{k}=\,1-p_{k}}ورك=صك/qك{\displaystyle \,r_{k}=p_{k}/q_{k}}. لاحظ أنرك{\displaystyle \,r_{k}}يمثل احتمالات أن يكون الحدث رقم k مثيرًا للاهتمام، وهو ما يفسر اسم خوارزمية الاحتمالات.

إجراء خوارزمي

تقوم خوارزمية الاحتمالات بجمع الاحتمالات بترتيب عكسي

رن+رن-1+رن-2+⋯،{\displaystyle r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,}

إلى أن يصل هذا المجموع إلى القيمة 1 أو يتجاوزها لأول مرة. إذا حدث هذا عند الفهرس s ، فإنه يحفظ s والمجموع المقابل.

Rs=رن+رن-1+رن-2+⋯+رs.{\displaystyle R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}.\,}

إذا لم يصل مجموع الاحتمالات إلى 1، فإنه يُعيّن قيمة s  =  1. وفي الوقت نفسه، يحسب

سؤالs=qنqن-1⋯qs.{\displaystyle Q_{s}=q_{n}q_{n-1}\cdots q_{s}.\,}

الناتج هو

  1. s{\displaystyle \,s}عتبة التوقف
  2. w=سؤالsRs{\displaystyle \,w=Q_{s}R_{s}}، احتمالية الفوز.

استراتيجية الاحتمالات

استراتيجية الاحتمالات هي قاعدة لمراقبة الأحداث واحداً تلو الآخر والتوقف عند أول حدث مثير للاهتمام من الفهرس s فصاعداً (إن وجد)، حيث s هو عتبة التوقف للمخرج a.

تكمن أهمية استراتيجية الاحتمالات، وبالتالي خوارزمية الاحتمالات، في نظرية الاحتمالات التالية.

نظرية الاحتمالات

تنص نظرية الاحتمالات على أن

  1. استراتيجية الاحتمالات هي الأمثل ، أي أنها تزيد من احتمالية التوقف عند الرقم 1 الأخير.
  2. احتمالية الفوز لاستراتيجية الاحتمالات تساوي w=سؤالsRs{\displaystyle w=Q_{s}R_{s}}
  3. لوRs≥1{\displaystyle R_{s}\geq 1}احتمالية الفوزw{\displaystyle w}دائماً ما يكون على الأقل 1/ e = 0.367879... ، وهذا الحد الأدنى هو الأفضل الممكن .

سمات

تحسب خوارزمية الاحتمالات الاستراتيجية المثلى واحتمالية الفوز المثلى في آنٍ واحد. كما أن عدد عملياتها يتناسب خطيًا أو شبه خطي مع n. لذا، لا يمكن أن توجد خوارزمية أسرع منها لجميع التسلسلات، مما يجعل خوارزمية الاحتمالات، في الوقت نفسه، خوارزمية مثالية.

مصادر

ابتكر بروس عام 2000 خوارزمية الاحتمالات، ومن هنا جاء اسمها. تُعرف أيضاً باسم خوارزمية بروس (الاستراتيجية). يمكن العثور على تطبيقات مجانية لها على الإنترنت.

التطبيقات

ثلاث حالات لمشكلة السكرتيرة مع ارتفاع الأيقونة الذي يدل على مدى الاستحسان:
  1. مجموعة الاستكشاف الصغيرة جدًا تختار مرشحًا دون المستوى الأمثل قبل رؤية الأفضل (*).
  2. تحدد المجموعة المثالية الأفضل.
  3. إذا كانت المجموعة كبيرة جدًا وتضمنت أفضل المرشحين، فسيتم اختيار المرشح الأخير.

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

يوجد، بنفس المبدأ، نظرية الاحتمالات لعمليات الوصول المستمرة ذات الزيادات المستقلة ، مثل عملية بواسون ( بروس، 2000 ). في بعض الحالات، لا تكون الاحتمالات معروفة مسبقًا بالضرورة (كما في المثال 2 أعلاه)، مما يجعل تطبيق خوارزمية الاحتمالات غير ممكن بشكل مباشر. في هذه الحالة، يمكن لكل خطوة استخدام تقديرات متسلسلة للاحتمالات. وهذا مفيد إذا لم يكن عدد المعلمات المجهولة كبيرًا مقارنةً بعدد الملاحظات (n). ومع ذلك، تصبح مسألة الأمثلية أكثر تعقيدًا، وتتطلب دراسات إضافية. تسمح تعميمات خوارزمية الاحتمالات بمكافآت مختلفة لعدم التوقف والتوقفات الخاطئة، بالإضافة إلى استبدال افتراضات الاستقلال بافتراضات أضعف ( فيرغسون، 2008 ) .

الاختلافات

ناقش بروس وبيندافين (2000) مشكلة اختيار الأخيرك{\displaystyle k}نجاحات.

أثبت تاماكي في عام 2010 نظرية الاحتمالات المضاعفة التي تتناول مشكلة التوقف عند أي من الاحتمالات الأخيرةℓ{\displaystyle \ell }النجاحات. تم الحصول على حد أدنى دقيق لاحتمالية الفوز بواسطة ماتسوي وأنو 2014 .

ناقش ماتسوي وأنو (2017) مشكلة الاختيارك{\displaystyle k}من بين آخرℓ{\displaystyle \ell }وقد حققنا نجاحات وحصلنا على حد أدنى دقيق لاحتمالية الفوز. عندما ℓ=ك=1،{\displaystyle \ell =k=1,}تُعادل هذه المسألة مسألة احتمالات بروس. إذا ℓ=ك≥1،{\displaystyle \ell =k\geq 1,}تُعادل هذه المشكلة تلك الواردة في بحث بروس وبيندافين عام 2000. ويمكن الحصول على مشكلة أخرى ناقشها تاماكي عام 2010 عن طريق وضعℓ≥ك=1.{\displaystyle \ell \geq k=1.}

مسألة الاختيار من متعدد

يُسمح للاعبر{\displaystyle r}أمامه خيارات، ويفوز إذا كان أي خيار هو النجاح الأخير. بالنسبة لمشكلة السكرتيرة الكلاسيكية، ناقش جيلبرت وموستيلر (1966) الحالاتر=2،3،4{\displaystyle r=2,3,4}مشكلة الاحتمالات معر=2،3{\displaystyle r=2,3}تمت مناقشة هذا الموضوع من قبل أنو، كاكينوما وميوشي 2010. لمزيد من الحالات المتعلقة بمشكلة الاحتمالات، انظر ماتسوي وأنو 2016 .

تُعتبر الاستراتيجية المثلى لهذه المشكلة من ضمن فئة الاستراتيجيات المحددة بمجموعة من الأرقام الحدية.(أ1،أ2،...،أر){\displaystyle (a_{1},a_{2},...,a_{r})}، أينأ1>أ2>⋯>أر{\displaystyle a_{1}>a_{2}>\cdots >a_{r}}.

على وجه التحديد، تخيل أن لديكر{\displaystyle r}خطابات قبول تحمل علامة من1{\displaystyle 1}لر{\displaystyle r}كان لديكر{\displaystyle r}موظفو استقبال الطلبات، يحمل كل منهم رسالة واحدة. تستمر في مقابلة المرشحين وترتيبهم على مخطط يمكن لكل موظف استقبال رؤيته. الآن أيها الموظفأنا{\displaystyle i}سيرسلون خطاب قبولهم إلى أول مرشح أفضل من جميع المرشحين.1{\displaystyle 1}لأأنا{\displaystyle a_{i}}(يتم إرسال خطابات القبول غير المرسلة بشكل افتراضي إلى آخر المتقدمين، كما هو الحال في مشكلة السكرتير القياسية.)

متىر=2{\displaystyle r=2}أظهرت دراسة أنو، كاكينوما، وميوشي عام 2010 أن الحد الأدنى الضيق لاحتمالية الفوز يساويهـ-1+هـ-32.{\displaystyle e^{-1}+e^{-{\frac {3}{2}}}.} بالنسبة للأعداد الصحيحة الموجبة العامةر{\displaystyle r}، أثبت ماتسوي وأنو 2016 أن الحد الأدنى الضيق لاحتمالية الفوز هو احتمالية الفوز في متغير مشكلة السكرتير حيث يجب على المرء اختيار أفضل k مرشح باستخدام k محاولة فقط .

متىر=3،4،5{\displaystyle r=3,4,5}، الحدود الدنيا الضيقة لاحتمالات الفوز تساويهـ-1+هـ-32+هـ-4724{\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}}،هـ-1+هـ-32+هـ-4724+هـ-27611152{\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}}و هـ-1+هـ-32+هـ-4724+هـ-27611152+هـ-41626371474560،{\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}},}على التوالى.

للاطلاع على المزيد من الحالات العددية لـر=6،...،10{\displaystyle r=6,...,10}وخوارزمية للحالات العامة، انظر Matsui & Ano 2016 .

انظر أيضاً

مراجع