Tengo dificultades para resolver el siguiente problema 
Adiviné que la cadena es irreducible cuando $\gcd(n,s)=1$ . Pero no puedo proceder. ¿Puede alguien ayudarme? Cualquier pista será apreciada.
Respuesta
¿Demasiados anuncios?
Tienes razón al pensar que la cadena es irreducible si $n$ y $s$ son coprimos: Supongamos que $n,s$ coprima, y que $i,j$ sean dos nodos, tenemos que existe $r$ tal que $sr\equiv j-i \mod n$ y así $$\Bbb P [X_r=j| X_0=i]=\Bbb P [X_r=j, X_0=i]\frac 1n \ge \frac 1n \Bbb P [X_0=i,X_1=i+s,...,X_{r-1} =i+(r-1)s,X_r=j]=\frac 1n \cdot p^r >0$$ y esto para todos $i,j$ por lo que su cadena es irriducible. Ahora, observa que si $X_0=i$ y $X_r=j$ para algunos $i,j$ entonces necesariamente $j-i=as+b(n-s)\equiv (a-b)s \mod n$ y por lo tanto si la cadena es irreducible $\exists a,b$ de tal manera que (estableciendo $j=i+1$ ) $1\equiv (a-b)s\mod n$ y esto sólo es posible si $\gcd (n,s)=1$ .
Llamemos a $p_i(r)= \Bbb P[X_r=i | X_0=i]$ . Sabemos que $i$ tiene periodo $\gcd \{r\in\Bbb N|\; p_i(r)>0\}$ . Observemos también que $p_i(2)>0$ ya que se puede pasar de $i$ a $i+s$ y luego volver a $i$ . Así que $i$ tiene periodo $1$ si $\exists r$ impar tal que $p_i(r)>0$ . Escribamos $n=2^k\cdot m$ con $m$ impar. Si $2^k$ divide $s$ tienes que $n$ divide $ms$ y así $p_i(m)>0$ ya que puedes seguir el camino $i, i+s, ..., i+ms=i$ y así la cadena en aperiódica en i (y así toda la cadena es aperiódica ya que nunca usamos realmente que el nodo fuera i). Al mismo tiempo si existe $r$ impar tal que $p_i(r)>0$ entonces $\exists a,b\in\Bbb N$ tal que $\begin{cases} a+b=r\\ i\equiv i+as+b(n-s) \mod n\end{cases}$ es decir $n$ divide $s(a-b)$ pero $a+b$ es impar y entonces también es $a-b$ , por lo que debe ser $2^k| s$ . Concluimos que la cadena es aperiódica $\iff \frac n{\gcd(n,s)}$ es impar.
