Pregunta técnica sobre caminatas aleatorias

9

(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 GGhi,jijGGmGGhi,j<2m+1Ghi,jG

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?Ghi,j<2mG

usuario686
fuente

Respuestas:

5

Esta respuesta demostró algo diferente de lo que realmente le interesaba al interrogador. Dejarlo aquí para que otros no repitan el mismo error.

En la mayoría de los casos, uno puede justificar formalmente la noción intuitiva de que "los bucles automáticos solo pueden ralentizar el camino" mediante un argumento de acoplamiento. En este caso, por ejemplo, uno puede acoplar la caminata con los self loops (llamémosla ) y la que no tiene los self loops (llamémosle B ) para que A siga los mismos pasos que B , pero se retrase en el tiempo. Esto puede hacerse, por ejemplo, de la siguiente manera: supongamos que B comienza en u = x 0 y pasa por x i : i = 1 , 2 , ... , kABABBu=x0xi:i=1,2,,k. Ahora, implementamos siguiente manera: A también atraviesa los mismos vértices que B , excepto que el vértice x i espera el tiempo geométrico ( p i ) donde p i es la probabilidad del bucle automático en x i . Tenga en cuenta que esta es una implementación correcta de A (todas las probabilidades de transición son correctas), y la forma del acoplamiento asegura que A nunca alcance ningún vértice antes de B , es decir, hemos acoplado H A t y H B tAABxipipixiAABHtAHtB (los tiempos de golpe aleatorio en las dos caminatas) de modo que con probabilidad 1 . Por lo tanto, sigue la desigualdad para el tiempo de golpe esperado.HtAHtB1

Piyush
fuente
Lo siento, pero no creo que esto responda mi pregunta. Estoy de acuerdo en que en G está limitada por h i , j en G ' , que a su vez está limitada por 2 m + 1 . Pero me gustaría obtener el límite más fuerte que h i , j en G tiene un límite superior de 2 m . (OK, me doy cuenta de que el " + 1 " no es gran cosa, pero por otro lado he visto la afirmación hecha sin el " + 1hi,jGhi,jG2m+1hi,jG2m+1+1"Y por eso me pregunto si es técnicamente precisa).
user686
@ user686 ¿Puedes compartir la referencia?
Tyson Williams
2

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 .)ijGh(i,j)ijh(i,j)<2m

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.ij

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 jijC(i,j)=h(i,j)+h(j,i)=2mR(i,j)R(i,j)ij1ijestá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)<2mijGh(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)=2mR(i,j)ij

Piyush
fuente
Gracias; si el resultado que indicó también es válido para gráficos bipartitos (comprobaré la referencia que proporcionó), ¡entonces esto sí responde a mi pregunta!
usuario686
0

@ 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+12mjiGGsamej , 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+1mhi,jΘ(m2)

PD: Actualicé mi respuesta anterior, ya que parece que no estaba abordando su principal preocupación.

Piyush
fuente
Por otro lado, 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 la resistencia efectiva entre i y j en G , y es como máximo 1 . Esto muestra que hijC(i,j)=h(i,j)+h(j,i)=2mR(i,j)R(i,j)ijG1 cuando i y j son adyacentes en G , ya que tanto h ( i , j ) como h ( j , i ) son estrictamente positivas. h(i,j)<2mijGh(i,j)h(j,i)
Piyush
Está bien (y a veces mejor) mantener la respuesta incluso cuando es incorrecta o no responde la pregunta para que otros no cometan el mismo error, solo agregue una línea al comienzo de la respuesta que explique por qué es incorrecta o no responde la pregunta :)
Kaveh
@Kaveh: Gracias, soy nuevo aquí. Mi respuesta anterior no fue incorrecta, pero no respondió lo que el usuario686 consideró el problema importante.
Piyush
@Piyush: simplemente agregue una línea en negrita a su parte superior para que quede claro que no está respondiendo la pregunta.
Kaveh