Using the markov chain $\{X_n\}$ on $\mathbb{N}_0$, with transition probabilities $p(x,x+1)=p(x,0)=1/2$ for all $x\in \mathbb{N}_0$, how can we compute (numerically) the sum of the series $$\sum_{n=0}^{\infty}\frac{1}{2^{n+\sqrt{n}}}~?$$
I don t seem to understant how a simulation of our process can approximate the desired sum. Any help will be appreciated.
Thank you in advance.
Following the hints by @Ian, we present an answer, using the ergodic theroem and and the Monte Carlo Simulation. First of all, we easily see that there is a unique invariant distribution $\pi:$ $$\pi=\pi P\iff \pi(k)=\frac{1}{2}~\pi(k-1),~k\in \mathbb{N} \Rightarrow~ \pi(k)=\frac{1}{2^k}\pi(0),~k\in \mathbb{N}$$ and $\displaystyle \sum_{k=0}^{\infty}\pi(k)=1\iff \pi(0)=1/2$, so $\pi(k)=1/2^{k+1},~k\in \mathbb{N}_0.$ Since the given Markov chain is irreducible, has an invariant distribution and is aperiodic, by the ergodic theorem, with probability one:
$$\frac{1}{n}(f(X_1)+\ldots+f(X_n)) \rightarrow E^\pi(f)=\sum_{n=0}^{\infty}f(n)\pi(n).$$
By choosing $f(n)=2^{1-\sqrt{n}},~n\in \mathbb{N}_0$, we get with probability one:
$$\lim\frac{1}{n}(f(X_1)+\ldots+f(X_n)) =\sum_{n=0}^{\infty}\frac{1}{2^{n+\sqrt{n}}}.$$
For the numerical part, we can use the Monte Carlo Simulation method, by taking the mean of a large sample enough of $f(X_n),~n\geq 0,$ to approximate the above series.