सचिव समस्या: Difference between revisions

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

प्रारूप को इस प्रकार परिभाषित किया गया है कि एक आवेदक को कुछ समय अंतराल पर चुना जाना चाहिए <math>[0,T]</math> किसी अनजान नंबर से <math> N</math> पद करने योग्य आवेदकों का लक्ष्य इस परिकल्पना के तहत केवल सर्वश्रेष्ठ का चयन करने की संभावना को अधिकतम करना है किसी विभिन्न पदों के सभी आगमन आदेशित समान रूप से होने की संभावना है मान लीजिए कि सभी आवेदकों का आगमन समय घनत्व समान है लेकिन एक-दूसरे से स्वतंत्र है <math>f</math> पर <math>[0,T]</math> और जाने  <math>F</math> इसी आगमन समय वितरण कार्यक्रम को निरूपित करें अर्थात्

<math>\tau</math> ऐसा हो कि <math> F(\tau)=1/e.</math> सभी आवेदक समय-समय पर प्रतीक्षा करने और निरीक्षण करने की रणनीति पर विचार करें <math>\tau </math> यदि संभव हो तो समय के बाद पहले उम्मीदवार का चयन करना <math>\tau </math> जो पिछले सभी से बेहतर है फिर इस रणनीति को जिसे 1/ई-रणनीति कहा जाता है इसमें निम्नलिखित गुण हैं

:(i) सभी के लिए पैदावार <math>N</math> कम से कम 1/e की सफलता की संभावना।

: (ii) चयनकर्ता के लिए एक न्यूनतम-इष्टतम रणनीति है जो <math>N</math>को नहीं जानता है।

:(iii) चयन करता है यदि कम से कम एक आवेदक हो जो 1/e संभावना के साथ कोई न हो।

एफ. थॉमस ब्रस द्वारा 1984 में सिद्ध किया गया पहला/ई-कानून एक आश्चर्य के रूप में सामने आया कारण यह था कि अज्ञात के लिए एक प्रारूप में पहुंच से बाहर होने से पहले लगभग 1/e के मान पर विचार किया गया था <math> N </math> जबकि यह मान 1/e अब सफलता की संभावना के लिए एक निचली सीमा के रूप में प्राप्त किया गया था और यह यकीनन बहुत कमजोर परिकल्पनाओं वाले प्रारूप में है उदाहरण के लिए समीक्षाएं 85: मिनट

जबकि कई अन्य रणनीतियाँ हैं जो (i) और (ii) प्राप्त करती हैं और इसके अलावा 1/ई-रणनीति की तुलना में सख्ती से बेहतर प्रदर्शन करती हैं एक साथ सभी के लिए <math>N</math>> 2। एक सरल उदाहरण वह रणनीति है जो समय के बाद या पहले अपेक्षाकृत सर्वश्रेष्ठ उम्मीद का चयन करती है यदि संभव हो जबकि <math>\tau </math> कम से कम एक आवेदक इस समय से पहले पहुंचे और समय के बाद दूसरे अपेक्षाकृत सर्वश्रेष्ठ उम्मीदवार का चयन करें {{sfn|Gnedin|2021}}

संख्या 1/ई की समान भूमिका के कारण 1/ई-कानून कभी-कभी ऊपर वर्णित शास्त्रीय सचिव समस्या के समाधान के साथ भ्रमित हो जाता है जबकि 1/ई-कानून में यह भूमिका अधिक सामान्य है परिणाम भी मजबूत है क्योंकि यह अज्ञात संख्या में आवेदकों के लिए है और चूंकि आगमन समय वितरण एफ पर आधारित प्रारूप अनुप्रयोगों के लिए अधिक हैं।

