Comparing two Markov chains

Question

I am interested in the question of the positive recurrence of a Markov chain that (in some sense) converges to another Markov chain known to be positive recurrent. The following is a concrete example of what I mean.

Consider a system where a single server is serving two clients. Time is slotted, and packets arrive at each client according to bernoulli processes, the process for client 1 defined by the probability $p_1$ and the one for client 2 defined by the probability $p_2$. Clients have queues of infinite capacity.

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

At each time slot, a client with non-empty queue can 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$.

Define $j = \{1, 2\} \setminus \{i\}$. Then the probability of this packet being processed is at least $1 - 2 \cdot p_j > \frac{3}{4}$. Thus, the probability of the size of a non-empty queue 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 appears intuitive that since $\hat p_i(T)$ converges to $p_i$, the resulting Markov chain will be positive recurrent too. But I don't know if this holds, and more importantly, if it does, how to prove that (and general questions of similar flavor).

Thanks.

Answer 1

Assuming that the policy at time $t$ is $(p_1(t),p_2(t))$, deterministic or random, the chain is positive recurrent as soon as $2p_i(t)(1-2p_j(t))\gt p_i(t)$ for every $\{i,j\}=\{1,2\}$, that is, $p_i(t)\lt\frac14$ for every $i$ in $\{1,2\}$.

The strategy you propose is to use $p_i(t)=\min\{1,A_i(t)/t\}$. One knows that $A_i(t)/t\to p_i$ almost surely, hence, for every positive $\varepsilon$, $p_i(t)\leqslant p_i+\varepsilon$ for every $i$ and every $t\geqslant T_\varepsilon$, where $T_\varepsilon$ is random but almost surely finite.

Assume that $p_i\lt\frac14$ for every $i$ and choose a positive $\varepsilon$ such that $p_i+\varepsilon\lt\frac14$ for every $i$. Then, the system of two queues is positive recurrent from time $T_\varepsilon$ on, starting from two random and possibly huge, but finite, queues. But positive recurrence does not depend on the starting state hence the system is indeed globally positive recurrent.

Finally, your argument is valid for every $p_1\lt\frac14$ and $p_2\lt\frac14$.

A slight extension shows that the strategy to submit a packet to server $i$ with probability $a_ip_i(t)$, where $a_i\gt1$ is fixed and $p_i(t)\to p_i$, is positive recurrent as soon as $p_i\lt (a_i-1)/(a_1a_2)$ for every $i$. One can show that such scalar $a_1$ and $a_2$ exist as soon as $$ 2(p_1+p_2)\lt1+(p_1-p_2)^2. $$ In particular, if $p_1+p_2\lt\frac12$, there exists a (dissymetric) strategy based on some $(a_1,a_2)$, which leads to positive recurrence, and every admissible $(p_1,p_2)$ is such that $p_1+p_2\lt1$ (for example, every $(p_1,p_2)$ such that $p_1+2\sqrt{p_2}=1$ is admissible)