🔬 condensed matter

Records, drift, and the longest increasing subsequence of biased Gaussian random walks

यह शोध पत्र पक्षपाती गॉसियन रैंडम वॉक (biased Gaussian random walks) के सबसे लंबे बढ़ते उपक्रम (longest increasing subsequence - LIS) की संख्यात्मक जांच करता है, जो यह प्रकट करता है कि जहाँ सममित मामला $\sqrt{n}\log{n}$ विकास शासन (growth regime) प्रदर्शित करता है, वहीं एक सकारात्मक ड्रिफ्ट (positive drift) को पेश करने से औसत LIS लंबाई रैखिक विकास में परिवर्तित हो जाती है जो ड्रिफ्ट बढ़ने के साथ-साथ रिकॉर्ड गणना (record count) के साथ तेजी से संरेखित होती है।

मूल लेखक: J. Ricardo G. Mendonça

प्रकाशित 2026-05-29

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: J. Ricardo G. Mendonça

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक लंबी, सीधी सड़क पर चलते हुए एक नशे में धुत व्यक्ति को देख रहे हैं। यह एक रैंडम वॉक (यादृच्छिक भ्रमण) है। वह हर कदम जो लेता है, थोड़ा सा रैंडम होता है: कभी वह आगे बढ़ता है, तो कभी पीछे।

दशकों तक, वैज्ञानिकों ने अध्ययन किया है कि क्या होता है यदि वह व्यक्ति आगे या पीछे कदम रखने के लिए समान रूप से संभावित हो (एक सिमेट्रिक/सममित वॉक)। उन्होंने पाया कि कदमों की सबसे लंबी रेखा, जहाँ व्यक्ति केवल ऊपर की ओर गया (कभी नीचे नहीं उतरा), कुल कदमों के वर्गमूल (square root) की तरह धीरे-धीरे बढ़ती है।

लेकिन क्या होगा यदि उस व्यक्ति का आगे की ओर झुकने का थोड़ा सा झुकाव हो? क्या होगा यदि वह ऊपर की ओर चलने के लिए थोड़ा पक्षपाती हो? यह शोध पत्र ठीक इसी परिदृश्य का अन्वेषण करता है।

यहाँ निष्कर्षों की कहानी है, जिसे सरल अवधारणाओं में विभाजित किया गया है:

1. सेटअप: पक्षपाती नशे में धुत व्यक्ति (The Biased Drunk)

शोधकर्ताओं ने एक ऐसे यात्री का अनुकरण (simulate) किया जो "गौसियन" (बेल-कर्व) वितरण के आधार पर कदम लेता है, लेकिन एक मोड़ के साथ: यात्री में एक पॉजिटिव बायस (धनात्मक पक्षपात) है।

सिमेट्रिक केस (50/50): यदि यात्री पूरी तरह से संतुलित है, तो सबसे लंबा ऊपर की ओर जाने वाला रास्ता धीरे-धीरे बढ़ता है।
बायस्ड केस (थोड़ा सा भी): यदि यात्री आगे बढ़ने की तुलना में पीछे हटने की संभावना से थोड़ा भी अधिक है, तो नियम पूरी तरह से बदल जाते हैं।

2. बड़ी खोज: "लीनियर" विस्फोट (The "Linear" Explosion)

सबसे आश्चर्यजनक खोज यह है कि सबसे लंबा ऊपर की ओर जाने वाला रास्ता कितनी तेजी से बढ़ता है।

संतुलित दुनिया में: रास्ता धीरे-धीरे बढ़ता है (जैसे $\sqrt{n}$ )।
पक्षपाती दुनिया में: जैसे ही आगे की दिशा में कोई भी पक्षपात होता है, सबसे लंबा ऊपर की ओर जाने वाला रास्ता अचानक लीनियर (रैखिक) रूप से बढ़ने लगता है।

उपमा: कल्पना कीजिए कि यात्री एक पहाड़ चढ़ रहा है।

यदि हवा शांत है (सिमेट्रिक), तो वह ऊपर-नीचे भटक सकता है, और उसकी निरंतर चढ़ाई का सबसे लंबा हिस्सा कुल समय की तुलना में अपेक्षाकृत छोटा होता है।
यदि एक हल्की हवा भी उसे आगे धकेल रही है (बायस), तो वह बिना किसी उद्देश्य के भटकना बंद कर देता है। वह लगातार चढ़ना शुरू कर देता है। उसकी निरंतर चढ़ाई की लंबाई सीधे तौर पर उसके चलने की अवधि के समानुपाती हो जाती है। यदि वह दोगुना चलता है, तो वह दोगुना ऊंचा चढ़ता है।

