MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I thought that this question is more appropriate for math.stackexchange, where I asked it, but seeing how I got no response, here it goes:

I am interested in the question of the positive recurrence of a Markov chain that "converges" to another Markov chain known to be positive recurrent. The following is, in the context of queueing theory, a concrete example of what I mean.

Consider a system where a single server is serving two clients. Time is slotted. For client $i \in \{1, 2\}$, the number of packets arriving in each time step is a iid Bernoulli random variable with probability $p_i$.

Each client has queues of infinite capacity.

Assume $p_1 + p_2 < \frac{1}{8}$.

At each time slot, a client with non-empty queue may choose to submit one packet to the server for processing. This packet will be processed and leave the relevant queue if and only if the other client did not submit a packet in that time slot.

Now consider the following simple algorithm. Assume that client $i$ knows $p_i$. Then at each time slot, client $i$ (if its queue is non-empty) will submit a packet to the server with iid probability $2 p_i$. Let $j$ be the other client.

The probability of a packet submitted by client $i$ being processed is at least $1 - 2 \cdot p_j > \frac{3}{4}$. Thus, the probability of the size of a non-empty queue at client $i$ reducing by $1$ is at least $2 \cdot p_i \times \frac{3}{4} > p_i$. Since the departure process has a higher rate than the arrival process, it is clear that the corresponding Markov chain is positive recurrent and the queues are stable.

Here comes my question. Assume the clients do not know their own $p_i$'s. Naturally, they could approximate it as follows: at time $T$, the approximation $\hat p_i(T)$ is defined by $\hat{p_i}(T) = $$\min \left\{ 1, \frac{A(T)}{T} \right\}$, where $A(T)$ is the number of packets that have arrived up to time $T$. The clients can now use $\hat p_i(T)$ instead of $p_i$ in the above algorithm.

It seems to me that since $\hat p_i(T)$ converges almost surely to $p_i$, the resulting Markov chain will be positive recurrent too. But I am not sure this simply can be stated as true, and/or how to show that this holds.


share|cite|improve this question
This question has meanwhile been answered on Math.SE, see… – Stefan Kohl Dec 6 '13 at 15:25

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.