Does MERW visit all nodes equally often?

Generally no; its stationary distribution is determined by the squared positive eigenvector in the undirected setting.

Is it the same as an ordinary random walk?

It is the same on regular undirected graphs, but can differ on irregular graphs.

Does a stationary distribution guarantee convergence from every starting state?

No. Periodicity, as in the four-node path example, can prevent that convergence.

AI Glossary / Mathematics and optimization / Intermediate

Maximal entropy random walk

Definition

A maximal entropy random walk is a graph-based Markov process whose transition probabilities maximize the long-run entropy rate of allowed paths. In the standard finite, connected, undirected graph setting, it uses the adjacency matrix's largest eigenvalue and positive eigenvector. It makes allowed paths of a given length with fixed starting and ending nodes equally probable.

What it means

An ordinary random walk chooses uniformly among the current node's neighbors. That maximizes uncertainty for the next local choice, but on an irregular graph it need not maximize uncertainty over whole trajectories. Different intermediate nodes offer different numbers of onward possibilities.
Maximal entropy random walk, often abbreviated MERW, accounts for this global structure. It generally favors moves toward regions supporting many possible paths. Consequently, maximizing path entropy does not mean spreading stationary visits uniformly across nodes. The walk can concentrate strongly in particular graph regions, so its objective must not be confused with equal coverage or fairness.

How it works

Let A be the symmetric adjacency matrix of a connected undirected graph containing an edge. Find its largest eigenvalue λ and a positive eigenvector ψ. Set P_ij=A_ij ψ_j/(λψ_i). The eigenvector equation ensures that each row of P sums to one.
Normalize ψ so that its squared entries sum to one. The stationary node probabilities are then π_i=ψ_i². Along a path of length t, the eigenvector ratios telescope, giving path probability ψ_end/(λ^t ψ_start). This explains why paths with the same length and endpoints receive equal probabilities. The entropy rate is log λ, using a logarithm base consistent with the chosen entropy units. Periodicity can prevent convergence from a particular initial distribution even though a stationary distribution exists.

Three practical examples

A network researcher can compare the global path behavior of MERW with an ordinary neighbor-uniform walk.
A graph-sampling study can examine whether a path-entropy objective concentrates samples in highly connected regions.
A scientific model can use MERW as a specified stochastic process for investigating localization, while checking whether that process suits the modeled system.

Think of it this way

Think of choosing a route through a building while considering the number of possible future routes beyond each door. Two doors may look equally available now but lead to very different onward possibilities. The analogy is limited: MERW follows a precise spectral rule, not a person making plans, and it does not guarantee uniform room visits or shortest journeys.

Worked example

Consider an original four-node path graph with edges 1-2, 2-3, and 3-4. Let φ=(1+sqrt(5))/2, approximately 1.618. The largest adjacency eigenvalue is φ, with an eigenvector proportional to (1,φ,φ,1). Check an inner node: its neighboring eigenvector entries sum to 1+φ=φ², as required.
At node one the only move is to node two. At node two, the MERW probability of moving to node one is 1/φ², approximately 0.382, while the probability of moving to node three is 1/φ, approximately 0.618. The corresponding probabilities at node three are mirrored. Each endpoint has a forced move.
The normalization factor for squared eigenvector entries is 2+2φ². Stationary probabilities are approximately (0.1382,0.3618,0.3618,0.1382). An ordinary random walk instead has stationary probabilities proportional to node degrees, namely (1/6,1/3,1/3,1/6). The MERW stationary distribution is more concentrated on the inner nodes.
Now compare two length-two paths from node two back to node two. The path 2-1-2 has probability (1/φ²)×1=1/φ². The path 2-3-2 has probability (1/φ)²=1/φ². They are equally probable under MERW. Under an ordinary walk, those probabilities are 1/2 and 1/4 respectively.
This graph is bipartite, so a walk starting at a single node alternates between the two node classes. Its distribution does not simply converge at every time step to the stationary vector. Starting in the stationary distribution keeps that distribution unchanged, which is a different statement. The distinction is especially important when checking a simulation against the stationary formula.

Illustrative case study

In a fictional graph-analysis team, an analyst proposes MERW to sample a network because its name suggests broad exploration. A small graph test reveals stronger concentration on central regions than the ordinary walk. The team records that behavior and decides whether path entropy matches its actual sampling goal before scaling up. This is an illustrative design review, not evidence that MERW improves recommendations, search quality, or customer outcomes.

Common misconceptions and mistakes

Maximal entropy does not mean maximum entropy of the stationary node distribution. Choosing neighbors uniformly is also not generally equivalent to maximizing the entropy rate of paths. The two walks coincide on connected regular undirected graphs, but that special case should not be generalized.
The squared-eigenvector stationary formula here uses a symmetric adjacency matrix. Directed graphs require a different treatment involving the relevant left and right eigenvectors. Disconnected graphs likewise need careful specification of components and initialization. Finally, adding self-loops to remove periodicity changes the graph and its entropy-maximizing walk; it is not merely a cosmetic adjustment.

Business use

For business applications involving graph sampling, MERW is a modeling option whose objective should be stated plainly. Assess which nodes or groups receive fewer visits and whether concentration supports the intended task. Account for the cost of computing or updating the spectral information when the network changes. A theoretically maximal path entropy is not, by itself, a business performance metric.

Check your understanding

Why do the two return paths in the worked example have equal probability?

Answer: Their transition products both equal 1/φ². More generally, the eigenvector ratios cancel along a path, leaving only its endpoints and length.

Related terms

Random walk
Markov Chain
Entropy rate
Stationary distribution
Localization
Adjacency matrix
Perron eigenvector
Eigenvector centrality

Learn next

Repeat the construction on a triangle, where every node has degree two. Verify that MERW chooses each neighbor with probability one-half and has a uniform stationary distribution. Compare its lack of bipartite alternation with the path example.

Stationary distribution

Sources

Primary source: Burda, Duda, Luck, and Waclaw, Localization of the Maximal Entropy Random Walk, original research: https://www.pure.ed.ac.uk/ws/portalfiles/portal/4414463/B_Waclaw_localization.pdf . The four-node calculation and fictional case are original.

Previous: Maxim, Gricean Next: Maximal independent set