शोध पत्र में पाया गया कि शून्य से अधिक किसी भी पक्षपात के लिए, यह लीनियर ग्रोथ तुरंत होती है। "एक्सपोनेंट" (वह शक्ति जो विकास का वर्णन करती है) लगभग 0.5 से उछलकर ठीक 1 हो जाती है।

3. वॉक का "कंकाल": रिकॉर्ड्स (Records)

यह समझने के लिए कि यह क्यों होता है, लेखकों ने रिकॉर्ड्स को देखा।

एक रिकॉर्ड वह क्षण है जब यात्री अपने अब तक के उच्चतम बिंदु पर पहुँचता है।
एक संतुलित वॉक में, रिकॉर्ड दुर्लभ होते हैं।
एक पक्षपाती वॉक में, रिकॉर्ड लगातार होते हैं, जो वॉक के एक "कंकाल" या रीढ़ की हड्डी का निर्माण करते हैं।

शोधकर्ताओं ने पाया कि लॉन्गेस्ट इनक्रीजिंग सबसीक्वेंस (LIS)—सबसे लंबा ऊपर की ओर जाने वाला रास्ता—अनिवार्य रूप से इसी "रिकॉर्ड कंकाल" का अनुसरण करता है।

उच्च पक्षपात (High Bias) पर: यात्री ऊपर जाने के लिए इतना दृढ़ है कि लगभग हर कदम एक रिकॉर्ड है। सबसे लंबा ऊपर की ओर जाने वाला रास्ता उनके सभी व्यक्तिगत सर्वश्रेष्ठ प्रदर्शनों की सूची के लगभग समान है।
कम पक्षपात (Low Bias) पर: वह अभी भी रिकॉर्ड का पालन करता है, लेकिन बीच-बीच में दो रिकॉर्ड के बीच एक अतिरिक्त कदम जोड़ने के लिए छोटे "विचलन" (fluctuations) ले सकता है।

4. रिकॉर्ड और पथ के बीच का "गैप" (The Gap)

शोध पत्र रिकॉर्ड्स की संख्या और लॉन्गेस्ट पाथ की लंबाई के बीच के अंतर को मापता है।

गैप: यह उन अतिरिक्त कदमों का प्रतिनिधित्व करता है जो यात्री के व्यक्तिगत सर्वश्रेष्ठ नहीं हैं, लेकिन फिर भी ऊपर की ओर जाने वाली श्रृंखला में फिट बैठते हैं।
गैप का आकार: यह गैप बहुत कम होता है जब पक्षपात बहुत कम होता है (क्योंकि वॉक अभी भी अराजक है) और तब भी कम होता है जब पक्षपात बहुत अधिक होता है (क्योंकि यात्री इतना दृढ़ है कि हर कदम एक रिकॉर्ड है)।
पीक (शिखर): गैप एक "मध्यम" पक्षपात (लगभग 60% आगे बढ़ने की संभावना) पर सबसे बड़ा होता है। यहाँ, यात्री लगातार चढ़ने के लिए पर्याप्त दृढ़ है, लेकिन फिर भी इतना डगमगाता हुआ है कि वह प्रमुख मील के पत्थरों के बीच अतिरिक्त "छिपे हुए" कदम ढूंढ सके।

5. "टिपिंग पॉइंट" (The Singular Limit)

शोध का सबसे नाजुक हिस्सा वह है जो बिल्कुल किनारे पर होता है, जहाँ पक्षपात लगभग शून्य है (49.9% बनाम 50.1%)।

शोध पत्र दिखाता है कि "धीमी वृद्धि" से "लीनियर वृद्धि" की ओर संक्रमण सिंगुलर (विलक्षण) है। यह एक सहज ढलान नहीं है; यह एक चट्टान (cliff) की तरह है।
जैसे-जैसे पक्षपात छोटा होता जाता है, रास्ते की लंबाई केवल लीनियर रूप से कम नहीं होती; यह लीनियर से भी धीमी गति से घटती है। ऐसा लगता है जैसे रास्ता पूर्ण शून्य होने तक पूरी तरह से गायब होने से इनकार करता है।
लेखक इस सूक्ष्म क्षेत्र में यह सटीक रूप से नहीं बता सके कि यह कैसे घटता है, लेकिन उन्होंने यह सिद्ध किया कि यह उम्मीद से अलग व्यवहार करता है।

6. डेटा का आकार: "अजीब" से "सामान्य" तक

अंत में, शोध पत्र ने इन रास्तों के वितरण (distribution) को देखा (यदि आप सिमुलेशन को 10,000 बार चलाते हैं, तो परिणाम क्या दिखेंगे?)।

