اوور ہینڈ پھینٹنا تاش کی گڈی کو کب بھولتا ہے؟

تاش پھینٹنا احتمالات کے ایک بنیادی سوال کی ٹھوس شکل ہے: کسی بے ترتیب عمل کو یہ بھولنے میں کتنا وقت لگتا ہے کہ وہ کہاں سے شروع ہوا تھا؟ نئی کھولی گئی گڈی ترتیب میں ہوتی ہے۔ ہر پھینٹ اسے تھوڑا اور گڈمڈ کرتی ہے، یہاں تک کہ اصل ترتیب کا کوئی نشان باقی نہیں رہتا جسے پہچانا جا سکے۔

ریاضی دان جواب کی دو سطحوں میں فرق کرتے ہیں۔ ملانے کا وقت (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π²) بن جاتا ہے۔

ثبوت کیسے کام کرتا ہے

ثبوت کے تین آزاد حصے ہیں۔

نچلی حد ایک اکیلے پتے کا پیچھا کرتی ہے۔ اس کا مقام نمایاں طور پر صاف انداز میں بدلتا ہے: کوسائن کی شکل کے قطعی نمونے ایک معلوم شرح سے ماند پڑتے ہیں، محدود گڈی کے لیے بھی۔ پوری گڈی پر جمع کیے جائیں تو وہ پیش گوئی کیے گئے لمحے تک ابتدائی ترتیب کا قابلِ شناخت نشان برقرار رکھتے ہیں۔
بالائی حد دو ایسی گڈیوں کا موازنہ کرتی ہے جن میں صرف دو پتوں کی جگہ بدلی ہوئی ہو۔ ایک جیسے بے ترتیب کٹوں کے ساتھ پھینٹنے پر یہ فرق دو نشان زد مقامات کی طرح برتاؤ کرتا ہے جو گڈی میں بھٹکتے رہتے ہیں یہاں تک کہ پڑوسی بن جائیں اور ضم ہو سکیں۔ ایسا ہونے کی شرح نچلی حد سے مطابقت رکھتی ہے۔
ترتیب بدلیوں (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 “دلائل تیار کرنے، حسابات جانچنے اور پیش کش کی تیاری میں استعمال ہوا”، اور یہ کہ ریاضیاتی مواد کی ذمہ داری مصنف کی ہے۔ مقالہ ایک پری پرنٹ ہے۔