Random Walk on Random Directed Graphs

on YouTube ↗42m

" summary

Random walks on the directed configuration model with bounded degrees exhibit cutoff at time approximately log N divided by μ where μ is the average log out‑branching (picked by a uniform random edge), with a cut‑off window of order window = σ√(log N) (σ the variance of that log) and a Gaussian tail profile. The invariant law concentrates and is approximated in Wasserstein distance by a local recursive distributional solution (Mandelbrot‑cascade type) computed from fixed‑radius balls; starting from uniform‑on‑edges mixes in O(1) (simulations: N=3000 mix <10).

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 1:03Markov mixing and variation distance
3. 2:50Card shuffling cutoff
4. 6:45Cutoff in Markov chains
5. 11:33Motivation for directed walks
6. 16:26PageRank applications
7. 18:59Directed configuration model
8. 23:17Cutoff results for directed graphs
9. 27:20Critical window analysis
10. 30:18Initial conditions impact
11. 32:29Convergence from uniform
12. 34:18Local structure equilibrium
13. 36:12Stationary mass equations
14. 38:03Real-world network implications
15. 41:15Open problems and conjectures