डार्ट्स, पासा और सिक्के: असतत वितरण एल्गोरिदम

मैंने एक बार स्टैक ओवरफ्लो को पासा धोखा देने के लिए डेटा संरचना के बारे में एक सवाल पूछा था। विशेष रूप से, मुझे इस प्रश्न के उत्तर में दिलचस्पी थी: "अगर हमारे पास एक एन-फेस की हड्डी है, तो चेहरे का मैं बाहर गिरने की संभावना है _i । ऐसी हड्डी के रोल के अनुकरण के लिए सबसे प्रभावी डेटा संरचना क्या है? "

इस डेटा संरचना का उपयोग कई कार्यों के लिए किया जा सकता है। उदाहरण के लिए, आप इसका उपयोग कर सकते हैं ईमानदार हेक्स रोल अनुकरण करने के लिए, संभावना को निर्दिष्ट करते हुए $$$\ frac {1} {6}$ हड्डी के प्रत्येक पक्ष, या एक द्विपक्षीय सिक्के की नकल करके एक उचित सिक्के का अनुकरण करने के लिए, प्रत्येक पक्ष के बाहर गिरने की संभावना जिसके बराबर है $$$\ frac {1} {2}$ । आप 11-पक्षीय हड्डी (चेहरे 2, 3, 4, ..., 12) के साथ दो ईमानदार हेक्स हड्डियों के योग को सीधे अनुकरण करने के लिए इस डेटा संरचना का उपयोग कर सकते हैं, जिनमें से प्रत्येक चेहरे का दो ईमानदार हड्डियों के रोल के अनुरूप संभावना वजन है। हालांकि, आप इस डेटा संरचना का उपयोग धोखा देने वाली हड्डियों को अनुकरण करने के लिए भी कर सकते हैं। उदाहरण के लिए, यदि आप एक हड्डी के साथ क्रेप्स खेलते हैं, जो, जैसा कि आप जानते हैं, पूरी तरह से ईमानदार नहीं है, तो आप इस डेटा संरचना का उपयोग बहुत सारे हड्डी रोल को अनुकरण करने और इष्टतम रणनीति का विश्लेषण करने के लिए कर सकते हैं। आप एक समान अपूर्ण रूलेट व्हील को अनुकरण करने का भी प्रयास कर सकते हैं।

यदि आप खेलों से परे जाते हैं, तो आप इस डेटा संरचना को उन रोबोटों के अनुकरण में लागू कर सकते हैं जिनके सेंसर विफलता स्तर जानते हैं। उदाहरण के लिए, यदि किसी रेंज सेंसर में सही मान लौटाने की 95% संभावना है, तो 4% की संभावना बहुत कम है, और 1% की संभावना बहुत बड़े मान की है, तो आप इस डेटा संरचना का उपयोग एक यादृच्छिक परिणाम उत्पन्न करके रीडिंग सेंसर रीडिंग का अनुकरण करने और सेंसर रीडिंग का अनुकरण करने के लिए कर सकते हैं। परिणाम है।

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

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

प्रविष्टि

विभिन्न तकनीकों के विशिष्ट विवरण पर आगे बढ़ने से पहले, आइए पहले शब्दावली और अंकन का मानकीकरण करें।

लेख के परिचय में, मैंने एक सामान्यीकृत परिदृश्य का वर्णन करने के लिए "धोखा देने वाली हड्डी" शब्द का इस्तेमाल किया, जिसमें परिणामों का एक निश्चित सेट होता है, जिनमें से प्रत्येक में एक संभावना होती है। औपचारिक रूप से, इसे असतत संभावना वितरण कहा जाता है, और एक धोखा देने वाली हड्डी के अनुकरण के कार्य को एक असतत वितरण से नमूनाकरण कहा जाता है।

हमारे असतत संभावना वितरण (चीटर बोन) का वर्णन करने के लिए, हम मानेंगे कि हमारे पास n संभावनाओं का एक समूह है $$$p_0, p_1, ..., p_ {n - 1}$ परिणामों से संबंधित $$$0, 1, ..., एन - 1$ । यद्यपि परिणाम किसी भी हो सकते हैं (ईगल / पूंछ, हड्डियों, रंगों आदि पर संख्या), सादगी के लिए मैं परिणाम को किसी दिए गए सूचकांक के अनुरूप सकारात्मक वास्तविक संख्या के रूप में मानूंगा।

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

इसके बाद, मैं मान लूंगा कि निम्नलिखित सभी कार्य निरंतर समय में किए जा सकते हैं:

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

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

ईमानदार हड्डी सिमुलेशन

इससे पहले कि हम एक मनमाने ढंग से धोखा देने वाली हड्डी को फेंकने के अधिक सामान्य मामले में आगे बढ़ें, चलो एक सरल एल्गोरिथ्म के साथ शुरू करते हैं जो निम्नलिखित एल्गोरिदम के लिए बिल्डिंग ब्लॉक के रूप में काम करेगा: एक ईमानदार एन-फेस बोन का अनुकरण करना। उदाहरण के लिए, एकाधिकार या जोखिम खेलते समय ईमानदार हेक्सागोनल पासा रोल, या एक ईमानदार सिक्का (दो तरफा पासा), आदि हमारे लिए उपयोगी हो सकते हैं।

इस विशेष मामले के लिए, परिणाम का अनुकरण करने के लिए एक सरल, सुरुचिपूर्ण और प्रभावी एल्गोरिथ्म है। एल्गोरिथ्म निम्नलिखित विचार पर आधारित है: मान लें कि हम अंतराल में वास्तव में यादृच्छिक, समान रूप से वितरित वास्तविक संख्या उत्पन्न कर सकते हैं $$$[0, 1)$ । इस अंतराल को निम्नानुसार चित्रित किया जा सकता है:


अब अगर हम पद छोड़ना चाहते हैं $$$एन$ हड्डी की हड्डी, फिर एक तरीका है अंतराल को विभाजित करना $$$[0, 1)$ पर $$$एन$ समान आकार के क्षेत्र, जिनमें से प्रत्येक की लंबाई है $$$\ frac {1} {n}$ । यह इस तरह दिखता है:


इसके बाद, हम अंतराल में एक बेतरतीब ढंग से चुनी गई वास्तविक संख्या उत्पन्न करते हैं $$$[0, 1)$ यह निश्चित रूप से इन छोटे क्षेत्रों में से एक में आता है। इससे हम हड्डी के रोल के परिणाम की गणना उस क्षेत्र को देखकर कर सकते हैं जिसमें संख्या गिर गई। उदाहरण के लिए, यदि हमारा बेतरतीब ढंग से चयनित मूल्य इस जगह गिर गया:


तब हम कह सकते हैं कि 2 हड्डी पर गिर गया (यदि हम मानते हैं कि हड्डी के किनारों को खरोंच से अनुक्रमित किया गया है)।

यह देखना आसान है कि किस क्षेत्र में यादृच्छिक मूल्य है, लेकिन हम इसे एल्गोरिथ्म में कैसे एन्कोड करते हैं? और यहां हम इस तथ्य का लाभ उठाते हैं कि यह एक ईमानदार हड्डी है। चूंकि सभी अंतराल समान आकार के होते हैं, अर्थात् $$$\ frac {1} {n}$ , तो हम देख सकते हैं कि सबसे बड़ा मूल्य क्या है $$$मैं$ ऐसा है $$$\ frac {i} {n}$ बेतरतीब ढंग से उत्पन्न मूल्य से अधिक नहीं (चलो इस मूल्य को एक्स कहते हैं)। आप देख सकते हैं कि यदि हम अधिकतम मूल्य ज्ञात करना चाहते हैं, तो ऐसा है $$$\ frac {i} {n} \ le x$ , तो यह अधिकतम मूल्य खोजने के समान है $$$एन$ ऐसा है $$$i \ le xn$ । लेकिन परिभाषा से इसका मतलब है कि $$$i = \ lfloor xn \ rfloor$ सबसे बड़ा धनात्मक पूर्णांक xn से अधिक नहीं है। इसलिए, यह हमें इस (बहुत ही सरल) ईमानदार एन-फेस्ड बोन सिमुलेशन एल्गोरिदम की ओर ले जाता है:

एल्गोरिथ्म: ईमानदार हड्डी सिमुलेशन

1. समान रूप से वितरित यादृच्छिक मान उत्पन्न करें $$$x$ सीमा में $$$[0, 1)$ ।
2. वापसी $$$\ lfloor xn \ rfloor$ ।

गणनाओं के बारे में हमारी उपरोक्त धारणाओं को देखते हुए, यह एल्गोरिथ्म समय में चलता है $$$O (1)$ ।

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

ईमानदार हड्डी के साथ अस्थि सिमुलेशन धोखा

एक ईमानदार हड्डी सिमुलेशन एल्गोरिथ्म के साथ, क्या हम इसे धोखा देने वाली हड्डी का अनुकरण करने के लिए अनुकूलित कर सकते हैं? दिलचस्प है, जवाब हाँ है, लेकिन एक समाधान के लिए अधिक स्थान की आवश्यकता होगी।

