अधिकतम 3 (बड़ी वर्णमाला) पर संपादित दूरी के साथ तारों की औसत संख्या
लंबाई की एक स्ट्रिंग पर विचार करें $n \geq 3$ एक वर्णमाला के ऊपर $\{1,\dots, \sigma\}$। एक संपादित ऑपरेशन एक एकल प्रतीक सम्मिलित, विलोपन या प्रतिस्थापन है। दो तारों के बीच की संपादित दूरी एक स्ट्रिंग को दूसरे में बदलने के लिए आवश्यक संपादित संचालन की न्यूनतम संख्या है। एक तार दिया$S$ लंबाई की $n$ साथ से $S_i \in \{1,\dots, \sigma\}$, मेरा प्रश्न विभिन्न स्ट्रिंग्स की संख्या से संबंधित है, जो कि दूरी पर संपादित की जाती हैं $3$ से $S$।
हमें लिखने दो $g_{k, \sigma}(S)$ वर्णमाला पर विशिष्ट तारों की संख्या के लिए $\{1,\dots, \sigma\}$ जो अधिक से अधिक दूरी को संपादित करते हैं $k$ से $S$, अर्थात $g_{k,\sigma}(S) = |\{S' : d(S', S) \leq k\}|$ कहां है $d(-,-)$ संपादित दूरी है।
चलो $X_n$ वर्णमाला पर एक यादृच्छिक स्ट्रिंग का प्रतिनिधित्व करने वाला एक यादृच्छिक चर हो $\{1,\dots, \sigma\}$ लंबाई की $n$, समान रूप से और स्वतंत्र रूप से चुने गए प्रतीकों के साथ।
यह सीधे मेरे प्रश्न की ओर जाता है:
चलो $X_n$ एक यादृच्छिक चर लंबाई की एक यादृच्छिक स्ट्रिंग का प्रतिनिधित्व करते हैं $n$, समान रूप से और स्वतंत्र रूप से चुने गए प्रतीकों के साथ। क्या है:
$$\mathbb{E}(g_{3, \sigma}(X_n))\;?$$
के लिये $\sigma=2$हम एक स्पष्ट सूत्र प्राप्त कर सकते हैं $(40+6n-4n^2)/2^n-83/2+(331/12)n-6n^2+(2/3)n^3$। तो मेरा सवाल है, वर्णमाला के आकार पर निर्भरता क्या है$\sigma$ हमशक्ल?
जवाब
वैरिंग वी। अपरिवर्तित स्ट्रिंग लंबाई
यदि, जैसा कि आपने शुरू में मेरी टिप्पणी के जवाब में संकेत दिया था, तब्दील स्ट्रिंग की लंबाई मूल की लंबाई से भिन्न हो सकती है, तो यह समस्या बहुत अधिक कठिन हो जाती है क्योंकि अलग-अलग संपादन संचालन (संचालन जो संभवतः एक अलग परिणाम प्राप्त कर सकते हैं) का सेट ) निम्नलिखित में से सभी 18 शामिल हैं:
- लंबाई +3 = 3 सम्मिलन
- लंबाई +2 = 2 सम्मिलन और 0 या 1 प्रतिस्थापन
- लंबाई +1 = 1 सम्मिलन और 0, 1, या 2 प्रतिस्थापन
- लंबाई अपरिवर्तित = 0, 1, 2, या 3 प्रतिस्थापन; 1 विलोपन, 1 सम्मिलन, और 0 या 1 प्रतिस्थापन
- लंबाई -1 = 1 विलोपन और 0, 1, या 2 प्रतिस्थापन
- लंबाई -2 = 2 विलोपन और 0 या 1 प्रतिस्थापन
- लंबाई -3 = 3 विलोपन
जब भी कई सम्मिलन या एक से अधिक विलोपन किए जाते हैं, तब भी, गणना मुश्किल से मुश्किल हो जाती है। यदि, दूसरी ओर, हमें आवश्यकता है कि लंबाई अपरिवर्तित रहे, तो हमारे पास विचार करने के लिए केवल 6 संपादन संयोजन हैं और समस्या अधिक सुगम हो जाती है क्योंकि उन 6 संयोजनों में से किसी में भी कई सम्मिलन या एकाधिक विलोपन शामिल नहीं हैं। दरअसल, छह मामलों में से प्रत्येक के लिए गिनती अपेक्षाकृत सरल हो जाती है; जब दो अलग-अलग एडिटिंग ऑपरेशन एक ही स्ट्रिंग का उत्पादन करेंगे - तो दूसरे प्रश्न के उत्तर में हल की गई समस्या से बचने के लिए ट्रिकिएस्ट बिट डबल-काउंटिंग उदाहरणों से बचने की छूट दे रहा है ।
छह मामले और अतिरंजना का खतरा
शुरू में हमारे बीयरिंग प्राप्त करने के लिए, हम इस तर्क को सामान्य कर सकते हैं :
- स्ट्रिंग को बनाए रखना चाहिए $n$ प्रतीकों।
- समान प्रतीकों के समूहों की अपेक्षित संख्या है $\frac{n+1}{\sigma}$
- आसन्न, समान प्रतीक जोड़े की अपेक्षित संख्या है $\frac{n-1}{\sigma}$
- सिरों की संख्या 2 है।
इस प्रकार की उपज के पांच संभावित प्रकारों का एक बारीक विचार
- संभावित प्रतिस्थापनों की संख्या है $n(\sigma-1)$
- समान प्रतीकों के एक समूह के संकोचन की अपेक्षित संख्या है $\frac{n+1}{\sigma}$
- समान प्रतीक वाले समान प्रतीकों के समूह के विस्तार की अपेक्षित संख्या है $\frac{n+1}{\sigma}$
- समान प्रतीकों वाले समान प्रतीकों के समूह में सम्मिलन की अपेक्षित संख्या है $\frac{n-1}{\sigma}$
- शुरुआत या अंत में एक अलग चरित्र के संभावित सम्मिलन की संख्या है $2(\sigma-1)$
अब हम अपने प्रत्येक छः मामलों में उस मूल तर्क को लागू कर सकते हैं:
कोई संपादन नहीं कोई संपादन
नहीं करता है जो भी केवल मूल स्ट्रिंग प्राप्त करता है, इसलिए इस मामले के लिए 1 परिणाम।एक प्रतिस्थापन
हैं$n$ विभिन्न प्रतीकों और $\sigma-1$ तरीकों को प्रत्येक को एक अलग प्रतीक में प्रतिस्थापित किया जा सकता है, इसलिए $n(\sigma-1)$ परिणाम।दो प्रतिस्थापन
हैं$\binom{n}{2}$ अलग जोड़े और $(\sigma-1)^2$ प्रत्येक को संशोधित करने के तरीके: $\binom{n}{2}(\sigma-1)^2$ परिणाम।तीन प्रतिस्थापन
हैं$\binom{n}{3}$ विभिन्न तिकड़ी और $(\sigma-1)^3$ प्रत्येक को संशोधित करने के तरीके: $\binom{n}{3}(\sigma-1)^3$।एक विलोपन, एक प्रविष्टि, कोई प्रतिस्थापन नहीं
इस मामले के लिए, हम इस समाधान के लिए सामान्यीकरण कर सकते हैं$\sigma=2$ किसी को $\sigma$, एक ही तर्क का उपयोग करते हुए उन उदाहरणों को दोहराए जाने से बचने के लिए जहां दो प्रतिस्थापन एक विलोपन और एक सम्मिलन के समान परिणाम प्राप्त करेंगे।
आइए उन मामलों की गणना करें जहां सम्मिलन विलोपन के बाईं ओर है और फिर 2. से गुणा करें। सम्मिलन और विलोपन का संयुक्त प्रभाव उन सभी के बीच 𝑘 बिट्स को दाईं ओर स्थानांतरित करना है जबकि पहले एक को हटाकर अंतिम एक को हटाना । यह परिणाम अधिकांश can प्रतिस्थापनों द्वारा भी प्राप्त किया जा सकता है, इसलिए हमें।> 2 की आवश्यकता है। Runs के एक रन के भीतर a सम्मिलित करने का रन के अंत में the सम्मिलित करने के समान प्रभाव पड़ता है। इस प्रकार हम हमेशा अलग-अलग प्रभावों के साथ सभी सम्मिलन की गणना कर सकते हैं, हमेशा प्रविष्टि के दाईं ओर एक बिट पूरक को सम्मिलित करके। इसी तरह, एक रन के भीतर एक डिलीशन का रन के शुरू में डिलीट होने के समान प्रभाव पड़ता है, इसलिए हमें केवल डिलीट को गिनना चाहिए, जो 0 और 1 के बीच बदलाव का पालन करता है। यह हमें एक प्रारंभिक गिनती देता है:
$2\cdot\frac12\sum_{k=3}^n(n+1-k)=\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}2\;$
चूँकि ट्रिक लॉजिक को डबल-काउंटिंग कैरी को सीधे तौर पर रोकने के लिए आवश्यक है, केवल एक वेरिएबल को बदलने के लिए आवश्यक संशोधन है $\sigma$ नियत के लिए $\sigma=2$:
$2\cdot\frac{1}{\sigma}\sum_{k=3}^n(n+1-k)=2\cdot\frac{1}{\sigma}\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}{\sigma}\;$
दो प्रतिस्थापन के रूप में पहले से ही लंबा हो चुके परिणामों के ओवरकाउंट की गणना निम्नानुसार की जा सकती है $\sigma=2$:
यदि विलोपन के पूर्व के अलावा ed शिफ्ट किए गए बिट्स में कोई और परिवर्तन नहीं होते हैं, तो केवल सम्मिलन और विलोपन के बगल में बिट्स बदलते हैं, और हम इसे 2 प्रतिस्थापन के साथ प्राप्त कर सकते हैं, इसलिए हमें घटाना होगा
$\sum_{k=3}^n\left(\frac12\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac12\right)^{n-k-1}k=n-3+2^{-(n-2)}\;$
फिर से, हमारा एकमात्र संशोधन स्थानापन्न करना है $\sigma$ 2 के लिए:
$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac1{\sigma}\right)^{n-k-1}k=n-3+{\sigma}^{-(n-2)}\;$
इसके अलावा, अगर शिफ्ट किए गए बिट्स की पूरी श्रृंखला में वैकल्पिक शून्य और वाले होते हैं, तो सम्मिलन और विलोपन को स्वैप करने से एक ही प्रभाव पड़ता है, इसलिए इस मामले में हम डबल-काउंटिंग थे और घटाना आवश्यक था
$\sum_{k=3}^n\left(\frac12\right)^{k-1}(n+1-k)\;$
में स्वैपिंग $\sigma$ एक अंतिम समय पैदावार:
$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$
ये दो ओवरकंट्स (जो, अलास को सफाई से नहीं जोड़ा जा सकता है, जब प्रतीक बाइनरी हैं) तब इस केस द्वारा उत्पादित समग्र परिणाम प्राप्त करने के लिए विलोपन / सम्मिलन संचालन की प्रारंभिक गणना से घटाया जाता है, लेकिन ऊपर केस 3 द्वारा नहीं:
$\frac{(n-1)(n-2)}{\sigma}\ - \left(n-3+{\sigma}^{-(n-2)}\right) - \sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$
- एक विलोपन, एक प्रविष्टि, एक प्रतिस्थापन
जो उसी गणना को अंतिम मामले तक ले जाता है। हालांकि, एक विलोपन और एक सम्मिलन के प्रत्येक संयोजन - इसी तरह, पहले से ही मामले 4 में ऊपर उठाए गए ट्रिपल प्रतिस्थापन की गिनती से बचने के लिए छूट दी गई है - एक तीसरे संपादन के साथ है: एक प्रतिस्थापन जिसमें से एक शामिल है$n-1$विलोपन के बाद शेष मूल प्रतीक। इनमें से प्रत्येक के बाद से$(n-1)$ प्रतीक मानते हैं $(\sigma-1)$ उपन्यास प्रतिस्थापन, छठे और अंतिम मामले के लिए कुल गणना बन जाती है:
$\left(\frac{(n-1)(n-2)}{\sigma}\ - \left(n-3+{\sigma}^{-(n-2)}\right) - \sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\right)(n-1)(\sigma-1);$
इन छह मामलों में से प्रत्येक के द्वारा उत्पादित (पहले बेशुमार) परिणामों को जोड़ते हुए स्ट्रिंग की लंबाई अपरिवर्तित रहने पर अपेक्षित गिनती प्राप्त करनी चाहिए। यह बदसूरत है (शायद अनावश्यक रूप से), लेकिन मुझे उम्मीद है कि सही होगा।