A maximal entropy random walk (MERW) is a popular type of biased random walk on a graph, in which transition probabilities are chosen accordingly to the principle of maximum entropy, which says that the probability distribution which best represents the current state of knowledge is the one with largest entropy. While a standard random walk samples for every vertex a uniform probability distribution of outgoing edges, locally maximizing entropy rate, MERW maximizes it globally (average entropy production) by sampling a uniform probability distribution among all paths in a given graph. MERW is used in various fields of science. A direct application is choosing probabilities to maximize transmission rate through a constrained channel, analogously to Fibonacci coding. Its properties also made it useful for example in analysis of complex networks, like link prediction, community detection, robust transport over networks and centrality measures. It is also used in image analysis, for example for detecting visual saliency regions, object localization, tampering detection or tractography problem. Additionally, it recreates some properties of quantum mechanics, suggesting a way to repair the discrepancy between diffusion models and quantum predictions, like Anderson localization.
Basic model
Consider a graph with n {\displaystyle n} vertices, defined by an adjacency matrix A ∈ { 0 , 1 } n × n {\displaystyle A\in \left\{0,1\right\}^{n\times n}} : A i j = 1 {\displaystyle A_{ij}=1} if there is an edge from vertex i {\displaystyle i} to j {\displaystyle j} , 0 otherwise. For simplicity, assume it is an undirected graph, which corresponds to a symmetric A {\displaystyle A} ; however, MERWs can also be generalized for directed and weighted graphs (for example Boltzmann distribution among paths instead of uniform). We would like to choose a random walk as a Markov process on this graph: for every vertex i {\displaystyle i} and its outgoing edge to j {\displaystyle j} , choose probability S i j {\displaystyle S_{ij}} of the walker randomly using this edge after visiting i {\displaystyle i} . Formally, find a stochastic matrix S {\displaystyle S} (containing the transition probabilities of a Markov chain) such that
0 ≤ S i j ≤ A i j {\displaystyle 0\leq S_{ij}\leq A_{ij}} for all i , j {\displaystyle i,j} and
∑ j = 1 n S i j = 1 {\displaystyle \sum _{j=1}^{n}S_{ij}=1} for all i {\displaystyle i} . Assuming this graph is connected and not periodic, ergodic theory says that evolution of this stochastic process leads to some stationary probability distribution ρ {\displaystyle \rho } such that ρ S = ρ {\displaystyle \rho S=\rho } . Using Shannon entropy for every vertex and averaging over probability of visiting this vertex (to be able to use its entropy), we get the following formula for average entropy production (entropy rate) of the stochastic process:
H ( S ) = ∑ i = 1 n ρ i ∑ j = 1 n S i j log ( 1 / S i j ) {\displaystyle H(S)=\sum _{i=1}^{n}\rho _{i}\sum _{j=1}^{n}S_{ij}\log(1/S_{ij})}
This definition turns out to be equivalent to the asymptotic average entropy (per length) of the probability distribution in the space of paths for this stochastic process. In the standard random walk, referred to here as generic random walk (GRW), we naturally choose that each outgoing edge is equally probable:
S i j = A i j ∑ k = 1 n A i k . {\displaystyle S_{ij}={\frac {A_{ij}}{\sum \limits _{k=1}^{n}A_{ik}}}.}
For a symmetric A {\displaystyle A} it leads to a stationary probability distribution ρ {\displaystyle \rho } with
ρ i = ∑ j = 1 n A i j ∑ i = 1 n ∑ j = 1 n A i j . {\displaystyle \rho _{i}={\frac {\sum \limits _{j=1}^{n}A_{ij}}{\sum \limits _{i=1}^{n}\sum \limits _{j=1}^{n}A_{ij}}}.}
It locally maximizes entropy production (uncertainty) for every vertex, but usually leads to a suboptimal averaged global entropy rate H ( S ) {\displaystyle H(S)} . MERW chooses the stochastic matrix which maximizes H ( S ) {\displaystyle H(S)} , or equivalently assumes uniform probability distribution among all paths in a given graph. Its formula is obtained by first calculating the dominant eigenvalue λ {\displaystyle \lambda } and corresponding eigenvector ψ {\displaystyle \psi } of the adjacency matrix, i.e. the largest λ ∈ R {\displaystyle \lambda \in \mathbb {R} } with corresponding ψ ∈ R n {\displaystyle \psi \in \mathbb {R} ^{n}} such that ψ A = λ ψ {\displaystyle \psi A=\lambda \psi } . Then the stochastic matrix and stationary probability distribution are given by
S i j = A i j λ ψ j ψ i {\displaystyle S_{ij}={\frac {A_{ij}}{\lambda }}{\frac {\psi _{j}}{\psi _{i}}}}
for which every possible path of length l {\displaystyle l} from the i {\displaystyle i} -th to j {\displaystyle j} -th vertex has probability
1 λ l ψ j ψ i . {\displaystyle {\frac {1}{\lambda ^{l}}}{\frac {\psi _{j}}{\psi _{i}}}.}
Its entropy rate is log ( λ ) {\displaystyle \log(\lambda )} and the stationary probability distribution ρ {\displaystyle \rho } is
ρ i = ψ i 2 ‖ ψ ‖ 2 2 . {\displaystyle \rho _{i}={\frac {\psi _{i}^{2}}{\left\|\psi \right\|_{2}^{2}}}.}
In contrast to GRW, the MERW transition probabilities generally depend on the structure of the entire graph, making it nonlocal. Hence, they should not be imagined as directly applied by the walker – if random-looking decisions are made based on the local situation, like a person would make, the GRW approach is more appropriate. MERW is based on the principle of maximum entropy, making it the safest assumption when we do not have any additional knowledge about the system. For example, it would be appropriate for modelling our knowledge about an object performing some complex dynamics – not necessarily random, like a particle.
Sketch of derivation Assume for simplicity that the considered graph is undirected, connected and aperiodic, allowing to conclude from the Perron–Frobenius theorem that the dominant eigenvector is unique. Hence A l {\displaystyle A^{l}} can be asymptotically ( l → ∞ {\displaystyle l\rightarrow \infty } ) approximated by λ l ψ ψ T {\displaystyle \lambda ^{l}\psi \psi ^{T}} (or λ l | ψ ⟩ ⟨ ψ | {\displaystyle \lambda ^{l}|\psi \rangle \langle \psi |} in bra–ket notation). MERW requires a uniform distribution along paths. The number m i l {\displaystyle m_{il}} of paths with length 2 l {\displaystyle 2l} and vertex i {\displaystyle i} in the center is
m i l = ∑ j = 1 n ∑ k = 1 n ( A l ) j i ( A l ) i k ≈ ∑ j = 1 n ∑ k = 1 n ( λ l ψ ψ ⊤ ) j i ( λ l ψ ψ ⊤ ) i k = ∑ j = 1 n ∑ k = 1 n λ 2 l ψ j ψ i ψ i ψ k = λ 2 l ψ i 2 ∑ j = 1 n ψ j ∑ k = 1 n ψ k ⏟ =: b , {\displaystyle {\begin{aligned}m_{il}&=\sum _{j=1}^{n}\sum _{k=1}^{n}\left(A^{l}\right)_{ji}\left(A^{l}\right)_{ik}\approx \sum _{j=1}^{n}\sum _{k=1}^{n}\left(\lambda ^{l}\psi \psi ^{\top }\right)_{ji}\left(\lambda ^{l}\psi \psi ^{\top }\right)_{ik}\\[1ex]&=\sum _{j=1}^{n}\sum _{k=1}^{n}\lambda ^{2l}\psi _{j}\psi _{i}\psi _{i}\psi _{k}=\lambda ^{2l}\psi _{i}^{2}\underbrace {\sum _{j=1}^{n}\psi _{j}\sum _{k=1}^{n}\psi _{k}} _{=:b},\end{aligned}}}
hence for all i {\displaystyle i} ,
ρ i = lim l → ∞ m i l ∑ k = 1 n m k l = lim l → ∞ λ 2 l ψ i 2 b ∑ k = 1 n λ 2 l ψ k 2 b = lim l → ∞ ψ i 2 ∑ k = 1 n ψ k 2 = ψ i 2 ∑ k = 1 n ψ k 2 = ψ i 2 ‖ ψ ‖ 2 2 . {\displaystyle {\begin{aligned}\rho _{i}&=\lim _{l\to \infty }{\frac {m_{il}}{\sum \limits _{k=1}^{n}m_{kl}}}=\lim _{l\to \infty }{\frac {\lambda ^{2l}\psi _{i}^{2}b}{\sum \limits _{k=1}^{n}\lambda ^{2l}\psi _{k}^{2}b}}\\[1ex]&=\lim _{l\rightarrow \infty }{\frac {\psi _{i}^{2}}{\sum \limits _{k=1}^{n}\psi _{k}^{2}}}={\frac {\psi _{i}^{2}}{\sum \limits _{k=1}^{n}\psi _{k}^{2}}}={\frac {\psi _{i}^{2}}{\left\|\psi \right\|_{2}^{2}}}.\end{aligned}}}
Analogously calculating probability distribution for two succeeding vertices, one obtains that the probability of being at the i {\displaystyle i} -th vertex and next at the j {\displaystyle j} -th vertex is
ψ i A i j ψ j ∑ i ′ = 1 n ∑ j ′ = 1 n ψ i ′ A i ′ j ′ ψ j ′ = ψ i A i j ψ j ψ A ψ ⊤ = ψ i A i j ψ j λ ‖ ψ ‖ 2 2 . {\displaystyle {\frac {\psi _{i}A_{ij}\psi _{j}}{\sum \limits _{i'=1}^{n}\sum \limits _{j'=1}^{n}\psi _{i'}A_{i'j'}\psi _{j'}}}={\frac {\psi _{i}A_{ij}\psi _{j}}{\psi A\psi ^{\top }}}={\frac {\psi _{i}A_{ij}\psi _{j}}{\lambda \left\|\psi \right\|_{2}^{2}}}.}
Dividing by the probability of being at the i {\displaystyle i} -th vertex, i.e. ρ i {\displaystyle \rho _{i}} , gives for the conditional probability S i j {\displaystyle S_{ij}} of the j {\displaystyle j} -th vertex being next after the i {\displaystyle i} -th vertex
S i j = A i j λ ψ j ψ i . {\displaystyle S_{ij}={\frac {A_{ij}}{\lambda }}{\frac {\psi _{j}}{\psi _{i}}}.}
Weighted MERW: Boltzmann path ensemble We have assumed that A i j ∈ { 0 , 1 } {\displaystyle A_{ij}\in \{0,1\}} , yielding a MERW corresponding to the uniform ensemble among paths. However, the above derivation works for any real nonnegative A {\displaystyle A} for which the Perron-Frobenius theorem applies. Given A i j = exp ( − E i j ) {\displaystyle A_{ij}=\exp(-E_{ij})} , the probability of a particular length- l {\displaystyle l} path ( γ 0 , … , γ l ) {\displaystyle (\gamma _{0},\ldots ,\gamma _{l})} is as follows:
Pr ( γ 0 , … , γ l ) = ρ γ 0 S γ 0 γ 1 … S γ l − 1 γ l = ψ γ 0 A γ 0 γ 1 … A γ l − 1 γ l λ l ψ γ l = ψ γ 0 exp ( − ( E γ 0 γ 1 + ⋯ + E γ l − 1 γ l ) ) λ l ψ γ l , {\displaystyle {\begin{aligned}\Pr(\gamma _{0},\ldots ,\gamma _{l})&=\rho _{\gamma _{0}}S_{\gamma _{0}\gamma _{1}}\ldots S_{\gamma _{l-1}\gamma _{l}}\\[1ex]&=\psi _{\gamma _{0}}{\frac {A_{\gamma _{0}\gamma _{1}}\ldots A_{\gamma _{l-1}\gamma _{l}}}{\lambda ^{l}}}\psi _{\gamma _{l}}\\[1ex]&=\psi _{\gamma _{0}}{\frac {\exp \left(-\left(E_{\gamma _{0}\gamma _{1}}+\dots +E_{\gamma _{l-1}\gamma _{l}}\right)\right)}{\lambda ^{l}}}\psi _{\gamma _{l}},\end{aligned}}}
which is the same as the Boltzmann distribution of paths with energy defined as the sum of E i j {\displaystyle E_{ij}} over the edges of the path. For example, this can be used with the transfer matrix to calculate the probability distribution of patterns in the Ising model.
Examples
Let us first look at a simple nontrivial situation: Fibonacci coding, where we want to transmit a message as a sequence of 0s and 1s, but not using two successive 1s: after a 1 there has to be a 0. To maximize the amount of information transmitted in such sequence, we should assume a uniform probability distribution in the space of all possible sequences fulfilling this constraint. To practically use such long sequences, after 1 we have to use 0, but there remains the freedom of choosing the probability of 0 after 0. Let us denote this probability q {\displaystyle q} . Entropy coding allows encoding a message using this chosen probability distribution. The stationary probability distribution of symbols for a given q {\displaystyle q} turns out to be ρ = ( 1 / ( 2 − q ) , 1 − 1 / ( 2 − q ) ) {\displaystyle \rho =(1/(2-q),1-1/(2-q))} . Hence, entropy produced is H ( S ) = ρ 0 ( q log ( 1 / q ) + ( 1 − q ) log ( 1 / ( 1 − q ) ) ) {\displaystyle H(S)=\rho _{0}\left(q\log(1/q)+(1-q)\log(1/(1-q))\right)} , which is maximized for q = ( 5 − 1 ) / 2 ≈ 0.618 {\displaystyle q=({\sqrt {5}}-1)/2\approx 0.618} , known as the golden ratio. In contrast, a standard random walk would choose the suboptimal q = 0.5 {\displaystyle q=0.5} . While choosing a