🤵 🤶 🐢 परिमित असतत वितरण उत्पन्न करने के लिए सूचकांक विधि ♌️ 💷 🦗

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

पर एक समान वितरण से [0,1]

। अर्थात्:

जहाँ

- तर्क का पूर्णांक भाग लेना।

लेकिन मान लीजिए कि हमारे पास एक "बेईमान" हड्डी है और किनारे असमान रूप से गिरते हैं। हमारी हड्डी में K चेहरे हैं, और p_i

एक चेहरे की संभावना

। ऐसा करने में, प्राकृतिक प्रतिबंध

। मैं इस सवाल का जवाब देने की कोशिश करूंगा: इस तरह के वितरण के साथ छद्म यादृच्छिक अनुक्रम का अनुकरण कैसे करें?

#Naive approach len<-10 ps<-seq(len,2, by=-1) ps<- 1/ps^2 ps<-ps/sum(ps) ss<-cumsum(ps) gen_naiv <- function() { alpha<-runif(1) return (min(which(alpha<ss))) } #sample val<-c() len<-10000 for(i in 1:len) { val<-append(val, gen_naiv()) } vals<-factor(val) plot(vals)

इस तरह के वितरण को उत्पन्न करने के "भोले" संस्करण पर विचार करें। हम आंशिक रकम की अवधारणा का परिचय देते हैं

, हम समानता लिख सकते हैं

। यह ज्ञात रहता है

और

विशिष्ट मैं मिल यदि आप बस 1 से शुरू करते हैं और K के साथ समाप्त करते हैं, तो औसतन यह औसत रूप से होता है

तुलना संचालन। सबसे खराब स्थिति में, जो संयोगवश, संभावना के साथ होता है

, हमें K तुलना की आवश्यकता है, उदाहरण के लिए, ऊपर दिए गए ग्राफ़ से, यह 0.45473749 की संभावना के साथ उत्पन्न होता है। औसतन, 7.5 तुलना और एक यादृच्छिक चर की पीढ़ी की आवश्यकता होती है। संचालन की संख्या आपको दुखी करती है, खासकर यदि आपको गलत हड्डी के साथ बड़ी संख्या में फेंकने की आवश्यकता होती है।

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

विधि का सार बहुत सरल है, हम विभाजित करते हैं [0,1]

एम बराबर भागों पर। हम तत्व में लंबाई एम की एक अतिरिक्त सरणी आर का परिचय देते हैं r_j

सरणी मैं संग्रहीत किया जाएगा i, ऐसे

 #Preprocessing ss<-cumsum(ps) ss<-append(ss, 0, after=0) M<-length(ss) rs<-c() for(k in 0:(M-1)) rs<-append(rs, min(which(ss>=k/M)))

इस स्थिति में, नया मान उत्पन्न करने के लिए एल्गोरिथ्म निम्नलिखित रूप लेता है:

 #chen's method finite discrete distribution generator gen_dfd <- function() { M<-10 alpha<-runif(1) idx<-rs[floor(alpha*M)+1] return (idx-1+min(which(alpha<ss[idx:(M+1)]))-1) } #sample code val<-c() len<-10000 for(i in 1:len) { val<-append(val, gen_dfd()) } vals<-factor(val) plot(vals)

सबसे खराब स्थिति में, ऊपर दिए गए उदाहरण के लिए, हमें 0.03712143 की संभावना के साथ (एम के बराबर 9) 4 तुलनाओं की आवश्यकता है। औसतन, आपको एक यादृच्छिक चर और 1.2 तुलना उत्पन्न करने की आवश्यकता है। यदि बहुत अधिक मेमोरी और डेटा तैयारी का चरण (कार्य) है p_i

) अपेक्षाकृत दुर्लभ है, एम को मनमाने ढंग से बड़ा चुना जा सकता है।

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

परिमित असतत वितरण उत्पन्न करने के लिए सूचकांक विधि

More articles: