Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.


I read a bit on $M/M/\infty$ queue and it may not be the right comparison and my notation may be confusing (I'm in discrete time and $\lambda,\mu$ look likes rates when they are probability). Let me rephrase the question:

I have an infinite Markov chain $M$ defined by its transition matrix $P$ such that: $P(n,m)=\sum_{i=0}^{min(m,n)} {n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)$.

Form $n\in\mathbb{N}$ I define the random variable $O^n:\mathbb{N}^*\rightarrow \mathbb{N}$ that sum the state visited before hitting back a state bellow $n$. Formally $$O^n(w)=\left\{\begin{array}{ll}\sum_{i=0}^{l}w_i& \exists l,\forall i<l,w_i>n ~and~ w_l\leq n\\\bot& otherwise\end{array}\right.$$

Let $\mathcal{E}^n$ be the conditional expectation $E(O^n|O^n\neq\bot)$.

The question is:

does there exists $B\in\mathbb{R}$ such that $\forall n\in\mathbb{N},\mathcal{E}^n\leq B$?

what I think:

It make me think about a discrete time $M/M/\infty$ queue where at each step $n$ arrives with probability $q^n(1-q)$ and at each step each services terminate with probability $p$.

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

[edit2(to answer @Did: 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}$$

[Previous question]:

I have a system where at each step:

  1. Each process in the system disappears with probability $\lambda$.

  2. $n$ processes appear with probability $\mu^n(1-\mu)$.

I associate a reward function to a state of my system $R(s)=\text{number of process in }s$.

So for example, if I represent a state by its number of processes, the run $0\rightarrow n\rightarrow 0$ has probability $\lambda^0\mu^n(1-\mu)*\lambda^n*(1-\mu)$ and a reward equal to $0+n+0$.

What I'm interested in, is the expected value of the reward on runs $x_1 \rightarrow x_2 \rightarrow .. \rightarrow x_k$ such that $x_1=n$, $\forall i\in [2,k-1], x_i>n$ and $x_k\leq n$.

I hope it's clear. I want the expected reward to come back to a state with less than $n$ process when I just left a state with n processes.

I think my system is close to $M/M/\infty$ queue, but I know really little about queuing theory. Actually, to know if this expected value is bounded by M for all $n$ would be enough.

Any help, hint, proof of the boundedness, references for $M/M/\infty$ queue with reward, will be kindly accepted.


share|improve this question
And, naturally, you checked that $P$ is a transition matrix? –  Did Mar 12 '13 at 17:55
And NOW, you checked it is? –  Did Mar 12 '13 at 18:26
Seems so. +1. You could add this to the body of the question. –  Did Mar 12 '13 at 19:46
Also posted to cstheory.stackexchange.com/questions/16925/… –  András Salamon Apr 24 '13 at 16:10
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.