Paseo aleatorio y tiempo medio de golpe en un gráfico simple no dirigido

10

Deje ser un gráfico simple no dirigido en n vértices ym bordes.G=(V,E)nm

Estoy tratando de determinar el tiempo de ejecución esperado de algoritmo de Wilson para generar un árbol de expansión aleatoria de . Allí, se muestra que es O ( τ ) , donde τ es el tiempo medio de golpeo : τ = v V π ( v ) H ( u , v ) , donde:GO(τ)τ

τ=vVπ(v)H(u,v),
  • es ladistribución estacionaria π ( v ) = d ( v )π ,π(v)=d(v)2m
  • es un vértice arbitrario, yu
  • es eltiempo de impacto(tiempo deaccesoAKA), es decir, el número esperado de pasos antes devisitar elvértice v , comenzando desde el vértice u .H(u,v)vu

¿Cuál es el límite superior general para el tiempo medio de golpe? ¿Y cuál es el peor gráfico de caso que maximiza el tiempo medio de golpe?G


Para aclarar mi pregunta, no necesito cálculos ni pruebas detalladas (aunque pueden ser útiles para otras personas que encuentren esta pregunta en el futuro). Para mí personalmente, una cita sería suficiente.

El documento menciona otro algoritmo de Broder que funciona en el tiempo de cobertura esperado (primera vez cuando se han visitado todos los vértices). Luego se dice que el tiempo medio de golpe es siempre menor que el tiempo de cobertura. Sin embargo, solo proporciona un límite asintótico de para la mayoría de los gráficos (es decir, gráficos de expansión ) para contrastarlo con Θ ( n log n ) de Broder para la mayoría de los gráficos (con una definición algo más inclusiva de la mayoría ).Θ(n)Θ(nlogn)

Da un ejemplo de un gráfico donde el tiempo medio de golpe es y el tiempo de cobertura es Θ ( n 3 ) . Si bien se sabe que este es el peor de los casos para este último, no dice específicamente nada sobre el peor de los primeros. Esto significaría que el peor de los casos para el algoritmo de Wilson puede caer entre O ( n 2 ) y O ( n 3 ) .Θ(n2)Θ(n3)O(n2)O(n3)

Hay dos implementaciones disponibles públicamente del algoritmo de Wilson que conozco. Uno está en la Biblioteca de gráficos Boost , mientras que el segundo está en la herramienta de gráficos . La documentación de la primera no menciona el tiempo de ejecución, mientras que la segunda establece:

El tiempo de ejecución típico para gráficos aleatorios es .O(nlogn)

Lo cual no responde a la pregunta, y en realidad parece ser inconsistente con el artículo de Wilson. Pero informo esto por si acaso, para ahorrar tiempo a cualquiera con la misma idea de consultar la documentación de implementación.

Inicialmente había esperado que el peor de los casos pudiera lograrse mediante un gráfico construido al adjuntar un camino a una camarilla, debido a Lovász , donde el tiempo de golpe puede ser tan alto como . Sin embargo, la probabilidad de este evento es de aproximadamente 1Ω(n3) al elegir vértices de distribución estacionaria. En consecuencia, se obtiene unlímiteO(n2)para el tiempo medio de golpe en este gráfico.1nO(n2)

Un artículo de Brightwell y Winkler muestra que un subconjunto de los gráficos de piruleta maximiza el tiempo de golpear esperado, alcanzando . Graph de Lovász también es un gráfico de paleta, pero en este caso el tamaño de la camarilla es 24n3/27, en lugar de la mitad. Sin embargo, se debe tener cuidado de no confundir el tiempo de golpe esperado con el tiempo de golpe medio. Este resultado, como el anterior, se refiere al tiempo de golpe esperado para dos vértices específicos elegidos de antemano.23n

arekolek
fuente
2
¡Gracias por detectar este error en la documentación de la herramienta gráfica! De hecho, para los gráficos aleatorios típicos, el tiempo medio de golpe es (véase, por ejemplo, arxiv.org/abs/1003.1266 ), no O ( n log n ) . Esto se corregirá en la próxima versión. (Tenga en cuenta también que la herramienta gráfica utiliza la Biblioteca de gráficos Boost debajo, por lo que no son implementaciones realmente distintas).O(n)O(nlogn)
Tiago Peixoto
1
@Tiago ¡Estoy feliz de contribuir! Gracias por tu comentario. También puede estar interesado en mencionar el tiempo esperado en el peor de los casos (aunque sea poco probable), ya que ahora he actualizado mi respuesta con una respuesta de David Wilson.
arekolek

Respuestas:

11

He decidido preguntarle al propio David Wilson, poco después recibí una respuesta:

Para gráficos no dirigidos en vértices, el tiempo de golpe medio en el peor de los casos es Θ ( n 3 ) . El ejemplo es el gráfico de barra , que consta de dos camarillas de tamaño n / 3 conectadas por una ruta de longitud n / 3nΘ(n3)n/3n/3H(x,y)xyH(x,y)xyx

Incluso hay una prueba de este hecho en el libro mencionado anteriormente, que dice así:

n=2n1+n2n1vlvLvRvrvL-w1-wnorte2-vR

norte1vL1norte1w1norte12w1w11n2n12n2

n1=n2=n/3O(n3)

Es cierto que estoy perdido en el punto que dicen:

w11n2

(n+1)354

Sin embargo, los comentarios sobre la prueba informal todavía son bienvenidos.

arekolek
fuente
3

En un artículo reciente , encontramos un límite superior de mn (sin grandes O) en el número esperado de "ciclos reventados" por el algoritmo de Wilson y está estrechamente relacionado con las constantes. No responde directamente a la pregunta del tiempo de ejecución de los algoritmos de Wilson, ya que el tamaño promedio de los ciclos reventados no parece obvio. Por otro lado, no tengo suficiente "reputación" para dejar un comentario ...

Heng Guo
fuente