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 standard random walk chooses for every vertex uniform probability distribution among its outgoing edges, locally maximizing entropy rate, MERW maximizes it globally (average entropy production) by assuming 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. Also 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 vertices, defined by an adjacency matrix : if there is an edge from vertex to , 0 otherwise. For simplicity assume it is an undirected graph, which corresponds to a symmetric ; however, MERW 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 and its outgoing edge to , choose probability of the walker randomly using this edge after visiting . Formally, find a stochastic matrix (containing the transition probabilities of a Markov chain) such that for all and for all . Assuming this graph is connected and not periodic, ergodic theory says that evolution of this stochastic process leads to some stationary probability distribution such that . 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: 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