पिछले अनुभाग से, यह सहज रूप से स्पष्ट है कि एक धोखा देने वाली हड्डी को फेंकने के लिए, अंतराल को विभाजित करना पर्याप्त है $$$[0, 1)$ टुकड़े करने के लिए, और फिर निर्धारित करें कि हम किस हिस्से को मारते हैं। हालांकि, सामान्य मामले में, यह जितना लगता है उससे कहीं अधिक जटिल हो सकता है। मान लीजिए कि हमारे पास चेहरे की संभावनाओं के साथ एक टेट्राहेड्रॉन है $$$\ frac {1} {2}$ । $$$\ frac {1} {3}$ । $$$\ frac {1} {12}$ और $$$\ frac {1} {12}$ (हम यह सुनिश्चित कर सकते हैं कि यह सही संभावना वितरण है, क्योंकि $$$\ frac {1} {2} + \ frac {1} {3} + \ frac {1} {12} + \ frac {1} {12} = \ frac {6} {12} + \ frac {4 } {12} + \ frac {1} {12} + \ frac {1} {12} = \ frac {12} {12}$ )। यदि हम अंतराल को विभाजित करते हैं $$$[0, 1)$ इन आकारों के चार भागों में, फिर हमें निम्नलिखित मिलते हैं:


दुर्भाग्य से, इस कदम पर हम फंस गए हैं। भले ही हमें अंतराल में एक यादृच्छिक संख्या पता हो $$$[0, 1)$ , फिर स्वचालित रूप से यह निर्धारित करने के लिए कोई सरल गणितीय चाल नहीं है कि यह संख्या किस हिस्से में गिरी। मैं यह नहीं कहना चाहता कि यह असंभव है - जैसा कि आप देखेंगे, हम कई बेहतरीन ट्रिक का उपयोग कर सकते हैं - लेकिन उनमें से किसी में भी ईमानदार हड्डी फेंकने की एल्गोरिथम की गणितीय सरलता नहीं है।

हालांकि, हम इस मामले में भी काम करने के लिए ईमानदार हड्डी के लिए इस्तेमाल की जाने वाली तकनीक को अनुकूलित कर सकते हैं। एक उदाहरण के रूप में ऊपर चर्चा की गई हड्डी को लेते हैं। गिरने वाले किनारों की संभावना है $$$\ frac {1} {2}$ । $$$\ frac {1} {3}$ । $$$\ frac {1} {12}$ और $$$\ frac {1} {12}$ । यदि हम इसे फिर से लिखते हैं ताकि सभी सदस्यों में एक सामान्य भाजक हो, तो हमें मूल्य मिलते हैं $$$\ frac {6} {12}$ । $$$\ frac {4} {12}$ । $$$\ frac {1} {12}$ और $$$\ frac {1} {12}$ । इसलिए, हम इस कार्य को निम्नानुसार देख सकते हैं: भारित संभावनाओं के साथ टेट्राहेड्रल हड्डी को फेंकने के बजाय, एक 12-पक्षीय ईमानदार हड्डी क्यों नहीं फेंकें, जिसके किनारों पर डुप्लिकेट मान हैं? चूंकि हम जानते हैं कि कैसे ईमानदार हड्डी का अनुकरण करना है, यह अंतराल पृथक्करण के अनुरूप होगा $$$[0, 1)$ इस तरह से टुकड़े करना:


फिर हम उन्हें निम्न प्रकार से विभिन्न परिणाम प्रदान करते हैं:


अब एक हड्डी फेंक को अनुकरण करना बहुत सरल होगा - हम सिर्फ इस नई ईमानदार हड्डी को फेंक देते हैं, और फिर हम देखते हैं कि कौन सा चेहरा गिर गया है और इसके मूल्य को पढ़ें। यह पहला चरण ऊपर प्रस्तुत एल्गोरिदम द्वारा किया जा सकता है, जो हमें अंतराल में संख्याओं का पूर्णांक देगा $$$0, 1, ..., 11$ । इस पूर्णांक को मूल चीटर बोन के चेहरे में से एक में बाँधने के लिए, हम इन संख्याओं में से प्रत्येक को मूल परिणाम के साथ जोड़ने वाले बारह तत्वों की एक सहायक सरणी को संग्रहीत करेंगे। इसे इस प्रकार चित्रित किया जा सकता है:


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

प्रारंभिक चरण में, हम हड्डी के किनारों के लिए दी गई सभी संभावनाओं में से कम से कम सामान्य एकाधिक की तलाश करके शुरू करते हैं (हमारे उदाहरण में, एलसीएल 12 है)। एनओसी यहां उपयोगी है क्योंकि यह सबसे छोटे सामान्य भाजक से मेल खाती है जिसे हम सभी अंशों के लिए उपयोग कर सकते हैं, और इसलिए नई ईमानदार हड्डी के चेहरे की संख्या जिसे हम रोल करेंगे। इस एनओसी को प्राप्त करने के बाद (हम इसे एल द्वारा निरूपित करते हैं), हमें यह निर्धारित करना चाहिए कि मूल चीटर की हड्डी के प्रत्येक चेहरे पर नई हड्डी के कितने चेहरे वितरित किए जाएंगे। हमारे उदाहरण में, संभावना के साथ चेहरा $$$\ frac {1} {2}$ के बाद से नई हड्डी के छह पक्ष हो जाता है $$$\ frac {1} {2} \ टाइम्स 12 = 6$ । इसी प्रकार, संभाव्यता वाली पार्टी $$$\ frac {1} {3}$ तब से 4 चेहरे मिले $$$\ frac {1} {3} \ गुना 12 = 4$ । अधिक सामान्यीकृत रूप में, यदि L संभावनाओं का LCL है, और $$$p_i$ एक चेहरे की संभावना है $$$मैं$ हड्डियों, तो हम चेहरे को उजागर करते हैं $$$मैं$ मूल तेज हड्डी $$$L \ cdot p_i$ ईमानदार हड्डी के पहलू।

यहाँ उपरोक्त एल्गोरिदम का छद्म कोड है:

एल्गोरिथम: ईमानदार हड्डी के साथ धोखा देने वाली हड्डी का अनुकरण

• आरंभ :
  
  1. संभावना के हर के एनओसी का पता लगाएं $$$p_0, p_1, ..., p_ {n-1}$ ; इसे निरूपित करें $$$एल$
  2. एक सरणी का चयन करें $$$ए$ आकार $$$एल$ मूल हड्डी के रोल के साथ ईमानदार हड्डी रोल के परिणामों की तुलना करने के लिए।
  3. हर चेहरे के लिए $$$मैं$ प्रारंभिक हड्डी से, हम किसी भी क्रम में निम्नलिखित कार्य करते हैं:
     
     1. हम निम्नानुसार असाइन करते हैं $$$L \ cdot p_i$ आइटम $$$ए$ अर्थ $$$मैं$ ।
• जनरेशन :
  
  1. हम के लिए एक ईमानदार हड्डी फेंक उत्पन्न करते हैं $$$एल$ -फेस बोन; चेहरे को बुलाओ $$$एस$ ।
  2. वापसी $$$ए [एस]$ ।

यह एल्गोरिथ्म सरल हो सकता है, लेकिन यह कितना कुशल है? हड्डी रोल की पीढ़ी काफी तेज है - प्रत्येक हड्डी रोल की आवश्यकता होती है $$$O (1)$ रनटाइम पिछले एल्गोरिथ्म का उपयोग करके एक यादृच्छिक पासा रोल उत्पन्न करने के लिए, और अधिक $$$O (1)$ तालिका को खोजने के लिए काम के घंटे। इससे हमें कुल काम का समय मिलता है। $$$O (1)$ ।

हालाँकि, इनिशियलाइज़ेशन स्टेप बेहद महंगा हो सकता है। इस एल्गोरिथ्म को काम करने के लिए, हमें एक सरणी के लिए जगह आवंटित करने की आवश्यकता है, जो सभी सभी आंशिक अंशों के एनएलसी के आकार का हो। हमारे उदाहरण में ( $$$\ frac {1} {2}$ । $$$\ frac {1} {3}$ । $$$\ frac {1} {12}$ । $$$\ frac {1} {12}$ ), यह 12 है, अन्य इनपुट मूल्यों के लिए मान पैथोलॉजिकली खराब हो सकते हैं। उदाहरण के लिए, आइए भिन्नों को देखें $$$\ frac {999999} {1,000,000}$ और $$$\ frac {1} {1000000}$ । हर के एनओसी एक मिलियन के बराबर है, इसलिए हमारी तालिका में एक मिलियन तत्व होने चाहिए!

दुर्भाग्य से, हालात और भी खराब हो सकते हैं। पिछले उदाहरण में, हम कम से कम "उम्मीद" कर सकते हैं कि एल्गोरिथ्म बहुत मेमोरी लेता है, क्योंकि दोनों भिन्नों के अंश एक मिलियन के बराबर हैं। हालांकि, हमारे पास कई संभावनाएं हो सकती हैं, जिसके लिए एनओसी प्रत्येक व्यक्ति हर की तुलना में काफी अधिक है। उदाहरण के लिए, आइए संभावनाओं को देखें $$$\ frac {1} {15}$ । $$$\ frac {1} {10}$ । $$$\ frac {5} {6}$ । यहाँ हर की एनओसी 30 है, जो कि किसी भी हर से अधिक है। डिजाइन यहाँ काम करता है क्योंकि $$$15 = 3 \ _ 5$ । $$$10 = 2 \ _ 5$ , और $$$6 = 2 \ _ 3$ ; दूसरे शब्दों में, प्रत्येक भाजक दो मूल्यों का एक उत्पाद है जिसे तीन मूल्यों के पूल से चुना गया है। इसलिए, उनका एनओसी इन सभी अभाज्य संख्याओं का उत्पाद है, क्योंकि प्रत्येक भाजक को NOC का विभाजक होना चाहिए। यदि हम इस निर्माण को सामान्य करते हैं और किसी भी सेट पर विचार करते हैं $$$k$ primes और इन primes के जोड़ीदार उत्पादों में से प्रत्येक के लिए एक अंश लेते हैं, तो एनओसी प्रत्येक व्यक्ति हर की तुलना में बहुत अधिक होगा। वास्तव में, एनओसी के लिए हमें प्राप्त होने वाले सबसे अच्छे ऊपरी सीमा में से एक होगा $$$O (\ prod_ {i = 0} ^ n {d_i})$ जहाँ $$$d_i$ हर है $$$मैं$ वह संभावना। यह वास्तविक स्थितियों में इस तरह के एक एल्गोरिथ्म के उपयोग की अनुमति नहीं देता है, जब संभावनाएं पहले से अज्ञात हैं, क्योंकि आकार तालिका को संग्रहीत करने के लिए आवश्यक मेमोरी है $$$O (\ prod_ {i = 0} ^ n {d_i})$ , यह आसानी से रैम में फिट होने वाली मात्रा से अधिक हो सकता है।

