Son las 2 ^ n . Daré un argumento intuitivo rápido de por qué deberíamos esperar este resultado, luego una prueba completa que espero sea clara.
En primer lugar, numere los vértices de 0 a 2 ^ n – 1. Estamos buscando el tiempo esperado que lleva volver al vértice 0 después de comenzar en el vértice 0. (Todo es simétrico, por lo que la respuesta sería la misma para cualquier otro vértice)
Aquí está el argumento intuitivo: supongamos que ejecutamos el proceso para T pasos y registramos todo el historial. Después de cierto número de pasos (el “tiempo de mezcla” para el proceso), no importa dónde empezamos: la probabilidad de estar en el vértice 0 en el paso t es casi igual a 1/2 ^ n en cualquier caso. Entonces, cuando T es grande, muchas veces el tiempo de mezcla, esperamos ver el vértice 0 sobre T / 2 ^ n veces. Eso significa que realizamos aproximadamente T / 2 ^ n viajes de ida y vuelta dejando el vértice 0 y regresando, en un total de T pasos, por lo que el tiempo medio para un viaje de ida y vuelta fue de T / (T / 2 ^ n) = 2 ^ n. Tome el límite cuando T va al infinito y obtiene el tiempo medio de retorno.
- ¿Cuál es la definición estricta entre datos continuos y discretos?
- Si resolvemos el problema del ciclo de Hamilton en el tiempo P, ¿eso realmente muestra P = NP?
- ¿Cuál es la función más compleja que has visto que, lógicamente, no debería funcionar, pero sí lo hace?
- ¿Qué buscan las escuelas de posgrado en estadística / aprendizaje automático en Ph.D. ¿solicitantes?
- ¿Por qué es más fácil la adición de peano para una computadora?
Ejercicio complicado de probabilidad (creo): convierte ese argumento en una prueba completa.
Ahora aquí hay una prueba. Sea v_i para cada i el tiempo esperado antes de llegar al vértice 0, comenzando desde el vértice i, con v_0 = 0, y sea v el vector que consiste en v_i. Este vector nos dice el tiempo de retorno medio: comenzando en el vértice 0, damos un paso y luego estamos en un vecino de 0, por lo que el tiempo de retorno promedio es 1 más el valor que v_i tiene en cada vecino de 0. Entonces ‘ Estudiaré este vector alrededor del vértice 0.
Sea A la matriz de adyacencia, entonces A_ {ij} es 1 justo donde los vértices i y j son adyacentes, y 0 en otros lugares. Deje L = I – A / n; Esta es mi matriz favorita, la laplaciana de la gráfica. Lo grandioso aquí sobre el Laplaciano es que expresa las condiciones en v. En particular, para cada i que no sea 0, [matemáticas] v_i = 1 + \ frac 1 n \ sum_ {j \ sim i} v_j = 1 + ( A v) _i / n [/ math] (porque al comenzar en el vértice i, das un paso y luego estás en uno de los vértices vecinos de manera uniforme al azar), y si reorganizas los términos obtienes [math] (L v) _i = 1 [/ matemáticas]. Por lo tanto, el producto Lv tiene el valor 1 en cada vértice excepto 0. Esto en realidad es suficiente para resolver v, si quisiéramos, para averiguar exactamente cuánto tiempo debería tomar volver a una cadena de ceros de 32 bits cuando tienen 6 bits incorrectos, etc. Pero podemos terminar con un atajo.
Estamos buscando el tiempo de retorno medio r, y sabemos que es 1 más el valor que v_i tiene en todos los vecinos de 0, que podríamos escribir como [matemáticas] r = 1 + \ frac 1 n \ sum_ {j \ sim i} v_j [/ matemáticas]. Como v_0 = 0, esto se reorganiza a [matemática] r = 1 – (L v) _0 [/ matemática]. Entonces Lv tiene el valor 1 en cada vértice que no sea 0, y si podemos encontrar el valor en el vértice 0, hemos terminado.
Ahora, aquí está lo realmente mágico que hace la laciana por nosotros: la suma de los componentes de Lv es cero. ¿Por qué? Bueno, dejemos que [math] \ vec 1 [/ math] sea el vector de todos; entonces [math] \ vec 1 ^ TL v [/ math] expresa la suma de los componentes de Lv. Pero eche un vistazo al vector de fila [math] \ vec 1 ^ TL [/ math], o de manera equivalente su transposición [math] L \ vec 1 [/ math]. Cada vértice tiene n vecinos, entonces [matemática] A \ vec 1 = n \ vec 1 [/ matemática], entonces [matemática] L \ vec 1 [/ matemática] es en realidad el vector cero. Eso significa [matemática] \ vec 1 ^ TL v = 0 v = 0 [/ matemática], entonces los componentes de Lv suman 0. Pero 2 ^ n-1 de ellos son 1, entonces el componente restante (L v) _0 es 1-2 ^ n, y r = 2 ^ n, QED .
Tradicionalmente escribiría esa prueba con muchas menos palabras, pero espero que sea más clara de esta manera.
He escrito esto para el n-cubo booleano, pero lo mismo funciona para cualquier cadena de Markov : para un vértice con probabilidad de equilibrio p, el tiempo de retorno medio es 1 / p. Si vuelve a ejecutar el argumento intuitivo, está bastante claro cómo funciona todo en la configuración general. Ejercicio (relativamente fácil): adapte la prueba para que funcione en cualquier cadena de Markov.
