Let $P$ be the transition matrix of random walk on $n$-cycle($n$ is odd). Find the smallest value of $t$ such that $Pt(x, y) > 0$ for all $x$ and $y.$

Question

Let $P$ be the transition matrix of a random walk on the $n$-cycle, where $n$ is odd. Find the smallest value of $t$ such that $Pt(x, y) > 0$ for all states $x$ and $y$. My solution: If I have $n$ states, I will need a minimum of $n-1$ steps ahead of $1$st state, to cover all $n$ states. As I have covered all states, $Pn-1(x, y) > 0$ for all states $x$ and $y$.Thus minimum $t$ is $n-1$.

Where am I lacking in the proof? What things have I discarded/overlooked? What more do I need to prove my claim?

Answer 1

Okay, this turned out slightly more finicky than I was really expecting. The upshot is that yes, $n-1$ is the minimal number and you were right all along. However, your argument remains somewhat lacking in detail, so here is a full solution:

First, some formalities:

Label the vertices $1,...,n$ in order and let $\oplus$ denote addition mod $n$. I'll denote going around the cycle in increasing order as 'going to the right'.

Clearly, since the walk is symmetric and the graph is transient, $P_t(x,y)=P_t(y,x)=P_t(y\oplus (n-y),x\oplus (n-y))$. Hence, it suffices to consider $P_t(1,j)$ for general $j$.

And now, a proof:

You're absolutely correct that $P_t(1,j)>0$ if and only if there exists a path $(\alpha_s)_{1\leq s\leq t}$ of neighbours such that $\alpha_1=1$ and $\alpha_t=j$. Hence, we want to find the minimal $t$ such that there exists some path of length $t$ from $1$ to $j$ for all $j$. Let's argue that $t\leq n-1$, i.e. that $t=n-1$ satisfies the condition.

It's clear that there is a path of said length from $1$ to $n$ , namely the path of length $n-1$ that keeps going to the right. If you have a path of length $n-1$ from $1$ to $j$ such that the second to last step is $j-1$, you also get a pth of length $n-1$ from $1$ to $j-2$ by simply reversing the last step. Thus, there is a path of length of $n-1$ from $1$ to every odd $j$. However, the same logic applies to the path of length $n-1$ which goes left from $1$ until it hits $2$, and we get that there exists a path of length $n-1$ from $1$ to any even $j$. Thus, $t\leq n-1$.

Now, let $t<n-1$ and let us find a $j$ such that $P_t(1,j)=0$. If $t$ is odd, then $P_t(1,1)=0$, since no path of length less than $n$ can form a full loop of the cycle. If, on the other hand, $t$ is even, we see that $P_t(1,2)=0$. Indeed, for any walk $(\alpha_s)_{0\leq s\leq t}$ with $\alpha_0=1$, we see that $\alpha_s-2$ is odd for even $s$ unless at some point $\alpha$ goes from $1$ to $n$ and never crosses back again to $1$ - in particular it $\alpha_t-2$ could not be $0$. However, $n-2>t-1$, so even if $\alpha_1=n$, it's impossible that $\alpha_t$ could be $2$.

We conclude that $t=n-1$ is, indeed, minimal.