GATE CSE 2003 | Question: 61

Question

In a permutation \(a_1 ... a_n\), of n distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\).

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of \(1. . . n\)?

• A. \(\frac{n(n-1)}{2}\)
• B. \(\frac{n(n-1)}{4}\)
• C. \(\frac{n(n+1)}{4}\)
• D. \(2n[\log_2n]\)

Comments

http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2003.html

question 61) 62)

---

http://community.wvu.edu/~krsubramani/courses/sp11/doa/qen/hw2sol.pdf

---

thanks for sharing,it contains awesome questions

Answer 1

61. Option B is correct.

62. Option D is correct.

Answer 2

B is the Answer

Answer 3

Ans -B 

Let \(X_{ij}\) be an indicator random variable s.t. $$X_{ij} = \begin{cases} 0 &\mbox{if } (a_i,a_j) \text {not inverted} \\ 1 & \mbox{if } otherwise. \end{cases}$$ Let random variable \(X\) denotes total number of inversions. So clearly \(X=\sum\limits_{\substack{i,j \\ i<j}}X_{ij}\). Note that their are \(^n\mathrm{C}_2\) terms in summation, because there are total \(^n\mathrm{C}_2\) pairs, and each pair is either inverted or not.
So now we want to find \(E(X)\). Now \(E(X)=\sum\limits_{\substack{i,j \\ i<j}}E(X_{ij})\). But \(E(X_{ij}) = \frac{1}{2}\), because for any pair, probability of inversion is same as of not inversion.
So \(E(X) = \frac{^n\mathrm{C}_2}{2} = \frac{n(n-1)}{4}\).
So option (B) is correct.

Answer 4

https://youtu.be/KFcodn4qfrQ

please check this video for the method used by others to solve the question (linearity of expectation) MIT video

just think it as expected no. of heads in n coin flips.

here n coin flips refers to no. of pairs in the sequence which is n©2. probability of head = probability of a pair being a inversion=0.5

 

remember expectation of a binomial distribution is np, here also same.

expectation of no. of inversion pairs =np=n©2*0.5