Prophet inequality
ऑनलाइन एल्गोरिदम और इष्टतम रोक के सिद्धांत में, एक भविष्यवक्ता असमानता एक निर्णय लेने की प्रक्रिया के अपेक्षित मूल्य पर एक बंधन है जो ज्ञात संभाव्यता वितरण से यादृच्छिक निवेश के एक अनुक्रम को संभालती है, जो एक "भविष्यवक्ता" द्वारा प्राप्त किए जा सकने वाले अपेक्षित मूल्य के सापेक्ष है जो सभी निवेश (और न केवल उनके वितरण) को समय से पहले जानता है। एल्गोरिदमिक मैकेनिज्म डिजाइन और गणितीय वित्त के सिद्धांत में इन असमानताओं के अनुप्रयोग हैं। एकल वस्तु शास्त्रीय एकल-वस्तु भविष्यवक्ता असमानता को डी. जे. एच. (बेन) गार्लिंग द्वारा प्रकाशित किया गया था, जिसके तंग रूप का श्रेय डी. जे. एच. (बेन) गार्लिंग को जाता है। यह एक ऐसी प्रक्रिया से संबंधित है जिसमें यादृच्छिक चरों का एक क्रम ज्ञात वितरणों से आता है। जब प्रत्येक आता है, निर्णय लेने की प्रक्रिया को यह तय करना चाहिए कि क्या इसे स्वीकार करना है और प्रक्रिया को रोकना है, या क्या इसे अस्वीकार करना है और अनुक्रम में अगले चर पर जाना है। प्रक्रिया का मूल्य एकल स्वीकृत चर है, यदि एक है, या अन्यथा शून्य है। यह माना जा सकता है कि सभी चर गैर-नकारात्मक हैं; अन्यथा, शून्य से नकारात्मक मूल्यों को बदलने से परिणाम नहीं बदलता है। उदाहरण के लिए, यह वित्तीय स्थितियों का मॉडल हो सकता है जिसमें चर एक निश्चित मूल्य पर कुछ अविभाज्य वस्तु खरीदने के लिए प्रस्ताव करते हैं, और विक्रेता को यह तय करना होगा कि कौन सा (यदि कोई हो) प्रस्ताव स्वीकार करना है। एक पैगंबर, चरों के पूरे अनुक्रम को जानते हुए, स्पष्ट रूप से उनमें से सबसे बड़े का चयन कर सकता है, इस प्रक्रिया के किसी भी विशिष्ट उदाहरण के लिए मूल्य प्राप्त कर सकता है, और अपेक्षित मूल्य पैगंबर असमानता इस प्रक्रिया के लिए एक ऑनलाइन एल्गोरिथ्म के अस्तित्व को बताती है जिसका अपेक्षित मूल्य पैगंबर का कम से कम आधा हैः कोई भी एल्गोरिथ्म सभी वितरणों के लिए अधिक अपेक्षित मूल्य प्राप्त नहीं कर सकता है। प्रत्येक चर पर कम से कम संभाव्यता के साथ सीमा एल्गोरिथ्म द्वारा विचार किया जाएगा और यदि यह माना जाता है कि यह अधिकता में योगदान देगा, तो अपेक्षा की रैखिकता से अपेक्षित अधिकता कम से कम वितरण के मध्य में सेट हो रही है ताकि और इस सीमा में अपेक्षित अधिकता को जोड़कर, और शब्दों को एक दूसरे को रद्द करने का कारण बने, यह दर्शाता है कि सीमा एल्गोरिथ्म की इस सेटिंग के लिए कम से कम एक अलग सीमा का अपेक्षित मूल्य प्राप्त होता है, कम से कम इसी अपेक्षित मूल्य को भी प्राप्त करता है। सामान्यीकरण अन्य ऑनलाइन परिदृश्यों के लिए एकल-वस्तु भविष्यवक्ता असमानता के विभिन्न सामान्यीकरण ज्ञात हैं, और इन्हें भविष्यवक्ता असमानता भी कहा जाता है। प्रतिस्पर्धी विश्लेषण से तुलना पैगंबर असमानताएँ ऑनलाइन एल्गोरिदम के प्रतिस्पर्धी विश्लेषण से संबंधित हैं, लेकिन दो तरीकों से भिन्न हैं। सबसे पहले, अधिकांश प्रतिस्पर्धी विश्लेषण सबसे खराब स्थिति के निवेश को मानता है, जिसे गणना किए गए मूल्य और इष्टतम मूल्य के बीच के अनुपात को अधिकतम करने के लिए चुना जाता है जो भविष्य के ज्ञान के साथ प्राप्त किया जा सकता था, जबकि भविष्यवक्ता असमानताओं के लिए इनपुट, इसके वितरण के बारे में कुछ ज्ञान माना जाता है। और दूसरा, एक निश्चित प्रतिस्पर्धी अनुपात प्राप्त करने के लिए, एक ऑनलाइन एल्गोरिथ्म को सभी निवेशों पर इष्टतम प्रदर्शन के उस अनुपात के भीतर प्रदर्शन करना चाहिए। इसके बजाय, एक भविष्यवक्ता असमानता केवल अपेक्षा में प्रदर्शन को सीमित करती है, जिससे कुछ इनपुट अनुक्रम खराब प्रदर्शन का उत्पादन करने की अनुमति देते हैं जब तक कि औसत अच्छा है। संदर्भ बाहरी लिंक मैट्रायड पैगंबर असमानता और तंत्र डिजाइन, द मैट्रायड यूनियन पैगंबर असमानताओं का एक आर्थिक दृष्टिकोण ऑनलाइन एल्गोरिदम अनुक्रमिक प्रयोग तंत्र डिजाइन