கைக்குக் கை கலைத்தல் சீட்டுக்கட்டை எப்போது மறக்கிறது?

சீட்டுக் கலைத்தல் என்பது நிகழ்தகவுக் கோட்பாட்டின் ஒரு அடிப்படைக் கேள்வியின் உருவான வடிவம்: ஒரு தற்செயல் செயல்முறை தான் எங்கே தொடங்கியது என்பதை மறக்க எவ்வளவு நேரம் ஆகும்? புதிதாகத் திறக்கப்பட்ட சீட்டுக்கட்டு வரிசையில் இருக்கிறது. ஒவ்வொரு கலைத்தலும் அதைச் சற்று அதிகமாகக் குலைக்கிறது; இறுதியில் மூல வரிசையின் எந்தத் தடயத்தையும் கண்டறிய முடியாது.

கணிதவியலாளர்கள் இரண்டு நிலை விடைகளை வேறுபடுத்துகின்றனர். கலப்பு நேரம் (mixing time) அளவின் வரிசையைத் தருகிறது. வெட்டுநிலை (cutoff) இன்னும் அதிகம் சொல்கிறது: ஒரு துல்லியமான கணத்தைச் சுற்றி, சீட்டுக்கட்டு “வெளிப்படையாகக் கலக்காதது” என்பதிலிருந்து “முழுமையாகக் கலந்தது” என்பதற்கு ஏறக்குறைய ஒரே கணத்தில் மாறுகிறது. அதைவிடச் சற்றுக் குறைவாகக் கலைத்தால் இன்னும் வேறுபாட்டைக் கண்டறியலாம்; சற்று அதிகமாகக் கலைத்தால் முடியாது.

ஒரு கணிதவியலாளரின் பார்வையில் கலைத்தல்

கைக்குக் கை கலைத்தலில், சீட்டுக்கட்டை ஒரு கையில் பிடித்து, சிறிய சீட்டுக் கட்டுகளை மறு கையில் போடுகிறீர்கள். ஆய்வுக் கட்டுரை இதை இப்படி மாதிரியாக்குகிறது: அடுத்தடுத்த சீட்டுகளுக்கு இடையிலான n − 1 இடைவெளிகள் ஒவ்வொன்றும் p நிகழ்தகவுடன் தனித்தனியாக வெட்டப்படுகிறது; உருவாகும் கட்டுகளின் வரிசை தலைகீழாக்கப்படுகிறது. சீட்டுக்கட்டு முழுவதையும் ஒருமுறை கடப்பது ஒரு கலைத்தலாகக் கணக்கிடப்படுகிறது.

கட்டுரையின்படி, முந்தைய ஆய்வுகள் அளவின் வரிசையை ஏற்கெனவே நிர்ணயித்திருந்தன. பெமான்டில் கலப்பு நேரத்தை n²-க்கும் n² log n-க்கும் இடையே அடைத்தார்; பின்னர் யோனாசன் n² log n தான் சரியான வரிசை என்று காட்டினார். ஆனால் சரியான மாறிலியும், கூர்மையான வெட்டுநிலை நிகழ்கிறதா என்பதும் திறந்தே இருந்தன: டயக்கோனிஸும் பாலும் 2022-இல் கைக்குக் கை கலைத்தலின் வெட்டுநிலையைத் தீர்க்கப்படாத சிக்கலாகப் பட்டியலிட்டிருந்தனர்.

முடிவு

வெட்டுநிலை உள்ளது என்று யுன்ஜியாங் ஜியாங் நிறுவி, அதன் இடத்தையும் கண்டறிகிறார்.

தேற்றம். நிலையான வெட்டு நிகழ்தகவு p-க்கு, கைக்குக் கை கலைத்தல் முதல் வரிசையில்

p² / (2(1 − p)π²) × n² log n

கலைத்தல்களில் கலக்கிறது. சற்று முன்பு, சீட்டுக்கட்டு சீரற்ற நிலையிலிருந்து தொலைவில் இருக்கிறது; சற்றுப் பின்பு, சீரற்ற நிலைக்கு அருகில் இருக்கிறது.

p = 1/2 என்றால் — சராசரியாகப் பாதி இடைவெளிகளில் வெட்டு — சூத்திரம் n² log n / (4π²) ஆகிறது.

நிரூபணம் எப்படிச் செயல்படுகிறது

நிரூபணத்துக்கு ஒன்றையொன்று சாராத மூன்று பகுதிகள் உள்ளன.

