ऑड्स एल्गोरिथम

निर्णय सिद्धांत में, ऑड्स एल्गोरिथम (या ब्रस एल्गोरिथम) समस्याओं के एक वर्ग के लिए इष्टतम रणनीतियों की गणना करने के लिए एक गणितीय विधि है जो कि इष्टतम रोक समस्याओं के डोमेन से संबंधित है। उनका समाधान 'ऑड्स स्ट्रैटेजी' से होता है, और ऑड्स स्ट्रैटेजी का महत्व इसकी इष्टतमता में निहित है, जैसा कि नीचे बताया गया है।

बाधाओं एल्गोरिथ्म अंतिम सफलता समस्याओं नामक समस्याओं की एक श्रेणी पर लागू होता है। औपचारिक रूप से, इन समस्याओं का उद्देश्य अनुक्रमिक रूप से देखी गई स्वतंत्र घटनाओं के अनुक्रम में पहचानने की संभावना को अधिकतम करना है, अंतिम घटना एक विशिष्ट मानदंड (एक विशिष्ट घटना) को संतुष्ट करती है। यह पहचान अवलोकन के समय की जानी चाहिए। पूर्ववर्ती टिप्पणियों के पुनरीक्षण की अनुमति नहीं है। आम तौर पर, एक विशिष्ट घटना को निर्णय निर्माता द्वारा एक ऐसी घटना के रूप में परिभाषित किया जाता है जो एक अच्छी तरह से परिभाषित कार्रवाई करने के लिए रुकने की दृष्टि से वास्तविक रुचि है। इस तरह की समस्याएं कई स्थितियों में सामने आती हैं।

उदाहरण

दो अलग-अलग स्थितियां अंतिम विशिष्ट घटना पर रुकने की संभावना को अधिकतम करने में रुचि का उदाहरण देती हैं।

1. मान लीजिए कि एक कार को उच्चतम बोली लगाने वाले (सर्वश्रेष्ठ प्रस्ताव) को बिक्री के लिए विज्ञापित किया गया है। n संभावित खरीदारों को जवाब देने दें और कार देखने के लिए कहें। प्रत्येक बोली को स्वीकार करने या न करने के लिए विक्रेता से तत्काल निर्णय लेने पर जोर देता है। एक बोली को दिलचस्प के रूप में परिभाषित करें, और 1 को कोडित करें यदि यह पिछली सभी बोलियों से बेहतर है, और 0 को कोडित किया गया है। बोलियां 0s और 1s का एक यादृच्छिक क्रम बनाएंगी। केवल 1 ही विक्रेता को रूचि देता है, जिसे डर हो सकता है कि प्रत्येक क्रमिक 1 अंतिम हो सकता है। यह परिभाषा से अनुसरण करता है कि अंतिम 1 उच्चतम बोली है। अंतिम 1 पर बेचने की संभावना को अधिकतम करने का अर्थ है सर्वोत्तम बिक्री की संभावना को अधिकतम करना।
2. एक चिकित्सक, एक विशेष उपचार का उपयोग करते हुए, एक सफल उपचार के लिए कोड 1 का उपयोग कर सकता है, अन्यथा 0। चिकित्सक उसी तरह n रोगियों के अनुक्रम का इलाज करता है, और किसी भी पीड़ा को कम करना चाहता है, और क्रम में प्रत्येक उत्तरदायी रोगी का इलाज करना चाहता है। 0 और 1 के ऐसे यादृच्छिक क्रम में अंतिम 1 पर रुकने से यह उद्देश्य प्राप्त होगा। चूंकि चिकित्सक कोई पैगंबर नहीं है, इसका उद्देश्य अंतिम 1 पर रुकने की संभावना को अधिकतम करना है। (दयालु उपयोग देखें।)

परिभाषाएँ

के क्रम पर विचार करें $n$ स्वतंत्र घटनाएँ। इस क्रम के साथ स्वतंत्र घटनाओं का एक और क्रम जोड़ें $I_{1},\,I_{2},\,\dots ,\,I_{n}$ मान 1 या 0 के साथ। यहाँ $\,I_{k}=1$, सफलता कहा जाता है, के लिए खड़ा है घटना कि kth अवलोकन दिलचस्प है (जैसा कि निर्णय निर्माता द्वारा परिभाषित किया गया है), और $\,I_{k}=0$ गैर दिलचस्प के लिए। ये यादृच्छिक चर $I_{1},\,I_{2},\,\dots ,\,I_{n}$ क्रमिक रूप से देखे जाते हैं और लक्ष्य अंतिम सफलता का सही ढंग से चयन करना है जब इसे देखा जाता है।

होने देना $\,p_{k}=P(\,I_{k}\,=1)$ संभावना है कि k वीं घटना दिलचस्प है। आगे चलो $\,q_{k}=\,1-p_{k}$ और $\,r_{k}=p_{k}/q_{k}$. ध्यान दें कि $\,r_{k}$ कठिनाइयाँ एल्गोरिथम के नाम की व्याख्या करते हुए, दिलचस्प होने वाली kth घटना के ऑड्स का प्रतिनिधित्व करता है।

