# 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& \text{where l is the smallest index such that w_l\le n}\\\bot& \text{if w_i > 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)&=&\sum_{m\in\mathbb{N}}\sum_{i=0}^{min(m,n)} {n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)\\ &=&\sum_{i=0}^{n}\sum_{m\geq i}{n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)\\ &=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\sum_{m\geq i}q^{m-i}(1-q)\\ &=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\sum_{m\geq 0}q^{m}(1-q)\\ &=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\\ &=&1 \end{array}$$

• I'm having trouble parsing your definition of $O^n(w)$. Do you mean "where $l$ is the smallest index such that $w_l\le n$"? Also, what's the initial state for your Markov chain? (If the initial state is $0$, then apparently $E[O^n] = 0$.) Mar 18, 2013 at 19:21
• Yes $l$ is the smallest index such that $w_l\leq n$. The idea of $O^n$ is the reward you will get once you leaved the state below $n$ to get back below $n$. Is it clear? It's after you leave the state below $n$ so sadly $E[O^n]$ is not $0$. Thanks for your interest.
– wece
Mar 18, 2013 at 19:34
• But if you start in state 0, then $w_0 = 0 \le n$ for any natural number $n$. So how could $O^n$ be anything other than $0$? Mar 19, 2013 at 1:30
• @JɛﬀE Ok, I edited the definition of $O^n$ I hope that what I wanted is more clear now. Sorry if it was confusing.
– wece
Mar 19, 2013 at 8:26
• @JɛﬀE, thanks for your edit. I just removed the $s$ from the summation in $O^n_s$ other way I believe that $O^n_s\geq s$ hence is not bounded for all $s$
– wece
Mar 19, 2013 at 10:06

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)$.