दूसरे शब्दों में, कई मामलों में, यह एल्गोरिथ्म अच्छा व्यवहार करता है। यदि सभी संभावनाएं समान हैं, तो इनपुट पर प्राप्त सभी संभावनाएं समान हैं $$$\ frac {1} {n}$ कुछ के लिए $$$एन$ । फिर एनओसी भाजक बराबर होता है $$$एन$ , कि, परिणामस्वरूप, ईमानदार हड्डी फेंक दिया जाएगा $$$एन$ चेहरे, चेहरे और मूल हड्डी के प्रत्येक पहलू ईमानदार हड्डी के एक पहलू के अनुरूप होंगे। इसलिए, प्रारंभिक समय है $$$O (n)$ । इसे इस प्रकार चित्रित किया जा सकता है:


यह हमें एल्गोरिथ्म के बारे में निम्नलिखित जानकारी देता है:

एल्गोरिथ्म	प्रारंभिक समय		पीढ़ी का समय		स्मृति ने कब्जा कर लिया
	सबसे अच्छा	सबसे खराब	सबसे अच्छा	सबसे खराब	सबसे अच्छा	सबसे खराब
ईमानदारी की हड्डी शार्क की हड्डी	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$

इस एल्गोरिथ्म के बारे में एक और महत्वपूर्ण विवरण: यह मानता है कि हम अच्छे विभाजनों के साथ अंशों के रूप में सुविधाजनक संभावनाएं प्राप्त करेंगे। यदि संभावनाओं को IEEE-754 डबल के रूप में निर्दिष्ट किया जाता है, तो यह दृष्टिकोण छोटी गोलाई त्रुटियों के कारण विनाशकारी होने की संभावना है; कल्पना कीजिए कि हमारे पास संभावनाएं 0.25 और 0.250000000001 हैं! इसलिए, यह दृष्टिकोण संभवतः उपयोग करने के लिए बेहतर नहीं है, विशेष मामलों को छोड़कर जब संभावनाएं अच्छी तरह से व्यवहार करती हैं और तर्कसंगत संख्याओं के साथ संचालन के अनुरूप प्रारूप में निर्दिष्ट होती हैं।

असममित सिक्का अनुकरण

एक सरल यादृच्छिक आदिम (ईमानदार हड्डी) की हमारी व्याख्या ने एक सरल लेकिन संभावित रूप से बहुत ही अप्रभावी धोखा हड्डी सिमुलेशन एल्गोरिदम का नेतृत्व किया। शायद अन्य सरल यादृच्छिक प्राथमिकताओं का अध्ययन इस समस्या को हल करने के लिए अन्य तरीकों पर कुछ प्रकाश डालेगा।

एक सरल लेकिन आश्चर्यजनक रूप से उपयोगी कार्य एक यादृच्छिक संख्या जनरेटर का उपयोग करके एक असममित सिक्के का अनुकरण करना है। यदि हमारे पास एक चील की संभावना वाला एक सिक्का है $$$p_ {प्रमुख}$ , फिर हम इस तरह के एक असममित सिक्के को कैसे फेंक सकते हैं?

इससे पहले, हमने एक सहज दृष्टिकोण विकसित किया था: अंतराल विभाजन $$$[0, 1)$ ऐसे क्षेत्रों के अनुक्रम में जब अंतराल में एक यादृच्छिक मूल्य चुनते हैं, तो यह कुछ क्षेत्र में क्षेत्र के आकार के बराबर संभावना के साथ दिखाई देता है। अंतराल में समान रूप से वितरित यादृच्छिक मान का उपयोग करके एक असममित सिक्के का अनुकरण करने के लिए $$$[0, 1)$ हमें अंतराल को तोड़ना चाहिए $$$[0, 1)$ निम्नानुसार है:


और फिर अंतराल में समान रूप से वितरित यादृच्छिक मान उत्पन्न करते हैं $$$[0, 1)$ यह देखने के लिए कि यह किस क्षेत्र में है। सौभाग्य से, हमारे पास केवल एक विभाजन बिंदु है, इसलिए यह निर्धारित करना बहुत आसान है कि बिंदु किस क्षेत्र में है; यदि मान कम है $$$p_ {प्रमुख}$ , फिर चील सिक्के पर गिर गई, अन्यथा - पूंछ। छद्म कोड:

एल्गोरिथ्म: एक असममित सिक्के का अनुकरण करें

1. अंतराल में समान रूप से वितरित यादृच्छिक मान उत्पन्न करें $$$[0, 1)$ ।
2. अगर $$$x <p_ {प्रमुख}$ , "ईगल" लौटें।
3. अगर $$$x \ ge p_ {प्रमुख}$ , वापसी पूंछ।

चूंकि हम अंतराल में समान रूप से वितरित यादृच्छिक मूल्य उत्पन्न कर सकते हैं $$$[0, 1)$ समय में $$$O (1)$ , और हम इसके लिए वास्तविक संख्याओं की तुलना भी कर सकते हैं $$$O (1)$ , तो यह एल्गोरिथ्म समय में चलता है $$$O (1)$ ।

असममित सिक्कों का उपयोग करके ईमानदार हड्डियों का अनुकरण

पिछली चर्चा से, हम जानते हैं कि हम ईमानदार हड्डी का उपयोग करके धोखा देने वाली हड्डी का अनुकरण कर सकते हैं, अगर हम मानते हैं कि हम अतिरिक्त मेमोरी स्पेस खर्च करने के लिए तैयार हैं। चूंकि हम एक असममित सिक्के को दो तरफा हड्डी को धोखा देने के रूप में देख सकते हैं, इसका मतलब है कि हम एक ईमानदार हड्डी की मदद से एक असममित सिक्के का अनुकरण कर सकते हैं। यह दिलचस्प है कि विपरीत भी किया जा सकता है - एक असममित सिक्के का उपयोग करके एक ईमानदार हड्डी का अनुकरण करने के लिए।डिजाइन सरल, सुरुचिपूर्ण है और विभिन्न प्रकार के असममित सिक्कों का उपयोग करके एक धोखा देने वाली हड्डी का अनुकरण करने के लिए आसानी से सामान्यीकृत किया जा सकता है।

एक असममित सिक्के के अनुकरण के लिए डिज़ाइन अंतराल को विभाजित करता है$$[ ० , १ ) दो क्षेत्रों में - "ईगल्स" क्षेत्र और "टेल्स" क्षेत्र हड्डियों पर गिरने वाले ईगल की संभावना के आधार पर। हम पहले से ही ईमानदार अनुकरण करने के लिए उपयोग की जाने वाली एक समान चाल देख चुके हैं$[0, 1)$$$खोज परिणाम के लि न -face हड्डियों: अंतराल$एन$$$[ 0 , 1 ) में विभाजित किया गया था$[0, 1)$$$ए न के बराबर क्षेत्र। उदाहरण के लिए, जब टेट्राहेड्रल हड्डी फेंकते हैं, तो हमें निम्नलिखित अलगाव मिला:$एन$


अब मान लें कि हम असममित सिक्कों के एक सेट का उपयोग करके इस ईमानदार हड्डी के एक रोल का अनुकरण करने में रुचि रखते हैं। एक समाधान इस प्रकार है: कल्पना करें कि हम इन क्षेत्रों में बाएं से दाएं घूमते हैं, हर बार पूछते हैं कि क्या हम वर्तमान क्षेत्र में रुकना चाहते हैं, या यदि हम आगे बढ़ेंगे। उदाहरण के लिए, मान लें कि हम इनमें से किसी एक क्षेत्र का चयन करना चाहते हैं। सबसे बाएं क्षेत्र से शुरू होकर, हम एक असममित सिक्के को पलटाएंगे, जो हमें बताता है कि क्या हमें इस क्षेत्र में रुकना चाहिए, या आगे बढ़ना जारी रखना चाहिए। चूंकि हमें संभावना के साथ समान रूप से इन सभी क्षेत्रों से चुनने की आवश्यकता है$$14 , फिर हम एक असममित सिक्के को उछालकर ऐसा कर सकते हैं, जिन पर संभावना के साथ ड्रॉप होता है$\frac{1}{4}$$$$\frac{1}{4}$ ।यदि कोई बाज गिरता है, तो हम वर्तमान क्षेत्र में रुक जाते हैं। अन्यथा, हम अगले क्षेत्र में चले जाते हैं।

