Muestreo de caminata con expansor

En la disciplina matemática de la teoría de grafos , el teorema de muestreo del recorrido del expansor establece intuitivamente que el muestreo de vértices en un grafo expansor al realizar un recorrido aleatorio relativamente corto puede simular el muestreo de los vértices independientemente de una distribución uniforme . La primera versión de este teorema se debe a Ajtai, Komlós y Szemerédi (1987), y la versión más general se atribuye típicamente a Gillman (1998).

Declaración

Sea un gráfico expansor de n vértices con aristas ponderadas positivamente, y sea . Sea la matriz estocástica del gráfico, y sea el segundo valor propio más grande de . Sea los vértices encontrados en un paseo aleatorio de -pasos comenzando en el vértice , y sea . Donde ${\displaystyle G=(V,E)}$ ${\displaystyle A\subset V}$ ${\displaystyle P}$ ${\displaystyle \lambda _{2}}$ ${\textstyle P}$ ${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ ${\displaystyle (k-1)}$ ${\displaystyle G}$ ${\displaystyle y_{0}}$ ${\textstyle \pi (A):=}$ ${\displaystyle \lim _{k\rightarrow \infty }{\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})}$ ${\textstyle \mathbf {1} _{A}(y){\begin{cases}1,&{\text{if }}y\in A\\0,&{\text{otherwise }}\end{cases}}}$

(Es bien sabido ^[1] que casi todas las trayectorias convergen a algún punto límite, , como .) ${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ ${\textstyle \pi (A)}$ ${\textstyle k\rightarrow }$ ${\textstyle \infty }$

El teorema establece que para un gráfico ponderado y un paseo aleatorio donde se elige mediante una distribución inicial , para todo , tenemos el siguiente límite: ${\displaystyle G=(V,E)}$ ${\displaystyle y_{0},y_{1},\ldots ,y_{k-1}}$ ${\displaystyle y_{0}}$ ${\textstyle \mathbf {q} }$ ${\displaystyle \gamma >0}$

${\displaystyle \Pr \left[{\bigg |}{\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})-\pi (A){\bigg |}\geq \gamma \right]\leq Ce^{-{\frac {1}{20}}(\gamma ^{2}(1-\lambda _{2})k)}.}$

Donde depende de y . ${\displaystyle C}$ ${\displaystyle \mathbf {q} ,G}$ ${\displaystyle A}$

El teorema da un límite para la tasa de convergencia con respecto a la longitud del recorrido aleatorio, lo que proporciona un método más eficiente para estimar, en comparación con el muestreo independiente, los vértices de . ${\displaystyle \pi (A)}$ ${\displaystyle \pi (A)}$ ${\displaystyle G}$

Prueba

Para demostrar el teorema, proporcionamos algunas definiciones seguidas de tres lemas.

Sea el peso de la arista y sea Denotado por . Sea la matriz con entradas , y sea . ${\displaystyle {\it {{w}_{xy}}}}$ ${\displaystyle xy\in E(G)}$ ${\textstyle {\it {{w}_{x}=\sum _{y:xy\in E(G)}{\it {{w}_{xy}.}}}}}$ ${\textstyle \pi (x):={\it {{w}_{x}/\sum _{y\in V}{\it {{w}_{y}}}}}}$ ${\textstyle {\frac {\mathbf {q} }{\sqrt {\pi }}}}$ ${\textstyle {\frac {\mathbf {q} (x)}{\sqrt {\pi (x)}}}}$ ${\textstyle N_{\pi ,\mathbf {q} }=||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}}$

Sea y . Sea donde es la matriz estocástica, y . Entonces: ${\displaystyle D={\text{diag}}(1/{\it {{w}_{i})}}}$ ${\displaystyle M=({\it {{w}_{ij})}}}$ ${\textstyle P(r)=PE_{r}}$ ${\textstyle P}$ ${\textstyle E_{r}={\text{diag}}(e^{r\mathbf {1} _{A}})}$ ${\textstyle r\geq 0}$

${\displaystyle P={\sqrt {D}}S{\sqrt {D^{-1}}}\qquad {\text{and}}\qquad P(r)={\sqrt {DE_{r}^{-1}}}S(r){\sqrt {E_{r}D^{-1}}}}$

Donde . Como y son simétricos, tienen valores propios reales. Por lo tanto, como los valores propios de y son iguales, los valores propios de son reales. Sean y el primer y segundo valores propios más grandes de respectivamente. ${\displaystyle S:={\sqrt {D}}M{\sqrt {D}}{\text{ and }}S(r):={\sqrt {DE_{r}}}M{\sqrt {DE_{r}}}}$ ${\displaystyle S}$ ${\displaystyle S(r)}$ ${\displaystyle S(r)}$ ${\displaystyle P(r)}$ ${\textstyle P(r)}$ ${\textstyle \lambda (r)}$ ${\textstyle \lambda _{2}(r)}$ ${\textstyle P(r)}$

Para facilitar la notación, sea , , y sea el vector todo-1. ${\textstyle t_{k}={\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})}$ ${\textstyle \epsilon =\lambda -\lambda _{2}}$ ${\textstyle \epsilon _{r}=\lambda (r)-\lambda _{2}(r)}$ ${\displaystyle \mathbf {1} }$

Lema 1

${\displaystyle \Pr \left[t_{k}-\pi (A)\geq \gamma \right]\leq e^{-rk(\pi (A)+\gamma )+k\log \lambda (r)}(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}}$

Prueba:

Por la desigualdad de Markov ,

${\displaystyle {\begin{alignedat}{2}\Pr \left[t_{k}\geq \pi (A)+\gamma \right]=\Pr[e^{rt_{k}}\geq e^{rk(\pi (A)+\gamma )}]\leq e^{-rk(\pi (A)+\gamma )}E_{\mathbf {q} }e^{rt_{k}}\end{alignedat}}}$

