Complejidad media de la ordenación por comparación de selección aleatoria

Question

Motivación. Supongamos que tenemos una serie de imágenes que queremos ordenar linealmente de la más bonita a la más fea. Tenemos a nuestra disposición un esteta entrenado, al que podemos mostrar dos imágenes y preguntarle cuál es la más bonita. Suponemos que las preferencias del esteta son invariables y consistentes internamente. (Es una suposición bastante grande, pero esto es matemática: Nuestras suposiciones no tienen que ser probables, sólo consistentes).

Nuestra tarea es descubrir el verdadero orden estético entre las imágenes sin pagar al esteta por demasiado trabajo. Lo ideal sería utilizar un buen algoritmo de ordenación por comparación cercano al mínimo, como la ordenación por inserción binaria que viene a ser $n$ del límite teórico de información de $\log_2 n!$ comparaciones.

Por desgracia, la mayoría de los algoritmos disponibles tienden a plantear al esteta una serie de preguntas en las que se le pide que compare la misma imagen con varias otras imágenes sucesivamente, y eso le parece tan aburrido que amenaza con aumentar sus tarifas. Mientras intentamos encontrar un algoritmo mejor, el miembro más joven del equipo de diseño sugiere que nos limitemos a hacer preguntas al azar hasta que sepamos lo suficiente (pero evitando las preguntas de las que ya podemos deducir la respuesta). ¿Es una buena idea?

Pregunta real . Dado $n$ , dejemos que $R_0$ sea la relación de identidad en $\{1,2,3,\ldots,n\}$ . Mientras $R_k$ no es una orden total, elija $(a,b)$ uniformemente en $\{(a,b) \mid 1\le a<b\le n\}\setminus R_k$ y que $R_{k+1}$ sea el cierre transitivo de $R_k\cup\{(a,b)\}$ .

¿Cuál es el número previsto de pasos hasta $R_k$ ¿es una orden total?

La respuesta ideal sería dar una forma explícita (y factible) de calcularla, pero sólo el comportamiento asintótico sería interesante de conocer.

Answer 1

Esta respuesta es parcial -- es lo que obtengo de las ideas de Obinna hasta el punto en que ya no puedo seguir su razonamiento. (Algunas partes están mal; las dejo aquí como ejemplos de algo que no funciona).

Podemos reformular el problema como

Procesar los bordes $\{(a,b)\mid 1\le a < b \le n\}$ en un orden aleatorio (elegido uniformemente). Cada vez que una arista es no en el cierre transitivo de las aristas consideradas hasta ahora, corresponde a una pregunta que hay que formular. ¿Cuál es el número previsto de preguntas que hay que formular?

Esta reformulación corresponde a la exclusión de las aristas que son en el cierre transitivo perezosamente cuando nuestra elección aleatoria les llega, en lugar de antes de cada elección. En cada momento la siguiente pregunta en realidad que se pregunta siempre acaba siendo elegida uniformemente entre las preguntas que tiene sentido hacer en cualquier paso, por lo que la reformulación no cambia las posibles secuencias de preguntas ni su probabilidad.

Por aditividad de las expectativas, el número esperado de preguntas es simplemente la suma sobre todas las aristas posibles de la probabilidad de que esta arista se convierta en una pregunta durante una ejecución del algoritmo.

Para el borde $(i,j)$ El hecho de que se convierta en una pregunta depende de las aristas $(a,b)$ con $i\le a < b \le j$ se han considerado antes de $(i,j)$ . Bordes con extremos antes de $i$ o después de $j$ no importan, y se ve que la probabilidad depende sólo de la distancia entre $i$ y $j$ .

Dejemos que $f(k)$ sea la probabilidad de que, en un gráfico aleatorio en los vértices $\{1,2,3,\ldots k\}$ donde cada arista posible aparece con probabilidad $1/2$ no hay un camino estrictamente creciente desde $1$ a $k$ que contenga al menos $2$ bordes.

La probabilidad de que el borde $(i,j)$ se convierte en una pregunta es entonces $f(j-i+1)$ , porque cada otros borde es igualmente probable que se considere antes de $(i,j)$ o después (Ups, no. La probabilidad de que cada arista esté en el gráfico es $1/2$ pero las aristas no son independientes) . Y la respuesta que buscamos es $$\sum_{1\le i<j\le n} f(j-i+1) = \sum_{k=2}^n (n-k+1)f(k) $$

La respuesta de Obinna parece concluir (utilizando una analogía que no puedo seguir) que $f(k)=2/k$ . Sin embargo, eso no puede ser correcto, porque hay $2^{k(k-1)/2}$ gráficos aleatorios igualmente probables que se consideran en la definición anterior de $f(k)$ Así que $f(k)$ es seguramente algún múltiplo de $2^{-k(k-1)/2}$ . Y eso no puede ser $2/k$ cuando $k$ no es un poder de $2$ .

No encuentro una expresión para $f(k)$ Sin embargo. (Tengo un algoritmo de programación dinámica para calcular $f(2)$ hasta $f(k)$ en $O(k^2)$ tiempo, pero no es inmediatamente esclarecedor).