ఓవర్‌హ్యాండ్ షఫుల్ కట్ట క్రమాన్ని ఎప్పుడు మరచిపోతుంది?

పేకముక్కలను కలపడం అనేది సంభావ్యతా శాస్త్రంలోని ఒక ప్రాథమిక ప్రశ్నకు స్పష్టమైన రూపం: ఒక యాదృచ్ఛిక ప్రక్రియ తాను ఎక్కడ మొదలైందో మరచిపోవడానికి ఎంత సమయం పడుతుంది? అప్పుడే తెరిచిన కట్ట క్రమంలో ఉంటుంది. ప్రతి షఫుల్ దానిని కొంచెం ఎక్కువగా కలగాపులగం చేస్తుంది, అసలు క్రమం యొక్క ఏ జాడా గుర్తించలేనంత వరకు.

గణిత శాస్త్రవేత్తలు జవాబుకు రెండు స్థాయిలను వేరు చేస్తారు. మిక్సింగ్ సమయం (mixing time) పరిమాణపు క్రమాన్ని ఇస్తుంది. కటాఫ్ (cutoff) దానికంటే చాలా ఎక్కువ చెబుతుంది: ఒక కచ్చితమైన క్షణం చుట్టూ, కట్ట “స్పష్టంగా కలవలేదు” నుంచి “పూర్తిగా కలిసింది” స్థితికి దాదాపు ఒక్కసారిగా మారుతుంది. దానికంటే కొంచెం తక్కువ షఫుల్ చేస్తే ఇంకా గుర్తించగలరు; కొంచెం ఎక్కువ చేస్తే గుర్తించలేరు.

గణిత శాస్త్రవేత్త దృష్టిలో షఫుల్

ఓవర్‌హ్యాండ్ షఫుల్‌లో (overhand shuffle) మీరు కట్టను ఒక చేతిలో పట్టుకుని, ముక్కల చిన్న గుట్టలను మరో చేతిలోకి వదులుతారు. పరిశోధనా పత్రం దీనిని ఇలా నమూనాగా రూపొందిస్తుంది: పక్కపక్క ముక్కల మధ్య ఉన్న 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. ప్రస్తారాల గురించిన ఒక స్థిర అసమానత, షఫులింగ్‌తో సంబంధం లేనిది, ఈ పోలికను మొత్తం కట్ట గురించిన ప్రకటనగా మారుస్తుంది. ఇది పత్రంలో అత్యంత సాంకేతిక భాగం, ముక్కలు ఖండాల్లో ఎలా విస్తరించి ఉన్నాయో లెక్కించే పట్టికలపై పునరావృతం ద్వారా నిర్మించబడింది.

గందరగోళాన్ని కొలిచే మరో విధానమైన సాపేక్ష ఎంట్రోపీకి కూడా పత్రం కటాఫ్‌ను నిరూపిస్తుంది, కానీ దాని కచ్చితమైన స్థానాన్ని నిర్ధారించకుండా.

నిజమైన కట్ట గురించి సూత్రం ఏమి చెబుతుంది

p = 1/2తో 52 ముక్కల కట్టను సూత్రంలో పెడితే 52² × ln 52 / (4π²), అంటే సుమారు 270 షఫుల్‌లు వస్తాయి. ఇది మా సొంత లెక్క, పత్రంలోని అంకె కాదు, దీనిని స్థూల సూచికగా చదవాలి: సిద్ధాంతం చాలా పెద్ద కట్టల ప్రవర్తనను వర్ణిస్తుంది, సవరణ పదాన్ని పరిమాణీకరించలేదు. పోలిక కోసం, రిఫిల్ షఫుల్‌కు బేయర్, డయకోనిస్ నిర్ధారించిన (3/2) log₂ n స్థాయిని పత్రం ఉదహరిస్తుంది — 52 ముక్కలకు సుమారు 8.6, అదే హెచ్చరికతో. n² log n, log n మధ్య ఉన్న అంతరమే ఓవర్‌హ్యాండ్ షఫుల్‌ను ఇంత నెమ్మదిగా చేస్తుంది.

ప్రథమ క్రమం, ఆదర్శీకరించిన చేతులు

ఈ ఫలితం ప్రథమ క్రమానికి చెందినది: ఇది పరివర్తన కిటికీ వెడల్పును గానీ, దాని కచ్చితమైన ఆకారాన్ని గానీ ఇవ్వదు. కోత సంభావ్యతను స్థిరంగా ఉంచారు, కోతలు స్వతంత్రమని ఊహించారు, ఇది నిజమైన చేతుల ఆదర్శీకరణ. ఒక పాదసూచికలో, GPT-6 Astra అనే ఏఐ వ్యవస్థను “వాదనలను అభివృద్ధి చేయడంలో, లెక్కలను తనిఖీ చేయడంలో, వివరణను సిద్ధం చేయడంలో ఉపయోగించాం” అని, గణిత విషయానికి రచయితే బాధ్యులని రచయిత పేర్కొన్నారు. ఈ పత్రం ఒక ప్రీప్రింట్.