Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Maximal entropy random walk
open-in-new
<p>A maximal entropy random walk (MERW) is a popular type of <a href="/facts/Biased_random_walk_on_a_graph/vw5rD6ht">biased random walk on a graph</a>, in which transition probabilities are chosen accordingly to the <a href="/facts/Principle_of_maximum_entropy/T0gybmPF">principle of maximum entropy</a>, which says that the <a href="/facts/Probability_distribution/EpsKKVRu">probability distribution</a> which best represents the current state of knowledge is the one with largest entropy. While a standard <a href="/facts/Random_walk/08v0jmfv">random walk</a> samples for every vertex a uniform probability distribution of outgoing edges, locally maximizing <a href="/facts/Entropy_rate/L2VllINH">entropy rate</a>, MERW maximizes it globally (average <a href="/facts/Entropy_production/HxNR6Yza">entropy production</a>) by sampling a uniform probability distribution among all paths in a given graph. </p><p>MERW is used in various fields of science. A direct application is choosing probabilities to maximize transmission rate through a constrained channel, analogously to <a href="/facts/Fibonacci_coding/GXCLAf7t">Fibonacci coding</a>. Its properties also made it useful for example in analysis of complex networks, like <a href="/facts/Link_prediction/vd9FbAxe">link prediction</a>, community detection, robust transport over networks and <a href="/facts/Centrality/4n24KqLt">centrality</a> measures. It is also used in <a href="/facts/Image_analysis/woLB8cX7">image analysis</a>, for example for detecting visual saliency regions, object localization, tampering detection or <a href="/facts/Tractography/UzsnkIJ0">tractography</a> problem. </p><p>Additionally, it recreates some properties of <a href="/facts/Quantum_mechanics/BRc3Mzgr">quantum mechanics</a>, suggesting a way to repair the discrepancy between <a href="/facts/Diffusion/KbAxroBa">diffusion</a> models and quantum predictions, like <a href="/facts/Anderson_localization/LB5Cf5Q5">Anderson localization</a>. </p>