How to choose random walk, diffusion? (local vs global entropy maximization)

[Duda Jarek]

To choose random walk on a graph, it seems natural to to assume that the walker jumps using each possible edge with the same probability (1/degree) - such GRW (generic random walk) maximizes entropy locally (for each step).
Discretizing continuous space and taking infinitesimal limit we get various used diffusion models.

However, looking at mean entropy production: averaged over stationary probability distribution of nodes, its maximization leads to usually a bit different MERW: https://en.wikipedia.org/wiki/Maximal_entropy_random_walk

It brings a crucial question which philosophy should we choose for various applications - I would like to discuss.

GRW
- uses approximation of (Jaynes) https://en.wikipedia.org/wiki/Principle_of_maximum_entropy
- has no localization property (nearly uniform stationary probability distribution),
- has characteristic length of one step - this way e.g. depends on chosen discretization of a continuous system.

MERW
- is the one maximizing mean entropy, "most random among random walks",
- has strong localization property - stationary probability distribution exactly as quantum ground state,
- is limit of characteristic step to infinity - is discretization independent.

Simulator of both for electron conductance: https://demonstrations.wolfram.com/ElectronConductanceModelsUsingMaximalEntropyRandomWalks/
Diagram with example of evolution and stationary denstity, also some formulas (MERW uses dominant eigenvalue):

Edited September 3, 2020 by Duda Jarek

[studiot]

 

4 hours ago, Duda Jarek said:

I would like to discuss.

 

Nice topic +1

But.

Beware of confusing random progression through a mathematical graph with a spatial random walk for say a gaseous molecule.

[Duda Jarek]

Thanks, my general thoughts is that:

GRW should be used when the walker directly uses the assumed random walk, like "drunken sailor" throwing a dice in each node, or just human making looking random local decisions which link to click at for https://en.wikipedia.org/wiki/PageRank - it is for walkers performing nearly random decisions accordingly to local situation, having characteristic length like one web link.

MERW stochastic propagator is nonlocal - depends on the entire space (in eigenequation of adjacency matrix) - it shouldn't be seen as directly used by the walker. Instead, this is thermodynamical picture - the safest (entropy maximizing) assumption we can make for limited knowledge situations like some complex hidden dynamics e.g. in electron conductance.

Edited September 3, 2020 by Duda Jarek

[studiot]

Hidden beneath all those big words and phrases is the fact that the random walks described are more like drunk wandering the grid pattern of streets at night.
He takes a 'random' decision at each intersection but is constrained as to the four directions he can take. Furthermore it does not matter how much time he takes deciding or walking.

This is a single discrete random variable.

 

A gaseous particle, on the other hand does not take decisions.
Its random walk come from being buffetted by other particles in a random fashion.
This random fashion occurs at random instants, imparting random momenta in random directions.

All of these three variables are fully continuous independent random variables.

[Duda Jarek]

Exactly,

GRW is perfect e.g. for human wandering through the web, indeed performing local randomly looking decisions.

MERW for electrons - having extremely complex EM&wave-based dynamics, expressing our limited knowledge through its entropy maximization, with Anderson-like localization property e.g. preventing semiconductor from being a conductor, like in below electron densities from STM (scanning tunneling microscope) from http://www.phy.bme.hu/~zarand/LokalizacioWeb/Yazdani.pdf

The big question is what to choose between, like for this molecular dynamics?

Practical difference is that only MERW has QM-like localization property - do we observe this kind of effects for molecules?

Like entropic boundary avoidance, e.g. for [0,1] range GRW/diffusion/chaos would predict nearly uniform rho=1 stationary distribution, while QM/MERW predicts rho~sin^2 distribution avoiding boundaries - do we observe it for molecules?

[dimreepr]

40 minutes ago, Duda Jarek said:

GRW is perfect e.g. for human wandering through the web, indeed performing local randomly looking decisions.

I think the point is, GRW is a random choice in a bounded enviroment; which becomes more bounded (and less random) with each subsequent decision.

[Duda Jarek]

It is also crucial that it is local random choice: based on possible single steps, having characteristic length like use of single step.

MERW can be seen as scale-free limit of GRW_k: using uniform (/Boltzmann) distribution of length k paths from given position:

GRW = GRW_1

MERW = lim_{k->infty} GRW_k