थॉमस एस. फर्ग्यूसन के अनुसार सचिव समस्या पहली बार छपाई में दिखाई दी जब इसे [[मार्टिन गार्डनर]] ने अपने फरवरी 1960 में [[ अमेरिकी वैज्ञानिक ]]में [[गणितीय खेल स्तंभ]] में चित्रित किया {{r|TomFer89}} यहां बताया गया है कि गार्डनर ने इसे कैसे तैयार किया किसी को कागज की जितनी चाहें उतनी पर्चियां लेने के लिए कहें और प्रत्येक पर्ची पर एक अलग सकारात्मक संख्या लिखें संख्याएँ 1 के छोटे अंशों से लेकर एक गोगोल के आकार की संख्या 1 के बाद सौ शून्य या इससे भी बड़ी हो सकती हैं इन पर्चियों को उल्टा कर दिया जाता है और एक मेज के ऊपर से फेर दिया जाता है एक समय में आप फिसलकर उल्टा कर देते हैं लक्ष्य यह है कि जब आप उस संख्या तक पहुंचें जिसे आप श्रृंखला में सबसे बड़ा मानते हैं तो मुड़ना बंद कर दें आप वापस नहीं जा सकते हैं और पहले से मुड़ी हुई पर्ची नहीं उठा सकते हैं यदि आप सभी पर्चियों को पलट देते हैं तो निश्चित रूप से आपको अंतिम मुड़ी हुई पर्चियों को चुनना चाहिए।{{sfn|Gardner|1966}}

लेख में सचिव समस्या का समाधान किसने किया फर्ग्यूसन ने बताया कि सचिव की समस्या अनसुलझी रही जैसा कि एम. गार्डनर ने कहा था जो दो विरोधी खिलाड़ियों के साथ दो-व्यक्ति शून्य-राशि के खेल के रूप में है {{r|TomFer89}} इस खेल में ऐलिस, सूचित खिलाड़ी, गुप्त रूप से अलग-अलग नंबर लिखता है <math>n</math> पत्ते बॉब, रोकने वाला खिलाड़ी, वास्तविक मूल्यों को देखता है और जब भी वह चाहता है तो कार्ड को बदलना बंद कर सकता है अगर आखिरी कार्ड बदल गया तो जीतना कुल अधिकतम संख्या है बुनियादी सचिव की समस्या से अंतर यह है कि बॉब कार्डों पर लिखे वास्तविक मूल्यों का अवलोकन करता है जिसका उपयोग वह अपनी निर्णय प्रक्रियाओं में कर सकता है सचिव समस्या के कुछ संस्करणों में कार्ड पर संख्या आवेदकों के संख्यात्मक गुणों के अनुरूप होती है संख्याओं का [[संयुक्त संभाव्यता वितरण]] ऐलिस के नियंत्रण में है।

बॉब उच्चतम संभव संभावना के साथ अधिकतम संख्या का अनुमान लगाना चाहता है जबकि ऐलिस का लक्ष्य इस संभावना को यथासंभव कम रखना है ऐलिस के लिए कुछ निश्चित वितरण से स्वतंत्र रूप से संख्याओं का नमूना लेना इष्टतम नहीं है और वह कुछ आश्रित तरीके से यादृच्छिक संख्याओं को चुनकर बेहतर खेल सकती है के लिए <math>n=2</math> ऐलिस की कोई न्यूनतम रणनीति नहीं है जो थॉमस एम. कवर टी के विरोधाभास से निकटता से संबंधित है  <math>n>2</math> खेल में एक समाधान है ऐलिस यादृच्छिक संख्या जो आश्रित यादृच्छिक चर हैं यह इस तरह से चुन सकता है कि बॉब सापेक्ष पदों के आधार पर शास्त्रीय रोक रणनीति का उपयोग करने से बेहतर नहीं खेल सकता।{{sfn|Gnedin|1994}}

{{harvnb|Stein|Seale|Rapoport|2003}} ने कई मनोवैज्ञानिक रूप से प्रशंसनीय अनुमानों के लिए अपेक्षित सफलता की संभावनाएँ प्राप्त कीं जिन्हें सचिव समस्या में नियोजित किया जा सकता है उन्होंने ह्यूरिस्टिक्स की जांच की थी

* कटऑफ नियम पहले y आवेदकों में से किसी को भी स्वीकार न करें इसके बाद पहले सामना करने वाले उम्मीदवार यानी सापेक्ष पद 1 वाला आवेदक का चयन करें इस नियम में एक विशेष स्थान के रूप में शास्त्रीय सचिव समस्या के लिए इष्टतम नीति है जिसके लिए y = r

