Arrays

Question

Let A[1:n ] be such an array such that A[i]=i.An algorithm randomly permutes the elements of A,call the resulting array A'.Let X denote the number of locations such that A'[i]=i.What is expectation of X?

a)n^2

b)n/2

c)n

d)1

Comments

1???

P(1 element in its place is)= 1/n

Now E[x]=Xp(x)

=n*(1/n)

=1

not sure

---

Expectation is = 1

---

my answer is also 1 but in made easy book it is n^2

Answer 1

Assume n = 4,

random variable X = no of elements at correct place.

So, P(X=k) means Probability of exactly k elements at correct place.

E = 1*P(X=1) + 2*P(X=2) + 3*P(X=3) + 4*P(X=4)

note : P(X=3) = 0

But calculating no of permutations with exacly k elements in correct place invloves inclusion-exclusion principle.

No of permutations for exactly k elements in correct positions

= $\left( \sum_{\ell = 0}^{N-K} \frac{(-1)^{\ell}}{\ell!} \right) \frac{N!}{K!}.$

So, P(X=K) = $\left( \sum_{\ell = 0}^{N-K} \frac{(-1)^{\ell}}{\ell!} \right) \frac{1!}{K!}.$

E = $\sum_{K=1}^{N}\left \{ \left( \sum_{\ell = 0}^{N-K} \frac{(-1)^{\ell}}{\ell!} \right) \frac{1}{(K-1)!} \right \}$

=> E = 1

NOTE : $\left( \sum_{\ell = 0}^{N-K} \frac{(-1)^{\ell}}{\ell!} \right) \frac{N!}{K!}.$ if we put K = 0 here,We get the no of dearrangement formula.

Link : 

A brute force checking of This expectation using a c++ code as follows :

• Generate permutations one-by-one and then increment count when $\text{array}[x] = x$ for all permutations.
• finally E = $\frac{\text{count}}{\text{No of permutations}}$

#include <bits/stdc++.h>
using namespace std;
int m[10];
int factorial(int n) {
        if(n!=1) return n*factorial(n-1);
}
int main() {
	int x,cnt=0,n=0;
	string array = "1234";
	/*sort(begin(array), end(array));*/ // sort if not sorted
	int correct_nos;
	do {
		correct_nos = 0;
		for(int i=1;i<=array.length();i++) {
			if(array[i-1] == ('0'+i)) {
				correct_nos++;
				cnt++;
			}
		}
		cout << array << " correct_elements = " << correct_nos<<endl;
		m[correct_nos]++;
        }while( std::next_permutation(begin(array), end(array)) );

	cout << "Exptdval = "<<(1.0)*(cnt/factorial(array.length())) << endl;
	cout << "No of permutations : "<<endl;
	for(int i=1;i<=array.length();i++) {
		cout <<"For exactly "<< i <<" elements in "<< " correct position"<<" = "<< m[i] << endl;
	}
	return 0;
}

O/P :

Calculate Expected Value 

$\\ 1*\frac{8}{4!} + 2*\frac{6}{4!} + 3*0 + 4*\frac{1}{4!} \\ \\ = \frac{8}{24} + \frac{12}{24} + \frac{4}{24} \\ \\ = 1$

Comments

gate booklet is wrong den probably..

---

25 years solved ? for 2017

---

Postal study course of Made easy ...arrays chapter question 10