YAUSHE CAKUDA KATIN HANNU-DA-HANNU KE MANTA TSARIN KATIN?

Cakuɗa kati sigar zahiri ce ta wata muhimmiyar tambaya a ilimin yiwuwa (probability): har yaushe tsari na barkatai ke ɗauka kafin ya manta inda ya fara? Sabon damin kati da aka buɗe yana cikin tsari. Kowace cakuɗa tana ɗan ƙara rikita shi, har sai ba za a iya gano wata alama ta tsarin farko ba.

Masana lissafi suna bambanta matakan amsa biyu. Lokacin cakuɗawa (mixing time) yana ba da girman adadi. Cutoff yana faɗi fiye da haka: a kewayen wani takamaiman lokaci, katin yana sauyawa daga “a fili ba a cakuɗa ba” zuwa “an cakuɗa sosai” kusan nan take. Idan ka cakuɗa ƙasa da haka kaɗan za ka iya gane bambanci; idan ka ɗan ƙara, ba za ka iya ba.

Cakuɗar, kamar yadda masanin lissafi ke ganinta

A cikin cakuda hannu-da-hannu, kana riƙe da katin a hannu ɗaya kuma kana zubar da ƙananan damin kati zuwa ɗayan. Takardar ta kwaikwayi haka: kowane ɗaya daga cikin gibi n − 1 da ke tsakanin katuna maƙwabta ana yanka shi daban da yiwuwar p, kuma ana juya tsarin damin da suka fito. Wucewa ɗaya cikakkiya ta cikin katin ita ce cakuɗa ɗaya.

Bisa ga takardar, ayyukan da suka gabata sun riga sun tantance girman adadin. Pemantle ya sanya lokacin cakuɗawa tsakanin n² da n² log n; Jonasson sannan ya nuna cewa n² log n shi ne girman da ya dace. Amma ainihin ƙayyadadden adadin, da ko cutoff mai kaifi yana faruwa ko kaɗan, sun kasance a buɗe: Diaconis da Pal sun sanya cutoff na cakuda hannu-da-hannu cikin matsalolin da ba a warware ba a 2022.

Sakamakon

Yunjiang Jiang ya tabbatar da cewa cutoff ɗin yana nan kuma ya gano inda yake.

Ka’ida. Ga ƙayyadaddiyar yiwuwar yanka p, cakuda hannu-da-hannu yana cakuɗawa, a matakin farko, a

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

cakuɗa. Ɗan kafin haka, katin yana nesa da barkatai; ɗan bayan haka, yana kusa da barkatai.

Ga p = 1/2 — yanka a rabin gibin a matsakaici — dabarar ta zama n² log n / (4π²).

Yadda hujjar ke aiki

Hujjar tana da sassa uku masu zaman kansu.

1. Iyakar ƙasa tana bin kati guda ɗaya. Matsayinsa yana canzawa ta hanya mai tsabta abin mamaki: ainihin tsare-tsare masu siffar cosine suna raguwa a sanannen sauri, ko da ga damin kati mai iyaka. Idan aka haɗa su a dukan katin, suna riƙe alamar tsarin farko da za a iya gano ta har zuwa lokacin da aka hasashe.
2. Iyakar sama tana kwatanta damin kati biyu da suka bambanta kawai da musanyar katuna biyu. Idan aka gudanar da su da yankan barkatai iri ɗaya, bambancin yana kama da wurare biyu masu alama da ke yawo cikin katin har sai sun zama maƙwabta kuma su haɗu. Saurin da hakan ke faruwa ya dace da iyakar ƙasa.
3. Wani rashin daidaito tsayayye game da permutations, wanda ba shi da alaƙa da cakuɗa, yana mayar da wannan kwatance zuwa bayani game da dukan katin. Shi ne ɓangare mafi fasaha na takardar, wanda aka gina ta maimaitawa (recursion) a kan teburan da ke ƙirga yadda katuna suka rarrabu a cikin tubala.

Takardar kuma ta tabbatar da cutoff ga wata hanyar auna rikicewa, relative entropy, ba tare da tantance ainihin wurinsa ba.

Abin da dabarar ke faɗi game da damin kati na gaske

Saka damin kati 52 cikin dabarar tare da p = 1/2 yana ba da 52² × ln 52 / (4π²), kusan cakuɗa 270. Wannan lissafinmu ne, ba adadi daga takardar ba, kuma ya kamata a karanta shi a matsayin ƙiyasi kawai: ka’idar tana bayyana halin manyan damin kati sosai, kuma ba a ƙididdige kalmar gyara ba. Don kwatance, takardar ta ambaci ma’aunin (3/2) log₂ n da Bayer da Diaconis suka tabbatar ga cakuda riffle — kusan 8.6 ga kati 52, tare da gargaɗi iri ɗaya. Tazarar da ke tsakanin n² log n da log n ita ce ke sa cakuda hannu-da-hannu ya yi jinkiri haka.

Matakin farko, hannaye na tunani

Sakamakon na matakin farko ne: ba ya ba da faɗin tagar sauyawar ko ainihin siffarta. Yiwuwar yanka tana nan tsayayye, kuma ana ɗauka cewa yankan suna da zaman kansu, wani tunanin hannaye na gaske. A cikin bayanin ƙasa, marubucin ya bayyana cewa an yi amfani da tsarin AI GPT-6 Astra “wajen haɓaka hujjoji, duba lissafi, da shirya bayani”, kuma marubucin ne ke da alhakin abin da ke cikin lissafin. Takardar preprint ce.