(Mi pregunta original aún no ha sido respondida. He agregado más aclaraciones).
Al analizar caminatas aleatorias (en gráficos no dirigidos) al ver la caminata aleatoria como una cadena de Markov, requerimos que el gráfico no sea bipartito para que se aplique el teorema fundamental de las cadenas de Markov.
¿Qué sucede si el gráfico es bipartito? Estoy interesado específicamente en el momento de bateo , donde hay un borde entre y en . Digamos que el gráfico bipartito tiene aristas. Podemos agregar un bucle automático a un vértice arbitrario en el gráfico para hacer que el gráfico resultante no sea bipartito; aplicando el teorema fundamental de las cadenas de Markov para nos ofrece entonces que en , y esto es claramente también un límite superior para en .h i , j i j G G m G ′ G ′ h i , j < 2 m + 1 G ′ h i , j G
Pregunta: ¿Es cierto que el reclamo más fuerte mantiene en ? (Esto se ha visto afirmado en los análisis del algoritmo de caminata aleatoria para 2SAT). ¿O realmente tenemos que pasar por este paso adicional de agregar el auto-loop?G
fuente
Había publicado esto como un comentario antes, y creo que responde afirmativamente a la pregunta modificada del usuario686 (cuando y j están conectados por un borde en un gráfico G (no importa si es bipartito o no), h ( i , j ) , el tiempo de golpe esperado de i a j satisface h ( i , j ) < 2 m .)yo j sol h ( i , j ) yo j h ( i , j ) < 2 m
También debo señalar que en su versión original sin editar, la cuestión no afirmó que y j son adyacentes, así que mientras que las respuestas anteriores son relevantes a la pregunta original, que no son relevantes a la nueva versión editada.yo j
Si y j son adyacentes, el tiempo de viaje C ( i , j ) = h ( i , j ) + h ( j , i ) = 2 m R ( i , j ) , donde R ( i , j ) es el efectivo resistencia entre i y j en G, y es como máximo 1 (ya que i y jyo j C( i , j ) = h ( i , j ) + h ( j , i ) = 2 m R ( i , j ) R ( i , j ) yo j 1 yo j están conectados por un borde). Esto muestra que cuando i y j son adyacentes en G , ya que tanto h ( i , j ) como h ( j , i ) son estrictamente positivas.h ( i , j ) < 2 m yo j sol h ( i , j ) h ( j , i )
La identidad cumple para vértices arbitrarios i y j . Aparece una prueba, por ejemplo, en el libro de Lyons y Peres.C( i , j ) = 2 m R ( i , j ) yo j
fuente
@ user686 Lo siento, por mi respuesta anterior: no me di cuenta de que estaba preocupado por vs 2 m . Sin embargo, en ese caso, no creo que la afirmación realizada sea cierta si agrega un bucle automático solo en j . Random paseos a partir de i en el caso de tanto G ' y y G se puede acoplar para que tomen las s un m e medidas en los mismos tiempos hasta que alcanzan j . Esto significa que H ( i , j ) G = H ( i ,2m+1 2m j i G′ G same j , y los tiempos de golpe previstos, por lo tanto, deben ser iguales.H(i,j)G=H(i,j)G′
Además, dado que el límite no es correcto en general (en una ruta de m nodos, h i , j puede ser tan grande como Θ ( m 2 ) ), ¿es su gráfico especial?hi,j<2m+1 m hi,j Θ(m2)
PD: Actualicé mi respuesta anterior, ya que parece que no estaba abordando su principal preocupación.
fuente