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.