KUCHANGANYA KADI KWA MKONO HUSAHAU MPANGILIO LINI?

Kuchanganya kadi ni toleo halisi la swali la msingi katika uwezekano: mchakato wa nasibu huchukua muda gani kusahau ulikoanzia? Kifurushi cha kadi kilichofunguliwa sasa hivi kiko kwa mpangilio. Kila uchanganyaji hukivuruga kidogo zaidi, mpaka hakuna dalili yoyote ya mpangilio wa awali inayoweza kugunduliwa.

Wanahisabati hutofautisha viwango viwili vya jibu. Muda wa kuchanganyika (mixing time) hutoa kiwango cha ukubwa. Cutoff husema mengi zaidi: kuzunguka wakati mmoja maalum, kadi hubadilika kutoka “waziwazi hazijachanganyika” hadi “zimechanganyika kabisa” karibu mara moja. Changanya kidogo pungufu ya hapo na bado unaweza kutambua; changanya kidogo zaidi na huwezi.

Uchanganyaji, kama mwanahisabati anavyouona

Katika uchanganyaji wa overhand (overhand shuffle), unashika kadi kwa mkono mmoja na kudondosha mafungu madogo ya kadi kwenye mkono mwingine. Makala inauiga hivi: kila mwanya kati ya mianya n − 1 iliyo kati ya kadi jirani hukatwa kwa kujitegemea kwa uwezekano p, na mpangilio wa mafungu yanayotokea hugeuzwa. Mzunguko mmoja kamili kupitia kadi zote huhesabiwa kama uchanganyaji mmoja.

Kwa mujibu wa makala, kazi za awali zilikuwa tayari zimebainisha kiwango cha ukubwa. Pemantle aliweka muda wa kuchanganyika kati ya n² na n² log n; kisha Jonasson akaonyesha kwamba n² log n ndicho kiwango sahihi. Lakini kiasili kamili, na ikiwa cutoff kali hutokea kabisa, vilibaki wazi: Diaconis na Pal waliorodhesha cutoff ya overhand kama tatizo lililo wazi mwaka 2022.

Matokeo

Yunjiang Jiang anathibitisha kwamba cutoff ipo na anaibainisha mahali ilipo.

Nadharia. Kwa uwezekano maalum wa kukata p, uchanganyaji wa overhand huchanganyika, kwa kiwango cha kwanza, baada ya

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

michanganyiko. Kidogo kabla ya hapo, kadi zinabaki mbali na nasibu; kidogo baada yake, ziko karibu na nasibu.

Kwa p = 1/2 — kukata nusu ya mianya kwa wastani — fomula inakuwa n² log n / (4π²).

Jinsi uthibitisho unavyofanya kazi

Uthibitisho una sehemu tatu zinazojitegemea.

1. Mpaka wa chini unafuatilia kadi moja. Nafasi yake hubadilika kwa njia safi ya kushangaza: mifumo kamili yenye umbo la kosaini hufifia kwa kasi inayojulikana, hata kwa kifurushi chenye kadi chache. Zikijumlishwa katika kifurushi kizima, zinadumisha dalili inayoweza kugunduliwa ya mpangilio wa mwanzo mpaka wakati uliotabiriwa.
2. Mpaka wa juu unalinganisha vifurushi viwili vinavyotofautiana tu kwa kubadilishana kwa kadi mbili. Vikichanganywa kwa mikato ileile ya nasibu, tofauti hiyo hufanya kama nafasi mbili zilizowekwa alama zinazozurura ndani ya kifurushi mpaka zinapokuwa jirani na kuweza kuungana. Kasi ambayo hilo hutokea inalingana na mpaka wa chini.
3. Kutolingana tuli kuhusu vibali (permutations), kusikohusiana na uchanganyaji, kunageuza ulinganisho huu kuwa kauli kuhusu kifurushi kizima. Hii ndiyo sehemu ya kiufundi zaidi ya makala, iliyojengwa kwa kujirudia juu ya majedwali yanayohesabu jinsi kadi zilivyosambaa katika vitalu.

Makala pia inathibitisha cutoff kwa njia nyingine ya kupima vurugu, entropia linganishi, bila kubainisha mahali pake hasa.

Fomula inasema nini kuhusu kifurushi halisi

Kuweka kifurushi cha kadi 52 katika fomula na p = 1/2 kunatoa 52² × ln 52 / (4π²), takriban michanganyiko 270. Hii ni hesabu yetu wenyewe, si takwimu kutoka makalani, na inapaswa kusomwa kama dalili ya kukadiria: nadharia inaeleza tabia ya vifurushi vikubwa sana, na kipengele cha marekebisho hakijapimwa. Kwa kulinganisha, makala inataja kiwango cha (3/2) log₂ n kilichothibitishwa na Bayer na Diaconis kwa uchanganyaji wa riffle — takriban 8.6 kwa kadi 52, kwa tahadhari ileile. Pengo kati ya n² log n na log n ndilo linalofanya uchanganyaji wa overhand kuwa wa polepole hivyo.

Kiwango cha kwanza, mikono ya kinadharia

Tokeo hili ni la kiwango cha kwanza: halitoi upana wa dirisha la mpito wala umbo lake kamili. Uwezekano wa kukata umeshikiliwa thabiti, na mikato inadhaniwa kujitegemea, hali ya kinadharia isiyolingana kabisa na mikono halisi. Katika tanbihi, mwandishi anaeleza kwamba mfumo wa AI GPT-6 Astra “ulitumika katika kukuza hoja, kukagua hesabu, na kuandaa maelezo”, na kwamba mwandishi anawajibika kwa maudhui ya kihisabati. Makala hii ni chapisho la awali (preprint).