एल्गोरिथम प्रक्रिया

ऑड्स एल्गोरिथम विपरीत क्रम में ऑड्स को सारांशित करता है

$r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,$

जब तक कि यह राशि पहली बार 1 के मान तक न पहुँच जाए या उससे अधिक न हो जाए। यदि यह इंडेक्स s पर होता है, तो यह s और संबंधित योग को बचाता है

$R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}.\,$

यदि ऑड्स का योग 1 तक नहीं पहुंचता है, तो यह s = 1 सेट करता है। साथ ही यह गणना करता है

$Q_{s}=q_{n}q_{n-1}\cdots q_{s}.\,$

आउटपुट है

1. $\,s$, रोक दहलीज
2. $\,w=Q_{s}R_{s}$, जीत की संभावना।

बाधाओं की रणनीति

बाधाओं की रणनीति एक के बाद एक घटनाओं का निरीक्षण करने और इंडेक्स एस के आगे (यदि कोई हो) से पहली दिलचस्प घटना पर रुकने का नियम है, जहां एस आउटपुट ए की रोक सीमा है।

ऑड्स रणनीति का महत्व, और इसलिए ऑड्स एल्गोरिथम, निम्नलिखित ऑड्स प्रमेय में निहित है।

विषम प्रमेय

विषम प्रमेय कहता है कि

1. बाधाओं की रणनीति इष्टतम है, अर्थात यह अंतिम 1 पर रुकने की संभावना को अधिकतम करती है।
2. ऑड्स रणनीति की जीत की संभावना बराबर है $w=Q_{s}R_{s}$
3. अगर $R_{s}\geq 1$, जीत की संभावना $w$ कम से कम हमेशा होता है 1/e = 0.367879..., और यह निचली सीमा सर्वोत्तम संभव है।

विशेषताएं

बाधाओं एल्गोरिथ्म एक ही समय में इष्टतम रणनीति और इष्टतम जीत की संभावना की गणना करता है। साथ ही, ऑड्स एल्गोरिथम के संचालन की संख्या n में (उप) रैखिक है। इसलिए कोई तेज एल्गोरिदम संभवतः नहीं हो सकता सभी अनुक्रमों के लिए मौजूद हैं, ताकि ऑड्स एल्गोरिथम एक ही समय में एक एल्गोरिथम के रूप में इष्टतम हो।

स्रोत

Bruss 2000 ने ऑड्स एल्गोरिथम तैयार किया, और उसका नाम गढ़ा। इसे ब्रस एल्गोरिथम (रणनीति) के रूप में भी जाना जाता है। नि:शुल्क क्रियान्वयन वेब पर पाया जा सकता है।

अनुप्रयोग

बिक्री समस्याओं, सचिव समस्याओं, पोर्टफोलियो (वित्त) चयन, (एक तरफ़ा) खोज रणनीतियों, प्रक्षेपवक्र समस्याओं और ऑनलाइन रखरखाव और अन्य में समस्याओं के लिए पार्किंग समस्या पर नैदानिक ​​​​परीक्षणों में चिकित्सा प्रश्नों से आवेदन पहुँचते हैं।

उसी भावना में मौजूद है, स्वतंत्र वृद्धि के साथ निरंतर-समय आगमन प्रक्रियाओं के लिए एक ऑड्स प्रमेय जैसे कि पॉइसन प्रक्रिया (Bruss 2000). कुछ मामलों में, ऑड्स आवश्यक रूप से पहले से ज्ञात नहीं हैं (जैसा कि ऊपर उदाहरण 2 में है) ताकि ऑड्स एल्गोरिथम का अनुप्रयोग सीधे संभव न हो। इस मामले में प्रत्येक चरण बाधाओं के अनुक्रमिक अनुमानों का उपयोग कर सकता है। यह अर्थपूर्ण है, यदि अवलोकनों की संख्या n की तुलना में अज्ञात मापदंडों की संख्या बड़ी नहीं है। इष्टतमता का प्रश्न तब अधिक जटिल है, हालांकि, और अतिरिक्त अध्ययन की आवश्यकता है। ऑड्स एल्गोरिथम का सामान्यीकरण रोकने में विफल रहने के लिए अलग-अलग पुरस्कारों की अनुमति देता है और गलत स्टॉप के साथ-साथ कमजोर लोगों द्वारा आजादी की धारणाओं को बदलना (फर्ग्यूसन (2008))।

विविधताएं

Bruss & Paindaveine 2000 अंतिम को चुनने की समस्या पर चर्चा की $k$ सफलताओं।

Tamaki 2010 गुणनात्मक ऑड्स प्रमेय साबित हुआ जो किसी भी अंतिम पर रुकने की समस्या से संबंधित है $\ell$ सफलताओं।

जीत की संभावना की एक तंग निचली सीमा द्वारा प्राप्त की जाती है Matsui & Ano 2014.

