# Prove $m_{1,0}\ge n-1$ in one dimensional symmetric random walk

Let $$m_{1,0}$$ denotes the expected time of transitions starting from state $$1$$, until a transition into state $$0$$ occurs, in one dimensional symmetric random walk, with infinite countable states i.e. state $$0,\pm 1, \pm2,...$$

In the one dimensional symmetric random walk, it has been proven that: the mean number of transitions to go from state $$1$$ to either $$0$$ or $$n$$ is $$n − 1$$

From state $$1$$ to state $$n$$, there are at least $$n-1$$ transitions and $$n-1 = m_{1,0}$$*Pr{getting to $$0$$}+$$m_{1,n}$$*Pr{getting to $$n$$}

so I think is should be $$m_{1,0}\le n-1$$ because the mean number is $$n-1$$.

But in the book: Introduction to Probability Models (Sheldon M. Ross) $$~~$$page 218, there is:

The classical example of a null recurrent Markov chain is the one dimensional symmetric random walk of Example 4.18. One way to show it is null recurrent is to argue that the mean time to return to a state is infinite.
(For another argument, see Exercise 39.) To show this, let $$m_{i,j}$$ denote the mean number of transitions, starting in state i, until a transition into state j occurs.
Now, in Example 3.16, it was shown that the mean number of transitions to go from state 1 to either $$0$$ or $$n$$ is $$n-1$$, implying that $$m_{1,0}\ge n-1$$

So I wonder which one is wrong.

The book is correct. Getting to $$0$$ takes at least as long as getting to either $$0$$ or $$n$$, so the expected time to get from $$1$$ to $$0$$ is at least the expected time to get from $$1$$ to either $$0$$ or $$n$$.
• Thanks for comment, but I wonder why "Getting to 0 takes at least as long as getting to either 0 or n". In my opinion, "Getting to 0" belongs to "getting to either 0 or n", and expected number of getting to 0 or n = n-1 = $m_{1,0}$*Pr{getting to 0} + $m_{1,n}$*Pr{getting to n}, and $m_{1,n}\ge n-1$, in consequence $m_{1,0}\le n-1$ Commented Feb 20, 2023 at 4:39
• @Gangmen: No. The event "$0$ was reached" is a subset of the event "($0$ was reached) or ($n$ was reached)"; a subset has at most the probability of its superset; and if $A(t)$ is a subset of $B(t)$ for all $t$, then the expected time until $A(t)$ occurs is at least the expected time until $B(t)$ occurs. I don't understand your equation; it's not clear what "Pr{getting to 0}" and "Pr{getting to n}" are supposed to mean – in a symmetric walk, these would both be $1$. Commented Feb 20, 2023 at 6:51
• I suspect you're confusing some of these quantities with their conditional versions – perhaps you were thinking of $$\mathsf E(\text{time to reach 0 or n})=\mathsf E(\text{time to reach 0\mid0 is reached before n})\mathsf P(\text{0 is reached before n})+\mathsf E(\text{time to reach n\mid n is reached before 0 })\mathsf P(\text{n is reached before 0})\;.$$ But that's a completely different equation. Commented Feb 20, 2023 at 6:52
• I am a little bit confused, so $m_{1,0}\ne \mathsf E(\text{time to reach$0\mid0$is reached before$n$})$? If so, what is the expectation expression of $m_{1,0}$ Commented Feb 20, 2023 at 7:07
• @Gangmen: I don't have the book, I can only go by what you wrote: "$m_{1,0}$ denotes the expected time of transitions starting from state $1$ to state $0$ in one dimensional symmetric random walk with $n+1$ states form state $0$ to state $n$". You didn't say what happens at the endpoints. If the walk is absorbed at the endpoints, i.e. ends when it reaches an endpoint, then $m_{1,0}$ is infinite, since the walk may never reach $0$. If the walk is reflected at the endpoints, $m_{1,0}$ is just the usual expectation, which is greater than the one conditioned on $0$ being reached before $n$. Commented Feb 20, 2023 at 7:32