इनवर्जन की अपेक्षित संख्या - कॉर्मन द्वारा परिचय से एल्गोरिदम तक

Question

चलो ए [1 .. एन] एन distinct संख्याओं की एक सरणी बनें। अगर मैं < जे और ए [i]> ए [जे], तो जोड़ी (i, j) को ए का उलटा कहा जाता है (इनवर्जन पर अधिक के लिए समस्या 2-4 देखें।) मान लें कि ए के प्रत्येक तत्व को चुना गया है यादृच्छिक रूप से, स्वतंत्र रूप से, और समान रूप से सीमा 1 से एन तक। इनवर्जन की अपेक्षित संख्या की गणना करने के लिए सूचक यादृच्छिक चर का उपयोग करें।

---

समस्या Cormen द्वारा एल्गोरिदम के परिचय में व्यायाम 5.2-5 से है। यहां मेरा रिकर्सिव समाधान है:

मान लीजिए एक्स (i) एक [1..i] में उलटा की संख्या है, और ई (i) एक्स (i), तो ई (i) का अपेक्षित मान है +1) को निम्नलिखित के रूप में गणना की जा सकती है:
छवि हमारे पास i+1 पदों को सभी नंबरों पर रखने के लिए है, यदि हम पहले स्थान पर i + 1 डालते हैं, तो x (i + 1) = i + x (i); अगर हम दूसरी स्थिति पर i + 1 डालते हैं, तो एक्स (i + 1) = i-1 + x (i), ..., तो ई (i + 1) = 1/(i + 1) * योग (के) + ई (i), जहां के = [0, i]। अंत में हमें ई (i + 1) = i/2 + E (i) मिलता है।
क्योंकि हम जानते हैं कि ई (2) = 0.5, इसलिए हम पुनः प्राप्त करते हैं: ई (एन) = (एन -1 + एन -2 + ... + 2)/2 + 0.5 = एन * (एन -1)/4।

---

कटौती ऊपर सही प्रतीत हो रहा है, लेकिन मैं अभी भी इस बात का बहुत यकीन नहीं है हालांकि। तो मैं इसे यहाँ साझा करता हूं।

यदि कुछ गड़बड़ है, तो कृपया मुझे सही करें।

सभी एक्स और वाई हम के लिए

:

Answer 1

मुझे लगता है कि यह सही है, लेकिन मैं इसे साबित करने के लिए उचित तरीके से लगता है conditionnal उम्मीदों उपयोग करने के लिए है ई [X] = ई [ई [X | Y]]

तो अपने मामले में

:

ई (i + 1) = ई [x (i +1)] = ई [ई [x (i + 1) | एक्स (i)]] = ई [एसयूएम (के)/(1 + i) + एक्स (i)] = i/2 + ई [x (i)] = i/2 + ई (i)

दूसरा कथन के बारे में:

यदि:

ई (एन) = n * (n-1)/4।

फिर ई (एन + 1) = (एन + 1) * एन/4 = (एन -1) * एन/4 + 2 * एन/4 = (एन -1) * एन/4 + एन/2 = ई (एन) + एन/2

तो एन * (एन -1)/4। सभी n> = 2 के लिए प्रत्यावर्तन संबंध को सत्यापित करने और यह n के लिए यह सत्यापित करता = 2

तो ई (एन) = n * (एन-1)/4

आशा मैं आपकी समस्या को समझा और यह

में मदद करता है

Answer 2

सभी समाधान सही होने लगते हैं, लेकिन समस्या कहती है कि हमें सूचक यादृच्छिक चर का उपयोग करना चाहिए। तो यहां मेरा समाधान है:

Let Eij be the event that i < j and A[i] > A[j]. 

    Let Xij = I{Eij} = {1 if (i, j) is an inversion of A 

         0 if (i, j) is not an inversion of A} 

    Let X = Σ(i=1 to n)Σ(j=1 to n)(Xij) = No. of inversions of A. 

    E[X] = E[Σ(i=1 to n)Σ(j=1 to n)(Xij)] 

     = Σ(i=1 to n)Σ(j=1 to n)(E[Xij]) 

     = Σ(i=1 to n)Σ(j=1 to n)(P(Eij)) 

     = Σ(i=1 to n)Σ(j=i + 1 to n)(P(Eij)) (as we must have i < j) 

     = Σ(i=1 to n)Σ(j=i + 1 to n)(1/2) (we can choose the two numbers in 
              C(n, 2) ways and arrange them 
              as required. So P(Eij) = C(n, 2)/n(n-1)) 

     = Σ(i=1 to n)((n - i)/2) 

     = n(n - 1)/4 

Answer 3

एक और समाधान भी सरल है, आईएमओ, हालांकि यह "सूचक यादृच्छिक चर" का उपयोग नहीं करता है।

के बाद से संख्या के सभी भिन्न हैं, तत्वों की प्रत्येक जोड़ी या तो एक उलट (A[i] > A[j] साथ i < j) या एक गैर उलट (A[i] < A[j] साथ i < j) है। एक और तरीका रखो, संख्याओं की प्रत्येक जोड़ी या तो क्रम में या आदेश से बाहर है।

तो किसी दिए गए क्रमपरिवर्तन के लिए, इनवर्जनों की कुल संख्या और गैर-इनवर्जन केवल जोड़ों की कुल संख्या है, या n*(n-1)/2 है।

