Sobol sequence
'सोबोल' अनुक्रम (आधार 2 में एल. पी. टी. ओ. अनुक्रम या (टी, एस) अनुक्रम भी कहा जाता है) अर्ध-यादृच्छिक निम्न-विसंगति अनुक्रमों का एक उदाहरण है। इन्हें पहली बार 1967 में रूसी गणितशास्त्री इल्या एम. सोबोल द्वारा पेश किया गया था। ये अनुक्रम इकाई अंतराल के क्रमिक रूप से महीन समान विभाजन बनाने के लिए दो के आधार का उपयोग करते हैं और फिर प्रत्येक आयाम में निर्देशांक को फिर से व्यवस्थित करते हैं। एस-आयामी इकाई हाइपरक्यूब में अच्छा वितरण मान लीजिए कि आई. एस. = [0,1] एस.-आयामी इकाई हाइपरक्यूब है, और आई. एस. पर एक वास्तविक समाकलन फलन है। 'सोबोल' की मूल प्रेरणा इस में एक अनुक्रम xn का निर्माण करना था ताकि अभिसरण यथासंभव तेजी से हो सके। यह कमोबेश स्पष्ट है कि सम को समाकलन की ओर अभिसरण करने के लिए, xn बिंदुओं को भरना चाहिए जो छेद को कम कर रहा है। एक अन्य अच्छा गुण यह होगा कि इस के निम्न-आयामी चेहरे पर xn के अनुमान भी बहुत कम छेद छोड़ते हैं। इसलिए इस की सजातीय पूर्ति योग्य नहीं है क्योंकि कम आयामों में कई बिंदु एक ही स्थान पर होंगे, इसलिए अभिन्न अनुमान के लिए बेकार है। इन अच्छे वितरणों को आधार बी में (टी, एम, एस)-नेट और (टी, एस)-अनुक्रम कहा जाता है। उन्हें प्रस्तुत करने के लिए, पहले आधार b में एक प्राथमिक s-अंतराल को परिभाषित करें जो कि Is का एक उपसमुच्चय है, जहां aj और dj गैर-ऋणात्मक पूर्णांक हैं, और {1,., s} में सभी j के लिए। 2 पूर्णांकों को देखते हुए, आधार b में a (t, m, s)-नेट bm बिंदुओं का एक अनुक्रम xn है जो इस प्रकार है कि सभी प्राथमिक अंतराल P के लिए आधार b में हाइपरवॉल्यूम λ (P) = bt−m के लिए है। एक गैर-नकारात्मक पूर्णांक t को देखते हुए, आधार b में a (t, s)-अनुक्रम बिंदुओं xn का एक अनंत अनुक्रम है जैसे कि सभी पूर्णांकों के लिए, अनुक्रम आधार b में a (t, m, s)-नेट है। अपने लेख में, सोबोल ने Πτ-मेशेस और LPτ अनुक्रमों का वर्णन किया, जो आधार 2 में क्रमशः (t, m, s)-नेट और (t, s)-अनुक्रम हैं। आधार बी (जिसे निडेराइटर अनुक्रम भी कहा जाता है) में शब्द (टी, एम, एस)-नेट और (टी, एस)-अनुक्रम 1988 में हेराल्ड निडेराइटर द्वारा बनाए गए थे। हाल्टन, फॉरे और अन्य कम विसंगति वाले अनुक्रमों की तुलना में अंग्रेजी बोलने वाले पत्रों में 'सोबोल' अनुक्रम शब्द को पेश किया गया था। एक तेज एल्गोरिथ्म एंटोनोव और सालेव द्वारा एक अधिक कुशल ग्रे कोड कार्यान्वयन का प्रस्ताव दिया गया था। जहाँ तक सोबोल 'संख्याओं की उत्पत्ति का संबंध है, उन्हें स्पष्ट रूप से एन-th बिंदु ड्रॉ के निर्माण के लिए एन के बजाय ग्रे कोड के उपयोग से सहायता मिलती है। मान लीजिए कि हम पहले से ही सभी सोबोल अनुक्रम उत्पन्न कर चुके हैं जो n−1 तक खींचते हैं और सभी आवश्यक आयामों के लिए xn−1, j मानों को स्मृति में रखते हैं। चूँकि ग्रे कोड G (n) पूर्ववर्ती G (n−1) से केवल एक एकल से भिन्न होता है, मान लीजिए कि k-th, बिट (जो n−1 का सबसे सही शून्य बिट है), इसलिए सभी xn−1 को xn में प्रसारित करने के लिए प्रत्येक आयाम के लिए एक एकल XOR ऑपरेशन करने की आवश्यकता है, अर्थात। अतिरिक्त एकरूपता गुण 'सोबोल' ने अतिरिक्त एकरूपता स्थितियों की शुरुआत की जिन्हें गुण ए और ए 'के रूप में जाना जाता है। परिभाषा एक निम्न-विसंगति अनुक्रम को गुण ए को संतुष्ट करने के लिए कहा जाता है यदि लंबाई 2 डी के डी-आयामी अनुक्रम के किसी भी द्विआधारी खंड (एक मनमाना सबसेट नहीं) के लिए प्रत्येक 2 डी हाइपरक्यूब में बिल्कुल एक ड्रॉ होता है जो इकाई हाइपरक्यूब को इसके प्रत्येक लंबाई विस्तार के साथ आधे में उपविभाजित करने के परिणामस्वरूप होता है। परिभाषा एक निम्न-विसंगति अनुक्रम को गुण ए 'को संतुष्ट करने के लिए कहा जाता है यदि लंबाई 4 डी के डी-आयामी अनुक्रम के किसी भी द्विआधारी खंड (एक मनमाना सबसेट नहीं) के लिए प्रत्येक 4 डी हाइपरक्यूब में बिल्कुल एक ड्रॉ होता है जो इकाई हाइपरक्यूब को इसके प्रत्येक लंबाई विस्तार के साथ चार समान भागों में उपविभाजित करने के परिणामस्वरूप होता है। गणितीय स्थितियाँ हैं जो गुणों ए और ए 'की गारंटी देती हैं। प्रमेय डी-आयामी सोबोल अनुक्रम में गुण ए आई. एफ. एफ. होता है जहां वी. डी. डी. × डी. द्विआधारी मैट्रिक्स है जिसे वी. के., जे., एम. के साथ परिभाषित किया गया है जो दिशा संख्या वी. के., जे. = (0. वी. के., जे., 1वी. के., जे., 2.) 2 के द्विआधारी बिंदु के बाद एम.-वें अंक को दर्शाता है। प्रमेय डी-आयामी सोबोल अनुक्रम में गुण ए 'आई. एफ. एफ. होता है जहां उद 2 डी × 2 डी द्विआधारी मैट्रिक्स है जिसे वीके, जे, एम के साथ परिभाषित किया गया है जो दिशा संख्या वीके, जे = (0. वीके, जे, 1वीके, जे, 2.) 2 के द्विआधारी बिंदु के बाद एम-वें अंक को दर्शाता है। ए और ए 'गुणों के लिए परीक्षण स्वतंत्र हैं। इस प्रकार सोबोल अनुक्रम का निर्माण करना संभव है जो ए और ए दोनों गुणों या उनमें से केवल एक को संतुष्ट करता है। सोबोल 'संख्याओं का आरंभीकरण' सोबोल 'अनुक्रम के निर्माण के लिए, दिशा संख्या vi, j के एक समूह का चयन करने की आवश्यकता है। प्रारंभिक दिशा संख्याओं के चयन में कुछ स्वतंत्रता है। इसलिए, चयनित आयामों के लिए 'सोबोल' अनुक्रम की विभिन्न उपलब्धियां प्राप्त करना संभव है। प्रारंभिक संख्याओं का एक खराब चयन गणना के लिए उपयोग किए जाने पर 'सोबोल' अनुक्रमों की दक्षता को काफी कम कर सकता है। यकीनन आरंभीकरण संख्याओं के लिए सबसे आसान विकल्प सिर्फ एल-सबसे बाएँ बिट सेट होना है, और अन्य सभी बिट्स शून्य होना है, यानी। mk, j = 1 सभी k और j के लिए। इस आरंभीकरण को आमतौर पर इकाई आरंभीकरण कहा जाता है। हालाँकि, इस तरह का अनुक्रम कम आयामों के लिए भी गुण ए और ए के लिए परीक्षण में विफल रहता है और इसलिए यह आरंभीकरण खराब है। कार्यान्वयन और उपलब्धता विभिन्न आयामों के लिए अच्छी प्रारंभिक संख्याएँ कई लेखकों द्वारा प्रदान की जाती हैं। उदाहरण के लिए, 'सोबोल' 51 तक के आयामों के लिए प्रारंभिक संख्या प्रदान करता है। प्रारंभिक संख्या के एक ही समूह का उपयोग ब्रैटली और फॉक्स द्वारा किया जाता है। उच्च आयामों के लिए प्रारंभिक संख्याएँ जो और कुओ पर उपलब्ध हैं। पीटर जैकेल ने अपनी पुस्तक "मोंटे कार्लो मेथड्स इन फाइनेंस" में आयाम 32 तक की प्रारंभिक संख्याएँ प्रदान की हैं। सॉफ्टवेयर के संख्यात्मक व्यंजनों के संग्रह में अन्य कार्यान्वयन सी, फोरट्रान 77, या फोरट्रान 90 दिनचर्या के रूप में उपलब्ध हैं। जो और कुओ आरंभीकरण संख्या के आधार पर 1111 आयामों तक का एक मुक्त/मुक्त-स्रोत कार्यान्वयन सी में और पायथन और जूलिया में 21201 आयामों तक उपलब्ध है। सी + +, फोरट्रान 90, मैटलैब और पायथन के लिए 1111 आयामों तक एक अलग मुक्त/मुक्त-स्रोत कार्यान्वयन उपलब्ध है। अंत में, वाणिज्यिक 'सोबोल' अनुक्रम जनरेटर, उदाहरण के लिए, एनएजी पुस्तकालय के भीतर उपलब्ध हैं। एक संस्करण ब्रिटिश-रूसी अपतटीय विकास एजेंसी (बी. आर. ओ. डी. ए.) से उपलब्ध है। MATLAB में अपने सांख्यिकी टूलबॉक्स के हिस्से के रूप में एक कार्यान्वयन भी शामिल है। निम्न-विसंगति अनुक्रम अर्ध-मोंटे कार्लो विधि नोट्स संदर्भ बाहरी लिंक एसीएम के एकत्रित एल्गोरिदम भी देखें (एल्गोरिदम 647,659 और 738 देखें।) 'सोबोल' अनुक्रम जनरेटर प्रोग्रामिंग कोड का संग्रह 'सोबोल' अनुक्रम के फ्रीवेयर सी + + जनरेटर कम विसंगति वाले अनुक्रम अनुक्रम और श्रृंखला