¿Por qué convergen exponencialmente rápido cadenas de Markov?

Question

Deje $G$ ser un grupo finito, $q$ una función de masa de probabilidad (fmp) en $G$ $u$ el uniforme pmf en $G$. Utilizamos el producto de convolución $$q^{(k)}(\sigma) = \sum_{\alpha \beta =\sigma} p^{(k-1)}(\alpha)q(\beta)$$ y el $L^1$ distancia entre el $q^k$ $u$ $$d(k) := || q^{(k)}-u || = \sum_{\sigma \in G} |q^{(k)}(\sigma) - u(\sigma)|.$$ De este modo (ver nota a continuación) $q^{(k)}$ es la distribución de la cadena de Markov en $G$ asociado a $q$ a $kth$ paso y $d(k)$ es su velocidad de convergencia.

Pregunta: se establece, como una observación aquí (Diaconis y Saloff-Coste, 1995, página 3), que $d$ es submultiplicative. Esto significa que $d(n+m) \le d(n)d(m)$. Por qué es esto cierto?

La observación es muy interesante: implica, al menos exponencial de la tasa de convergencia (podemos suponer $q^{(k)}$ converge a $u$).

---

Notas.

1. La cadena de Markov en $G$ asociado a $q$ se define como sigue. Dado el estado actual de la $x_n\in G$, la probabilidad de transición de a$x_{n+1}$$q(x_n^{-1}x_{n+1})$. Se puede comprobar que el $q^{(k)}$ es la distribución de esta cadena en la $k$th paso cuando a partir de la identidad.

2. El problema puede ser formulado para el general de las cadenas de Markov, pero yo quería seguir con las notaciones del informe técnico.

Answer 1

Basta para demostrar que para cada distribución $p$ y $q$ $G$, $$\sum_s\left|(p\ast q)(s)-u(s)\right|\leqslant\sum_s|p(s)-u(s)|\cdot\sum_s|q(s)-u(s)|$ $ asumir que $|G|=n$ y recordar que $u$ denota la distribución uniforme en $G$ por lo tanto, $u(s)=n^{-1}$ cada $s$ $G$. Además,$$ (p\ast q)(s)-n^{-1}=\left(\sum_tp(t)q(st^{-1})\right)-n^{-1}=\sum_t(p(t)-n^{-1})(q(st^{-1})-n^{-1}) $$where the second identity uses the fact that, for every $s$,$$ \sum_tn^{-1}=\sum_tp(t)=\sum_tq(st^{-1})=1 $$Thus, the triangular inequality yields$$ \sum_s\left|(p\ast q)(s)-n^{-1}\right|\leqslant\sum_s\sum_t|p(t)-n^{-1}|\cdot|q(st^{-1})-n^{-1}| $$The double sum on the RHS is$$ \sum_t|p(t)-n^{-1}|\cdot\sum_s|q(st^{-1})-n^{-1}|$$ and the proof is complete since, for every $t$, the map $s\mapsto st ^ {-1}$ is a bijection of $G$, hence $%$ $\sum_s|q(st^{-1})-n^{-1}|=\sum_s|q(s)-n^{-1}|$