I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis.
Setting in CLRS
First let $Z = \{z_1, ..., z_n\}$ be the set of elements of the input array $A$ in sorted order. $X$ is defined as the number of comparison we make (i.e., between pivot and an element). Because any two elements of the array $A$ is compared at most once, we have $X = \sum_{i=1}^{n-1} \sum_{j = i+1}^{n} X_{ij}$ where $X_{ij} = 1$ if $z_i$ and $z_j$ are compared. So we just need to calculate the expectation, $\mathbb{E} \left[ X \right] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \mathbb{P} \left(X_{ij} = 1\right)$.
So we just need to calculate $\mathbb{P} \left(X_{ij} = 1\right)$. According to the book, $\mathbb{P} \left(X_{ij} = 2\right) = \frac{1}{j - i + 1}$ and I don't follow this result.
My analysis
Let $k$ be the index of the randomly selected pivot. Conditioning on the event that $k \in Z_{ij}$ where $Z_{ij} = \{z_i, z_{i+1}, ..., z_j\}$,
\begin{equation} \begin{aligned} \mathbb{P} \left(X_{ij} = 1\right) &= \mathbb{P} \left( \left.X_{ij} = 1 \right| k \in Z_{ij}\right) \mathbb{P} \left(k \in Z_{ij} \right) + \mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \mathbb{P} \left(k \not\in Z_{ij} \right) \\ &= \frac{2}{j - i + n} \frac{j - i + 1}{n} + \mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \left(1 - \frac{j - i + 1}{n} \right). \end{aligned} \end{equation}
From this, we can see that if $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) = \mathbb{P} \left(X_{ij} = 1 \right)$, then indeed $\mathbb{P} \left(X_{ij} = 1 \right) = \frac{2}{j-i+n}$ agreeing the book's result. But I don't think that equality holds.
Suppose we choose pivot $k > j$ which is not in $Z_{ij}$. Then, we reduce the problem size to $\{1, ..., k-1\}$. Because $z_i$ and $z_j$ still belong to the same partition, we are given another chance to pick another pivot such that it is either $i$ or $j$. So I would expect that $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) = \mathbb{P} \left(X_{ij} = 1 \right)$ does not hold.
Question
Is my analysis correct, i.e., $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \not= \mathbb{P} \left(X_{ij} = 1 \right)$? If not, how to derive $\mathbb{P} \left(X_{ij} = 1 \right)$ considering the fact that if the chose pivot is not in $Z_{ij}$ we are given another chance?
Update
Yuval Filmus' answer is very good and complete in itself. But let me just add a little more step just for completeness. In particular steps leading to $\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1}$ were not trivial to me. So hopefully this may help others.
As Yuval Filmus said we can prove that $p(n,i,j) = 2/(j-i+1)$ using (strong) induction (over $n$). First check the base case which is $n = 2$ because we need at least two elements in order to even think about comparing $z_i$ and $z_j$. With $n = 2$, $j = 2$, $i = 1$ and $p(2,1,2) = \frac{2}{2 - 1 + 1} = 1$. If we have 2 elements, then pivot has to be one of them, and $\mathbb{P} \left(X_{ij} =1; 2\right) = 1$. This proves the base case.
Now consider the inductive step. Assume that $p(m,i,j) = \frac{2}{j-i+1}$ for all $m < n$. In particular, note that all the values of the first argument of $p(\cdot, \cdot, \cdot)$ inside both summations are less than $n$. Hence, we can plug in $p(m,i,j) = \frac{2}{j-i+1}$.
\begin{equation} \begin{aligned} p(n,i,j) &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{1}{n} \sum_{k=1}^{i-1} \frac{2}{(j-k)-(i-k)+1} + \frac{1}{n} \sum_{k=j+1}^{n} \frac{2}{j-i+1} \\ &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{2}{n} \frac{i-1}{j-i+1} + \frac{2}{n} \frac{n-j}{j-i+1}, \end{aligned} \end{equation}
which is the expression given by Yuval Filmus. The rest of the step is in his answer.
