ORIGINAL ARTICLE: Jarek Duda, From Maximal Entropy Random Walk to quantum thermodynamics, arXiv:1111.2253v3 [quant-ph]. https://doi.org/10.48550/arXiv.1111.2253.
DEMONSTRATION: http://demonstrations.wolfram.com/ElectronConductanceModelsUsingMaximalEntropyRandomWalks/
In many situations we have to choose a random walk - transition probabilities e.g. on a graph, for diffusion models. A naive basic approach, also nearly default, is uniform distribution among outgoing edges, like drunken sailor rolling a dice to choose one of directions - let us call it GRW (generic random walk). While it maximizes entropy separately for each step (locally), turns out it usually only approximates maximization of mean entropy production (globally), what is required by (Jaynes’) maximal entropy principle - finally satisfied by MERW (Maximal Entropy Random Walk). Equivalently, MERW can be viewed as coming from uniform or Boltzmann distribution among paths - exactly like imagining random walk along spin sequence in Ising model and its extensions. MERW has much stronger than GRW Anderson-like localization, with stationary probability distribution exactly is in quantum mechanics, repairing disagreement of standard (GRW-based) diffusion models e.g. for electron conductance in semiconductor - incorrectly predicted to be conductors by them. MERW naturally gets Born rule from symmetry, allowing for violation of Bell-like inequalities. There are now hundreds of articles about MERW with various applications, e.g. analysis of complex networks like link prediction, community detection, robust transport over networks, centrality measures. Also in image analysis, for example for detecting visual saliency regions, object localization, tampering detection, or tractography problem to reconstruct neural tracts from diffusion MRI imaging.
This notebook briefly introduces to the growing world of MERW and its applications from 3 perspectives: encoding with constraints, Ising model and electron conductance models - repairing often suboptimal naive (GRW) choice of random walk. Here are hundreds of articles about MERW, for example for applications in complex network analysis, link prediction, community detection, robust transport over networks, centrality measures. Also in image analysis, for example for detecting visual saliency regions, object localization, tampering detection, or tractography problem. This notebook uses some slides from here, with available video lecture.
Imagine we have a graph defined by adjacency matrix
M:
M
ij
1
if
(i,j)
is edge, 0 otherwise. We would like to choose a random walk on this graph: stochastic matrix
S
ij
as probability of jumping to
j
when being in
i
(using only edges): satisfying
0≤
S
ij
≤
M
ij
,
∑
j
S
ij
1
. The naive choice (GRW) is assuming uniform probability distribution among possible edges from the current vertex, this way locally maximizing entropy:
GRW
S
ij

M
ij

d
i
for
d
i

∑
j
M
ij
degree of current vertex. For
M
T
M
undirected graphs it leads to
Pr(i):
ρ
i
∝
d
i
stationary probability distribution:
ρSρ
. To see that this naive (but nearly default) GRW choice can be suboptimal, let us look at so called Fibonacci coding scenario: we would like to store information in sequence of 0 and 1, but with constraints - forbid the use of two neighboring ones: "11". So after 0 we can use 0 or 1, but after 1 we have to use 0 - getting the below adjacency matrix M={{1,1},{1,0}}. Wanting to choose a stochastic matrix S={{q,1-q},{1,0}}, it has one free parameter
0≤q≤1
: what is the probability of choosing 0 after 0. GRW would choose q=1/2, maximizing entropy locally. However, as we can see below, it is suboptimal - entropy rate averaged over probability distribution of vertices is maximized by MERW, here using golden ratio
q≈0.618
. Intuitively, the reason is that increasing q over 1/2, we reduce entropy produced from state 0, but also increase its frequency - reduce probability of state 1 with zero entropy production.
Having such entropy optimized (MERW) stochastic model, we can store information very close to its entropy e.g. ~0.694 bits/node here (reduced from 1 bit/node due to constraints), by using entropy coder switching encoder with decoder. For my 2006 physics MSc (its translation: arXiv:0710.3861) I was working on its extension to 2D Fibonacci problem (also called hard square problem): now forbidding "11" in horizontal and vertical direction, e.g. to improve capacity of HDD. As the entropy coder I have started asymmetric numeral systems back then - now popular in data data compression (e.g. in Linux kernel, products of Apple, Facebook, Google), and MERW to optimize the stochastic model - similarly as for discussed further 2D Ising model.
Let us now briefly derive MERW formulas. To maximize information capacity for Fibonacci problem, instead of thinking about single steps (GRW), we should assume uniform probability distribution among entire allowed sequences/paths (MERW). To find e.g. stationary probability distribution inside such uniform path ensemble, notice that
(
t
M
)
ij
is combinatorially the number of length t paths from i to j. Using it twice: t steps toward past and future, usually (Frobenius-Perron theorem) in
t∞
limit leads to
ρ(x)∝
2
ψ
x
stationary probability distribution (like QM Born rule), for
ψMλψ
dominant eigenvector of
M
(maximizing eigenvalue corresponding to minus energy e.g. in Hubbard model).
Here are gathered formulas for the two philosophies of choosing random walk for a graph given by adjacency matrix M:
Let us now use it to find random walk on defected 1D lattice (cyclic boundary conditions) - with defects as removed self-loops: vertex has degree 3 or 2. For GRW stationary probability distributions is proportional to degree - there is very weak localization. For MERW we have to find the dominant eigenvector: maximizing λ. Denoting energy as
E3-λ
like below, we need to equivalently minimize energy, generally getting discrete stationary Schrödinger equation, with MERW stationary probability distribution exactly as QM ground state - in agreement with quantum prediction, having much stronger localization that GRW.
Here is a simple code to calculate stationary probability distributions like above for both QM and MERW - nearly completely localized in the largest defect-free region:

CITE THIS NOTEBOOK

From Maximal Entropy Random Walk to quantum thermodynamics​
by Jarek Duda​
Wolfram Community, STAFF PICKS, May 23 2023
​https://community.wolfram.com/groups/-/m/t/2924355