Considere el siguiente $n \times n$ matriz $$ \left( \begin{matrix} 1/2 & 1/2 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 1/2 & 0 & 0 \\ \vdots & \ & \ddots & & \ddots & \\ 0 & \cdots & 0 & 1/2 & 0 & 1/2 \\ 0 & \cdots & 0 & 0 & 1/2 & 1/2 \end{de la matriz} \right) $$
Tiene su mayor autovalor en $1$, y la brecha entre el$1$, y el segundo autovalor es del orden de $1/n^2$. El otro día, alguien me ofreció la siguiente heurística argumento de por qué, para un gran $n$, esta diferencia no puede ser mayor que $c/n^2$ para algunas constantes $c>0$:
Esta es la matriz de transición de una cadena de Markov en $n$ nodos que, excepto en los extremos, se mueve a la izquierda y a la derecha, con igual probabilidad. Su distribución estacionaria es uniforme. Ahora el segundo autovalor mide el tiempo hasta llegar cerca de la distribución estacionaria, y observar que por el teorema del límite central, como $n$ se hace grande, una partícula que comienza en el punto medio se tome en el orden de $n^2$ pasos hasta que se pone una constante de probabilidad en orden de $n$ nodos. En consecuencia, la brecha no puede ser mayor que en el orden de $1/n^2$.
Intuitivamente, esto tiene sentido. Me gustaría preguntar:
Pregunta: ¿hay una manera de hacer que el argumento anterior riguroso?
Una de las dificultades es que el menor autovalor también afecta el tiempo de mezcla, pero tal vez podemos deshacernos de esta dificultad mediante la adopción de un convexo combinación con la identidad. Un problema más grave parece ser el límite de los efectos, pero quizás uno puede argumentar que "desaparecen" como $n \rightarrow \infty$. No estoy seguro de cómo argumentar nada de esto, y yo estaría muy interesado en ver una formalización de este argumento.
