Podemos definir una caminata aleatoria en el gráfico como Dado un gráfico y un punto de partida, seleccionamos un vecino al azar y nos movemos a este vecino; luego seleccionamos un vecino de este punto al azar, y nos movemos hacia él, etc. La secuencia (aleatoria) de puntos seleccionados de esta manera es una caminata aleatoria en el gráfico. Prácticamente el movimiento brownie es el mejor ejemplo de caminata aleatoria. Una caminata aleatoria es una cadena de Markov finita que es reversible en el tiempo. De hecho, no hay mucha diferencia entre la teoría de las caminatas aleatorias en gráficos y la teoría de las cadenas finitas de Markov; cada cadena de Markov puede verse como una caminata aleatoria en un gráfico dirigido, si permitimos bordes ponderados. Del mismo modo, las cadenas de Markov reversibles en el tiempo pueden verse como caminatas aleatorias en gráficos no dirigidos y cadenas simétricas de Markov, como caminatas aleatorias en gráficos simétricos regulares.
Estas son algunas propiedades de la caminata aleatoria en el gráfico.
Distribución estacionaria : ¿cuál es la distribución de nuestra ubicación actual si ejecutamos la caminata aleatoria por un número infinito de pasos?
- ¿Por qué las letras P, Q, R, S y T se usan tan comúnmente en matemáticas?
- ¿Cuál es una buena manera de aprender y comprender la escritura dependiente en un idioma como Idris / Coq / Agda?
- ¿Cuál es la diferencia entre notación matemática y notación de programación? ¿Por qué usar uno sobre el otro? ¿Por qué no solo usar siempre la programación?
- ¿En qué se diferencia la teoría lógica de las matemáticas de la teoría lógica de la informática?
- ¿La mayoría de los cursos requeridos en un programa universitario de ciencias de la computación son inútiles para la aplicabilidad de trabajo de programador del mundo real?
Si tenemos una distribución π sobre los nodos, podemos obtener la distribución después de un paso calculando π ′ = PT · π. Usando esta definición, podemos definir una distribución estacionaria π * como una distribución con la propiedad que PT · π * = π *. Las distribuciones estacionarias no siempre son únicas, pero bajo ciertas condiciones, lo son. También es el caso que bajo ciertas condiciones, limt → ∞ (PT) tπ = π * para todas las distribuciones iniciales π
Matriz de transición: una caminata aleatoria (o cadena de Markov) se representa más convenientemente por su matriz de transición. La matriz de transición es una matriz cuadrada que denota la probabilidad de transición de cualquier vértice en el gráfico a cualquier otro vértice. Formalmente, Puv = Pr [yendo de u a v, dado que estamos en u]. Por lo tanto, para una caminata aleatoria, Puv = 1 / du if (u, v) ∈ E, y 0 en caso contrario (donde du es el grado de u)
Caminatas aleatorias en los bordes: pensaremos en las caminatas aleatorias de una manera ligeramente diferente, donde en lugar de caminar de nodo a nodo, nuestra caminata va de borde a borde. Siempre que estemos en un borde uv, elegimos el siguiente borde u al azar del conjunto de bordes incidentes con v. Luego podemos ver que la distribución uniforme en los bordes (πu → v = 1 / 2m ∀ (u → v) ∈ E ) es una distribución estacionaria. Esto se debe a que ([matemáticas] P ^ T · [/ matemáticas] π) v → w = suma (de u, u: (u, v) ∈E) 1 / 2m.1 / dv = 1 / 2m = πv → w
Tiempo de cobertura: – Si tuviéramos un límite en el tiempo de viaje para todos los pares (u, v) (llame a esto límite x), podríamos obtener un límite (en expectativa) en el tiempo de cobertura ejecutando la caminata aleatoria para x ∗ n pasos. Desafortunadamente, el límite solo es válido para pares (u, v) donde hay un límite entre u y v. Sin embargo, todavía podemos encontrar un método diferente para limitar el tiempo de cobertura.
