হাতে তাস ফেটালে প্যাকেট কখন তার ক্রম ভুলে যায়?

তাস ফেটানো সম্ভাবনাতত্ত্বের একটি মৌলিক প্রশ্নের বাস্তব রূপ: একটি দৈব প্রক্রিয়ার কোথা থেকে শুরু হয়েছিল তা ভুলে যেতে কত সময় লাগে? সদ্য খোলা প্যাকেট সাজানো থাকে। প্রতিবার ফেটানোয় এটি আরেকটু এলোমেলো হয়, যতক্ষণ না মূল ক্রমের কোনো চিহ্নই আর শনাক্ত করা যায়।

গণিতবিদেরা উত্তরের দুটি স্তরে পার্থক্য করেন। মিশ্রণ-সময় (mixing time) মাত্রার ক্রম জানায়। কাটঅফ (cutoff) জানায় অনেক বেশি: একটি নির্দিষ্ট মুহূর্তের আশপাশে প্যাকেটটি প্রায় হঠাৎই “স্পষ্টত অমিশ্রিত” থেকে “পুরোপুরি মিশ্রিত” অবস্থায় চলে যায়। তার চেয়ে একটু কম ফেটালে এখনো বোঝা যায়; একটু বেশি ফেটালে আর যায় না।

গণিতবিদের চোখে তাস ফেটানো

ওভারহ্যান্ড শাফলে আপনি প্যাকেটটি এক হাতে ধরে অন্য হাতে তাসের ছোট ছোট গোছা ফেলেন। গবেষণাপত্রটি এর মডেল বানায় এভাবে: পাশাপাশি তাসের মধ্যকার n − 1টি ফাঁকের প্রতিটি স্বাধীনভাবে p সম্ভাবনায় কাটা হয়, এবং তৈরি হওয়া গোছাগুলোর ক্রম উল্টে দেওয়া হয়। পুরো প্যাকেটের ওপর দিয়ে একবার যাওয়াকে একবার ফেটানো ধরা হয়।

গবেষণাপত্র অনুযায়ী, আগের কাজ ইতিমধ্যে মাত্রার ক্রম নির্ধারণ করেছিল। পেমান্টল (Pemantle) মিশ্রণ-সময়কে n² ও n² log n-এর মধ্যে বেঁধেছিলেন; পরে ইয়োনাসন (Jonasson) দেখান যে n² log n-ই সঠিক ক্রম। কিন্তু সঠিক ধ্রুবক, এবং আদৌ কোনো তীক্ষ্ণ কাটঅফ ঘটে কি না, তা অমীমাংসিত ছিল: ডায়াকোনিস (Diaconis) ও পাল (Pal) ২০২২ সালে ওভারহ্যান্ড কাটঅফকে একটি অমীমাংসিত সমস্যা হিসেবে তালিকাভুক্ত করেছিলেন।

ফলাফল

ইউনজিয়াং জিয়াং প্রমাণ করেন যে কাটঅফ আছে, এবং তার অবস্থান নির্ণয় করেন।

উপপাদ্য। একটি নির্দিষ্ট কাটার সম্ভাবনা p-এর জন্য, ওভারহ্যান্ড শাফল প্রথম ক্রমে মিশে যায়

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

বার ফেটানোয়। তার একটু আগে প্যাকেটটি দৈবতা থেকে অনেক দূরে থাকে; একটু পরে তা দৈবতার কাছাকাছি।

p = 1/2-এর জন্য — অর্থাৎ গড়ে অর্ধেক ফাঁকে কাটা — সূত্রটি হয় n² log n / (4π²)।

প্রমাণ কীভাবে কাজ করে

প্রমাণটির তিনটি স্বাধীন অংশ।

