Tiempo de cobertura

En matemáticas, el tiempo de cobertura de una cadena de Markov finita es el número de pasos que da la cadena, desde un estado inicial dado, hasta el primer paso en el que se han alcanzado todos los estados. Es una variable aleatoria que depende de la cadena de Markov y de la elección del estado inicial. El tiempo de cobertura de un grafo no dirigido conexo es el tiempo de cobertura de la cadena de Markov que realiza un paseo aleatorio sobre el grafo, moviéndose en cada paso de un vértice a un vecino uniformemente aleatorio de ese vértice. ^{[ 1 ]}

Los tiempos de cobertura de los grafos se han estudiado ampliamente en la informática teórica para aplicaciones que involucran la complejidad de la conectividad st , la teoría algebraica de grafos y el estudio de grafos expansores , y el modelado de la tecnología de redes informáticas Token Ring . ^{[ 1 ]}

Un problema clásico en la teoría de la probabilidad , el problema del coleccionista de cupones , puede interpretarse como el resultado de que el tiempo de cobertura esperado de un gráfico completo${\displaystyle K_{n}}$es${\displaystyle n\ln n(1+o(1))}$. Por cada otro${\displaystyle n}$-grafo de vértices, el tiempo de cobertura esperado es al menos tan grande como esta fórmula. ^{[ 2 ]} Cualquier${\displaystyle n}$-El grafo expansor regular de vértices también tiene un tiempo de cobertura esperado${\displaystyle \Theta (n\log n)}$desde cualquier vértice inicial, y más generalmente el tiempo de cobertura de cualquier grafo regular es$${\displaystyle O\left({\frac {n\log n}{1-\lambda _{2}}}\right),}$$dónde${\displaystyle \lambda _{2}}$es el segundo autovalor más grande del gráfico, normalizado de modo que el autovalor más grande sea uno. ^{[ 1 ]} Para arbitrario${\displaystyle n}$-grafos de vértices, desde cualquier vértice inicial, el tiempo de cobertura es como máximo$${\displaystyle \left({\frac {4}{27}}+o(1)\right)n^{3},}$$y existen grafos cuyo tiempo de cobertura esperado es tan grande. ^{[ 3 ]} En grafos planares , el tiempo de cobertura esperado es${\displaystyle \Omega (n\log ^{2}n)}$y${\displaystyle O(n^{2})}$. ^{[ 4 ]}

• Tiempo de llegada , el número de pasos hasta que se alcanza por primera vez un conjunto de estados.