संतुलित वॉक (50/50): परिणाम "स्क्यूड" (झुका हुआ) और "फैट-टेल्ड" (मोटी पूंछ वाले) होते हैं। यह लॉग-नॉर्मल वितरण जैसा है। अधिकांश रास्ते छोटे होते हैं, लेकिन कभी-कभी आपको आश्चर्यजनक रूप से लंबे रास्ते मिल सकते हैं। यह अप्रत्याशित और "अजीब" है।
पक्षपाती वॉक (थोड़ा सा भी): परिणाम एक गौसियन (बेल कर्व) में बदल जाते हैं। रास्ते बहुत अनुमानित और "सामान्य" हो जाते हैं। आप जितना अधिक पक्षपात करेंगे, परिणाम उतने ही मानक बेल कर्व की तरह दिखेंगे।

सारांश

यह शोध पत्र हमें बताता है कि रैंडम वॉक की दुनिया में, दिशा का एक छोटा सा अंश भी सब कुछ बदल देता है।

पहले: एक संतुलित यात्री भटकता है, और उसकी सबसे अच्छी चढ़ाइयाँ छोटी और अप्रत्याशित होती हैं।
बाद में: एक पक्षपाती यात्री आगे की ओर मार्च करता है। उसकी सबसे अच्छी चढ़ाइयाँ समय के साथ लगातार और लीनियर रूप से बढ़ती हैं, जो व्यक्तिगत सर्वश्रेष्ठों के "कंकाल" का अनुसरण करती हैं।
संक्रमण (Transition): जैसे ही आप पक्षपात पेश करते हैं, खेल के नियम तुरंत बदल जाते हैं, जो एक अराजक, धीमी वृद्धि वाली दुनिया से एक स्थिर, लीनियर-वृद्धि वाली दुनिया में बदल जाता है।

तकनीकी सारांश: रिकॉर्ड्स, ड्रिफ्ट और बायस्ड गॉसियन रैंडम वॉक का लॉन्गएस्ट इंक्रीजिंग सबसीक्वेंस (LIS)

समस्या विवरण
लॉन्गेस्ट इंक्रीजिंग सबसीक्वेंस (LIS) की समस्या, जो पारंपरिक रूप से रैंडम परम्यूटेशन और जीरो-मीन सिमेट्रिक रैंडम वॉक के लिए अध्ययन की जाती है, ने कठोर स्केलिंग लॉ स्थापित किए हैं जहाँ अपेक्षित LIS लंबाई $\sqrt{n \log n}$ (परिमित विचरण के लिए) या $n^\theta$ (हेवी-टेल्ड इंक्रीमेंट्स के लिए) के रूप में बढ़ती है। हालाँकि, बायस्ड (biased) रैंडम वॉक—विशेष रूप से सकारात्मक ड्रिफ्ट वाले—के लिए LIS का व्यवहार अनछुआ रहा है। बायस्ड वॉक दिशात्मक रुझानों वाले टाइम सीरीज़ को मॉडल करते हैं, जहाँ LIS सह-संबंधित (correlated), गैर-स्थिर (non-stationary) अनुक्रमों में मोनोटोनिक संरचनाओं की जांच करता है। यह शोध यूनिट वेरियंस और एक सकारात्मक मीन ड्रिफ्ट $\mu_p$ वाले गॉसियन रैंडम वॉक के LIS की जांच करता है, जिसे बायस पैरामीटर $p = P(\xi > 0) \ge 1/2$ द्वारा पैरामीट्राइज किया गया है। केंद्रीय प्रश्न यह है कि कैसे एक छोटी सी विषमता (asymmetry) भी सिमेट्रिक केस की तुलना में LIS के एसिम्प्टोटिक स्केलिंग और वितरण गुणों को बदल देती है।

कार्यप्रणाली (Methodology)
यह अध्ययन बायस्ड गॉसियन रैंडम वॉक के लिए LIS लंबाई ( $L_n$ ) की गणना करने हेतु पेशिएंस सॉर्टिंग एल्गोरिदम (patience sorting algorithm) का उपयोग करते हुए एक संख्यात्मक दृष्टिकोण अपनाता है।