1. கீழ் வரம்பு ஒரே ஒரு சீட்டைப் பின்தொடர்கிறது. அதன் நிலை வியக்கத்தக்க வகையில் தெளிவாக மாறுகிறது: துல்லியமான கொசைன் வடிவ அமைப்புகள், வரம்புள்ள சீட்டுக்கட்டுக்குக் கூட, அறியப்பட்ட வீதத்தில் தணிகின்றன. சீட்டுக்கட்டு முழுவதும் கூட்டினால், அவை தொடக்க வரிசையின் கண்டறியக்கூடிய தடயத்தை முன்கணித்த கணம் வரை தக்கவைக்கின்றன.
2. மேல் வரம்பு, இரண்டு சீட்டுகளின் இடமாற்றத்தால் மட்டுமே வேறுபடும் இரண்டு சீட்டுக்கட்டுகளை ஒப்பிடுகிறது. ஒரே தற்செயல் வெட்டுகளுடன் இயக்கினால், அந்த வேறுபாடு, அண்டை நிலைகளாகி இணையும் வரை சீட்டுக்கட்டுக்குள் அலையும் குறிக்கப்பட்ட இரண்டு நிலைகள் போல நடந்துகொள்கிறது. அது நிகழும் வீதம் கீழ் வரம்புடன் பொருந்துகிறது.
3. கலைத்தலுடன் தொடர்பில்லாத, வரிசைமாற்றங்கள் (permutations) பற்றிய ஒரு நிலையான சமனின்மை, இந்த ஒப்பீட்டை முழுச் சீட்டுக்கட்டு பற்றிய கூற்றாக மாற்றுகிறது. இதுவே கட்டுரையின் மிகத் தொழில்நுட்பமான பகுதி; சீட்டுகள் தொகுதிகளில் எப்படிப் பரவியுள்ளன என்பதை எண்ணும் அட்டவணைகளின் மீது சுழல்முறையில் (recursion) கட்டப்பட்டது.

ஒழுங்கின்மையை அளக்கும் மற்றொரு வழியான சார்பு என்ட்ரோப்பிக்கும் (relative entropy) கட்டுரை ஒரு வெட்டுநிலையை நிறுவுகிறது; ஆனால் அதன் சரியான இடத்தை நிர்ணயிக்கவில்லை.

உண்மையான சீட்டுக்கட்டு பற்றிச் சூத்திரம் சொல்வது

52 சீட்டுக் கட்டை p = 1/2 உடன் சூத்திரத்தில் பொருத்தினால் 52² × ln 52 / (4π²), அதாவது சுமார் 270 கலைத்தல்கள் கிடைக்கின்றன. இது எங்கள் சொந்தக் கணக்கு, கட்டுரையில் உள்ள எண் அல்ல; தோராயமான சுட்டியாகவே படிக்க வேண்டும்: தேற்றம் மிகப் பெரிய சீட்டுக்கட்டுகளின் நடத்தையை விவரிக்கிறது; திருத்த உறுப்பு அளவிடப்படவில்லை. ஒப்பீட்டுக்கு, ரிஃபிள் கலைத்தலுக்கு (riffle shuffle) பேயரும் டயக்கோனிஸும் நிறுவிய (3/2) log₂ n அளவைக் கட்டுரை மேற்கோள் காட்டுகிறது — 52 சீட்டுகளுக்குச் சுமார் 8.6, அதே எச்சரிக்கையுடன். n² log n-க்கும் log n-க்கும் இடையிலான இடைவெளிதான் கைக்குக் கை கலைத்தலை இவ்வளவு மெதுவாக்குகிறது.

முதல் வரிசை, இலட்சியக் கைகள்

முடிவு முதல் வரிசையிலானது: மாற்றச் சாளரத்தின் அகலத்தையோ அதன் சரியான வடிவத்தையோ தரவில்லை. வெட்டு நிகழ்தகவு நிலையாக வைக்கப்படுகிறது; வெட்டுகள் ஒன்றையொன்று சாராதவை எனக் கருதப்படுகின்றன — இது உண்மையான கைகளின் இலட்சியப்படுத்தல். ஒரு அடிக்குறிப்பில், GPT-6 Astra என்ற AI அமைப்பு “வாதங்களை உருவாக்குவதிலும், கணக்குகளைச் சரிபார்ப்பதிலும், விளக்கத்தைத் தயாரிப்பதிலும் பயன்படுத்தப்பட்டது” என்றும், கணித உள்ளடக்கத்துக்குத் தானே பொறுப்பு என்றும் ஆசிரியர் கூறுகிறார். இந்தக் கட்டுரை ஒரு முன்பதிப்பு.