बिना प्रतिस्थापन के चयन का गणित

50 के पूल में से 5 अद्वितीय संख्याओं का चयन करना संयोजन-विज्ञान (combinatorics) की एक मूलभूत क्रिया है। परिणाम एक संयोजन होता है: एक ऐसा सेट जिसमें क्रम मायने नहीं रखता और पुनरावृत्ति वर्जित है। संभावित परिणामों की संख्या द्विपद गुणांक C(50, 5) = 2,118,760 से निर्धारित होती है। इनमें से प्रत्येक संयोजन के प्रकट होने की प्रायिकता बिल्कुल समान है। यह निष्पक्ष प्रतिचयन (fair sampling) की गणितीय गारंटी है।

फिशर-येट्स एल्गोरिदम

1938 में, रोनाल्ड फिशर और फ्रैंक येट्स ने अपनी पुस्तक Statistical Tables for Biological, Agricultural and Medical Research में यादृच्छिक क्रमचय (random permutations) उत्पन्न करने की एक विधि प्रकाशित की। यह एल्गोरिदम पूल में से प्रत्येक स्थिति को शेष तत्वों में से यादृच्छिक रूप से चुनी गई स्थिति के साथ अदला-बदली करके काम करता है। उपसमुच्चय निकालने के लिए, केवल पहले k अदला-बदली की आवश्यकता होती है। यह आंशिक शफ़ल O(k) समय में चलता है और गारंटी देता है कि k आइटमों का प्रत्येक संयोजन समान रूप से संभावित है, बशर्ते अंतर्निहित यादृच्छिक स्रोत एकसमान हो।

इस पृष्ठ का टूल crypto.getRandomValues() द्वारा संचालित आंशिक फिशर-येट्स शफ़ल लागू करता है, जो आपके ब्राउज़र में निर्मित Web Cryptography API है। यह वही एन्ट्रॉपी स्रोत है जो TLS कनेक्शन और एन्क्रिप्टेड मैसेजिंग को सुरक्षित करता है। हार्डवेयर-स्तरीय थर्मल शोर और विद्युत जिटर ऐसी यादृच्छिकता उत्पन्न करते हैं जिसे क्वांटम यांत्रिकी मूलभूत रूप से अप्रत्याशित सिद्ध करती है। एल्गोरिदम पूर्णतः आपके उपकरण पर चलता है। सर्वर इस पृष्ठ को वितरित करता है और इसके अलावा कुछ नहीं करता।

आश्चर्यजनक ओवरलैप

ओवरलैप प्रायिकता का अनुमान लगाने में अंतर्ज्ञान बुरी तरह विफल होता है। यदि दो लोग स्वतंत्र रूप से 1 से 50 में से 5 संख्याएँ निकालें, तो कम से कम एक संख्या समान होने की संभावना क्या है? 50 में से 5 के लिए, उत्तर लगभग 42% है। लगभग आधी बार, दो स्वतंत्र ड्रॉ कम से कम एक मान पर मेल खाएँगे। यह जन्मदिन समस्या (birthday problem) का एक रूपांतर है, जो प्रायिकता सिद्धांत के सबसे प्रसिद्ध प्रतिज्ञानात्मक परिणामों में से एक है। मूल जन्मदिन सूत्रीकरण दिखाता है कि केवल 23 लोगों के समूह में, साझा जन्मदिन की प्रायिकता 50% से अधिक हो जाती है। तंत्र वही है: तुलना करने के लिए लोगों की अपेक्षा कहीं अधिक जोड़ियाँ होती हैं।

व्यवहार में प्रतिचयन

बिना प्रतिस्थापन के यादृच्छिक प्रतिचयन सर्वेक्षण पद्धति, नैदानिक परीक्षणों और गुणवत्ता नियंत्रण की रीढ़ है। जेर्ज़ी नेमैन ने 1934 में प्रतिचयन के गणितीय सिद्धांत को औपचारिक रूप दिया, यह स्थापित करते हुए कि एक उचित रूप से निकाला गया यादृच्छिक प्रतिदर्श पूरी जनसंख्या के बारे में वैध अनुमान लगाने की अनुमति देता है। जब कोई दवा कंपनी लाखों की जनसंख्या में से 500 रोगियों पर एक नई चिकित्सा का परीक्षण करती है, तो चयन प्रक्रिया की निष्पक्षता ही परिणामों को सामान्यीकरण योग्य बनाती है। प्रत्येक रोगी के शामिल होने की समान प्रायिकता होनी चाहिए, और कोई भी रोगी दो बार प्रकट नहीं हो सकता। अमूर्त रूप में "एक सीमा से अद्वितीय यादृच्छिक संख्याएँ" ठीक यही करती हैं।

कक्षा में

यादृच्छिक संख्या सेट एक बहुमुखी शिक्षण उपकरण हैं। प्रत्येक छात्र से /numbers/6/1/49 पर जाकर एक सेट निकालने को कहें। कक्षा से पूछें कि कितने छात्रों की कम से कम एक संख्या किसी सहपाठी से मिलेगी, फिर सत्यापित करें। पूर्वानुमान और वास्तविकता के बीच का अंतर सशर्त प्रायिकता और जन्मदिन समस्या पर चर्चा के लिए एक उपयोगी प्रारंभ बिंदु है। अधिक उन्नत पाठ के लिए, छात्रों से बार-बार 50 में से 5 निकालने और चलित औसत (running average) को ट्रैक करने को कहें। इस पृष्ठ का अभिसरण चार्ट वास्तविक समय में कक्षा के औसत को 25.5 की ओर बढ़ते दिखाता है।

यह टूल URL के माध्यम से किसी भी पाठ योजना के अनुसार अनुकूलित होता है। छोटे सेट खोजने वाले छोटे छात्रों के लिए /numbers/3/1/10 या बड़े अन्वेषण के लिए /numbers/10/1/100 आज़माएँ। कोई खाता नहीं, कोई साइन-अप नहीं, कोई डेटा संग्रह नहीं। छात्र टूल का उपयोग करते हैं और कोई निशान नहीं छोड़ते।

आर्किटेक्चर द्वारा गोपनीय

इस पृष्ठ पर प्रत्येक संख्या सेट पूर्णतः आपके ब्राउज़र के अंदर उत्पन्न होता है। सर्वर URL में अपने पैरामीटर के साथ पृष्ठ वितरित करता है। आपका उपकरण Web Cryptography API से हार्डवेयर-सीडेड यादृच्छिकता का उपयोग करके यादृच्छिक परिणाम बनाता है। आपका ड्रॉ इतिहास आपके ब्राउज़र के localStorage में रहता है, केवल आपके नियंत्रण में। URL साझा करने से टूल कॉन्फ़िगरेशन किसी मित्र को भेजा जाता है, और उनका उपकरण पूर्णतः स्वतंत्र परिणाम उत्पन्न करता है। एक ही लिंक पर जाने वाले दो लोग लगभग निश्चित रूप से अलग-अलग संख्या सेट देखेंगे। URL टूल को ले जाता है। आपका उपकरण यादृच्छिकता को ले जाता है।