Randomized quicksort expected running time analysis
Let us denote by $p(n,i,j)$ the probability that $X_{ij} = 1$ given that there are $n$ elements.

Let $k$ be the first chosen pivot. If $k \in \{i,j\}$ then $X_{ij} = 1$. If $i &lt; k &lt; j$, then $X_{ij} = 0$. Otherwise, if $k &lt; i$ then $X_{ij} = 1$ with probability $p(n-k, i-k, j-k)$, and if $k &gt; j$ then $X_{ij} = 1$ with probability $p(k-1, i, j)$. Altogether, we get
$$
p(n,i,j) = \frac{2}{n} + \frac{1}{n} \sum_{k=1}^{i-1} p(n-k, i-k, j-k) + \frac{1}{n} \sum_{k=j+1}^n p(k-1,i,j).
$$
We can now prove that $p(n,i,j) = 2/(j-i+1)$ by induction, by noticing that
$$
\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1} = \\
\frac{2}{n} + \frac{2}{n} \cdot \frac{n-(j-i+1)}{j-i+1} = \\
\frac{2}{n} + \frac{2}{j-i+1} - \frac{2}{n} = \\ 
\frac{2}{j-i+1}.
$$
Another way to get this result is to follow the algorithm until the first time when a pivot (at any level of recursion) in $\{i,\ldots,j\}$ gets selected. Elements $i$ and $j$ are compared if and only if this pivot happens to be $i$ or $j$, which happens with probability $2/(j-i+1)$.