retagged by
20,602 views
66 votes
66 votes

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\)?

  1. \(\frac{n(n-1)}{2}\)
  2. \(\frac{n(n-1)}{4}\)
  3. \(\frac{n(n+1)}{4}\)
  4. \(2n[\log_2n]\)
retagged by

12 Answers

0 votes
0 votes

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.

0 votes
0 votes

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

 

Answer:

Related questions

1 votes
1 votes
1 answer
3
rsansiya111 asked Dec 7, 2021
316 views
In an array A[1..n] of n distinct elements, if i < j and A[i] A[j], then the pair (i,j) is called an inversion of A.How many inversions are there in the array A = {n,n-1...