Boundedness of expected reward Markov chain This is a repost of a question I asked on math.SE.

The problem:

I have an infinite Markov chain $M$ over the natural numbers, with transition probabilities $$P(n,m)=\sum_{i=0}^{min(m,n)} {n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q).$$

For any natural numbers $n$ and $s$, I define the random variable $O^n_s:\mathbb{N}^*\rightarrow \mathbb{N}$ to be sum of all states visited if we start in state $s$ and end when we first reach a state less than or equal to $n$. Formally, let $w = (s, w_1, w_2, \dots)$ denote the random sequence of states visited by the Markov chain, and let $$O^n_s(w)=\left\{\begin{array}{ll} \sum_{i=1}^{l}w_i&amp; \text{where $l$ is the smallest index such that $w_l\le n$}\\\bot&amp; \text{if $w_i &gt; n$ for all $i$}\end{array}\right.$$

Let $\mathcal{E}^n_s$ denote the conditional expectation $E_w[O^n_s(w)\mid O^n_s(w)\neq\bot]$.

The question is:

Is there a real number $B$ such that $\mathcal{E}^n_s\leq B$ for all natural numbers $n$ and $s$?

what I think:

This process reminds me of a discrete time $M/M/\infty$ queue where at each step $n$ arrives with probability $q^n(1-q)$ and at each step each service terminates with probability $p$.

What I'm looking for:

But I couldn't find any references or hint about a model like that. If you have any idea or references (or, even better, a proof) please tell me.

Any ideas, (even if it doesn't apply directly there) would be accepted. I'm a bit out of idea on how to solve this.

[note: why P is a transition matrix]

For all $n\in \mathbb{N}$, $$\begin{array}{rcl}
\sum_{m\in\mathbb{N}}P(n,m)&amp;=&amp;\sum_{m\in\mathbb{N}}\sum_{i=0}^{min(m,n)} {n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)\\
&amp;=&amp;\sum_{i=0}^{n}\sum_{m\geq i}{n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)\\
&amp;=&amp;\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\sum_{m\geq i}q^{m-i}(1-q)\\
&amp;=&amp;\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\sum_{m\geq 0}q^{m}(1-q)\\
&amp;=&amp;\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\\
&amp;=&amp;1
\end{array}$$
It is not bounded sorry for the inconvenience. Here is the proof a friend gave me (thanks a lot to him): 

Let consider the set $W_1 = \{w = (s,w_1,\dots)| w_1 \leq n\}$. Then $\mathcal{E}^n_n$ is bigger than $\displaystyle\sum_{w\in W_1}O^n_n(w)*P(w)$.

\begin{align}
\sum_{w\in W_1}O^n_n(w)*P(w) &amp;= \sum_{k=0}^n \sum_{i=0}^k {n\choose i}(1-p)^i p^{n-i}q^{k-i}(1-q) * k \\
&amp;= (1-q) \sum_{i=0}^n \sum_{k=i}^n {n\choose i}(1-p)^i p^{n-i}q^{k-i}*k\\
&amp;= (1-q) \sum_{i=0}^n  {n\choose i}(1-p)^i p^{n-i}\sum_{k=i}^n q^{k-i}*k\\
&amp;\geq (1-q) \sum_{i=1}^n  {n\choose i}(1-p)^i p^{n-i}i \\
&amp;\geq (1-q) \sum_{i=0}^{n-1} {n\choose i+1}(1-p)^{i+1} p^{n-1-i}(i+1) \\
&amp;\geq (1-q) n (1-p) \sum_{i=0}^{n-1} {n-1 \choose i}(1-p)^i p^{n-1-i} \\
&amp;\geq (1-q) n (1-p)
\end{align}