Let \(Q\) be an irreducible symmetric transition matrix and \[ p_{ij} = \left\{ \begin{array}{l} q_{ij}\,min(1,\frac{\mu_j}{\mu_i}), \:\: j \neq i\\ 1 - \sum_{k \neq i} q_{ik} \, min(1, \frac{\mu_k}{\mu_i}), \:\: j=i \end{array} \right.\ \]
Write out a proof that P is reversible with respect to \(\mu\). Conclude that \(\mu\) is an invariant probability distribution for P.
\(\underline{Proof}:\)
For \(P\) to be irreducible with respect to \(\mu\), we must show that:
\[\mu_i p_{ij}=\mu_j p_{ji} \hspace{.5cm} \forall \hspace{.1cm} i,j\]
Recall that \(Q\) is symmetric (i.e \(q_{ij}=q_{ji}\)), as this is key to the reversibility of \(P\).
Now, given by the definition of \(P\), we have that:
\[p_{ij}=q_{ij}min(1,\frac{\mu_j}{\mu_i})\]
and we also have that:
\[p_{ji}=q_{ji}min(1,\frac{\mu_i}{\mu_j})=q_{ij}min(1,\frac{\mu_i}{\mu_j})\]
From here, we can deal with different cases for the \(\mu\)’s, taking into account that we know \(\mu_k\) is strictly positive for all \(k\), and thus their ratios are strictly positive as well. We will show, that in all cases, reversibility holds true.
Notice that this implies that \(\frac{\mu_i}{\mu_j}<1\) and \(\frac{\mu_j}{\mu_i}>1\) Therefore, we can conclude that \[p_{ij}=q_{ij}min(1,\frac{\mu_j}{\mu_i})=q_{ij}\cdot 1=q_{ij}\] and \[p_{ji}=q_{ij}min(1,\frac{\mu_i}{\mu_j})=q_{ij}\frac{\mu_i}{\mu_j}\] Let us plug these values of \(p_{ij}\) and \(p_{ji}\) into the reversibility equality to see if it holds. \[\mu_i q_{ij}=\mu_j q_{ij}\frac{\mu_i}{\mu_j}\] which simplifies to: \[\mu_i q_{ij}=\mu_i q_{ij}\] The equality holds true, and thus the condition for reversibility of \(P\) is satisfied.
This case is analogous to that of the first. Notice that this implies that \(\frac{\mu_i}{\mu_j}\geq 1\) and \(\frac{\mu_j}{\mu_i}\leq 1\)
Therefore, we can conclude that \[p_{ij}=q_{ij}min(1,\frac{\mu_j}{\mu_i})=q_{ij}\frac{\mu_j}{\mu_i}\] and \[p_{ji}=q_{ij}min(1,\frac{\mu_i}{\mu_j})=q_{ij}\cdot 1=q_{ij}\] As we did before, let us plug these values of \(p_{ij}\) and \(p_{ji}\) into the reversibility equality to see if it holds. \[\mu_i q_{ij}\frac{\mu_j}{\mu_i}=\mu_j q_{ij}\] which simplifies to: \[\mu_j q_{ij}=\mu_j q_{ij}\]
The equality holds true, and thus the condition for reversibility of \(P\) is satisfied.
As this proof is for any arbitrary states \(i\) and \(j\) in \(P\), we can conclude that \(P\) is indeed reversible with respect to \(\mu\). \(\blacksquare\)
Write out a proof that that \(P\) is irreducible, and that if \(\mu\) isn’t perfectly uniform then P is aperiodic. [Hint: Show that if \(i \to j\) under \(Q\) then \(i \to j\) under \(P\). For aperidocity, consider a* *site where where a transition can occur]
\(\underline{Proof}:\)
As established in Task 1, all the elements of \(\mu\) are strictly positive, the ratios \(\frac{\mu_i}{\mu_j}\) for any \(i\) and \(j\) can range from an arbitrarily small real number near zero to an arbitrarily large real number. As a result:
\[min(1,\frac{\mu_i}{\mu_j})\in(0,1]\]
for all \(i\) and \(j\).
Now, recall that \(P\) being reducible means have a return probability \(f_{ij}>0\) for all states \(i\) and \(j\), where:
\[f_{ij}=p_{ij}+\sum_{k\neq j}p_{ik}f_{kj}\]
In words, we have that we can go directly go from \(i\) to \(j\) (i.e \(p_{ij}>0\)), or we can reach \(j\) from \(i\) via other states (\(p_{ia}\cdot p_{ab}\cdot p_{bc}\cdot p_{cj}>0\), where each \(p\) is strictly positive), or possibly both. Now, we already know this holds true for \(Q\), as it is irreducible.
Now, let the minimum of 1 and the ratio of the \(\mu\)’s for each transition from states \(i\) to \(j\) be \(r_{ij}\):
\[r_{ij}=min(1,\frac{\mu_i}{\mu_j})\in(0,1]\]
\(Q\) being irreducible implies at least one of the following two for any two states \(i\) and \(j\).
Case 1: We can transition directly: \(q_{ij}>0\)
In this case, notice that \(p_{ij}=q_{ij}\cdot r_{ij}\). And as we established \(r_{ij}>0\), we can conclude that \(p_{ij}>0\). Notice that this implies that \(f_{ij}>0\)
Case 2: We reach \(j\) from \(i\) indirectly: \(i\to a_1 \to a_2 \to ... \to a_n \to j\)
In this case, we clearly have that \(q_{ia_{1}}\cdot q_{a_{1}a_{2}}\cdot ...\cdot q_{a_{n-1}a_{n}}\cdot q_{a_{n}j}>0\)
Recall that as all our \(\mu\) ratios are strictly positive, we can claim that:
\[r_{ia_{1}}q_{ia_{1}}\cdot r_{a_{1}a_{2}}q_{a_{1}a_{2}}\cdot ...\cdot r_{a_{n-1}a_{n}}q_{a_{n-1}a_{n}}\cdot r_{a_{n}j}q_{a_{n}j}>0\]
Notice that this is just another way of expressing:
\[p_{ia_{1}}\cdot p_{a_{1}a_{2}}\cdot ...\cdot p_{a_{n-1}a_{n}}\cdot p_{a_{n}j}>0\]
Which implies that \(f_{ij}>0\).
Needless to say, there is a the third case where \(i\) can reach \(j\) both directly and indirectly, and we see by the two cases above that we also get \(f_{ij}>0\).
By the cases we went through above, we now know that if two states communicate under \(Q\), then they also communicate under \(P\). Now, as \(Q\) is irreducible, all its states communicate, and thus all of \(P\)’s states communicate. \(P\) is irreducible. \(\blacksquare\)
\(\underline{Proof}:\)
For \(\mu\) that is not uniform, there exists a maximum element (not necessarily unique) \(\mu_t\) for some state \(t\). Let us show that \(p_{tt}>0\) in order to prove that \(t\) is an aperiodic state. Recall the definition of diagonals in \(P\) as:
\[p_{tt}=1-\sum_{k\neq t}q_{tk}\cdot min(1,\frac{\mu_k}{\mu_t})=1-\sum_{k\neq t}q_{tk}\cdot r_{kt}\]
As we know that \(\mu_t \geq \mu_k\) for all states \(k\) (strictly greater for at least some cases, as this is not a uniform \(\mu\)), we have that
\[r_{kt}\leq 1\]
which again, at least some of which are strictly less than 1. Now this tells us that
\[q_{tk}\cdot r_{kt}\leq q_{tk}\]
for all states \(k\neq t\), where at least for some states the inequality is strict. We can thus conclude that:
\[\sum_{k\neq t}q_{tk}\cdot r_{kt}< \sum_{k\neq t}q_{tk}\]
we use all this to find that:
\[p_{tt}=1-\sum_{k\neq t}q_{tk}\cdot r_{kt}>1-\sum_{k\neq t}q_{tk}=q_{tt}\]
As \(p_{tt}>q_{tt}\), we can safely conclude that \(p_{tt}>0\), and thus state \(t\) is aperiodic. Recall, however, that we proved earlier that \(P\) is irreducible (i.e \(P\) is one equivalence class). As aperiodicity is a class property, we can finally conclude that \(P\) is aperiodic.
This proof might be a bit tedious to go through, so let us understand the intuition of why this all works. In essence, it has to do with the way the Metropolis Algorithm functions. Starting at state \(i\), a transition to state \(j\) (assuming it does not create forbidden travel) is accepted with probability \(P(U\leq\frac{\mu_i}{\mu_j})\), where \(U\) follows uniform[0,1]. As already stated in the project description, a uniform \(\mu\) implies that all (non-forbidden) transitions are accepted. But when \(\mu\) is not uniform, the ratios are not always 1. As discussed in the proof, if we take our state \(t\) and propose a move (i.e switching of two cities) to state \(j\) with \(\mu_j<\mu_t\), we accept it with probability:
\[P(U\leq\frac{\mu_j}{\mu_t})=\frac{\mu_j}{\mu_t}<1\]
and thus the probability of rejecting the transition is:
\[1-P(U\leq\frac{\mu_j}{\mu_t})=1-\frac{\mu_j}{\mu_t}>0\]
which in turn implies that we can stay at \(t\) with positive probability (i.e \(p_{tt}>0\)).\(\blacksquare\)
Check that \(Q\) is symmetric.
\(\underline{Proof}:\)
Let us make a quick review of how our algorithm works. Let us say we start at an arbitrary state \(i\) (i.e a sequence of 20 cities) with no forbidden travel. From there, our algorithm will, at random, pick two cities, say 1 and 7. It will then switch the location of these two cities in our current Hamiltonian Circuit, checking if the switch introduces any forbidden travel. If it does not, then we have arrived at a new state, call it \(j\).
Now, if we were at this state \(j\), going back to state \(i\) would imply going through the exact same procedure again. We would need our algorithm to pick the pair 1 and 7 as we initially did, then switch their locations, leaving us back at \(i\). Therefore, we have:
\[p_{ij}=p_{ji}>0\]
In fact, since our algorithm gives each city an equal probability of being chosen, any switch from \(i\) is of equal probability (if we do without the caveat of forbidden travel, of course).
Now let us deal with the case where a one-step transition is not possible. For example, let the first six cities in state \(a\) be:
\[2,1,3,7,4,9,...\]
and let another state \(b\) have the first six cities:
\[10,5,12,18,3,9,...\]
As should be obvious by the first six cities of each, there is no switch of two cities such that \(a\) becomes \(b\). Therefore, \(p_{ab}=0\). Analogously, the converse also is not possible. If there is no switch that allows \(a\) to become \(b\), then the same is true for \(b\) to \(a\). Recall that we showed earlier that the switch that takes us from state \(a\) to \(b\) (assuming it is possible), would be the exact same switch required to move from state \(b\) to \(a\). Thus in this case: \[p_{ab}=p_{ba}=0\]
Therefore, given that the cases of positive probability and zero probability of transitions covers the entirety of options, we see that \(Q\) must be symmetric. \(\blacksquare\)
By Howell Lu, Adeeb Rouhani , Sebhat Yacob