Maximal entropy random walk: Difference between revisions

Revision as of 01:24, 31 May 2025

Latest revision as of 01:37, 31 May 2025

(One intermediate revision by the same user not shown)

Line 1:

{{Use dmy dates|date=October 2017}}

{{Mcn|date=May 2025}}

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.

Line 60 ⟶ 62:

[[Image:Examples of using MERW, Fibonacci coding(left) and 1D defected lattice (right).png|thumb|320px|right|Left: choosing the optimal probability after symbol 0 in [[Fibonacci coding]]. Right: a one-dimensional defected lattice and its stationary density for a length-1000 cycle (it has three defects). In a standard random walk, the stationary density is proportional to degree of a vertex, leading to 3/2 difference here; however, in MERW, the density is nearly completely localized in the largest defect-free region, analogous to the [[ground state]] predicted by [[quantum mechanics]].]]

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 athe freedom of choosing the probability of 0 after 0. Let us denote this probability by <math>q</math>, then. [[entropyEntropy coding]] would allowallows encoding a message using this chosen probability distribution. The stationary probability distribution of symbols for a given <math>q</math> turns out to be <math>\rho=(1/(2-q),1-1/(2-q)) </math>. Hence, entropy productionproduced is <math>H(S)=\rho_0 \left(q\log(1/q)+(1-q)\log(1/(1-q))\right)</math>, which is maximized for <math>q=(\sqrt{5}-1)/2\approx 0.618</math>, known as the [[golden ratio]]. In contrast, a standard random walk would choose the suboptimal <math>q=0.5</math>. While choosing a larger <math>q</math> reduces the amount of information produced after 0, it also reduces the frequency of 1, after which we cannot write any information.

A more complex examplecase is the defected one-dimensional cyclic lattice:, letfor sayexample, 1000a nodesring connectedwith in1000 aconnected ringnodes, for which all nodes but the defects have a self-loop (edge to itself). In a standard random walk (GRW), the stationary probability distribution would have the defect probability beingbe 2/3 of probability of the non-defect vertices – {{Snd}}there is nearly no localization, also analogously for standard diffusion, which is the infinitesimal limit of a GRW. For a MERW, we have to first find the dominant eigenvector of the adjacency matrix – maximizing <math>\lambda</math> in:

<math>(\lambda \psi)_x = (A\psi)_x = \psi_{x-1}+ (1-V_x) \psi_x +\psi_{x+1}</math>

Line 70 ⟶ 74:

<math>E \psi_x =-(\psi_{x-1} -2 \psi_x +\psi_{x+1}) + V_x \psi_x</math>

where <math>E = 3-\lambda</math> is minimized now, becoming the analog of energy. The formula inside the bracket is [[discrete Laplace operator]], making this equation a discrete analogue of the stationary [[Schrödinger equation]]. As in quantum mechanics, MERWs predict that the probability distribution shouldis leadthat exactly toof the one of quantum [[ground state]]: <math>\rho_x \propto \psi_x^2</math> with its strongly localized density (in contrast to standard diffusion). Taking the [[infinitesimal]] limit, we can get the standard continuous stationary (time-independent) Schrödinger equation (<math>E\psi=-C\psi_{xx}+V\psi</math> for <math>C=\hbar^2/2m</math>) here.<ref name="ext">[http://www.fais.uj.edu.pl/documents/41628/d63bc0b7-cb71-4eba-8a5a-d974256fd065 J. Duda, ''Extended Maximal Entropy Random Walk''], PhD Thesis, 2012.</ref>

==See also==