Para la lista $X={x_1,\cdots,x_n}$ de $n$ elementos con un orden desconocido. Se selecciona un pivote $p$ de $X$ de manera uniforme al azar. ¿Cuál es la probabilidad de que dos elementos dados $x_i$ y $x_j$ estén en particiones diferentes de la lista con respecto al pivote $p$?
Tenemos una lista de $n$ elementos $X={x_1,\cdots,x_n}$ en la que no tenemos idea sobre el orden de sus elementos. Ahora, un pivote se selecciona de manera uniforme al azar de $X$, es decir, $P(p=x_k)=1/n$ para todo $i=1$ a $n$. Necesitamos encontrar la probabilidad de que para cualquier elemento $x_i,x_j\in X$, sea $x_i o $x_j. En su lugar, podemos empezar encontrando la probabilidad de que $x_i para todos los posibles $p$.
Ordenemos la lista en orden ascendente para formar $X'=\{x'_1,\cdots,x'_n\}$ lo cual no alterará la probabilidad ya que el $p$ se elige uniformemente al azar. Si $p=x'_1$, entonces no hay elementos menores que $p$, si $p=x'_2$, entonces solo hay un elemento menor que $p$, si $p=x'_3$, entonces hay 2 elementos menores que $p$, y así sucesivamente. Por lo tanto,
\begin{align} P(x'_k De manera similar, \begin{align} P(x'_k>p\text{ para un }p\text{ elegido al azar})=\frac{n-1}{2n} \end{align} \begin{align} \implies P(x'_ip)=\frac{(n-1)^2}{4n^2} \end{align} y la probabilidad requerida es $\frac{2(n-1)^2}{4n^2}=\frac{(n-1)^2}{2n^2}$.
¿Estoy pensando en la forma correcta?
