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?

  • $\begingroup$ Drift bounded below or above? $\endgroup$ – Yuval Peres Nov 9 at 1:28
  • $\begingroup$ above-- corrected! $\endgroup$ – Deepanshu Vasal Nov 10 at 21:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Peres Nov 10 at 22:00
  • $\begingroup$ 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. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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