Donde es la expectativa de elegido según la distribución de probabilidad . Como esto se puede interpretar sumando todas las trayectorias posibles , por lo tanto: ${\displaystyle E_{\mathbf {q} }}$ ${\displaystyle x_{0}}$ ${\displaystyle \mathbf {q} }$ ${\displaystyle x_{0},x_{1},...,x_{k}}$

${\displaystyle E_{\mathbf {q} }e^{rt}=\sum _{x_{1},x_{2},...,x_{k}}e^{rt}\mathbb {q} (x_{0})\Pi _{i=1}^{k}p_{x_{i-1}x_{i}}=\mathbf {q} P(r)^{k}\mathbf {1} }$

Combinando los dos resultados se demuestra el lema.

Lema 2

Para , ${\displaystyle 0\leq r\leq 1}$

${\displaystyle (\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}\leq (1+r)N_{\pi ,\mathbf {q} }}$

Prueba:

Como los valores propios de y son iguales, ${\displaystyle P(r)}$ ${\displaystyle S(r)}$

${\displaystyle {\begin{aligned}(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}&=(\mathbf {q} P{\sqrt {DE_{r}^{-1}}}S(r)^{k}{\sqrt {D^{-1}E_{r}}}\mathbf {1} )/\lambda (r)^{k}\\&\leq e^{r/2}||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}||S(r)^{k}||_{2}||{\sqrt {\pi }}||_{2}/\lambda (r)^{k}\\&\leq e^{r/2}N_{\pi ,\mathbf {q} }\\&\leq (1+r)N_{\pi ,\mathbf {q} }\qquad \square \end{aligned}}}$

Lema 3

Si es un número real tal que , ${\displaystyle r}$ ${\displaystyle 0\leq e^{r}-1\leq \epsilon /4}$

${\displaystyle \log \lambda (r)\leq r\pi (A)+5r^{2}/\epsilon }$

Resumen de la prueba:

Nosotros Taylor ampliamos el punto a conseguir: ${\textstyle \log \lambda (y)}$ ${\textstyle r=z}$

${\displaystyle \log \lambda (r)=\log \lambda (z)+m_{z}(r-z)+(r-z)^{2}\int _{0}^{1}(1-t)V_{z+(r-z)t}dt}$

Donde son las derivadas primera y segunda de en . Demostramos que Luego demostramos que (i) mediante manipulación de matrices, y luego demostramos (ii) utilizando (i) y la estimación de Cauchy a partir del análisis complejo. ${\displaystyle m_{x}{\text{ and }}V_{x}}$ ${\displaystyle \log \lambda (r)}$ ${\displaystyle r=x}$ ${\displaystyle m_{0}=\lim _{k\to \infty }t_{k}=\pi (A).}$ ${\textstyle \epsilon _{r}\geq 3\epsilon /4}$ ${\displaystyle V_{r}\leq 10/\epsilon }$

Los resultados se combinan para mostrar que

${\displaystyle {\begin{aligned}\log \lambda (r)=\log \lambda (0)+m_{0}r+r^{2}\int _{0}^{1}(1-t)V_{rt}dt\leq r\pi (A)+5r^{2}/\epsilon \end{aligned}}}$

Una prueba línea a línea se puede encontrar en Gilman (1998)[1].

Prueba del teorema

Combinando el lema 2 y el lema 3, obtenemos que

${\displaystyle \Pr[t_{k}-\pi (A)\geq \gamma ]\leq (1+r)N_{\pi ,\mathbf {q} }e^{-k(r\gamma -5r^{2}/\epsilon )}}$

Interpretando el exponente en el lado derecho de la desigualdad como una ecuación cuadrática y minimizando la expresión, vemos que ${\displaystyle r}$

${\displaystyle \Pr[t_{k}-\pi (A)\geq \gamma ]\leq (1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }e^{-k\gamma ^{2}\epsilon /20}}$

Un límite similar

${\displaystyle \Pr[t_{k}-\pi (A)\leq -\gamma ]\leq (1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }e^{-k\gamma ^{2}\epsilon /20}}$

se mantiene, por lo tanto la configuración da el resultado deseado. ${\displaystyle C=2(1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }}$

Usos

Este teorema es útil en la reducción de aleatoriedad en el estudio de la desaleatoriedad . El muestreo de un recorrido de expansor es un ejemplo de un muestreador de aleatoriedad eficiente . Nótese que la cantidad de bits utilizados en el muestreo de muestras independientes de es , mientras que si tomamos muestras de una familia infinita de expansores de grado constante esto cuesta solo . Tales familias existen y son eficientemente construibles, por ejemplo, los grafos de Ramanujan de Lubotzky -Phillips- Sarnak . ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle k\log n}$ ${\displaystyle \log n+O(k)}$

Referencias

1. Doob, JL (1953). Procesos estocásticos . Teorema 6.1: Wiley.{{cite book}}: CS1 maint: location (link)

• Ajtai, M.; Komlós, J.; Szemerédi, E. (1987). "Simulación determinista en LOGSPACE". Actas del decimonoveno simposio anual de la ACM sobre teoría de la computación . STOC '87. ACM . pp. 132–140. doi : 10.1145/28395.28410 . ISBN . 0897912217.
• Gillman, D. (1998). "Un límite de Chernoff para paseos aleatorios en gráficos expansores". Revista SIAM de Computación . 27 (4). Sociedad de Matemáticas Industriales y Aplicadas: 1203–1220. doi :10.1137/S0097539794268765. S2CID  26319459.
• Doob, JL (1953), Procesos estocásticos , vol. Teorema 6.1, Wiley