निर्दिष्ट असतत वितरण से यादृच्छिक संख्या कैसे उत्पन्न करें?

Question

आइए कहें कि हमारे पास संभावित परिणामों की सीमित संख्या के साथ कुछ अलग वितरण है, क्या ओ (लॉगन) की तुलना में इस वितरण से यादृच्छिक संख्या उत्पन्न करना संभव है, जहां एन संभावित परिणाम हैं?

कैसे यह हे में बनाने के लिए (logn):
- संचयी संभावना के साथ एक सरणी (सरणी [i] = संभावना है कि यादृच्छिक संख्या कम या उसके बराबर मैं करने के लिए किया जाएगा) सुनिश्चित
- से यादृच्छिक संख्या उत्पन्न करें समान वितरण (इसे के द्वारा इंगित करने देता है)
- मुझे सबसे छोटा पता है कि k < ऐरे [i]। यह बाइनरी खोज का उपयोग करके किया जा सकता है।
- मैं हमारी यादृच्छिक संख्या है।

Answer 1

वॉकर की ऊर्फ विधि आकार के कुछ सहायक सरणी का उपयोग करके निरंतर सबसे खराब मामले में नमूना खींच सकती है, जिसे प्रीकंप्यूटेड होने की आवश्यकता होती है। इस विधि को Devroye's book on sampling के अध्याय 3 में वर्णित किया गया है और आर नमूना() फ़ंक्शन में कार्यान्वित किया गया है। आप आर के स्रोत कोड या this thread से कोड प्राप्त कर सकते हैं। एक 1991 paper by Vose प्रारंभिक लागत को कम करने का दावा करता है।

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

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