यदि सिक्के गिरते हैं, तो हम खुद को दूसरे क्षेत्र में पाते हैं और फिर से पूछते हैं कि क्या हमें इस क्षेत्र को फिर से चुनना चाहिए या आगे बढ़ना जारी रखना चाहिए। आप सोच सकते हैं कि इसके लिए हमें एक और सिक्का ईगल की संभावना के साथ फेंकना होगा$$14 , लेकिन वास्तव में यह सच नहीं है! इस तर्क में दोष देखने के लिए, हमें एक चरम स्थिति में आना चाहिए - यदि प्रत्येक क्षेत्र में हम एक सिक्का फेंकते हैं जिस पर ईगल संभावना के साथ गिरता है$\frac{1}{4}$$$14 , अर्थात् , एक छोटा सा मौका है कि प्रत्येक क्षेत्र में सिक्का पूंछ से बाहर हो जाएगा, अर्थात, हमें सभी क्षेत्रों को छोड़ना होगा। जब क्षेत्रों के माध्यम से आगे बढ़ रहे हैं, तो हमें किसी तरह एक ईगल के सिक्के पर गिरने की संभावना को बढ़ाने की आवश्यकता है। एक चरम स्थिति में, यदि हम अपने आप को अंतिम क्षेत्र में पाते हैं, तो सिक्के में संभावना के साथ एक ईगल होना चाहिए$\frac{1}{4}$$$1 , क्योंकि यदि हमने पिछले सभी क्षेत्रों को अस्वीकार कर दिया, तो अंतिम क्षेत्र में रुकने का सही निर्णय होगा। संभावना को निर्धारित करने के लिए जिसके साथ हमारे असममित सिक्के को पहले क्षेत्र को छोड़ देने के बाद एक ईगल फेंकना चाहिए, हमें यह ध्यान देने की आवश्यकता है कि पहले क्षेत्र को छोड़ देने के बाद केवल तीन शेष हैं। जैसा कि हम एक ईमानदार हड्डी का रोल करते हैं, हमें इन तीन क्षेत्रों में से प्रत्येक को संभाव्यता के साथ चुनने की आवश्यकता है$1$

$$$\frac{1}{3}$ । इसलिए, सहज रूप से ऐसा लगता है कि हमारे पास एक दूसरी हड्डी होनी चाहिए जिस पर ईगल संभावना के साथ गिरता है $$$\frac{1}{3}$ । इसी तरह के तर्क का उपयोग करते हुए, यह समझा जा सकता है कि जब तीसरे क्षेत्र में जाली के दूसरे क्षेत्र में एक पूंछ दिखाई देती है, तो सिक्का को ईगल द्वारा संभाव्यता से गिरा दिया जाना चाहिए $$12 , और अंतिम क्षेत्र में - संभावना के साथ$\frac{1}{2}$$$$1$ ।

यह सहज ज्ञान हमें निम्नलिखित एल्गोरिथ्म की ओर ले जाता है। ध्यान दें कि हमने इस एल्गोरिथ्म की शुद्धता या गिरावट की चर्चा नहीं की ; जल्द ही हम यह करेंगे।

एल्गोरिथम: असममित सिक्कों का उपयोग करके ईमानदार हड्डियों का अनुकरण

1. के लिए $$मैं = 0 करने के लिए$i = 0$$$$n - 1$ :
   
   1. एक ईगल की संभावना के साथ एक असममित सिक्का फेंक दें $$$\frac{1}{n - i}$ ।
   2. गरुड़ गिरे तो लौट आये $$$मैं$ ।

यह एल्गोरिथ्म सरल है और, सबसे खराब स्थिति में, समय में चलता है। $$$O (n)$ ।लेकिन अगर यह सही है तो हम कैसे जांचेंगे? यह जानने के लिए, हमें निम्नलिखित प्रमेय की आवश्यकता है:

प्रमेय: उपरोक्त एल्गोरिथ्म पक्ष देता है$$म देता ह ं संभावना के साथ$मैं$$$1n किसी भी चयनित के लिए$\frac{1}{n}$$$$मैं$ ।

प्रमाण: किसी भी स्थिरांक पर विचार करें$$$n \ge 0$ । मजबूत प्रेरण का उपयोग करना, हम साबित करते हैं कि प्रत्येक $$ए न चेहरे के चुनाव की संभावना है$एन$$$$\frac{1}{n}$ ।

हमारे उदाहरण के लिए, हम दिखाते हैं कि चेहरा $$0 पासा पसंद की संभावना है$0$$$$\frac{1}{n}$ । — 0, $$$\frac{1}{n}$ , $$$\frac{1}{n}$ ।

$$$0, 1, 2, ..., k - 1$ , $$$\frac{1}{n}$ $$$k$ । $$$k$ , $$$k$ , $$$\frac{1}{n - k}$ . $$$k$ $$$\frac{1}{n}$ , , $$$k$ $$$\frac{k}{n}$ । , , $$$k$ $$$1 - \frac{k}{n} = \frac{n}{n} - \frac{k}{n} = \frac{n - k}{n}$ । $$$k$ $$$\frac{n - k}{n} \frac{1}{n - k} = \frac{1}{n}$ , . , .

, — $$$O(1)$ ! .

, . , . .

, . $$$\frac{1}{2}$ । $$$\frac{1}{3}$ । $$$\frac{1}{12}$ । $$$\frac{1}{12}$ । , , $$$[0, 1)$ :


, . $$$\frac{1}{2}$ , 0. , ! . , , . , , $$$\frac{1}{3}$ , , $$$\frac{1}{3}$ , «» , $$$\frac{1}{2}$ । , , , : $$$\frac{2}{3}$ । $$$\frac{1}{6}$ । $$$\frac{1}{6}$ । , $$$\frac{2}{3}$ । , $$$\frac{1}{12}$ । $$$\frac{5}{6}$ , $$$\frac{1}{12}$ , $$$\frac{1}{2}$ , $$$\frac{1}{2}$ । , - , $$$1$ , .

— :

1. : $$$\frac{1}{2}$
2. : $$$\frac{2}{3}$
3. : $$$\frac{1}{2}$
4. : $$$1$

, , , . — . , , $$$1$ । $$$1 - p_0$ । $$$1 - p_0 - p_1$ । $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ । , , , $$$k$ , , , $$$p_k$ , $$$\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}}$ । ( ):

:

• :
  
  1. $$$p_i$ .
• :
  $$$mass = 1$
  For $$$i = 0$ to $$$n - 1$ :
  
  1. $$$\frac{p_i}{mass}$ ।
  2. , $$$मैं$ ।
  3. $$$mass = mass - p_i$

, ? , :

: $$$मैं$ $$$p_i$ $$$मैं$ ।

: $$$n \ge 0$ । , $$$एन$ $$$p_i$ ।

, $$$0$ $$$p_0$ । $$$0$ , , $$$\frac{p_0}{mass}$ । $$$mass$ $$$1$ , $$$\frac{p_0}{1} = p_0$ , 0 $$$p_0$ , .

, $$$0, 1, ..., k - 1$ $$$p_0, p_1, ..., p_{k-1}$ $$$k$ । $$$k$ , $$$k$ , $$$\frac{p_k}{mass}$ . $$$k$ , , $$$k$ $$$\sum_{i = 0}^{k - 1}{p_i}$ । , $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ । , $$$k$ , $$$\frac{p_k}{mass}$ $$$k$ , $$$mass = 1 - \sum_{i = 0}^{k - 1}{p_i}$ । , $$$k$ $$$(1 - \sum_{i = 0}^{k - 1}{p_i})\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}} = p_k$ , .

. , $$$\Theta(1)$ , , $$$\Theta(n)$ , ( , ). $$$\Theta(n)$ , .

, . , , . . , . $$$एन$ .

. $$$X$ , . $$$\mathbb{P}[X = 1]$ , , $$$\mathbb{P}[X = 2]$ — , , .. $$$X$ , $$$\mathbb{E}[X]$ । ,

$$

$$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]}$$

$$$\mathbb{P}[X = i]$ ? - . $$$0$ , . $$$1$ , — , $$$0$ , , $$$1$ । , $$$मैं$ , $$$i + 1$ : $$$मैं$ , , $$$i - 1$ , , , $$$मैं$ । , $$$मैं$ $$$p_i$ , ,

$$

$$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]} = \sum_{i = 1}^n{i \cdot p_{i - 1}} = \sum_{i = 1}^n{((i - 1) p_{i - 1} + p_{i - 1})} = \sum_{i = 1}^n{((i - 1) p_{i - 1})} + \sum_{i = 1}^n{p_{i - 1}}$$

ध्यान दें कि अंतिम सरलीकरण में, पहला शब्द समतुल्य है $$$\ sum_ {i = 0} ^ {n-1} {i \ cdot p_i}$ जो बराबर है $$$\ mathbb {E} [p]$ एक पासा रोल के अपेक्षित परिणाम! इसके अलावा, दूसरा शब्द के बराबर है $$$1$ क्योंकि यह सभी संभावनाओं का योग है। इसका मतलब है कि $$$\ mathbb {E} [X] = \ mathbb {E} [p] + १$ । यही है, सिक्का रोल की अपेक्षित संख्या एक से अधिक के बराबर है और एक डाई रोल की गणितीय अपेक्षा!

एल्गोरिथ्म	प्रारंभिक समय		पीढ़ी का समय		व्यस्त स्मृति
	सबसे अच्छा	सबसे खराब	सबसे अच्छा	सबसे खराब	सबसे अच्छा	सबसे खराब
ईमानदारी की हड्डी शार्क की हड्डी	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
असममित सिक्कों की शूलर हड्डी	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$

असममित सिक्के को सामान्य करना: एक धोखा देने वाली हड्डी का अनुकरण करना

