# Markov Chain Perturbation

Suppose I have an infinite and reversible Markov chain $X_n$ with transition kernel $P_1(x,y)$ and stationary measure $\pi(x)$.

For concreteness, suppose my state space is on a graph and my edges have weights $a_{xy}$, so that $$P_1(x,y)=\frac {a_{xy}}{\sum_{z\sim x}a_{xz}}$$ I'm interested in references which deal with the following:

Suppose $a_{x^*y^*}$ (the weight between vertices $x^*$ and $y^*$) is changed to $b_{x^*y^*}$. In particular, by changing a single weight, I get a new transition kernel $P_2(x,y)$.

What can be said about the behavior of $P^n_2(x,x)$ compared to $P^n_1(x,x)$ as $n$ gets large?

If I tell you that every state in this Markov chain is transient, can something be said about the Radon Nikodym derivative $dP_1/dP_2$, in the sense that $\displaystyle P_1^n(x,x)=E_x^{(2)}\left(\frac{dP_1}{dP_2} 1_{X_n=x}\right)$.

I would like to say that $P_1^n(x,x)$ and $P_2^n(x,x)$ become commensurate but, this likely needs strong conditions on what $b_{x^*y^*}$ can be.

-
I fixed the tilde, but I don't know what you mean by the subscripted $1$. Is that supposed to be a vertical bar? What do you mean by $X_n=0$? –  joriki May 28 '11 at 4:35
To wit, it seems one is left with the hypothesis that $P_1$ and $P_2$ are two Markov transition kernels such that there exists a finite and positive constant $c$ with, for every states $x$ and $y$, $$c^{-1}P_1(x,y)\le P_2(x,y)\le cP_1(x,y).$$ Then it is a general (and easy) fact that, for every $n\ge1$ and state $x$, $$c^{-n}P_1^n(x,x)\le P_2^n(x,x)\le c^nP_1^n(x,x).$$ If $n$ and $P_1$ are fixed and one chooses different kernels $P_2$ more and more like $P_1$ in the sense that $c\to1$, then obviously $P_2^n(x,x)$ is more and more like $P_1^n(x,x)$.
In the reversible situation described by the OP where one changes the weight $a_{x^*y^*}$ of a single edge $x^*y^*$, $P_1(x,y)$ is modified only when $x$ or $y$ is $x^*$ or $y^*$ but it is not clear how this helps. Of course, if $b_{x^*y^*}\to a_{x^*y^*}$, then $c\to1$. Quantitative estimates on $c$ could be derived from a more precise description of the deformation of $a$ into $b$.
Finally, note that the Radon-Nykodym derivative $dP_1/dP_2$ invoked by the OP does not exist since $P_1$ and $P_2$ are singular to each other. But, for every fixed time $n$, there exists a Radon-Nykodym derivative of the restrictions of $P_1$ and $P_2$ to the sigma-algebra $F_n$ of the past of the Markov chain up to time $n$.