ओव्हरहँड पिसणे पत्त्यांचा क्रम केव्हा विसरते?

पत्ते पिसणे हे संभाव्यताशास्त्रातील एका मूलभूत प्रश्नाचे ठोस रूप आहे: एखादी यादृच्छिक प्रक्रिया आपण कुठून सुरुवात केली हे विसरायला किती वेळ घेते? नुकताच उघडलेला कॅट क्रमाने असतो. प्रत्येक पिसणे त्याला थोडे अधिक विस्कळीत करते, जोपर्यंत मूळ क्रमाचा कोणताही मागमूस ओळखता येत नाही.

गणितज्ञ उत्तराच्या दोन पातळ्या वेगळ्या करतात. मिसळण्याचा काळ (mixing time) परिमाणाचा क्रम देतो. कटऑफ (cutoff) त्याहून कितीतरी अधिक सांगतो: एका नेमक्या क्षणाभोवती कॅट “स्पष्टपणे न मिसळलेला” या स्थितीतून “पूर्णपणे मिसळलेला” या स्थितीत जवळजवळ एकाएकी जातो. त्यापेक्षा थोडे कमी पिसा, तर अजून ओळखता येते; थोडे अधिक पिसा, तर नाही.

गणितज्ञाच्या नजरेतून पिसणे

ओव्हरहँड पिसण्यात (overhand shuffle) तुम्ही कॅट एका हातात धरता आणि पत्त्यांचे लहान गठ्ठे दुसऱ्या हातात टाकता. शोधनिबंध याचे प्रारूप असे बनवतो: शेजारी असलेल्या पत्त्यांमधील 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. क्रमचयांविषयीची एक स्थिर असमानता, जिचा पिसण्याशी संबंध नाही, या तुलनेचे रूपांतर संपूर्ण कॅटविषयीच्या विधानात करते. हा शोधनिबंधातील सर्वात तांत्रिक भाग आहे, जो पत्ते खंडांमध्ये कसे पसरलेले आहेत हे मोजणाऱ्या तक्त्यांवर आवर्ती पद्धतीने रचला आहे.

शोधनिबंध विस्कळितपणा मोजण्याच्या आणखी एका पद्धतीसाठी, सापेक्ष एन्ट्रॉपीसाठी, कटऑफ सिद्ध करतो, पण त्याचे नेमके स्थान निश्चित न करता.

सूत्र खऱ्या कॅटबद्दल काय सांगते

p = 1/2 घेऊन 52 पत्त्यांचा कॅट सूत्रात घातल्यास 52² × ln 52 / (4π²), म्हणजे सुमारे 270 पिसणी मिळतात. हे आमचे स्वतःचे अंकगणित आहे, शोधनिबंधातील आकडा नव्हे, आणि ते ढोबळ सूचक म्हणून वाचले पाहिजे: प्रमेय अतिशय मोठ्या कॅटच्या वर्तनाचे वर्णन करतो, आणि दुरुस्ती-पद मोजलेले नाही. तुलनेसाठी, शोधनिबंध रिफल पिसण्यासाठी बेयर आणि डायकोनिस यांनी प्रस्थापित केलेल्या (3/2) log₂ n या प्रमाणाचा उल्लेख करतो — 52 पत्त्यांसाठी सुमारे 8.6, त्याच इशाऱ्यासह. n² log n आणि log n यांच्यातील दरीमुळेच ओव्हरहँड पिसणे इतके संथ ठरते.

प्रथम क्रम, आदर्शीकृत हात

हा निकाल प्रथम क्रमाचा आहे: तो संक्रमण-खिडकीची रुंदी किंवा तिचा नेमका आकार देत नाही. कापण्याची संभाव्यता स्थिर ठेवली आहे, आणि कापणी स्वतंत्र असल्याचे गृहीत धरले आहे, जे खऱ्या हातांचे आदर्शीकरण आहे. एका तळटिपेत लेखक नमूद करतात की GPT-6 Astra ही एआय प्रणाली “युक्तिवाद विकसित करण्यात, गणने तपासण्यात आणि मांडणी तयार करण्यात वापरली गेली”, आणि गणितीय आशयाची जबाबदारी लेखकाची आहे. हा शोधनिबंध एक प्रीप्रिंट आहे.