ऊपर दिखाए गए उदाहरण में, हम एक असममित सिक्के को प्रभावी ढंग से अनुकरण करने में सक्षम थे, क्योंकि हमें केवल एक विभाजन बिंदु को ध्यान में रखना था। हम इस विचार को प्रभावी रूप से एक धोखा देने वाली हड्डी में कैसे सामान्य कर सकते हैं जिसमें चेहरे की संख्या मनमानी हो सकती है?

जैसा कि आप देख सकते हैं, एक असममित सिक्का एक धोखा देने वाली हड्डी है, जिसमें केवल दो चेहरे हैं। इसलिए, हम एक असममित सिक्के को बस एक सामान्य समस्या के विशेष मामले के रूप में देख सकते हैं जिसे हम हल करना चाहते हैं। असममित सिक्का समस्या को हल करते समय, हम अंतराल को विभाजित करते हैं $$$[0, 1)$ दो क्षेत्रों में - एक ईगल के लिए, दूसरा पूंछ के लिए - और फिर उस क्षेत्र को खोजने के लिए हम इस तथ्य का उपयोग करते हैं कि केवल एक विभाजन बिंदु है। यदि हमारे पास एक एन-फेस की हड्डी है, तो अधिक क्षेत्र होंगे, और इसलिए कई विभाजन बिंदु होंगे। उदाहरण के लिए, मान लीजिए कि हमारे पास संभावनाओं के साथ सात-पक्षीय हड्डी है $$$\ frac {1} {4}$ । $$$\ frac {1} {5}$ । $$$\ frac {1} {8}$ । $$$\ frac {1} {8}$ । $$$\ frac {1} {10}$ । $$$\ frac {1} {10}$ । $$$\ frac {1} {10}$ । अगर हम अंतराल को विभाजित करना चाहते हैं $$$[0, 1)$ सात भागों में, फिर हम इसे निम्नानुसार करते हैं:


ध्यान दें कि ये क्षेत्र कहाँ स्थित हैं। पहले क्षेत्र से शुरू होता है $$$0$ और समाप्त होता है $$$\ frac {1} {4}$ । दूसरा क्षेत्र से शुरू होता है $$$\ frac {1} {4}$ और में समाप्त होता है $$$\ frac {1} {4} + \ frac {1} {5} = \ frac {9} {20}$ । आमतौर पर, यदि संभावनाएँ समान हैं $$$p_0, p_1, ..., p_ {n - 1}$ , तब क्षेत्र अंतराल होंगे $$$[0, p_0)$ । $$$[p_0, p_0 + p_1)$ । $$$[p_0 + p_1, p_0 + p_1 + p_2)$ आदि वह क्षेत्र है $$$मैं$ अंतराल द्वारा सीमित

$$

$$[\ sum_ {j = 0} ^ {i - 1} {p_j}, \ sum_ {j = 0} ^ {i} {p_j})$$

ध्यान दें कि इन दो मूल्यों के बीच का अंतर क्या है $$$p_i$ , अर्थात्, क्षेत्र का कुल क्षेत्रफल है $$$p_i$ आवश्यकता के रूप में।

अब हम जानते हैं कि क्षेत्र कहां हैं। यदि हम समान रूप से वितरित यादृच्छिक मान चुनना चाहते हैं $$$x$ सीमा में $$$[0, 1)$ , तो हम कैसे निर्धारित करते हैं कि यह किस अंतराल में गिरता है? यदि हम शुरुआती बिंदु के रूप में असममित सिक्का एल्गोरिथ्म का उपयोग करते हैं, तो विचार निम्नानुसार होगा: पहले क्षेत्र के अंत बिंदु से शुरू, लगातार सभी क्षेत्रों से गुजरते हैं जब तक कि हम एक अंत बिंदु नहीं पाते हैं जिसका मूल्य मूल्य से अधिक है $$$x$ । यदि हम ऐसा करते हैं, तो हम उस बिंदु वाले पहले क्षेत्र को पाएंगे $$$x$ , और इसलिए हमारे मूल्य। उदाहरण के लिए, यदि हमने एक यादृच्छिक मान चुना है $$$x = \ frac {27} {40}$ , फिर निम्नलिखित खोज करें:


जिससे हम यह निष्कर्ष निकाल सकते हैं कि स्कैच 3 अनुक्रमणिका के साथ खरोंच से गिर गया।

इस तरह के एक रैखिक स्कैनिंग एल्गोरिथ्म हमें एक समय एल्गोरिथ्म देगा $$$O (n)$ हड्डी के बेदखल किनारे खोजने के लिए। हालांकि, हम निम्नलिखित अवलोकन का उपयोग करके इसके निष्पादन समय में महत्वपूर्ण सुधार कर सकते हैं: क्षेत्रों के समापन बिंदुओं की एक श्रृंखला एक बढ़ता क्रम बनाती है (क्योंकि हम हमेशा अधिक से अधिक संभावनाएं जोड़ते हैं, जिनमें से कोई भी शून्य से कम नहीं हो सकता है)। इसलिए, हम निम्नलिखित प्रश्न का उत्तर देना चाहते हैं: मूल्यों और कुछ चेकपॉइंट के बढ़ते क्रम के बाद, हमें अंतराल में पहला मान चेकपॉइंट से अधिक सख्ती से खोजने की आवश्यकता है। यह बाइनरी खोज का उपयोग करने का सही समय है! उदाहरण के लिए, यहां के सरणी पर एक द्विआधारी खोज उस क्षेत्र को खोजने के लिए जिसके पास वह है $$$x = \ frac {39} {40}$ :


यह हमें समय के साथ एक एल्गोरिथ्म देता है। $$$\ Theta (\ log n)$ अंतराल में एक समान रूप से वितरित यादृच्छिक मूल्य को बांधने के लिए $$$[0, 1)$ एक परित्यक्त हड्डी के कगार पर। इसके अलावा, समापन बिंदु तालिका बनाने के लिए पूर्व-प्रसंस्करण समय पर्याप्त है $$$\ Theta (n)$ ; जैसे-जैसे हम आगे बढ़ते हैं, हम बस संभावनाओं के आंशिक योगों की गणना करते हैं।

इस एल्गोरिथ्म को कभी-कभी रूलेट व्हील चयन एल्गोरिदम कहा जाता है क्योंकि यह एक रूलेट व्हील के समान तकनीक का उपयोग करके एक यादृच्छिक क्षेत्र का चयन करता है - एक गेंद को एक अंतराल में फेंकना और अवलोकन करना कि वह कहां रुकती है। छद्म कोड में, एल्गोरिथ्म इस तरह दिखता है:

एल्गोरिथ्म: रूले पहिया चयन

• आरंभ :
  
  1. एक सरणी का चयन करें $$$ए$ आकार $$$एन$
  2. हमने सेट किया $$$A [0] = p_0$ ।
  3. हर संभावना के लिए $$$मैं$ से $$$1$ को $$$n - 1$ :
     
     1. हमने सेट किया $$$A [i] = A [i - 1] + p_i$
  
  
• जनरेशन :
  
  1. समान रूप से वितरित यादृच्छिक मान उत्पन्न करें $$$x$ सीमा में $$$[0, 1)$
  2. एक बाइनरी खोज का उपयोग करते हुए, हम सूचकांक पाते हैं $$$मैं$ सबसे छोटा तत्व $$$ए$ जो कम है $$$x$ ।
  3. वापसी $$$मैं$ ।

इस एल्गोरिथ्म और पहले दिए गए एक के बीच तुलना काफी प्रभावशाली लगती है:

एल्गोरिथ्म	प्रारंभिक समय		पीढ़ी का समय		व्यस्त स्मृति
	सबसे अच्छा	सबसे खराब	सबसे अच्छा	सबसे खराब	सबसे अच्छा	सबसे खराब
ईमानदारी की हड्डी शार्क की हड्डी	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
असममित सिक्कों की शूलर हड्डी	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
रूले व्हील चयन	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$

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

इस एल्गोरिथ्म का एक दिलचस्प विवरण यह है कि यद्यपि द्विआधारी खोज का उपयोग यादृच्छिक संख्या उत्पन्न करने के सबसे खराब समय की गारंटी देता है $$$O (\ log n)$ , यह भी एक तेज खोज की अनुमति नहीं देता है; यानी पीढ़ी का समय भी बराबर होगा $$$\ Omega (\ log n)$ । क्या इसे सुधारा जा सकता है? यह पता चला है कि आप कर सकते हैं।

मान लीजिए कि हम बाइनरी खोज से बाइनरी खोज ट्री का उपयोग करने के लिए संचयी संभावनाओं की सूची पर चलते हैं। उदाहरण के लिए, ऊपर दी गई संभावनाओं का समूह होने पर, हम उनके संचयी वितरण के लिए निम्नलिखित बाइनरी सर्च ट्री का निर्माण कर सकते हैं:


अब, यदि हम किसी हड्डी के रोल का अनुकरण करना चाहते हैं, तो हम अंतराल में समान रूप से वितरित संख्या उत्पन्न कर सकते हैं $$$[0, 1)$ और फिर इस बाइनरी सर्च ट्री (BST) में क्या अंतराल है, इसे देखें। चूंकि यह एक संतुलित बाइनरी सर्च ट्री है, इसलिए सबसे अच्छा खोज समय है $$$O (1)$ और सबसे खराब $$$O (\ log n)$ ।