নিম্নসীমা একটিমাত্র তাসকে অনুসরণ করে। তার অবস্থান লক্ষণীয়ভাবে পরিচ্ছন্ন উপায়ে বদলায়: কোসাইন-আকৃতির নিখুঁত নকশাগুলো একটি জানা হারে ক্ষয় হয়, এমনকি সসীম প্যাকেটের জন্যও। পুরো প্যাকেট জুড়ে যোগ করলে এগুলো পূর্বাভাসিত মুহূর্ত পর্যন্ত প্রারম্ভিক ক্রমের একটি শনাক্তযোগ্য চিহ্ন ধরে রাখে।
ঊর্ধ্বসীমা এমন দুটি প্যাকেটের তুলনা করে যারা শুধু দুটি তাসের অদলবদলে আলাদা। একই দৈব কাটা দিয়ে চালালে, তাদের পার্থক্য আচরণ করে দুটি চিহ্নিত অবস্থানের মতো, যারা প্যাকেটের মধ্যে ঘুরে বেড়ায় যতক্ষণ না পাশাপাশি এসে মিশে যেতে পারে। এটি যে হারে ঘটে, তা নিম্নসীমার সঙ্গে মেলে।
বিন্যাস (permutation) সম্পর্কে একটি স্থির অসমতা, যার সঙ্গে ফেটানোর কোনো সম্পর্ক নেই, এই তুলনাকে পুরো প্যাকেট সম্পর্কে একটি বিবৃতিতে রূপান্তর করে। এটি গবেষণাপত্রের সবচেয়ে কারিগরি অংশ, এমন সারণির ওপর পুনরাবৃত্তি দিয়ে গড়া যা গোনে তাসগুলো ব্লকে কীভাবে ছড়িয়ে আছে।

গবেষণাপত্রটি বিশৃঙ্খলা মাপার আরেকটি উপায়, আপেক্ষিক এনট্রপি, এর জন্যও কাটঅফ প্রমাণ করে, তবে তার সঠিক অবস্থান নির্ণয় না করে।

আসল প্যাকেট সম্পর্কে সূত্রটি কী বলে

p = 1/2 নিয়ে সূত্রে ৫২ তাসের প্যাকেট বসালে পাওয়া যায় 52² × ln 52 / (4π²), অর্থাৎ প্রায় ২৭০ বার ফেটানো। এটি আমাদের নিজস্ব হিসাব, গবেষণাপত্রের সংখ্যা নয়, এবং একে মোটামুটি ইঙ্গিত হিসেবেই পড়া উচিত: উপপাদ্যটি খুব বড় প্যাকেটের আচরণ বর্ণনা করে, আর সংশোধনী পদটির পরিমাণ নির্ধারিত নয়। তুলনার জন্য, গবেষণাপত্রটি রিফল শাফলের জন্য বেয়ার (Bayer) ও ডায়াকোনিসের প্রতিষ্ঠিত (3/2) log₂ n মাপকাঠির উল্লেখ করে — ৫২ তাসের জন্য প্রায় ৮.৬, একই সতর্কতাসহ। n² log n আর log n-এর মধ্যকার ফারাকই ওভারহ্যান্ড শাফলকে এত ধীর করে।

প্রথম ক্রম, আদর্শায়িত হাত

ফলাফলটি প্রথম ক্রমের: এটি রূপান্তরের জানালার প্রস্থ বা তার সঠিক আকার দেয় না। কাটার সম্ভাবনা স্থির রাখা হয়েছে, এবং কাটাগুলোকে স্বাধীন ধরা হয়েছে, যা আসল হাতের একটি আদর্শায়ন। একটি পাদটীকায় লেখক জানান যে AI ব্যবস্থা GPT-6 Astra “যুক্তি গড়তে, হিসাব যাচাই করতে এবং উপস্থাপনা প্রস্তুত করতে ব্যবহৃত হয়েছে”, এবং গাণিতিক বিষয়বস্তুর দায়িত্ব লেখকের। গবেষণাপত্রটি একটি প্রিপ্রিন্ট।