I came across the following average-case time complexity analysis for the insertion sort algorithm on page 483 of "Discrete Mathematics and its Application" by Kenneth Rosen:
Average-Case Complexity of the Insertion Sort: What is the average number of comparisons used by the insertion sort to sort $n$ distinct elements?
Solution: We first suppose that $X$ is the random variable equal to the number of comparisons used by the insertion sort to sort a list $a_1 ,a_2 ,...,a_n$ of $n$ distinct elements. Then $E(X)$ is the average number of comparisons used. (Recall that at step $i$ for $i = 2,...,n$ , the insertion sort inserts the $i$ th element in the original list into the correct position in the sorted list of the first $i − 1$ elements of the original list.)
We let $X_i$ be the random variable equal to the number of comparisons used to insert $a_i$ into the proper position after the first $i − 1$ elements $a_1 ,a_2,...,a_{i−1}$ have been sorted. Because
$X=X_2+X_3+···+X_n$,
we can use the linearity of expectations to conclude that
$E(X) = E(X_2 + X_3 +···+X_n) = E(X_2) + E(X_3) +···+E(X_n).$
To find $E(X_i )$ for $i = 2, 3,...,n$ , let $p_j (k)$ denote the probability that the largest of the first $j$ elements in the list occurs at the $k$ th position, that is, that $max(a_1 ,a_2 ,...,a_j ) = a_k$ , where $1 ≤ k ≤ j$. Because the elements of the list are randomly distributed, it is equally likely for the largest element among the first $j$ elements to occur at any position. Consequently, $p_j (k) = \frac{1}{j}$. If $X_i (k)$ equals the number of comparisons used by the insertion sort if $a_i$ is inserted into the $k$ th position in the list once $a_1,a_2 ,...,a_{i−1}$ have been sorted, it follows that $X_i (k) = k$. Because it is possible that $a_i$ is inserted in any of the first $i$ positions, we find that
$E(X_i)$ = $$\sum_{k=1}^{i} p_i(k).X_i(k) = \sum_{k=1}^{i} \frac{1}{i}.k = \frac {1}{i}\sum_{k=1}^{i} k = \frac{1}{i}.\frac{i(i+1)}{2} = \frac{i+1}{2}$$
It follows that
$E(X)$ = $$\sum_{i=2}^{n} E(X_i) = \sum_{i=2}^{n} \frac{i+1}{2} =\frac{n^{2} + 3n -4}{4}$$
I'm having trouble understanding the last paragraph (in bold above). In particular, how can $p_i(k)$ be $1/i$ for all values of $k$?
$p_i(k)$ is the probability of the largest of the first $i$ elements occurring at the $k$-th position. But wouldn't the probability $p_i(k)$ be non-zero only for $k = i - 1$ and $k = i$, and 0 for all other values of $k$? Since the subarray $A[1..i-1]$ is sorted, the largest of the first $i$ elements is either the element to the immediate left of $i$ or $i$ itself, so how can $p_i(k) = 1/i$?