हालांकि, यह मानते हुए कि हम संभावना वितरण के बारे में अधिक जानते हैं, हम बहुत बेहतर कर सकते हैं। उदाहरण के लिए, मान लें कि हमारी संभावनाएँ बराबर हैं $$$\ frac {99} {100}$ । $$$\ frac {1} {600}$ । $$$\ frac {1} {600}$ । $$$\ frac {1} {600}$ । $$$\ frac {1} {600}$ । $$$\ frac {1} {600}$ । $$$\ frac {1} {600}$ । यही है, संभाव्यता वितरण अत्यंत तिरछा है, और लगभग पूरी संभावनाएं एक चेहरे पर केंद्रित हैं। हम इन संभावनाओं के लिए एक संतुलित BST का निर्माण कर सकते हैं:


हालांकि यह बाइनरी सर्च ट्री पूरी तरह से संतुलित है, लेकिन यह हमारे कार्यों के लिए बहुत उपयुक्त नहीं है। चूंकि हम जानते हैं कि 100 में से 99 मामलों में, यादृच्छिक मूल्य सीमा में होगा $$$[0, \ frac {99} {100})$ , फिर इस अंतराल के लिए नोड को संग्रहीत करने का कोई मतलब नहीं है जहां यह अभी स्थित है। वास्तव में, इसका मतलब यह होगा कि लगभग हर समय हम नीले और पीले क्षेत्रों के साथ दो अनावश्यक तुलना करेंगे। चूंकि बहुत अधिक संभावना के साथ हमें सबसे बड़े अंतराल की जांच करने वाला पहला होना चाहिए, इसलिए पेड़ को असंतुलित करना तर्कसंगत होगा ताकि शेष लोगों के कारण औसत मामले को बेहतर बनाया जा सके। यह यहाँ दिखाया गया है:


अब हम सबसे पहले पहले प्रयास के बाद वांछित क्षेत्र ढूंढकर खोज को पूरा करेंगे। बहुत ही अप्रत्याशित घटना में कि वांछित क्षेत्र शेष में है $$$(\ frac {99} {100}, 1]$ हम शांति से पेड़ के अंत तक जाते हैं, जो वास्तव में अच्छी तरह से संतुलित है।

सामान्यीकृत रूप में, हम निम्नलिखित समस्या को हल करना चाहते हैं:

संभावनाओं के दिए गए सेट को देखते हुए, इन संभावनाओं के लिए एक द्विआधारी खोज ट्री ढूंढें जो अपेक्षित खोज समय को कम करता है।

सौभाग्य से, इस समस्या का बहुत अच्छी तरह से अध्ययन किया जाता है और इसे इष्टतम बाइनरी सर्च ट्री समस्या कहा जाता है । इस समस्या को हल करने के लिए कई एल्गोरिदम हैं; यह ज्ञात है कि सटीक समाधान समय पर मिल सकता है $$$O (n ^ 2)$ गतिशील प्रोग्रामिंग का उपयोग करना, और यह कि अच्छे रैखिक समय एल्गोरिदम हैं जो अनुमानित समाधान पा सकते हैं। इसके अलावा, इष्टतम समाधान का एक निरंतर कारक प्राप्त करने के लिए, आप स्प्ले ट्री डेटा संरचना (ट्री का विस्तार) (सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री) का उपयोग कर सकते हैं।

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

सबसे अच्छी स्थिति में, हमारे पास एक धोखा देने वाली हड्डी होती है जिसमें एक चेहरा हमेशा बाहर निकलता है (अर्थात, इसकी संभावना 1 है, और अन्य सभी चेहरों में 0 की संभावना है)। यह हमारे पिछले उदाहरण का एक चरम अतिशयोक्ति है, लेकिन इस मामले में, पहले प्रयास के बाद खोज हमेशा समाप्त हो जाएगी। सबसे खराब स्थिति में, सभी संभावनाएं समान हैं, और हमें एक मानक बीएसटी खोज मिलती है। हम निम्नलिखित पर आते हैं:

एल्गोरिथ्म	प्रारंभिक समय		पीढ़ी का समय		व्यस्त स्मृति
	सबसे अच्छा	सबसे खराब	सबसे अच्छा	सबसे खराब	सबसे अच्छा	सबसे खराब
ईमानदारी की हड्डी शार्क की हड्डी	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
असममित सिक्कों की शूलर हड्डी	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
रूले व्हील चयन	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$
इष्टतम रूलेट व्हील चयन	$$$O (n ^ 2)$		$$$\ Theta (1)$	$$$O (\ log n)$	$$$\ Theta (n)$

डार्ट फेंक रहा है

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

इस क्षण तक, हमने अंतराल की कल्पना की $$$[0, 1)$ और एक-आयामी अंतराल के रूप में हड्डियों के चेहरे की संभावनाएं। ये दोनों एल्गोरिदम अंतराल में कुछ बिंदु का चयन करते हैं $$$[0, 1)$ और इसे एक सीधी रेखा के खंड पर रखना, जिसकी लंबाई किसी प्रकार की संभावना से मेल खाती है। हम जितने लंबे खंड बनाएंगे, इस सेगमेंट को चुनने की संभावना उतनी ही अधिक होगी। लेकिन क्या होगा अगर आप एक नहीं बल्कि दो आयामों में सोचने की कोशिश करें? क्या होगा अगर हम संभाव्यता लेते हैं $$$p_i$ एक सीधी रेखा खंड की लंबाई नहीं, बल्कि एक आयत का क्षेत्रफल?

आइए संभावनाओं के साथ अपने पिछले उदाहरण पर लौटते हैं $$$\ frac {1} {2}$ । $$$\ frac {1} {3}$ । $$$\ frac {1} {12}$ । $$$\ frac {1} {12}$ । हम एक चौड़ाई के साथ आयतों के रूप में इन संभावनाओं का प्रतिनिधित्व करते हैं $$$w$ (कुछ मनमानी के साथ $$$w> 0$ ) और ऊंचाई $$$p_i$ (इस प्रकार, आयत का क्षेत्रफल बराबर होगा $$$w \ cdot p_i$ ):


ध्यान दें कि इन आयतों का कुल क्षेत्रफल है $$$w$ क्षेत्र के बाद से

$$

$$\ sum_ {i = 0} ^ {n - 1} {w p_i} = w \ sum_ {i = 0} ^ {n - 1} {p_i} = w$$

अब मान लीजिए कि हम इन आयतों के चारों ओर एक बाउंडिंग आयत बनाते हैं जिसकी चौड़ाई है $$$4w$ (चूंकि चार चतुर्भुज हैं), और ऊंचाई है $$$\ frac {1} {2}$ (चूंकि सबसे ऊंची आयत की ऊंचाई है $$$\ frac {1} {2}$ ):


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

$$

$$\ mathbb {P} [\ mbox {पक्ष के लिए आयत हिट} | \ mbox {कुछ आयत को मारो}] = \ frac {\ mbox {आयत का क्षेत्र i}}} {\ mbox {कुल आयत क्षेत्र}}} = \ frac {w p_i} {w} = p_i$$

दूसरे शब्दों में, जब हम अंततः अपने समान रूप से वितरित डार्ट के साथ किसी प्रकार के आयत में आते हैं, तो हम चेहरे की आयत का चयन करते हैं $$$मैं$ संभावना के साथ चीटर की हड्डी $$$p_i$ , वह है, इस संभावना के साथ कि हमें क्या चाहिए! यही है, अगर हम इस आयत पर यादृच्छिक डार्ट्स फेंकने का अनुकरण करने के लिए कुछ प्रभावी तरीका पा सकते हैं, तो हमारे पास एक यादृच्छिक पासा फेंकने का अनुकरण करने का एक प्रभावी तरीका होगा।

इस आयत में डार्ट थ्रो को अनुकरण करने का एक तरीका अंतराल में दो समान रूप से वितरित मूल्यों का चयन करना है $$$[0, 1)$ डार्ट के तहत क्षेत्र की जाँच करके, उचित चौड़ाई और ऊंचाई तक उन्हें स्केलिंग। हालांकि, यह उसी समस्या का कारण बनता है जो हमारे पास था जब हमने एक-आयामी क्षेत्र को निर्धारित करने का प्रयास किया था जिसमें यादृच्छिक मूल्य स्थित है। हालांकि, टिप्पणियों का वास्तव में अद्भुत श्रृंखला है, जिसके लिए प्रभाव का स्थान निर्धारित करना एक सरल हो सकता है, यदि तुच्छ, कार्य नहीं।

पहला अवलोकन: हमने दिखाया कि इन आयतों की चौड़ाई को मनमाने ढंग से चुना जा सकता है, क्योंकि इन सभी की चौड़ाई समान है। बेशक, हाइट्स हड्डियों के चेहरे की संभावनाओं पर निर्भर करता है। हालांकि, अगर हम समान रूप से कुछ सकारात्मक वास्तविक संख्या से सभी ऊंचाइयों को मापते हैं $$$ज$ , तो सभी आयतों के सापेक्ष क्षेत्र समान होंगे। वास्तव में, किसी भी सकारात्मक वास्तविक संख्या के लिए $$$ज$ द्वारा अपनी ऊंचाइयों को बढ़ाने के बाद सभी आयतों का कुल क्षेत्रफल $$$ज$ के रूप में गणना की

$$

$$\ sum_ {i = 0} ^ {n - 1} {w h p_i} = w h \ sum_ {i = 0} ^ {n - 1} {p_i} = w h$$

अब हम किसी भी व्यक्तिगत आयत को चुनने की संभावना पर विचार करेंगे, अपने आप को इस स्थिति तक सीमित कर लेंगे कि हम निश्चित रूप से किसी प्रकार की आयत को हिट करें। उसी गणना का उपयोग करते हुए, हमें निम्नलिखित मिलते हैं:

