0
$\begingroup$

I was reading the paper 0810.4113v2, burda, which analyzed the stationary distribution maximal entropy random walk on the irregular lattice. I am confused on some of the steps.

Description:

The graph is defined by asymmetric adjacency matrix $A$, with elements $A_{ij} = 1$ if $i$ and $j$ are neighboring nodes and $A_{ij} = 0$ otherwise. The hopping is a local Markov process: the particle which arrives at some moment to node $i$ will hop to a neighboring node $j$ with probability $P_{ij}$, independently of the past history. The elements of the transition matrix are $P_{ij} = 0$ if $A_{ij} = 0$, that is if nodes $i$, $j$ are not linked, and for each $i$ one has $\sum_j P_{ij} = 1$.

The main quantity of interest is the probability, $\pi_i(t)$, of finding the particle at node $i$ at time $t$. One can calculate it recursively, applying the Markov property: $$\pi_i(t + 1) = \sum_j\pi_j(t)P_{ji}. ~~~~~~~~(1)$$

Using spectral properties of the matrix $P_{ij}$ , one can show that πi(t) reaches for $t \rightarrow \infty$ a unique stationary state $\pi^*_i$ obeying the following eigenequation: $$\pi^*_i=\sum_j\pi^*_j P_{ji}. ~~~~~~~~(2)$$

........

Let $\psi_i$ be the normalized eigenvector, $\sum_i \psi^2_i=1$, corresponding to the maximal eigenvalue $\lambda$ of the adjacency matrix $A_{ij}$: $$\sum_j A_{ij}\psi_j = \lambda\psi_i.~~~~~~~~(6)$$

The eigenvalue $\lambda$ is clearly in the range $k_{min} \leq \lambda \leq k_{max}$ ,where $k_{min}$ and $k_{max}$ are the maximal and minimal node degrees of the graph, respectively. The Frobenius-Perron theorem tells us that the eigenvetor has all elements of the same sign, so that one can choose $\psi_i > 0$. Let us use this eigenvector to define the following transition matrix: $$P_{ij}=\frac{A_{ij}}{\lambda}\frac{\psi_j}{\psi_i}.~~~~~~~~(7)$$

By construction, the entries $P_{ij}$ are positive if $i$ and $j$ are neighboring nodes. They are also properly normalized:$\sum_j P_{ij} = 1$. A similar onstrution has been reently proposed in the ontext of optimal information coding [7]. The weight (4) is now independent of intermediate nodes: $$P(\gamma^{(t)}_{i_0~i_t}) = \frac{1}{\lambda^t}\frac{\psi_{i_t}}{\psi_{i_0}},~~~~~~~~(8)$$ and thus all trajectories having length $t$ and given endpoints $i_0$ and $i_t$ are equiprobable. For a closed trajectory, the probability (8) depends only on its length $t$. The stationary distribution of MERW is $$\pi^*_i=\psi^2_i~~~~~~~~(9)$$ which is easy to check by combining Eqs. (7) and (2). It is a normalized probability: $\sum_i\pi^*_i=1$, and the detailed balance condition is fulilled: $\pi^*_i P_{ij}=\pi^*_j P_{ji}$.

I am confused about how to obtain (9). Does any one can give me the detail intermediate steps to obtain (9)? Thanks in advance.

I tried:

$$\pi^*_i=\sum_j\pi^*_jP_{ji}$$ $$j\rightarrow i, P_{ji}=\frac{A_{ji}}{\lambda}\frac{\psi_i}{\psi_j}$$ $$i\rightarrow j, P_{ij}=\frac{A_{ij}}{\lambda}\frac{\psi_j}{\psi_i}$$ $$\pi^*_i=\sum_j\pi^*_jP_{ji}$$ $$=\sum_j(\sum_i\pi^*_i P_{ij})P_{ji}$$ $$=\sum_j\sum_i\pi^*_i P_{ij}P_{ji}$$ $$=\sum_j\sum_i\pi^*_i \frac{A_{ij}}{\lambda}\frac{\psi_j}{\psi_i}\frac{A_{ji}}{\lambda}\frac{\psi_i}{\psi_j}$$ $$????~~~~=\psi^2_i~~~~????$$

I also read ref Maximal_entropy_random_walk. I still confused.

$\endgroup$
  • $\begingroup$ By detailed balance the transition matrix can be symmetrized. This is the key step $\endgroup$ – Steve Huntsman Aug 20 '18 at 16:15
  • $\begingroup$ How to derive $\pi^*_i=\psi^2_i~$? $\endgroup$ – Nick Dong Aug 21 '18 at 2:57
  • $\begingroup$ See, e.g. arxiv.org/pdf/1509.08212.pdf for a similar construction $\endgroup$ – Steve Huntsman Aug 21 '18 at 13:10
1
$\begingroup$

The name for this object (though not always used) is "Parry measure", see e.g. page 20 here — https://personalpages.manchester.ac.uk/staff/charles.p.walkden/magic/lecture08.pdf or here https://homepages.warwick.ac.uk/~masdbl/survey10.pdf . Exactly what you are looking for is explained here — http://www.fais.uj.edu.pl/documents/41628/d63bc0b7-cb71-4eba-8a5a-d974256fd065 , see pages 25-26 and especially formula (3.20) — and I'll sketch a really handwaving explanation.

If one has to maximize the entropy, a natural idea is to say "OK, let's consider maximal entropy we can get on a finite chain from moment $t=-N$ to the moment $t=N$". This means that one is considering a uniform measure on these finite words. What does it give "in the middle", at the moment $t=0$?

For each possible letter (or vertex of the graph) there is a number of ways that it can be reached from $t=-N$, and the number of ways that it can be reached from the future $t=N$, going to the past. And the total number of times the letter appears at $t=0$ is the product of the two.

Though, if one varies the letter, the number of ways to reach it from the past is almost proportional to the right eigenvector of the transition matrix (to count the number of paths, one applies its $N$-th power), and from the future — to the left eigenvector. Hence, one has to take a left- and right- eigenvectors and to multiply them coordinatewise, then normalizing the result to get the probability measure.

The same idea gives the transition probabilities for the measure of maximal entropy: now one has to consider two letters, the ones at $t=0$ and at $t=1$.

$\endgroup$

Your Answer

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

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