Número de nodos distintos en una caminata aleatoria

El tiempo de conmutación en un gráfico conectado se define como el número esperado de pasos en una caminata aleatoria que comienza en , antes de que se visite el nodo y luego se vuelva a alcanzar el nodo . Básicamente es la suma de los dos tiempos de golpeo y . $G=(V,E)$ $i$ $j$ $i$ $H(i,j)$ $H(j,i)$

¿Hay algo similar al tiempo de viaje (no exactamente el mismo) pero definido en términos de nodos? En otras palabras, ¿cuál es el número esperado de nodos distintos que visitará una caminata aleatoria que comienza en y regresa en ? $i$ $i$

Actualización (30 de septiembre de 2012): hay una serie de trabajos relacionados sobre la cantidad de sitios distintos visitados por un caminante aleatorio en una red (es decir, ). Por ejemplo, consulte: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=no $\mathbb{Z}^n$

¿Alguien ha leído algo sobre esto?

graph-theory co.combinatorics random-walks pr.probability Fabrizio Silvestri
fuente

¿Cuál es el problema con el siguiente argumento? Una caminata aleatoria en un gráfico puede describirse mediante una cadena de Markov donde los estados son los nodos. Del mismo modo, uno puede representar la misma caminata por una cadena de Markov donde los estados pueden ser los bordes. (Cada borde también contiene la información del nodo visitado actual). Una vez que se obtiene una cadena de Markov, puede usar cualquier definición / resultado de cadenas de Markov.

Abuzer Yakaryilmaz

Gracias por el comentario. De hecho, olvidé decir nodos distintos . Voy a modificar la pregunta ahora mismo.

Fabrizio Silvestri

Tal vez me lo perdí (lo siento si es así), pero ¿cuál es la URL de la publicación SE?

He eliminado la publicación SE ... Está prohibido publicar la misma pregunta en dos lugares diferentes.

Fabrizio Silvestri

depende del gráfico particular, ¿verdad? ¿Puedes esbozar algo conocido sobre problemas similares?

vzn

Respuestas:

de preguntas y respuestas con usted en los comentarios que parece estar interesado en estudiar algo definido como la distancia de la pila en este conjunto de diapositivas, en el modelado matemático de cachés

defina la distancia de la pila de una referencia para que sea el número de direcciones de bloque únicas entre la referencia actual y la referencia anterior al mismo número de bloque.

tiene algunos análisis empíricos a través de puntos de referencia. dice que, en general, "no se conoce la medida de la localidad" de las solicitudes de caché y luego propone la distancia de la pila como tal medida. no lo relaciona con la teoría de gráficas aleatorias, aunque esboza esa conexión en sus comentarios. (Parece que la distancia de la pila podría estar relacionada con la mezcla de la cadena de Markov ?)

parece que está interesado en modelar el rendimiento de la memoria caché o los algoritmos de optimización al considerar las solicitudes de memoria caché como nodos de un gráfico y los bordes como transiciones entre solicitudes adyacentes. No he visto documentos que estudien la estructura de este gráfico. parece probable que no sea un gráfico puramente aleatorio en aplicaciones reales debido al éxito de los cachés en la práctica y a lo que se conoce como localidad espacial y temporal en las diapositivas anteriores. es decir, algún tipo de "agrupamiento" como Joe esboza en su respuesta.

(¿Tal vez tiene una estructura de mundo pequeña ?, que es bastante ubicua en los datos del mundo real)

vzn
fuente

Buena atrapada. De hecho, tiene una pequeña estructura mundial. De hecho, en la aplicación que tengo en mente, la distribución de grados sigue una ley de poder. Ahora, esto puede ayudar ... Aún así, no hemos encontrado una buena manera de hacerlo :)

Fabrizio Silvestri

Gracias. ¿Qué parámetro de almacenamiento en caché está tratando de optimizar? parece probable que se correlacione directamente con el exponente de la ley de potencia de alguna manera ... Sospecha que los enfoques simples de Monte Carlo podrían mostrar que la distancia de la pila está relacionada con el exponente de la ley de potencia, etc.

