Well, first you want to compute the probability that you get back to zero, given you are in state 0. Can you compute that? Or 1 minus that?

Also, do you know any "indicator function" methods for defining the expected time to return?

Isn't the probability that you get back to 0, given you are in state 0, just q_j? As for indicator function methods, nope I have never heard of that.

The value $q_j$ depends on $j$, so its definition should have "$j$" in it somewhere. The definition of $q_j$ is the probability, that, given you are in state $j$, you go to $0$ next. In contrast, the notion of "recurrence" relates to the probability that, given you leave state 0, you ever return.

Sorry - I'm still having a lot of trouble understanding how to find $q_j$ or how to show recurrence here - would you mind showing me how to do it a bit more?

There is no need to "find $q_j$." The value $q_j$ is given to you as a transition probability. As a first step, you might compute the probability that, after you are in state 0, you visit 1 then 2 then 3 then 4 then 5.

So do you mean the probabilities $p_0,p_1,p_2,p_3...$ like that? What should I do with these to show recurrence?

I really am having trouble understanding your sentences.

What do you mean "so do you mean the probabilities $p_0, p_1, ...$." What are you talking about? I was asking about a simpler question: Given you are in state 0, what is the probability that 5 steps later you are in state 5? The answer is a single number. Not a collection of numbers.

Well why don't you try these two simpler questions first: (i) Given you are in state 0, what is the probability you visit 1 next? (ii) Given you are in state 1, what is the probability you visit 2 next?

Sorry. I thought you meant probability of going from 0 to 1 would be $p_0$, probability of going from 1 to 2 would be $p_1$, since the question states that when you start in state $j$ you move to $j+1$ with probability $p_j$. Maybe I'm misunderstanding that. According to that, (i) Given that you are in state 0, I think the probability that you visit 1 next is $p_0$ and (ii) Given you are in state 1, the probability you visit 2 next is $p_1$. But since you said it's a single number, maybe you just mean $p_j$ in general? I'm not sure.

Yes, that is correct. So now, given you are in state 0, what is the probability that two steps later you are in state 2? (I am ignoring your "But since you said its a single number" sentence which makes no sense to me...I do not know what your "it's" refers to).

Okay, here is a simpler (but very related) question: Suppose you flip a fair coin twice. What is the probability of getting "Heads" two times in a row?

To illustrate my confusion with your responses: A few comments ago I asked a single question "What is the probability that, given you are in state 0, five steps later you are in state 5?" I observe your answer was "$p_0$ and $p_1$ and $p_2$" and so on. So you gave multiple answers to a single question. It is like if I ask "what is your name" and you answer "Rex, Jack, Joe, Steve, Sam, David." Confusing. A single question has a single answer.

If the answer to a question is "$q_j$," it stands to reason that the question itself must have had a "$j$" in it somewhere. If the question has no "$j$" (and I don't think any of my questions involved a "$j$") then the answer cannot possibly be $q_j$. It would be like my asking "what is 2+2?" and you answering "Sam."

Okay, I understand your confusion and already answered your question, there is no need to rub it in so much. I had thought you meant the one-step transition probabilities for each of the steps from 0 to 5. The answer to the coin flip question would be $(1/2)(1/2) = 1/4$. If you are in state 0, the probability that two steps later you are in state 2 would be $p_0p_1$. I'm not sure why you were confused - you said "The answer is a single number." and you meant the product of the one-step transition probabilities to go multiple steps, right?

So I see what you are getting at, about the product of the one-step transition probabilities. But what I'm not sure is why the limit of that would go to 0, nor why that would demonstrate recurrence.

Well, can you describe what has to happen if we never get back to zero? What infinite chain of events?

If we never get back to zero, then there would just be an infinite chain of one-step transition probabilities from one step to the next, right?

Yes, in fact, we never get back to zero if and only if there is an infinite chain of one-step transitions to the right, and so the probability we never get back to zero is...