Random Walk Distance | Emergent Gravity

Topology

▵

Drop topology.json or click to upload

Random Pairs

Walks per Pair

Max Steps per Walk

Initializing...

-

Mean Distance (min of 10 walks)

Distribution: Exponential with lambda = 1/mean

-

Successful Pairs

-

Median Distance

-

Std Deviation

-

Min Distance

-

Max Distance

-

Computation Time

The hitting time H(A,B) is the expected number of steps for a random walker starting at node A to first reach node B.

We approximate this by taking the minimum of multiple random walks, which gives a better estimate of the true graph distance.

D(A,B) = min(H₁, H₂, ..., H_k)

On large random graphs, the hitting time distribution follows an exponential distribution:

P(D = d) = lambda * e^-lambda*d

This emerges because each step has roughly equal probability of "finding" the target node, leading to a memoryless process.

Mean/Std ratio ~ 1.0 confirms exponential behavior.

For a graph with N nodes and average degree k, the mean hitting time scales as:

E[H] ~ O(N)

On our 110k node Voronoi lattice (k ~ 12), the mean distance is approximately 15,000 steps, or about 0.14N.

While the graph-theoretic shortest path (BFS) might be ~100-200 hops, the random walk "effective diameter" is much larger.

This reflects the diffusive nature of random walks - they explore locally before finding distant targets.

D_effective >> D_shortest