# 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.$

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?

• You're overlooking the fact that the random walk can take steps in two different directions. Commented Jun 30, 2020 at 10:47
• I am sorry for not mentioning the definition of n-cycle random walk,from the reference book I am using.It says probability to step ahead=to step backward=0.5 Commented Jun 30, 2020 at 10:53
• Exactly. So there are two directions it can walk. Commented Jun 30, 2020 at 10:56
• And you overlooked that when you came up with your solution. Commented Jun 30, 2020 at 10:57
• Please elaborate. Commented Jun 30, 2020 at 10:58

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 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.