मॉडल: वॉक को $X_k = \mu_p k + W_k$ के रूप में परिभाषित किया गया है, जहाँ $W_k$ यूनिट वेरियंस वाला एक सेंटर्ड गॉसियन रैंडम वॉक है, और $\mu_p = \Phi^{-1}(p)$ ड्रिफ्ट है जो बायस पैरामीटर $p$ द्वारा निर्धारित होता है।
अवलोकनीय (Observables): प्रत्येक रियलाइजेशन के लिए, लेखक निम्नलिखित को मापते हैं:
1. LIS लंबाई $L_n(p)$ ।
2. रिकॉर्ड काउंट $R_n(p)$ (वह संख्या जितनी बार वॉक एक नया मैक्सिमम सेट करती है)।
3. ओवरलैप $R^{LIS}_n(p)$ (एक रिकवर्ड LIS में शामिल किए गए रिकॉर्ड समय की संख्या)।
सिमुलेशन प्रोटोकॉल: लेखकों ने $10^4$ से $10^7$ तक की वॉक लंबाई $n$ और बायस पैरामीटर $p \in [0.5, 0.999]$ के लिए 10,000 स्वतंत्र रियलाइजेशन उत्पन्न किए। $p=1/2$ के निकटवर्ती क्षेत्र और $p \to 1$ के निकट-डिटरमिनिस्टिक सीमा पर विशेष ध्यान दिया गया।
विश्लेषण: अध्ययन प्रभावी एक्सपोनेंट्स (effective exponents), लीनियर कोएफिशिएंट्स, डायग्नोस्टिक रेश्यो (जैसे $R^{LIS}_n/L_n$ ), और क्वांटाइल-क्वांटाइल प्लॉट्स एवं सांख्यिकीय परीक्षणों (कोलमोगोरोव–सीएस (Kolmogorov–KS), स्क्यूनेस, कर्टोसिस) के माध्यम से $L_n$ के वितरण संबंधी आकार का विश्लेषण करता है।

मुख्य योगदान और परिणाम

लीनियर स्केलिंग की ओर संक्रमण:
सिमेट्रिक केस ( $p=1/2$ ) के विपरीत, जहाँ $E[L_n] \sim \sqrt{n \log n}$ होता है, लेखक पाते हैं कि किसी भी निश्चित $p > 1/2$ के लिए, माध्य LIS लंबाई $n$ के साथ रैखिक रूप से बढ़ती है:
$\langle L_n(p) \rangle \sim a(p)n$
प्रभावी एक्सपोनेंट $\theta(p)$ सभी $p > 1/2$ के लिए तेजी से 1 की ओर अभिसरित (converge) होता है। प्रासंगिक अध्ययन का विषय एक्सपोनेंट से हटकर कोएफिशिएंट $a(p)$ पर स्थानांतरित हो जाता है, जो $p=1/2$ पर $0 $से शुरू होकर$ p \to 1 $की ओर$ 1$ तक सुचारू रूप से बढ़ता है।
रिकॉर्ड सांख्यिकी और "रिकॉर्ड स्केलेटन":
यह शोध स्थापित करता है कि बायस्ड रिजीम में LIS "रिकॉर्ड स्केलेटन" (रिकॉर्ड समय का अनुक्रम) के साथ तेजी से संरेखित होता है।

