En la disciplina matemática de la teoría de grafos , el teorema de muestreo del recorrido del expansor establece que el muestreo de vértices en un gráfico expansor haciendo un recorrido aleatorio es casi tan bueno como muestrear los vértices independientemente de una distribución uniforme . La primera versión de este teorema se debe a Ajtai, Komlós & Szemerédi (1987) , y la versión más general se atribuye típicamente a Gillman (1998) .
Declaración
Dejar ser un gráfico de expansión con el segundo valor propio más grande normalizado . Dejar denotar el número de vértices en . Dejar ser una función en los vértices de . Dejar denotar la media de , es decir . Entonces, si dejamos denotar los vértices encontrados en un -paso caminar al azar comenzando en un vértice aleatorio , tenemos lo siguiente para todos :
Aquí el esconde una constante absoluta . Un límite idéntico se mantiene en la otra dirección:
Usos
Este teorema es útil en la reducción de la aleatoriedad en el estudio de la desaleatorización . El muestreo de un recorrido de expansión es un ejemplo de un muestreador eficiente en la aleatoriedad . Tenga en cuenta que el número de bits utilizados en el muestreo muestras independientes de es , mientras que si tomamos muestras de una familia infinita de expansores de grado constante, esto solo cuesta . Estas familias existen y se pueden construir de manera eficiente, por ejemplo, los gráficos de Ramanujan de Lubotzky -Phillips- Sarnak .
Notas
Referencias
- Ajtai, M .; Komlós, J .; Szemerédi, E. (1987). "Simulación determinista en LOGSPACE". Actas del decimonoveno simposio anual ACM sobre teoría de la computación . STOC '87. ACM . págs. 132–140. doi : 10.1145 / 28395.28410 . ISBN 0897912217.
- Gillman, D. (1998), "A Chernoff Bound for Random Walks on Expander Graphs", SIAM Journal on Computing , Society for Industrial and Applied Mathematics, 27 (4): 1203-1220, doi : 10.1137 / S0097539794268765 , S2CID 26319459