1
$\begingroup$

Given an instance of the transverse Ising model, I am trying to sample from the Boltzmann probability distribution $\mu(s)=\frac{e^{-E(s)/T}}{Z}$ ($Z$ is the partition function, $s$ is a spin configuration) using Markov chains. Consider the following transition matrix P representing the MC process: $$P(s'|s)=A(s'|s)Q(s'|s)$$ where $Q$ is the proposal strategy and $A$ is the acceptance probability:$$A(s'|s)=min(1, \frac{\mu(s')Q(s|s')}{\mu(s)Q(s'|s)})$$ Given that $Q$ is symmetric $(Q(s'|s)=Q(s|s'))$, we have: $$A(s'|s)=min(1, \frac{\mu(s')}{\mu(s)})$$

$P$ satisfies the detailed balance condition: $$P(s'|s)\mu(s)=P(s|s')\mu(s')$$

Given a certain instance of the model, the spectrum of the $Q$ matrix always features an eigenvalue $\lambda=1$. However, this is not the case for $P$ whose eigenvalues are always $<1$. Being $P$ the transition matrix, isn't it supposed to always have an eigenvalue $\lambda=1$?

$\endgroup$
3
  • 1
    $\begingroup$ As you say, if $P$ is a stochastic matrix (i.e., its row sums are equal to 1), then it must have an eigenvalue equal to 1. Indeed, by definition $P\mathbf{1} = \mathbf{1}$, so $\mathbf{1}=(1,\dots,1)$ is an eigenvalue with eigenvector 1. Why do you say $P$ doesn't have such an eigenvalue? If you've determined this numerically, something is wrong with your code. The Perron-Frobenius theorem is relevant here. Also, note that while many people here will familiar with bra-ket notation, not everyone will be, so you might want to define your terms. $\endgroup$
    – snar
    Commented Feb 10, 2023 at 15:59
  • $\begingroup$ @snar thank you very much for your comment, I'll add more details such that the question is clear regardless of the reader's background. $\endgroup$
    – BlueTomato
    Commented Feb 10, 2023 at 16:12
  • $\begingroup$ @snar The problem is that in my simulations $Q$ turns out to be a stochastic matrix, but because I have to include the acceptance probability $A$ (since $P(s'|s)=Q(s'|s)A(s'|s)$), $P$ is not stochastic. I don't understand where is the mistake. $\endgroup$
    – BlueTomato
    Commented Feb 10, 2023 at 16:44

1 Answer 1

4
$\begingroup$

To avoid continuing a long discussion in the comments, I'll post an answer here, and possibly update with an edit if OP has more questions.

One of these statements is false:

\begin{align*} P(s'|s) &= A(s'|s) Q(s'|s) \tag{1}\\ P(s'|s)\mu(s) &= P(s|s')\mu(s') \tag{2}. \end{align*}

Most likely, OP is thinking of the Metropolis-Hastings algorithm, for which (2) is true, so long as one remembers to include the fact that if a proposal $s'$ is rejected, then $s' = s$. In words, the algorithm used says: pick a point according to $Q$, and then accept or reject it according to $A$; if rejected, continue with the previous point $s$. Thus, no matter whether the sample is accepted or rejected, the probability that $s$ moves to somewhere is 1.

If indeed OP meant (1), then I challenge OP to prove (2) while maintaining $\sum_{s\in S} \mu(s) = 1$. Here, $S$ is the state space.

The correct definition of the Metropolis-Hastings transition kernel (for which (2) holds) is $$P(s'|s) = A(s'|s)Q(s'|s) + \delta_{\{s\}}(s') \sum_{s''\in S} (1-A(s''|s))Q(s''|s). $$ From this correct representation of $P$ it follows immediately that \begin{align*} \sum_{s' \in S} P(s' | s) &= \sum_{s'\in S} A(s'|s)Q(s'|s) + \sum_{s' \in S} \delta_{\{s\}}(s') \sum_{s''\in S} (1-A(s''|s))Q(s''|s) \\ &= \left(\sum_{s'\in S} \delta_{\{s\}}(s')\right)+\left(\sum_{s'\in S} A(s'|s)Q(s'|s)\right) -\left(\sum_{s'\in S} \delta_{\{s\}}(s')\right)\left(\sum_{s''\in S} A(s''|s)Q(s''|s)\right) \\ &= 1 \end{align*} where we used the facts that for any $s,s'$, $$\sum_{s'\in S} Q(s'|s) =1, \quad \sum_{s'\in S} \delta_{\{s\}}(s') = 1$$ and that $s''$ is just a dummy variable (to cancel out the two sums over $A\times Q$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .