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

  • 1
    $\begingroup$ 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$.) $\endgroup$
    – Jeffε
    Commented Mar 18, 2013 at 19:21
  • $\begingroup$ 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. $\endgroup$
    – wece
    Commented Mar 18, 2013 at 19:34
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Jeffε
    Commented Mar 19, 2013 at 1:30
  • $\begingroup$ @JɛffE Ok, I edited the definition of $O^n$ I hope that what I wanted is more clear now. Sorry if it was confusing. $\endgroup$
    – wece
    Commented Mar 19, 2013 at 8:26
  • $\begingroup$ @JɛffE, 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$ $\endgroup$
    – wece
    Commented Mar 19, 2013 at 10:06

1 Answer 1


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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.