"से कम" और "से अधिक" की समरूपता के अनुसार, इनवर्जन की अपेक्षित संख्या गैर-इनवर्जन की अपेक्षित संख्या के बराबर होती है।

के बाद से उनका योग की उम्मीद n*(n-1)/2 (सभी क्रमपरिवर्तन के लिए निरंतर) है, और वे बराबर हैं, वे कहते हैं कि या n*(n-1)/4 के प्रत्येक आधे हैं।

[अपडेट 1]

जाहिर है मेरी " 'से कम' और 'से अधिक' की समरूपता" बयान कुछ विस्तार की आवश्यकता है।

रेंज 1 में संख्या A में से किसी सरणी के लिए n के माध्यम से, सरणी जब आप n+1 से प्रत्येक संख्या घटाना आपको मिल के रूप में ~A परिभाषित करते हैं। उदाहरण के लिए, यदि A[2,3,1] है, तो ~A[2,1,3] है।

अब, A में संख्याओं की किसी भी जोड़ी के लिए क्रमशः ~A के संबंधित तत्व क्रम से बाहर हैं। (दिखाने के लिए आसान है क्योंकि दो संख्याओं को अस्वीकार करने से उनके आदेश का आदान-प्रदान होता है।) यह मैपिंग इस संदर्भ में कम से कम और उससे अधिक के बीच समरूपता (द्वंद्व) को स्पष्ट रूप से दिखाती है।

तो, किसी भी A के लिए, इनवर्जनों की संख्या ~A में गैर-इनवर्जन की संख्या के बराबर होती है। लेकिन हर संभव A के लिए, वास्तव में एक ~A से मेल खाता है; जब संख्याओं को समान रूप से चुना जाता है, तो A और ~A दोनों समान रूप से संभावित होते हैं। इसलिए A में में इनवर्जन~A में अपेक्षित संख्या की तुलना की गई है, क्योंकि इन उम्मीदों की गणना उसी स्थान पर की जा रही है।

इसलिए A में इनवर्जन की अपेक्षित संख्या गैर-इनवर्जन की अपेक्षित संख्या के बराबर होती है। इन अपेक्षाओं का योग राशि की अपेक्षा है, जो निरंतर n*(n-1)/2 है, या जोड़े की कुल संख्या है।

[अपडेट 2]

एक सरल समरूपता: n से कोई भी तत्व सरणी A लिए, एक ही तत्व के रूप में, लेकिन उलटे क्रम में ~A परिभाषित करते हैं। में स्थिति n+1-i पर ~A में तत्व के साथ i स्थिति पर तत्व को संबद्ध करें। (यानी, प्रत्येक तत्व को अपने आप को उलटा सरणी में जोड़ दें।)

अब A में कोई भी उलटा ~A में किसी भी उलटा हुआ है, जैसा उपर्युक्त अद्यतन 1 में निर्माण के साथ है। तो एक ही तर्क लागू होता है: A में इनवर्जनों की संख्या ~A में इनवर्जनों की संख्या के बराबर होती है; A और ~A दोनों समान रूप से अनुक्रम हैं; आदि।

अंतर्ज्ञान का बिंदु यह है कि "कम से कम" और "से अधिक" ऑपरेटरों एक दूसरे के दर्पण छवियां हैं, जिन्हें आप तर्कों को अस्वीकार कर सकते हैं (जैसे अद्यतन 1 में) या उन्हें स्वैप करके (अपडेट 2 में)। तो इनवर्जन और गैर-इनवर्जन की अपेक्षित संख्या वही है, क्योंकि आप यह नहीं बता सकते कि क्या आप दर्पण के माध्यम से किसी भी विशेष सरणी को देख रहे हैं या नहीं।

Answer 4

का उपयोग सूचक यादृच्छिक परिवर्तनीय:

1. Let एक्स = यादृच्छिक चर जो व्युत्क्रम की संख्या के बराबर है।
2. Xij = 1 अगर ए [i] और ए [जे] एक उलटा जोड़ी बनाते हैं, और Xij = 0 अन्यथा।
3. उलट जोड़े = योग की संख्या 1 < से अधिक = मैं < जे < = (Xij)
4. अब पी के n [Xij = 1] = पी [एक [i]> एक [जे]] = (एन चुनें 2)/(2! * N चुनें 2) = 1/2
5. ई [एक्स] = ई [सभी आईजे जोड़े पर योग जैसे कि मैं < ज़ीज़ का जम्मू] = सभी आईजे जोड़े पर योग जैसे कि < जे ई [Xij] = n (n - 1)/4

Answer 5

भी सरल (ऊपर अमन का जवाब देने के लिए समान है, लेकिन शायद स्पष्ट) ...

Let Xij be a random variable with Xij=1 if A[i] > A[j] and Xij=0 otherwise. 
Let X=sum(Xij) over i, j where i < j 

Number of pairs (ij)*:    n(n-1)/2 
Probability that Xij=1 (Pr(Xij=1))): 1/2 
By linearity of expectation**:  E(X) = E(sum(Xij)) 
              = sum(E(Xij)) 
              = sum(Pr(Xij=1)) 
              = n(n-1)/2 * 1/2 
              = n(n-1)/4 

* I think of this as the size of the upper triangle of a square matrix. 
** All sums here are over i, j, where i < j.