औसत रिकॉर्ड काउंट भी रैखिक रूप से बढ़ता है: $\langle R_n(p) \rangle \sim \lambda(p)n$ ।
कोएफिशिएंट $\lambda(p)$ को स्पिट्जर के फॉर्मूला (Spitzer's formula) (इक्वेशन 24) द्वारा मात्रात्मक रूप से समझाया गया है, जो बायस्ड वॉक के लिए एक ज्ञात परिणाम है।
जैसे-जैसे $p \to 1$ , LIS तत्वों का रिकॉर्ड हिस्सा ( $R^{LIS}_n/L_n$ ) और रिकॉर्ड्स का उपयोग करने वाले रिकॉर्ड्स का अनुपात ( $R^{LIS}_n/R_n$ ) दोनों एकता (unity) की ओर बढ़ते हैं, जो दर्शाता है कि LIS एसिम्प्टोटिक रूप से रिकॉर्ड स्केलेटन के समान हो जाता है।

फ्लक्चुएशन एक्स्ट्रा ( $a(p) - \lambda(p)$ ):
एक प्रमुख निष्कर्ष $a(p)$ और $\lambda(p)$ के बीच का गैर-शून्य अंतर है। यह अंतर, $a(p) - \lambda(p)$ , गैर-रिकॉर्ड फ्लक्चुएशंस (रिकॉर्ड्स के बीच सेंटर्ड वॉक $W_k$ के स्थानीय एक्सकर्सन्स) के योगदान को दर्शाता है।

यह अंतर नॉन-मोनोटोनिक है, जो $p=1/2$ और $p \to 1$ पर शून्य हो जाता है, और $p \approx 0.6$ ( $\mu_p \approx 0.25$ ) के पास $\approx 0.1$ के अधिकतम मान तक पहुँचता है।
यह इंगित करता है कि लीनियर रिजीम में भी, LIS विशुद्ध रूप से एक रिकॉर्ड प्रक्रिया नहीं है; यह गैर-रिकॉर्ड स्टेप्स के एक महत्वपूर्ण अंश को शामिल करता है, विशेष रूप से मध्यम ड्रिफ्ट पर।

वितरणात्मक संक्रमण (Distributional Transition):
LIS लंबाई का अनुभवजन्य वितरण $p=1/2$ के सिंगुलर पॉइंट पर एक तीव्र संक्रमण से गुजरता है:

$p=1/2$ पर: वितरण राइट-स्क्यूड (right-skewed) और फैट-टेल्ड (fat-tailed) है, जो लॉग-नॉर्मल सन्निकटन (सिमेट्रिक वॉक में देखे गए अनुसार) के अनुरूप है।
$p > 1/2$ के लिए: स्टैंडर्डाइज्ड $L_n$ का वितरण गॉसियन फ्लक्चुएशंस के अनुरूप है, जो लीनियर रिजीम में LIS की एक्सटेंसिव सम-जैसी संरचना के लिए सेंट्रल-लिमिट चित्र का समर्थन करता है।

$p=1/2$ पर सिंगुलर लिमिट:
सिमेट्रिक पॉइंट लीनियर रिजीम का एक सिंगुलर लिमिट है।

रिकॉर्ड डेंसिटी $\lambda(\mu_p) \sim 1.39 \mu_p$ के रूप में स्केल करती है (छोटे ड्रिफ्ट के लिए)।
LIS कोएफिशिएंट $a(\mu_p)$ , लीनियर रूप से बढ़ने से अधिक धीरे गायब होता है। अनुपात $a(\mu_p)/\mu_p$ , $\mu_p \to 0$ होने पर बढ़ता है।
फ्लक्चुएशन एक्स्ट्रा $a(\mu_p) - \lambda(\mu_p)$ सैंपल किए गए रेंज में किसी एकल पावर लॉ का पालन नहीं करता है; स्थानीय लॉग-लॉग स्लोप ड्रिफ्ट करते हैं, जो यह सुझाव देते हैं कि एक जटिल बाउंड्री लेयर व्यवहार मौजूद है जिसे साधारण इंटर-रिकॉर्ड एक्सकर्सन अनुमानों द्वारा कैप्चर नहीं किया जा सकता है।

महत्व और दायरा
यह शोध बायस्ड रैंडम वॉक के लिए LIS का पहला संख्यात्मक लक्षण वर्णन प्रदान करता है, यह प्रदर्शित करते हुए कि कोई भी सकारात्मक ड्रिफ्ट स्केलिंग को सबलीनियर ( $\sqrt{n \log n}$ ) से लीनियर ( $n$ ) में मौलिक रूप से बदल देता है। अध्ययन पहचान करता है कि रिकॉर्ड स्केलेटन बायस्ड रिजीम में डोमिनेंट स्ट्रक्चर है, लेकिन यह गैर-रिकॉर्ड फ्लक्चुएशंस के निरंतर योगदान को भी मात्रात्मक रूप से मापता है।

लेखक स्पष्ट रूप से कहते हैं कि जबकि रिकॉर्ड कोएफिशिएंट $\lambda(p)$ स्पिट्जर की पहचान के माध्यम से विश्लेषणात्मक रूप से ज्ञात है, $a(p)$ के लिए वर्तमान में कोई क्लोज्ड-फॉर्म एक्सप्रेशन उपलब्ध नहीं है। पहचाना गया प्राथमिक खुला प्रश्न $a(p)$ का व्युत्पत्ति करना है, जिसके लिए रिकॉर्ड स्केलेटन की रिन्यूअल संरचना और रिकॉर्ड्स के बीच इंटरपोलेशन को नियंत्रित करने वाले ग्लोबल मोनोटोनिसिटी कंस्ट्रेंट्स के बीच सामंजस्य बिठाने की आवश्यकता है। शोध विनम्रता से समाप्त होता है, यह नोट करते हुए कि छोटे-ड्रिफ्ट व्यवहार का सटीक एसिम्प्टोटिक रूप अनसुलझा बना हुआ है, और परिणाम परिमित-विचरण गॉसियन इंक्रीमेंट्स के लिए विशिष्ट हैं, जिससे भविष्य के अनुसंधान के लिए इनफिनिट-वेरियंस केस (जैसे बायस्ड कॉची वॉक) खुले रह जाते हैं।