$$

$$\ mathbb {P} [\ mbox {पक्ष के लिए आयत हिट} | \ mbox {कुछ आयत को मारो}] = \ frac {\ mbox {आयत का क्षेत्रफल i}}} {\ mbox {कुल आयत क्षेत्र}}} = \ frac {w h p_i} {w h} = p_i$$

यही है, वास्तव में, किसी एक आयत को चुनने की संभावना नहीं बदलती है अगर हम उन्हें रैखिक और समान रूप से मापते हैं।

चूंकि हम किसी भी उपयुक्त स्केलिंग फैक्टर को चुन सकते हैं, इसलिए हम इन आयतों को स्केल नहीं करते हैं ताकि बाउंडिंग बॉक्स की ऊंचाई हमेशा 1 हो? चूंकि बाउंडिंग बॉक्स की ऊंचाई अधिकतम मूल्य से निर्धारित होती है $$$p_i$ इनपुट संभावनाएं, फिर हम एक कारक द्वारा आयतों में से प्रत्येक को स्केल करके शुरू कर सकते हैं $$$\ frac {1} {p_ {max}}$ जहाँ $$$p_ {अधिकतम}$ सभी इनपुट संभावनाओं की अधिकतम संभावना है। इसके लिए धन्यवाद, हमें आयत की ऊँचाई मिलती है। 1. इसी तरह, चूंकि हम आयतों के लिए कोई भी मनमाना चौड़ाई चुन सकते हैं, इसलिए हम चौड़ाई 1 लेते हैं। इसका मतलब है कि $$$एन$ बाउंडिंग बॉक्स की कुल चौड़ाई की संभावनाएं हैं $$$एन$ , और कुल ऊंचाई है 1. यह आंकड़ा में दिखाया गया है:


अब हम यह सोचने के लिए तैयार हैं कि हम एक यादृच्छिक डार्ट को एक आयत में कैसे फेंक सकते हैं और यह निर्धारित कर सकते हैं कि इसमें क्या गिर गया। सबसे महत्वपूर्ण बात यह है कि हम आयत को विभाजित कर सकते हैं ताकि इसमें कई छोटे आयत और एक अजीब आकार का खाली स्थान न हो। इसके बजाय, क्षेत्र को एक सेट में काट दिया जाता है $$$2 एन$ आयत, प्रत्येक पर दो $$$एन$ इनपुट संभावनाएँ। यह यहाँ दिखाया गया है:


ध्यान दें कि यह आयत कैसे बनता है। चीटर की हड्डी के प्रत्येक चेहरे के लिए, हमारे पास 1 कॉलम है और 1 की चौड़ाई के साथ, दो स्थानों में विभाजित है - एक आधा स्थान "हाँ" इस आकार के एक आयत के अनुरूप है, और शेष कॉलम के अनुरूप एक आधा स्थान "नहीं" है।

अब हम सोचते हैं कि हम डार्ट को कैसे फेंक सकते हैं। इस आयत में फेंके गए पूरी तरह से समान डार्ट में घटक होंगे $$$x$ और $$$य$ । यहाँ घटक है $$$x$ जो अंतराल में होना चाहिए $$$[0, 1)$ , जो कॉलम डार्ट हिट करता है, से मेल खाती है। अंग $$$य$ जो अंतराल में होना चाहिए $$$[0, 1)$ , कॉलम में हम कितने ऊंचे हैं। घटक चयन $$$x$ प्रभावित करता है कि हम चीटर बोन के किस चेहरे पर विचार कर रहे हैं, और घटक की पसंद $$$य$ इस बात से मेल खाती है कि हमने इस पहलू को चुना है या नहीं। लेकिन रुको - हम पहले से ही इन दो विचारों को जानते हैं! समन्वय का चयन करें $$$x$ कॉलम के समान, कॉलम की पसंद पर निर्णय लेने के लिए एक ईमानदार हड्डी फेंकने के समान। समन्वय का चयन करें $$$य$ एक असममित सिक्के के फेंकने से मेल खाती है यह निर्धारित करने के लिए कि चेहरे का चयन करें या फिर से टॉस करें! यह अवलोकन इतना महत्वपूर्ण है कि हम इसे पूरी तरह से समझने योग्य बनाते हैं:

इस अंतराल में एक यादृच्छिक बिंदु का चुनाव एक ईमानदार हड्डी को फेंकने और एक असममित सिक्के को उछालने के समान है।

वास्तव में, इस परिणाम को बहुत अधिक शक्तिशाली अवसर के रूप में माना जा सकता है। एक धोखा देने वाली हड्डी का अनुकरण करने के लिए, हम असममित सिक्कों का एक सेट बनाते हैं, जो हड्डी के प्रत्येक चेहरे के लिए होता है, और फिर एक ईमानदार हड्डी को रोल करके यह निर्धारित किया जाता है कि किस सिक्के को फेंकना है। , , , , .

. -, — «» $$$\frac{p_i}{p_{max}}$ , «» $$$\frac{p_{max} - p_i}{p_{max}}$ । , 1. -, $$$1$ , . , : - , , ( , ). . , , . .

: /

• :
  
  1. $$$p_i$ ; $$$p_{max}$ ।
  2. $$$Coins$ $$$एन$ , «» .
  3. $$$मैं$ $$$0$ को $$$n - 1$ :
     
     1. $$$Coins[i] = \frac{p_i}{p_{max}}$
  
  
• :
  
  1. :
     
     1. n- $$$मैं$ $$$[0, n)$ ।
     2. , $$$Coins[i]$ ।
     3. , $$$मैं$ ।

. $$$O (n)$ , $$$O (n)$ $$$Coins$ , $$$O (n)$ । , $$$O(1)$ । ? , , - . , . , ( $$$\frac{1}{n}$ ), . , , , , - , . , $$$मैं$ $$$\frac{p_i}{p_{max}}$ , -

$$

$$\sum_{i = 0}^{n - 1}{(\frac{1}{n} \frac{p_i}{p_{max}})} = \frac{1}{n}\sum_{i = 0}^{n - 1}{\frac{p_i}{p_{max}}} = \frac{1}{n \cdot p_{max}}\sum_{i = 0}^{n - 1}{p_i} = \frac{1}{n \cdot p_{max}}$$

- , , , , , $$$n \cdot p_{max}$ । ? $$$p_{max}$ । $$$p_{max}$ $$$1$ ( ). $$$एन$ , $$$एन$ . , , , , . , $$$p_{max}$ $$$\frac{1}{n}$ , , . अगर $$$p_{max} = \frac{1}{n}$ , 1. . अगर $$$p_{max} = \frac{1}{n}$ , ( $$$\frac{1}{n}$ ), 1, , 1. , , .

, $$$p_{max}$ , , , . , , $$$एन$ , , 1. , , «» $$$\frac{1}{p_{max}}$ , 1, $$$\frac{1}{p_{max}}$ । , «» $$$\frac{1}{n \cdot p_{max}}$ । , , «», $$$p_{max}$ । , , .

:

एल्गोरिथ्म
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$

, . . ?

Alias-

, . , . , , «» , . , , , . - , , - , .

, , , . . $$$\frac{1}{2}$ । $$$\frac{1}{3}$ । $$$\frac{1}{12}$ । $$$\frac{1}{12}$ । , $$$\frac{1}{4}$ । , $$$\frac{1}{4}$ , $$$\frac{1}{2}$ ? , . $$$1$ , :


, $$$\frac{1}{4}$ 1. , , :


$$$1 \times 4$ । , :


, , $$$\frac{1}{2}$ और $$$\frac{1}{3}$ . ? , $$$\frac{1}{2}$ $$$\frac{1}{12}$ ? , - , :


, , . , $$$\frac{1}{2}$ और $$$\frac{1}{3}$ , . $$$\frac{1}{2}$ , . , :


, , :


. -, . , ; . , , . -, , , - , , . , . — , . , — , , . , . , , , - ( ).

alias- . -, , . , , . , , , .

, , ? , , . , , , , , . , . , - , , , ( ) , - . (alias) , «» - . - «alias» «alias-».

, , . - ( !), () , , alias- : $$$Prob$ alias $$$Alias$ । $$$एन$ । , alias , ( ). , . - - $$$मैं$ । $$$Prob[i]$ । , , $$$मैं$ , , $$$Alias[i]$ । alias :

Alias

, $$$Alias$ और $$$Prob$ . , , :

• $$$(n \cdot p_i) \times 1$ $$$p_i$ ।
• $$$एन$
  
  • , $$$1$ ।
  • , $$$मैं$ , $$$मैं$ ।

, , . , $$$\frac{1}{2}$ । $$$\frac{1}{3}$ । $$$\frac{1}{12}$ । $$$\frac{1}{12}$ । ( $$$k = n = 4$ ), $$$1 = \frac{4}{4}$ । , alias, , . , 4, :


, , ( $$$\frac{1}{3}$ । $$$\frac{1}{3}$ ) 1. , - . ( ) :


- . , , , 1 ( $$$2$ और $$$\frac{4}{3}$ )। ; $$$\frac{4}{3}$ । $$$\frac{4}{3}$ , ; $$$\frac{2}{3}$ से $$$\frac{4}{3}$ , :


, . , $$$3$ , , , . , . , , $$$1$ , (, $$$\frac{2}{3}$ ) :


, - , 1, . ( $$$2$ ), $$$\frac{1}{3}$ से $$$2$ :


, . , - , 1 ( $$$\frac{1}{3}$ ), :


- $$$1$ , . — $$$\frac{5}{3}$ :


, 1. , :