Matsui & Ano 2017 चयन की समस्या पर चर्चा की $k$ पिछले से बाहर $\ell$ सफलताओं और जीत की संभावना की एक तंग निचली सीमा प्राप्त की। कब $\ell =k=1,$ समस्या ब्रस की बाधाओं की समस्या के बराबर है। अगर $\ell =k\geq 1,$ समस्या इसके बराबर है Bruss & Paindaveine 2000. द्वारा चर्चा की गई समस्या Tamaki 2010 लगाने से प्राप्त होता है $\ell \geq k=1.$

बहुविकल्पी समस्या

एक खिलाड़ी की अनुमति है $r$ विकल्प, और वह जीतता है यदि कोई विकल्प अंतिम सफलता है। शास्त्रीय सचिव समस्या के लिए, Gilbert & Mosteller 1966 मामलों पर चर्चा की $r=2,3,4$. बाधाओं के साथ समस्या $r=2,3$ द्वारा चर्चा की जाती है Ano, Kakinuma & Miyoshi 2010. बाधाओं की समस्या के और मामलों के लिए देखें Matsui & Ano 2016.

एक इष्टतम रणनीति थ्रेसहोल्ड संख्याओं के सेट द्वारा परिभाषित रणनीतियों की श्रेणी से संबंधित है $(a_{1},a_{2},...,a_{r})$, कहाँ $a_{1}<a_{2}<\cdots <a_{r}$. पहली पसंद के साथ शुरू होने वाले पहले उम्मीदवारों पर इस्तेमाल किया जाना है $a_{1}$वें आवेदक, और एक बार पहली पसंद का उपयोग करने के बाद, दूसरी पसंद का उपयोग पहले उम्मीदवार पर किया जाना है $a_{2}$वें आवेदक, और इसी तरह।

कब $r=2$, Ano, Kakinuma & Miyoshi 2010 ने दिखाया कि जीत की संभावना की तंग निचली सीमा बराबर है $e^{-1}+e^{-{\frac {3}{2}}}.$ सामान्य सकारात्मक पूर्णांक के लिए $r$, Matsui & Ano 2016 जीत की संभावना की तंग निचली सीमा पर चर्चा की। कब $r=3,4,5$, जीत की संभावनाओं की तंग निचली सीमाएं बराबर हैं $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}$, $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}$ और $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}},$ क्रमश। आगे के मामलों के लिए कि $r=6,...,10$, देखना Matsui & Ano 2016.

यह भी देखें

• कठिनाइयाँ
• नैदानिक ​​परीक्षण
• विस्तारित पहुंच
• सचिव समस्या

संदर्भ

• Ano, K.; Kakinuma, H.; Miyoshi, N. (2010). "Odds theorem with multiple selection chances". Journal of Applied Probability. 47 (4): 1093–1104. doi:10.1239/jap/1294170522. S2CID 17598431.
• Bruss, F. Thomas (2000). "Sum the odds to one and stop". The Annals of Probability. Institute of Mathematical Statistics. 28 (3): 1384–1391. doi:10.1214/aop/1019160340. ISSN 0091-1798.
• —: "A note on Bounds for the Odds Theorem of Optimal Stopping", Annals of Probability Vol. 31, 1859–1862, (2003).
• —: "The art of a right decision", Newsletter of the European Mathematical Society, Issue 62, 14–20, (2005).
• T. S. Ferguson: (2008, unpublished)
• Bruss, F. T.; Paindaveine, D. (2000). "Selecting a sequence of last successes in independent trials" (PDF). Journal of Applied Probability. 37 (2): 389–399. doi:10.1239/jap/1014842544.
• Gilbert, J; Mosteller, F (1966). "Recognizing the Maximum of a Sequence". Journal of the American Statistical Association. 61 (313): 35–73. doi:10.2307/2283044. JSTOR 2283044.
• Matsui, T; Ano, K (2014). "A note on a lower bound for the multiplicative odds theorem of optimal stopping". Journal of Applied Probability. 51 (3): 885–889. doi:10.1239/jap/1409932681.
• Matsui, T; Ano, K (2016). "Lower bounds for Bruss' odds problem with multiple stoppings". Mathematics of Operations Research. 41 (2): 700–714. arXiv:1204.5537. doi:10.1287/moor.2015.0748. S2CID 31778896.
• Matsui, T; Ano, K (2017). "Compare the ratio of symmetric polynomials of odds to one and stop". Journal of Applied Probability. 54: 12–22. doi:10.1017/jpr.2016.83. S2CID 41639968.
• Shoo-Ren Hsiao and Jiing-Ru. Yang: "Selecting the Last Success in Markov-Dependent Trials", Journal of Applied Probability, Vol. 93, 271–281, (2002).
• Tamaki, M (2010). "Sum the multiplicative odds to one and stop". Journal of Applied Probability. 47 (3): 761–777. doi:10.1239/jap/1285335408. S2CID 32236265.
• Mitsushi Tamaki: "Optimal Stopping on Trajectories and the Ballot Problem", Journal of Applied Probability Vol. 38, 946–959 (2001).
• E. Thomas, E. Levrat, B. Iung: "L'algorithme de Bruss comme contribution à une maintenance préventive", Sciences et Technologies de l'automation, Vol. 4, 13-18 (2007).

बाहरी संबंध

• Bruss Algorithmus http://www.p-roesler.de/odds.html