There are other questions regrading this topic on this site, that still leave me empty. I am considering direct computation, meaning, no guessing and induction.
Assume our sequence is ordered for simplicity.
Let $X_{i,j}$ be a random variable, counting how many times $i$-th and $j$-th element have been compared. As two elements cannot be compared twice we have
$$X_{i,j}:\Omega\to\{0,1\}$$
$$X=\sum\limits_{\forall_i}\sum\limits_{j<i}X_{i,j}$$ and thus $$E(X)=\sum\limits_{\forall_i}\sum\limits_{j<i}E(X_{i,j})$$
At each step n the algorithm, there are two possible events for pivot selection $$E_1: \text{pivot is between }i \text{-th and} j \text{-th element}$$ $$E_2: \bar{E}_1$$
Thus we can write $$P(X_{i,j})=P(X_{i,j}\cap E_1)+P(X_{i,j}\cap E_2)$$ We know that $P(X_{i,j}\cap E_2)$ must be zero.
Here is where my problem begins. In all sources it says $$P(X_{i,j})=\frac{2}{j-i+1}$$
But in my calculuations, this is actually $P(X_{i,j}|E_1)$.
Can someone please explain where I am making the mistake? There are two options, either I am wrong in thinking it is actually $P(X_{i,j}|E_1)$, or we are supposed to consider that specific event, meaining comparing the two elements, given that $E$ happens. In that case, why is this so?
Let the ordered sequence be $x_1, x_2, \cdots, x_n$. Assume in some iteration, element $x \in \{x_{i+1}, \cdots, x_{j-1}\}$ is selected as pivot before $x_i$ and $x_j$. In this case, $X_{i,j} = 0$. Actually, this is the only case that $x_i$ and $x_j$ are not compared. The probability of this case is $\frac{j - i - 1}{j - i + 1}$ in which $j - i + 1$ is the # of elements in the range $\{x_i, x_{i+1}, \cdots, x_j\}$ and $j - i - 1$ counts those in $\{x_{i+1}, \cdots, x_{j-1}\}$. Therefore, we have $$ \Pr[X_{i,j} = 1] = \frac{2}{j-i+1} $$
In your derivation, it is not correct to claim that $\Pr[X_{i,j}\land E_2] = 0$. Note that if a pivot is sampled from the range $\{\cdots, x_{i-1}\}\cup\{x_{j+1}, \cdots\}$, it is still possible that $x_i$ and $x_j$ are compared in later iterations.