بُر زدن دست‌به‌دست کِی ترتیب دسته را فراموش می‌کند؟

بُر زدن ورق نسخه‌ای ملموس از یک پرسش بنیادی در احتمالات است: یک فرایند تصادفی چقدر طول می‌کشد تا نقطهٔ آغازش را فراموش کند؟ دسته‌ای که تازه باز شده مرتب است. هر بُر آن را کمی بیشتر درهم می‌کند، تا جایی که هیچ ردی از ترتیب اولیه قابل تشخیص نباشد.

ریاضی‌دانان دو سطح پاسخ را از هم جدا می‌کنند. زمان آمیختن (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. نابرابری‌ای ایستا دربارهٔ جایگشت‌ها، بی‌ارتباط با بُر زدن، این مقایسه را به گزاره‌ای دربارهٔ کل دسته تبدیل می‌کند. این فنی‌ترین بخش مقاله است و به‌صورت بازگشتی روی جدول‌هایی ساخته شده که پخش شدن ورق‌ها در بلوک‌ها را می‌شمارند.

مقاله همچنین برای شیوهٔ دیگری از سنجش بی‌نظمی، یعنی آنتروپی نسبی، برش‌گاهی اثبات می‌کند، بی‌آنکه جای دقیقش را تعیین کند.

فرمول دربارهٔ یک دستهٔ واقعی چه می‌گوید

قرار دادن دسته‌ای 52 برگی در فرمول با p = 1/2 عدد 52² × ln 52 / (4π²)، یعنی حدود 270 بُر، را می‌دهد. این محاسبهٔ خود ماست، نه رقمی از مقاله، و باید آن را نشانه‌ای تقریبی خواند: قضیه رفتار دسته‌های بسیار بزرگ را توصیف می‌کند و جملهٔ تصحیح کمّی نشده است. برای مقایسه، مقاله به مقیاس (3/2) log₂ n ارجاع می‌دهد که بایر و دیاکونیس برای بُر ریفل (riffle shuffle) اثبات کردند — حدود 8.6 برای 52 ورق، با همان قید. فاصلهٔ میان n² log n و log n همان چیزی است که بُر دست‌به‌دست را این‌قدر کند می‌کند.

مرتبهٔ نخست، دست‌های آرمانی

نتیجه از مرتبهٔ نخست است: پهنای پنجرهٔ گذار یا شکل دقیق آن را نمی‌دهد. احتمال برش ثابت نگه داشته می‌شود و برش‌ها مستقل فرض می‌شوند، که آرمانی‌سازی دست‌های واقعی است. نویسنده در پانویسی اعلام می‌کند که سامانهٔ هوش مصنوعی GPT-6 Astra «در پروراندن استدلال‌ها، وارسی محاسبات و آماده‌سازی متن» به کار رفته و مسئولیت محتوای ریاضی با نویسنده است. مقاله یک پیش‌انتشار است.