*उम्मीदवार गणना नियम सीसीआर वाई-वें सामना करने वाले उम्मीदवार का चयन करें ध्यान दें कि यह नियम आवश्यक रूप से किसी भी आवेदक को छोड़ नहीं देता है यह केवल इस बात पर विचार करता है कि कितने उम्मीदवारों का अवलोकन किया गया है यह नहीं कि आवेदक अनुक्रम में निर्णय निर्माता कितना गहरा है।

* लगातार गैर-उम्मीदवार नियम एसएनसीआर वाई गैर-उम्मीदवारों यानी संबंधित पद वाले आवेदक > 1 का अवलोकन करने के बाद सबसे पहले सामना करने वाले उम्मीदवार का चयन करें ।

अनुमानी का एक एकल पैरामीटर y होता है आंकड़ा दाईं ओर दिखाया गया है n = 80 के साथ समस्याओं के लिए y के एक समारोह के रूप में प्रत्येक अनुमानी के लिए अपेक्षित सफलता की संभावनाएं प्रदर्शित करता है।

एकल सर्वश्रेष्ठ आवेदक ढूँढना एक सख्त उद्देश्य की तरह लग सकता है कोई कल्पना कर सकता है कि साक्षात्कारकर्ता एक कम-मूल्यवान आवेदक की तुलना में एक उच्च-मूल्यवान आवेदक को नियुक्त करेगा और न केवल सर्वश्रेष्ठ प्राप्त करने के लिए चिंतित होगा अर्थात् साक्षात्कारकर्ता एक आवेदक का चयन करने से कुछ मूल्य प्राप्त करेगा जो आवश्यक रूप से सर्वोत्तम नहीं है और व्युत्पन्न मूल्य चयनित के मूल्य के साथ बढ़ता है।

इस समस्या का प्रारूप बनाने के लिए मान लीजिए कि <math>n</math> आवेदकों के पास वास्तविक मूल्य हैं जो यादृच्छिक चर एक्स तैयार हैं 0, 1 पर एक [[समान वितरण (निरंतर)|समान वितरण निरंतर]] ऊपर वर्णित शास्त्रीय समस्या के समान साक्षात्कारकर्ता केवल यह देखता है कि क्या प्रत्येक आवेदक अब तक का सबसे अच्छा है एक उम्मीदवार प्रत्येक को मौके पर ही स्वीकार या अस्वीकार कर देना चाहिए और यदि वह पहुंच जाता है तो अंतिम को स्वीकार करना चाहिए साक्षात्कारकर्ता प्रत्येक आवेदक की वास्तविक सापेक्ष पद नहीं सीखता है वह केवल यह सीखता है कि आवेदक की सापेक्ष पद 1 है या नहीं जबकि इस संस्करण में भुगतान चयनित आवेदक के सही मूल्य द्वारा दिया गया है उदाहरण के लिए यदि वह एक आवेदक का चयन करता है जिसका सही मूल्य 0.8 है, तो वह 0.8 कमाएगा साक्षात्कारकर्ता का उद्देश्य चयनित आवेदक के [[अपेक्षित मूल्य]] को अधिकतम करना है।

चूंकि आवेदक के मान 0, 1 पर एक समान वितरण से प्राप्त करता है दिए गए tवें आवेदक का अपेक्षित मूल्य <math>x_{t}=\max\left\{x_1, x_2, \ldots, x_t\right\}</math> द्वारा दिया गया है

शास्त्रीय समस्या के रूप में इष्टतम नीति एक दहलीज द्वारा दी गई है जिसे इस समस्या के लिए हम निरूपित करेंगे <math>c</math>, जिस पर साक्षात्कारकर्ता को उम्मीदवारों को स्वीकार करना शुरू कर देना चाहिए बेयरडेन ने दिखाया कि सी या तो है <math>\lfloor \sqrt n \rfloor</math> या <math>\lceil \sqrt n \rceil</math>.{{sfn|Bearden|2006}} वास्तव में जो भी सबसे करीब है <math> \sqrt n </math>। यह इस तथ्य से अनुसरण करता है कि एक समस्या दी गई है <math>n</math> आवेदकों को कुछ मनमाने ढंग से सीमा के लिए अपेक्षित अदायगी <math>1 \le c \le n</math> प्ादानन करता है