निष्पक्ष शफ़लिंग का गणित

शफ़ल एक सटीक गणितीय प्रश्न प्रस्तुत करता है: n विभिन्न वस्तुओं में से, n! संभावित क्रमों में से एक उत्पन्न करें, प्रत्येक की समान संभावना के साथ। 20 पूर्णांकों के लिए, इसका अर्थ है 2.43 × 10¹⁸ क्रमचय। ऊपर दिया गया अनुक्रम उस समष्टि से समान संभावना के साथ चुना गया था, जो पूरी तरह से आपके ब्राउज़र के अंदर फिशर-येट्स एल्गोरिदम और Web Cryptography API का उपयोग करके उत्पन्न किया गया था।

फिशर-येट्स: निर्णायक एल्गोरिदम

रोनाल्ड फिशर और फ्रैंक येट्स ने अपनी 1938 की पुस्तक Statistical Tables for Biological, Agricultural and Medical Research में मूल शफ़लिंग विधि का वर्णन किया। डोनाल्ड नूथ ने बाद में The Art of Computer Programming (1969) में इसे कंप्यूटर कार्यान्वयन के लिए परिष्कृत किया। आधुनिक संस्करण सरणी में पीछे की ओर चलता है। प्रत्येक स्थिति पर, यह शेष अशफ़ल भाग से एक यादृच्छिक तत्व चुनता है और उन्हें अदला-बदली करता है। डेटा के एक ही पास में O(n) समय और O(1) अतिरिक्त स्थान का उपयोग करके एक पूर्ण समान शफ़ल उत्पन्न होता है।

शुद्धता का प्रमाण दर्शाता है कि स्थिति k को संसाधित करने के बाद, पहले k तत्वों की k! संभावित उप-व्यवस्थाओं में से प्रत्येक समान रूप से संभावित है। आगमन द्वारा, अंतिम परिणाम समान संभावना के साथ सभी n! क्रमचयों को कवर करता है। एक सामान्य कार्यान्वयन त्रुटि, "सरल शफ़ल," असंसाधित भाग के बजाय प्रत्येक चरण में पूरी सरणी से चयन करती है। यह nⁿ अदला-बदली अनुक्रम उत्पन्न करता है जो n! क्रमचयों पर मैप होते हैं। चूँकि nⁿ आम तौर पर n! से अविभाज्य होता है, कुछ क्रमचय दूसरों की तुलना में अधिक संभावित हो जाते हैं। फिशर-येट्स एल्गोरिदम इससे पूरी तरह बचता है।

क्रमचयों का चौंकाने वाला पैमाना

क्रमगुणन वृद्धि हर अन्य सामान्य गणितीय फलन से आगे निकल जाती है। दस वस्तुएँ 3,628,800 व्यवस्थाएँ उत्पन्न करती हैं। बीस वस्तुएँ 2.4 क्विंटिलियन से अधिक उत्पन्न करती हैं। 52 कार्ड की एक मानक डेक लगभग 8.07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7 संभावित क्रम उत्पन्न करती है। यह संख्या अवलोकनीय ब्रह्मांड में परमाणुओं की अनुमानित संख्या से अधिक है।

विचार करें: यदि ब्रह्मांड का हर परमाणु प्रति नैनोसेकंड एक बार डेक शफ़ल करता, और 13.8 अरब वर्ष पहले बिग बैंग से ऐसा करता आ रहा होता, तो भी कुल शफ़ल 52! का एक नगण्य अंश ही होते। इस पृष्ठ पर आपके द्वारा किया गया हर शफ़ल लगभग निश्चित रूप से एक ऐसी व्यवस्था बनाता है जो पहले कभी अस्तित्व में नहीं थी और फिर कभी नहीं होगी।

स्थिर बिंदु: विक्षोभ विरोधाभास

एक स्थिर बिंदु वह संख्या है जो शफ़ल करने के बाद अपनी मूल स्थिति में रहती है। ऊपर सुनहरी रिंग वाले वृत्तों को देखें: वे आपके स्थिर बिंदु हैं। स्थिर बिंदुओं की अपेक्षित संख्या ठीक 1 है, चाहे आप कितनी भी वस्तुएँ शफ़ल करें। दस वस्तुएँ, एक अपेक्षित स्थिर बिंदु। दस हज़ार वस्तुएँ, फिर भी एक।

किसी विशिष्ट तत्व के स्थिर रहने की संभावना 1/n है। n तत्वों पर योग करने पर, अपेक्षित गणना 1 के बराबर होती है। यह परिणाम, लियोनहार्ड ऑयलर द्वारा अध्ययन किए गए विक्षोभ की गणितीय अवधारणा से जुड़ा है, इसका अर्थ है कि लगभग 36.8% शफ़ल में शून्य स्थिर बिंदु होते हैं, 36.8% में ठीक एक, 18.4% में ठीक दो, और उसके बाद संभावनाएँ तेज़ी से गिरती हैं।

सात-शफ़ल प्रमेय

पर्सी डायकोनिस और डेव बेयर ने 1992 में सिद्ध किया कि 52 कार्ड की डेक के एक मानक रिफ़ल शफ़ल को पर्याप्त यादृच्छिकीकरण तक पहुँचने के लिए ठीक सात पुनरावृत्तियों की आवश्यकता होती है। एक डिजिटल फिशर-येट्स शफ़ल वही हासिल करता है जो सात भौतिक रिफ़ल शफ़ल अनुमानित करते हैं: एक कम्प्यूटेशनल पास में पूर्ण समान यादृच्छिकीकरण।

कक्षा में

प्रत्येक छात्र से /sequence/1/10 पर जाकर एक बार शफ़ल करने को कहें। फिर पूछें: क्या किसी दो छात्रों का क्रम एक जैसा आया? 3,628,800 संभावित व्यवस्थाओं के साथ, मिलान होना असाधारण रूप से असंभव है। प्रोजेक्टर प्रदर्शन के लिए, /sequence/1/52 खोलें और बार-बार शफ़ल करें। जीवंत रिंग हर बार नए पैटर्न में बिखरती हैं, जिससे यादृच्छिकता तुरंत दृश्य हो जाती है। इस टूल को किसी खाते की आवश्यकता नहीं है, कोई कुकीज़ सेट नहीं करता, और कोई छात्र डेटा संग्रहीत नहीं करता।