vzn

bueno ... Al principio, estaba pensando en correlacionar k con

en la ley de potencia. Obviamente, los diferentes valores de

, es decir,

, deberán tratarse por separado. Solo intentaba ver si había algo más allá de los gráficos de la ley de poder. Algo más general, por así decirlo. De todos modos, quiero comprobar el concepto de distancia de pila. No sabía sobre eso.

α

$\alpha$

α

$\alpha$

= 1, < 1, > 1

$=1, < 1, > 1$

Fabrizio Silvestri

Parece que la distancia de la pila no se ha estudiado directamente en la teoría de grafos, pero es un campo vasto. tenga en cuenta que el modelo watts / strogatz es bueno para los enfoques de monte-carlo que generan gráficos de mundo pequeño. también caminatas aleatorias en un gráfico de lovasz es un buen estudio de la teoría de caminatas en gráficas aleatorias.

vzn

Un comentario: Hace poco asistí a una charla de Bruce Reed con el título Atrapando a un malvado borracho , que fue un trabajo conjunto con Natasha Komorov y Peter Winkler. Si puede obtener los resultados de este trabajo, tal vez eso pueda ayudarlo en alguna dirección.

En general, demuestran un límite superior en el número de pasos que un policía necesita en un gráfico general para poder atrapar a un ladrón, cuando sabemos que el ladrón se mueve al azar a lo largo de los bordes.

Pål GD
fuente

¿Alguna posibilidad de tener un borrador o una copia de las diapositivas?

Fabrizio Silvestri

Lo siento, no tengo más para dar, pero tal vez este hilo de MO es de ayuda: policías y ladrones borrachos .

Pål GD

Gracias Pål ... Estoy mirando el papel vinculado desde el hilo MO.

Fabrizio Silvestri

Esta no es realmente una respuesta adecuada a su pregunta, pero es demasiado larga para un comentario.

La cantidad que busca variará de un gráfico a otro y dependerá del sitio inicial del caminante. El número esperado de nodos intermedios distintos dependerá en gran medida de la agrupación dentro del gráfico, y esperaría que el número esperado de nodos intermedios distintos esté correlacionado con el coeficiente de agrupación .

Un grupo es básicamente un subconjunto de vértices que comparten una gran cantidad de bordes, de modo que cada vértice está conectado a una gran fracción de los otros vértices dentro del grupo. Cuando un caminante ingresa a un grupo, es probable que permanezca en esa región durante un gran número de saltos, posiblemente visitando cada nodo muchas veces. De hecho, el uso de caminatas aleatorias de esta manera es una de las técnicas computacionales que se utilizan para identificar grupos en gráficos grandes. Por lo tanto, para un caminante que comienza en un grupo, el número esperado de vértices intermedios distintos probablemente se escalará con el tamaño del grupo y la probabilidad promedio de abandonar el grupo.

$N$ $\frac{1}{N}$ $N+1$

El grado promedio de vértices dentro del gráfico también jugará un papel importante, aunque esto está relacionado con la agrupación. La razón de esto es que cuando el caminante salta a un vértice con grado 1, debe volver al vértice anterior en el siguiente salto. Incluso cuando el grado es 2, solo hay una ruta que se puede seguir a través del gráfico, aunque se puede recorrer en cualquier dirección en cada salto. Por otro lado, para gráficos con un grado superior a 2, el número de rutas puede explotar, por lo que es extremadamente improbable que regrese al sitio inicial, incluso si la ruta más corta entre ellas es pequeña.

Por lo tanto, es de esperar que el número de vértices intermedios distintos sea alto para los gráficos que tienen un grado promedio sustancialmente superior a 2 y tampoco tienen agrupaciones significativas, como los árboles.

Por supuesto, estos comentarios ya no son válidos en el caso de caminatas aleatorias cuánticas, pero supongo que solo te importa el caso clásico.

Joe Fitzsimons
fuente