Selección Aleatoria

El algoritmo de selección aleatoria es el siguiente:

Entrada: una matriz de (distintos, por simplicidad) números y un número$A$$n$$k\in [n]$

Salida: El " elemento de rango " de (es decir, el que está en la posición si fue ordenado)$k$$A$$k$$A$

Método:

• Si hay un elemento en , devuélvalo$A$
• Seleccione un elemento (el "pivote") uniformemente al azar$p$
• Calcule los conjuntos yR = { a ∈ A : a > p $L = \{a\in A : a < p\}$$R = \{a\in A : a > p\}$
• Si $|L| \ge k$ , volver al rango $k$ elemento de $L$ .
• De lo contrario, devuelva el rango $k - |L|$elemento de $R$

Me hicieron la siguiente pregunta:

Suponga que $k=n/2$ , por lo que está buscando la mediana y deja que $\alpha\in (1/2,1)$ sea ​​una constante. ¿Cuál es la probabilidad de que, en la primera llamada recursiva, el conjunto que contiene la mediana tenga un tamaño como máximo $\alpha n$ ?

Me dijeron que la respuesta es $2\alpha - 1$ , con la justificación "El pivote seleccionado debe estar entre $1−\alpha$ y $\alpha$ veces la matriz original"

¿Por qué? Como $\alpha \in (0.5, 1)$ , cualquier elemento que se elija como pivote es más grande o más pequeño que más de la mitad de los elementos originales. La mediana siempre se encuentra en el subconjunto más grande, porque los elementos en el subconjunto particionado son siempre menores que el pivote.

Si el pivote se encuentra en la primera mitad de la matriz original (menos de la mitad de ellos), la mediana seguramente estará en la segunda mitad más grande, porque una vez que se encuentra la mediana, debe estar en la posición media de la matriz, y todo antes del pivote es más pequeño como se indicó anteriormente.

Si el pivote se encuentra en la segunda mitad de la matriz original (más de la mitad de los elementos), la mediana seguramente será la primera mitad más grande, por la misma razón, todo antes del pivote se considera más pequeño.

Ejemplo:

3 4 5 8 7 9 2 1 6 10

La mediana es 5.

Supongamos que el pivote elegido es 2. Entonces, después de la primera iteración, se convierte en:

1 2 .... parte más grande ...

Solo 1y 2se intercambian después de la primera iteración. El número 5 (la mediana) todavía está en la primera mitad mayor (de acuerdo con el pivote 2). El punto es que la mediana siempre se encuentra en la mitad mayor, ¿cómo puede tener la oportunidad de permanecer en un subconjunto más pequeño?

Supongamos que su matriz tiene elementos. Como ha notado, la mediana siempre está en la parte más grande después de la primera partición. La parte más grande tiene tamaño como máximo si la parte más pequeña tiene tamaño al menos . Esto sucede cuando elige un pivote que no es uno de los elementos más pequeños o más grandes . Como , sabes que estos son conjuntos disjuntos, por lo que la probabilidad de golpear uno de los pivotes malos es solo , y .α n ( 1 - α ) n ( 1 - α ) n α > 1 / 2 2 - 2 α 1 - 2 + 2 α = 2 α - $n$$\alpha n$$(1-\alpha) n$$(1-\alpha) n$$\alpha > 1/2$$2 - 2\alpha$$1- 2 + 2\alpha=2\alpha - 1$