I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as

\begin{array} [c]{cc}% P_{UU} & P_{UM}\\ P_{MU} & P_{MM}% \end{array}

Here $P_{UU}$ denotes transitions from unmarked to unmarked, $P_{UM}$ transitions from marked to unmarked and so on. From $P$ we form the absorbing walk $P'$, by turning all transitions from marked states to unmarked states into self-loops. Thus $P'$ has the form

\begin{array} [c]{cc}% P_{UU} & 0_{UM}\\ P_{MU} & I_{MM}% \end{array}

Here $I_{MM}$ is the identity matrix.

Define $D(P')$ as

\begin{array} [c]{cc}% P_{UU} & 0_{UM}\\ 0_{MU} & I_{MM}% \end{array}

I know the spectrum of $P$. Actually, let's say that $P$ is very nice, symmetric, corresponding to a regular graph. For instance, $P$ is the hypercube or the 2-D grid with periodic boundary conditions. Thus $P$ is diagonal in the Fourier basis.

How can I can find the spectrum of D(P')? I couldn't find any reference to this.

Of course, I could have formulated the question without introducing that $P'$, but I did so to provide the context where this situation appears. In short, I have a random walk $P$, I remove from it lines $10$ and $12$ and columns $10$ and $12$ let's say. I want to find the spectrum of the remaining matrix.

I used the notation $P_{xy}$ = the probability of jumping from $y$ to $x$. Thus, the eigevectors of $P$ are on the right.

Edit: if it is not possible to find the full spectrum, I'd be interested to find the eigenvector corresponding to the second-largest eigenvalue when $P$ is the 2-D grid and I have at least two marked vertices.

Edit 2: In the paper "Quantum speed-up of Markov chain based algorithms" by M. Szegedy, on page 9, the author states that "there are also several methods in store to estimate the spectral norm of $P_{UU}$." He gives the example $\left\lVert P_{UU} \right\rVert \le 1-\epsilon \delta /2$, where $\epsilon = |M|/N$ and $\delta$ is the spectral gap of $P$. Here $N$ is the number of states of $P$. Does anyone know and other methods to say something about $P_{UU}$?



Your Answer

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

Browse other questions tagged or ask your own question.