Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am given a uniformly chosen permutation of the set $\{1,\ldots,n\}$ as an array $A[1,\ldots,n]$. For an integer $1 \leq j \leq n$ I am studing the distribution of the variable $X$ counting the number of comparisions $(A[i]> key)$ in the above algorithm:

key = A[j]
i = j-1
while (i > 0) and (A[i] > key)
   A[i+1] = A[i]
   i--;

It is assumed that no comparison is performed when $i \leq 0$. The book I am reading states $Pr[X = k] = 1/j$ for $1 <= k < j-1$ and $Pr[X = j-1] = 2/j$.

There is no explanation why is that so, so I am wondering if anyone could explain to me why is $X$ distributed as stated since I am missing the intuition behind the calculation of this specific probability.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

When you're doing this step of the insertion sort algorithm, A[1] .. A[j-1] are the original A[1] .. A[j-1] sorted into increasing order. Since the initial permutation was random, the rank of A[j] among A[1] .. A[j] is equally likely to be each of the $j$ possibilities. If A[j] is the $i$'th largest of A[1] .. A[j], the algorithm will compare it to A[j-1], ..., A[j-i], so $X = i$, except that if $i=j$ there is no A[0] to compare it to. Thus for $k = 1, 2, \ldots j-2$ we have $P(X = k) = 1/j$, but $X = j-1$ covers two possibilities ($A[j]$ is either lowest or second-lowest) so $P(X = j-1) = 2/j$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.