KAPAN KOCOKAN OVERHAND MELUPAKAN URUTAN KARTU?

Mengocok kartu adalah versi konkret dari pertanyaan mendasar dalam teori peluang: berapa lama sebuah proses acak butuh waktu untuk melupakan titik awalnya? Tumpukan kartu yang baru dibuka tersusun berurutan. Setiap kocokan mengacaknya sedikit lagi, sampai tidak ada jejak urutan awal yang dapat dideteksi.

Para matematikawan membedakan dua tingkat jawaban. Waktu pengacakan (mixing time) memberikan orde besarnya. Sebuah cutoff mengatakan jauh lebih banyak: di sekitar satu saat yang tepat, tumpukan kartu beralih dari “jelas belum teracak” ke “teracak sempurna” hampir seketika. Kocok sedikit kurang dari itu dan Anda masih bisa melihatnya; kocok sedikit lebih lama dan Anda tidak bisa lagi.

Kocokan di mata matematikawan

Pada kocokan overhand, Anda memegang tumpukan kartu di satu tangan dan menjatuhkan paket-paket kecil kartu ke tangan lainnya. Makalah ini memodelkannya begini: setiap celah dari n − 1 celah di antara kartu-kartu yang bersebelahan dipotong secara independen dengan peluang p, dan urutan paket-paket yang dihasilkan dibalik. Satu putaran penuh melalui tumpukan dihitung sebagai satu kocokan.

Menurut makalah ini, penelitian sebelumnya sudah menetapkan orde besarnya. Pemantle membatasi waktu pengacakan antara n² dan n² log n; Jonasson kemudian menunjukkan bahwa n² log n adalah orde yang tepat. Namun konstanta tepatnya, dan apakah cutoff yang tajam benar-benar terjadi, masih terbuka: Diaconis dan Pal mencantumkan cutoff kocokan overhand sebagai masalah terbuka pada 2022.

Hasilnya

Yunjiang Jiang membuktikan bahwa cutoff itu ada dan menentukan letaknya.

Teorema. Untuk peluang potong p yang tetap, kocokan overhand mengacak, pada orde pertama, setelah

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

kocokan. Sedikit sebelumnya, tumpukan kartu masih jauh dari acak; sedikit sesudahnya, tumpukan itu sudah mendekati acak.

Untuk p = 1/2 — potongan di separuh celah secara rata-rata — rumus itu menjadi n² log n / (4π²).

Cara kerja pembuktiannya

Pembuktian ini terdiri atas tiga bagian yang independen.

1. Batas bawah mengikuti satu kartu. Posisinya berkembang dengan cara yang sangat rapi: pola berbentuk kosinus yang eksak meluruh dengan laju yang diketahui, bahkan untuk tumpukan berukuran hingga. Jika dijumlahkan atas seluruh tumpukan, pola-pola itu menyimpan jejak urutan awal yang dapat dideteksi hingga saat yang diramalkan.
2. Batas atas membandingkan dua tumpukan yang hanya berbeda karena dua kartu ditukar. Jika dikocok dengan potongan acak yang sama, perbedaannya berperilaku seperti dua posisi bertanda yang berkelana di dalam tumpukan sampai keduanya bersebelahan dan dapat bergabung. Laju terjadinya hal itu cocok dengan batas bawah.
3. Sebuah ketaksamaan statis tentang permutasi, yang tidak berkaitan dengan pengocokan, mengubah perbandingan ini menjadi pernyataan tentang seluruh tumpukan. Ini bagian paling teknis dari makalah, dibangun secara rekursif atas tabel-tabel yang menghitung bagaimana kartu tersebar di antara blok-blok.

Makalah ini juga membuktikan cutoff untuk ukuran ketidakteraturan lain, yaitu entropi relatif, tanpa menentukan letak tepatnya.

Apa kata rumus itu tentang tumpukan kartu sungguhan

Memasukkan tumpukan 52 kartu ke dalam rumus dengan p = 1/2 menghasilkan 52² × ln 52 / (4π²), sekitar 270 kocokan. Ini hitungan kami sendiri, bukan angka dari makalah, dan sebaiknya dibaca sebagai petunjuk kasar: teorema itu menggambarkan perilaku tumpukan yang sangat besar, dan suku koreksinya tidak dikuantifikasi. Sebagai pembanding, makalah ini mengutip skala (3/2) log₂ n yang ditetapkan Bayer dan Diaconis untuk kocokan riffle (riffle shuffle) — sekitar 8,6 untuk 52 kartu, dengan catatan yang sama. Jarak antara n² log n dan log n itulah yang membuat kocokan overhand begitu lambat.

Orde pertama, tangan yang diidealkan

Hasil ini berorde pertama: tidak memberikan lebar jendela transisi maupun bentuk tepatnya. Peluang potong dibuat tetap, dan potongan-potongan diandaikan independen, sebuah idealisasi dari tangan sungguhan. Dalam catatan kaki, penulis menyatakan bahwa sistem AI GPT-6 Astra “digunakan dalam mengembangkan argumen, memeriksa perhitungan, dan menyiapkan penyajian”, dan bahwa penulis bertanggung jawab atas isi matematisnya. Makalah ini berupa pracetak.