Frog on infinitely many lily pads (Markov chain)

Question

A frog on pad $i$ hops to one of the pads $(1,2,...,i,i+1)$ with equal probability. I know that if the frog starts on pad $k$ the expected number of times the frog jumps, before returning for the first time to $k$ is $e(k-1)!$ (I proved this already).

But what is the expected number of times the frog will visit pad $k+1$? I don't know how to find this. I thought that maybe we can use the fact that there is a probability of $1/(k+1)$ of visiting this the first time and then multiply this by the number of times I expect to return at $k+1$ when I start at $k+1$. If this is correct, then what is that expectation?

EDIT: Is the answer to the question really $\infty$ as michael says in the comments?

Answer 1

The Markov chain is irreducible, since for any pair of states $i,j$, there exists $n>0$ such that $P_{ij}^n>0$. Since the expected return time to a state is finite, each state is positive recurrent. It follows that each state is visited infinitely often.

To argue a bit more rigorously, let $F_n = \mathbb I_{\{X_n=k\mid X_0=k\}}$ and $$N_k = \sum_{n=0}^\infty F_n.$$ Then $$ \mathbb E[N_k] = \mathbb E\left[\sum_{n=0}^\infty F_n \right]. $$ By monotone convergence, this is equal to $$ \sum_{n=0}^\infty \mathbb E[F_n]. $$ We have $\mathbb E[N_k]\geqslant \mathbb E[F_0]=1$. Now assume that $\mathbb E[N_k]\geqslant m$ for some $m\geqslant 1$. Then $$\begin{align*} \mathbb E[N_k] &= m + \sum_{n=m+1}\mathbb P(F_n)\\ &\geqslant m + \mathbb P\left(\bigcup_{n=m+1}^\infty F_n\right)\\ &= m+1. \end{align*}$$ Hence $\mathbb E[N_k]=\infty$.

Answer 2

Heh, to the person giving the bounty, I imagine your teacher amended the question for clarity after enough people turned in infinite as their answer... Anyway, since this is an assignment, let me give you some hints:

Take a very large time $T$, and just keep jumping without stopping. How many times, in average, approximately, will you visit state $k$? How many times will you visit the state $k+1$? To be specific, just think of a long, thin strip of paper marked from 1 to T (with like one centimeter between each marking), and mark it with blue whenever your frog ends in lilypad $k$ and red whenever it ends in lilypad $k+1$. Now, cut your strip from the blue markings; what is the average length of each cut? Most importantly, how many pink dots are in each cut on average? (This is to give you an idea of the proof of the renewal theorem; if you want a more rigorous exposition, Durrett PTE 5.5 and 5.6 explains it) (The crucial thing is that since the process is Markov, one of these strips looks exactly like your stopped process, but it is easier to argue about the behaviour of these strips since we can say something about how many times we visit each state.)