Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on a problem concerning censoring of transitions in a Markov Chain. For example, take a Markov Chain that models a counter, it goes up or down but does not stay in position. A possible censoring could be to only observe the transitions where the new number is prime or to only observe those transitions where the new number is even.

According to what I'm told, this results in a new Markov Chain, but I can't really grasp how this changes the problem that the new Markov Chain could be modeling. Do you still take into account that you somehow got in a state to be able to make that kind of transition or can I just completely ignore it and only consider the leftover transitions?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

If the state space of the Markov chain is $S$ and you observe the chain only when it is in $U\subseteq S$, the result is still a Markov chain but with different transition probabilities.

Let $(X_n)$ denote the original Markov chain and $T=\min\{n\ge1\mid X_n\in U\}$. Then the transition probabilities of the new Markov chain are such that, for every $x$ and $y$ in $U$, $$ Q(x,y)=P_x(X_T=y). $$ In general, the new transition probabilities $Q(x,y)$ are a complicated functional of the transition probabilities of $(X_n)$ and of the disposition of $U$ in $S$.

Here is an example. Assume $(X_n)$ is the symmetric $\pm1$ random walk on $\mathbb Z$, with transition probabilities $P_x(X_1=x\pm1)=\frac12$ for every $x$ in $\mathbb Z$. Let $U\subseteq\mathbb Z$ with $U=\{x_k\mid k\in\mathbb Z\}$ and $x_k<x_{k+1}$ for every $k$. Then, starting from $x_k$, the new Markov chain can only jump to a vertex $x_j$ such that $j$ in $\{k-1,k,k+1\}$, and the transition probabilities are $$ Q(x_k,x_{k-1})=\frac1{2(x_k-x_{k-1})},\quad Q(x_k,x_{k+1})=\frac1{2(x_{k+1}-x_{k})}, $$ and $$ Q(x_k,x_{k})=1-\frac1{2(x_k-x_{k-1})}-\frac1{2(x_{k+1}-x_{k})}. $$ Hence the new chain behaves like a random walk on $\mathbb Z$ with jumps from $k$ to $k$ or $k\pm1$, and basically any kind of transition probabilities.

share|improve this answer
    
This was very helpful, thank you! –  Wim Sep 2 '11 at 23:03

As Didier points out, the transition probabilities for the new chain are complicated. But for a finite state space Markov chain, we can let linear algebra do the work. First partition the transition matrix $P$ as shown:

$$P= \matrix{&\hskip-15pt \matrix{&\small U&\small U^c}\cr\matrix{\small U\cr\small U^c}&\hskip-10pt\pmatrix{A&B\cr C&D}}.$$

That is, the matrix $A$ has the transitions from $U$ to $U$, the matrix $B$ has the transitions from $U$ to $U^c$, etc. The transition matrix for the new chain with state space $U$ is $$P^U=A+B(I-D)^{-1}C.$$

The inverse of $I-D$ will exist if it is possible to reach $U$ from any state in $U^c$.

share|improve this answer
    
+1. Quite nice. –  Did Jan 31 '13 at 12:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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