! .

, :

• - , 1, , $$$Prob$ .
• - , 1, , $$$Alias$ , .

, ? «», ? , . : , 1 ( $$$\frac{1}{n}$ , $$$एन$ )। , , , , 1 ( ) 1 ( ). , . , ? , . , , . , .

:

: $$$k$ $$$h_0$ । $$$h_1$ , ..., $$$h_{k-1}$ , , $$$\sum_{i=0}^{k-1}{h_i} = k$ , $$$k$ , 1, , , $$$मैं$ - $$$मैं$ - .

: . , $$$k = 1$ , 1. $$$0$ - . , 1, , $$$0$ - $$$0$ - .

, - $$$k$ $$$k + 1$ $$$1$ $$$h_0$ । $$$h_1$ , ..., $$$h_{k}$ , , $$$\sum_{i = 0}^{k}{h_i} = k + 1$ । , $$$h_l$ , , $$$h_l \le 1$ , - $$$h_g$ (, $$$l \ne g$ ), , $$$h_g \ge 1$ । , , $$$h_l$ साथ $$$h_l \le 1$ ; , $$$h_i > 1$ $$$मैं$ $$$0 \le i \le k$ । , $$$k + 1 = \sum_{i = 0}^k{h_i} > \sum_{i=0}^k{1} = k + 1$ , . , - $$$l$ , , $$$h_l \le 1$ । , $$$h_g$ ( $$$l \ne g$ ), , $$$h_g \ge 1$ । , $$$h_g < 1$ , ( ) $$$\sum_{i=0}^{k}{h_i} < k + 1$ . , $$$h_l \le 1$ और $$$h_g \ge 1$ ।

. $$$h_l$ $$$l$ $$$1 - h_l$ में $$$l$ - $$$h_g$ ( , $$$0 \le 1 - h_l \le 1$ और $$$h_g \ge 1$ )। . $$$k$ , $$$k$ , $$$1$ , $$$k + 1$ । , $$$l$ , . , , $$$k$ में $$$k$ , . , $$$l$ , , , . .

, , alias, , . alias.

Alias

, alias-. 1 1, :

: Alias-

• :
  
  1. $$$p_i$ पर $$$एन$ ।
  2. $$$Alias$ और $$$Prob$ , $$$एन$ ।
  3. For $$$j = 1 \mbox{ to } n - 1$ :
     
     1. $$$p_l$ , $$$p_l \le 1$ ।
     2. $$$p_g$ ( $$$l \ne g$ ), $$$p_g \ge 1$
     3. $$$Prob[l] = p_l$ ।
     4. $$$Alias[l] = g$ ।
     5. $$$p_l$ .
     6. $$$p_g := p_g - (1 - p_l)$ ।
     
     
  4. चलो $$$मैं$ , 1.
  5. $$$Prob[i] = 1$ ।
  
  
• :
  
  1. $$$एन$ - ; $$$मैं$ ।
  2. , $$$Prob[i]$ ।
  3. , $$$मैं$ ।
  4. $$$Alias[i]$ ।

, , $$$\Theta(1)$ । . -, $$$\Theta(n)$ $$$एन$ , $$$O (n)$ . $$$\Theta(n)$ , $$$O (n)$ , . $$$O(n^2)$ . , :

एल्गोरिथ्म
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$

alias- , . - (, $$$O (n)$ ), .

. , $$$O (n)$ । . $$$p_g$ और $$$p_l$ $$$O(\log n)$ , . $$$p_l$ $$$O(\log n)$ , $$$p_g$ $$$O(\log n)$ . :

: Alias-

• :
  
  1. $$$Alias$ और $$$Prob$ , $$$एन$ ।
  2. $$$T$ ।
  3. $$$n \cdot p_i$ में $$$T$ $$$मैं$ ।
  4. For $$$j = 1 \mbox{ to } n - 1$ :
     
     1. $$$T$ ; $$$p_l$ ।
     2. $$$T$ ; $$$p_g$ ।
     3. $$$Prob[l] = p_l$ ।
     4. $$$Alias[l] = g$ ।
     5. $$$p_g := p_g - (1 - p_l)$ ।
     6. $$$p_g$ $$$T$ ।
     
     
  5. चलो $$$मैं$ , 1.
  6. $$$Prob[i] = 1$ ।
  
  
• :
  
  1. $$$एन$ - ; $$$मैं$ ।
  2. , $$$Prob[i]$ ।
  3. , $$$मैं$ ।
  4. $$$Alias[i]$ ।

. $$$Alias$ और $$$Prob$ - $$$O (n)$ , BST $$$T$ $$$\Theta(n \log n)$ । $$$\Theta(n)$ , $$$O(\log n)$ । $$$O(n \log n)$ :

एल्गोरिथ्म
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$

, . , , , alias-. «A Linear Algorithm For Generating Random Numbers With a Given Distribution» , alias-.

: 1, 1. . «» , «» «». :

• «» 1.
• «» 1.
• .

, , , . , :

: () Alias-

: . .

• :
  
  1. $$$Alias$ और $$$Prob$ , $$$एन$ ।
  2. , $$$Small$ और $$$Large$ ।
  3. $$$एन$ ।
  4. $$$p_i$ :
     
     1. अगर $$$p_i < 1$ , $$$मैं$ $$$Small$ ।
     2. ( $$$p_i \ge 1$ ) $$$मैं$ $$$Large$ ।
     
     
  5. $$$Small$ :
     
     1. $$$Small$ ; $$$l$ ।
     2. $$$Large$ ; $$$जी$ ।
     3. $$$Prob[l] = p_l$ ।
     4. $$$Alias[l] = g$ ।
     5. $$$p_g := p_g - (1 - p_l)$ ।
     6. अगर $$$p_g < 1$ , $$$जी$ में $$$Small$ ।
     7. ($p_g \ge 1$) $$$जी$ में $$$Large$ ।
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$जी$ ।
     2. $$$Prob[g] = 1$ ।
     
     
  
  
• :
  
  1. $$$एन$ - ; $$$मैं$ ।
  2. , $$$Prob[i]$ ।
  3. , $$$मैं$ ।
  4. $$$Alias[i]$ ।

(, ) : - $$$Small$ $$$Large$ , . . $$$Small$ $$$Large$ ( $$$Small$ , , ). $$$Large$ 1, $$$k$ $$$Large$ $$$k$ , $$$Large$ 1, . 1, , , 1.

. , , , . .

, . $$$\frac{1}{4}$ । $$$\frac{1}{5}$ । $$$\frac{1}{8}$ । $$$\frac{1}{8}$ । $$$\frac{1}{10}$ । $$$\frac{1}{10}$ । $$$\frac{1}{10}$ । , , $$$\frac{1}{8}$ । $$$\frac{1}{5}$ । $$$\frac{1}{10}$ । $$$\frac{1}{4}$ । $$$\frac{1}{10}$ । $$$\frac{1}{10}$ । $$$\frac{1}{8}$ । :


$$$Small$ , :


$$$Large$ ( ) . $$$\frac{7}{4} - \frac{1}{8} = \frac{13}{8} \ge 1$ , $$$Large$ :


. $$$Small$ , $$$Large$ :


:


, , , . , :


$$$Small$ , :


$$$Small$ , , :


, $$$Small$ , .


alias .

, . , , IEEE-754 double, . , , :

1. , $$$Small$ $$$Large$ , . , , $$$एन$ , , $$$\frac{1}{n}$ , $$$1$ ( $$$Small$ , $$$Large$ )।
2. , , . , , $$$Large$ , $$$Small$ ।

, $$$Small$ $$$Large$ । , , $$$Small$ , $$$Large$ .

, . , , , $$$Large$ । -, , $$$1$ , , $$$1$ । , . :

: Alias-

• :
  
  1. $$$Alias$ और $$$Prob$ , $$$एन$ ।
  2. , $$$Small$ और $$$Large$ ।
  3. $$$एन$ ।
  4. $$$p_i$ :
     
     1. अगर $$$p_i < 1$ , $$$मैं$ में $$$Small$ ।
     2. ( $$$p_i \ge 1$ ) $$$मैं$ में $$$Large$ ।
     
     
  5. $$$Small$ और $$$Large$ : ( $$$Large$ )
     
     1. $$$Small$ ; $$$l$ ।
     2. $$$Large$ ; $$$जी$ ।
     3. $$$Prob[l] = p_l$ ।
     4. $$$Alias[l] = g$ ।
     5. $$$p_g := (p_g + p_l) - 1$ । ( . )
     6. अगर $$$p_g < 1$ , $$$जी$ में $$$Small$ ।
     7. ( $$$p_g \ge 1$ ) $$$जी$ में $$$Large$ ।
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$जी$ ।
     2. $$$Prob[g] = 1$ ।
     
     
  7. $$$Small$ : - .
     
     1. $$$Small$ ; $$$l$ ।
     2. $$$Prob[l] = 1$ ।
     
     
  
  
• :
  
  1. $$$एन$ - ; $$$मैं$ ।
  2. , $$$Prob[i]$ ।
  3. , $$$मैं$ ।
  4. $$$Alias[i]$ ।

, — . $$$\Theta(n)$ , . $$$\Theta(1)$ , , . $$$O (n)$ , () , . $$$O (n)$ , $$$Large$ और $$$Small$ $$$O (n)$ . $$$\Theta(n)$ , ( ) :

एल्गोरिथ्म
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$\Theta(n)$		$$$\Theta(1)$		$$$\Theta(n)$

! ! , . , (alias- ) , - .

alias- , , - , alias- Java , .

, !