Random Walk Around A Circle

Question

I am having difficulties in solving the following problem

I guessed that the chain is irreducible when $\gcd(n,s)=1$. But I'm unable to proceed. Can someone help me? Any hint will be appreciated.

Answer 1

You are right thinking the chain is irreducible iff $n$ and $s$ are coprime: Suppose $n,s$ coprime, and let $i,j$ be two nodes, we have that exists $r$ such that $sr\equiv j-i \mod n$ and so $$\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$$ and this for all $i,j$ so your chain is irriducible. Now, observe that if $X_0=i$ and $X_r=j$ for some $i,j$ then necessarily $j-i=as+b(n-s)\equiv (a-b)s \mod n$ and so if the chain is irreducible $\exists a,b$ such that (setting $j=i+1$) $1\equiv (a-b)s\mod n$ and this is possible only if $\gcd (n,s)=1$.

Let’s call $p_i(r)= \Bbb P[X_r=i | X_0=i]$. We know that $i$ has period $\gcd \{r\in\Bbb N|\; p_i(r)>0\}$. Let’s observe also that $p_i(2)>0$ since you can go from $i$ to $i+s$ and then come back to $i$. So $i$ has period $1$ iff $\exists r$ odd such that $p_i(r)>0$. Let’s write $n=2^k\cdot m$ with $m$ odd. If $2^k$ divides $s$ you have that $n$ divides $ms$ and so $p_i(m)>0$ since you can follow the path $i, i+s, ..., i+ms=i$ and so the chain in aperiodic in i (and so all the chain is aperiodic since we never used really that the node was i). At the same time if exists $r$ odd such that $p_i(r)>0$ then $\exists a,b\in\Bbb N$ such that $\begin{cases} a+b=r\\ i\equiv i+as+b(n-s) \mod n\end{cases}$ i.e. $n$ divides $s(a-b)$ but $a+b$ is odd and then it is also $a-b$, so it must be $2^k| s$. We conclude that the chain is aperiodic $\iff \frac n{\gcd(n,s)}$ is odd.