1
$\begingroup$

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.

1 Answers 1

2

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$.