<p>It is not bounded sorry for the inconvenience. Here is the proof a friend gave me (thanks a lot to him): </p>

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

<p>\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}</p>

CC BY-SA 3.0
2013-04-24T13:39:10.310Z
2013-04-24T13:39:10.310Z
wece
<p>This is a repost of a question I asked <a href="https://math.stackexchange.com/questions/324884/boundedness-of-expected-reward-markov-chain-may-be-related-to-discret-m-m-inf">on math.SE</a>.</p>

<h3>The problem:</h3>

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

<p>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.$$</p>

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

<h3>The question is:</h3>

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

<h3>what I think:</h3>

<p>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$.</p>

<h1>What I'm looking for:</h1>

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

<h2>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.</h2>

<h3>[note: why P is a transition matrix]</h3>

<p>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}$$</p>

CC BY-SA 3.0
2013-03-18T19:21:40.873Z
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$.)
Jeffε
CC BY-SA 3.0
2013-03-18T19:34:17.517Z
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
CC BY-SA 3.0
2013-03-19T01:30:19.650Z
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$?
Jeffε
CC BY-SA 3.0
2013-03-19T08:26:27.260Z
@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
CC BY-SA 3.0
2013-03-19T10:06:12.977Z
@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
<pr.probability><markov-chains><queueing-theory>
Boundedness of expected reward Markov chain
wece
# Boundedness of expected reward Markov chain

(Asked by: username_0 on 2013-03-18)

This is a repost of a question I asked [on math.SE](https://math.stackexchange.com/questions/324884/boundedness-of-expected-reward-markov-chain-may-be-related-to-discret-m-m-inf).

### 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}$$

**Tags:** pr.probability, markov-chains, queueing-theory
> **Comments:**
> **username_1**: 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$.)  
> **username_0**: 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.  
> **username_1**: 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$?  
> **username_0**: @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.  
> **username_0**: @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$  

---

## 1 answers

### Answer by username_0 on 2013-04-24. Score: 1 | Accepted answer

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) &= \sum\_{k=0}^n \sum\_{i=0}^k {n\choose i}(1-p)^i p^{n-i}q^{k-i}(1-q) \* k \\
&= (1-q) \sum\_{i=0}^n \sum\_{k=i}^n {n\choose i}(1-p)^i p^{n-i}q^{k-i}\*k\\
&= (1-q) \sum\_{i=0}^n {n\choose i}(1-p)^i p^{n-i}\sum\_{k=i}^n q^{k-i}\*k\\
&\geq (1-q) \sum\_{i=1}^n {n\choose i}(1-p)^i p^{n-i}i \\
&\geq (1-q) \sum\_{i=0}^{n-1} {n\choose i+1}(1-p)^{i+1} p^{n-1-i}(i+1) \\
&\geq (1-q) n (1-p) \sum\_{i=0}^{n-1} {n-1 \choose i}(1-p)^i p^{n-1-i} \\
&\geq (1-q) n (1-p)
\end{align}


---

