# Is there any foster-Lyapunov criterion for time varying Markov processes?

Suppose I have 2 Markov processes with transition kernels Q_1(y|x) and Q_2(y|x). Suppose i also have Lyapunov functions V_1, V_2 for these processes w.r.t. a common set, i.e. there exists a compact set S such that for x outside S, the drift of the respective Lyapunov function is bounded above by a negative number for both the processes.

Now suppose I construct a new Markov processes by using Q_1 kernel at odd times and Q_2 kernel at even times. Can I guarantee stability of this new process in the set S i.e. can I construct a Lyapunov function for this third process on set S such that the drift of the Lyapunov function is negative outside the set S?

• Drift bounded below or above? – Yuval Peres Nov 9 at 1:28
• above-- corrected! – Deepanshu Vasal Nov 10 at 21:43
• And don’t you want the negative drift outside $S$? en.m.wikipedia.org/wiki/Foster%27s_theorem Please add a reference to which version of Foster Theorem you are using. – Yuval Peres Nov 10 at 22:00
• We only assume negative drift outside the compact set S. There is a verison of Foster-Lyapunov Theorem in Meyn and Tweedie that guarantees stability of such processes. – Deepanshu Vasal Nov 11 at 10:36

The answer is negative- the combined process obtained by alternating the kernels need not be stable.

On the state space $$\Lambda=\{(x,y) \in {\bf Z}^2 : x,y\ge 0\}$$ (The non-negative quadrant in the square lattice) consider the following two kernels. Along the two axes both kernels will send the particle toward the origin. Elsewhere, $$Q_1$$ will have a strong drift right and a weak drift down, while $$Q_2$$ will have a strong drift up and a weak drift left. Each of these kernels will send any particle to the axes, and then to zero, but alternating them will yield a drift up and right.

Formally, for $$x,y>0$$ let $$Q_1((x',y')|(x,y))=1/2$$ iff $$x'=x+1$$ and $$(y'=y \,$$ or $$\, y'=y-1)$$.

Also for $$x,y>0$$ let $$Q_2((x',y')|(x,y))=1/2$$ iff $$y'=y+1$$ and $$(x'=x\,$$ or $$\, x'=x-1)$$.

If $$x>0$$ then $$Q_i((x-1,0)|(x,0))=1$$. If $$y>0$$ then $$Q_i((0,y-1)|(0,y)=1$$. Finally, $$S=\{(0,0)\}$$ is absorbing for both kernels: $$Q_i((0,0)|(0,0))=1$$.

Then $$L_1(x,y)=x+4y$$ is a Lyapunov function for $$Q_1$$ with drift at most $$-1$$ off $$S$$. Similarly, $$L_2(x,y)=4x+y$$ is a Lyapunov function for $$Q_2$$ off $$S$$. However, alternating $$Q_1$$ and $$Q_2$$ yields a process that tends to infinity from any initial lattice point $$(x,y)$$ with $$x,y>1$$.

• Thanks! That is very helpful. I believe this is also related to "Parrondo's paradox". – Deepanshu Vasal Nov 12 at 12:34