Non-backtracking vs. simple random walk

The problem asks whether lazy non-backtracking random walk always mixes faster than lazy simple random walk. No source identifies a proof or counterexample for this exact universal comparison.

Known results

• A 2006 paper proves that on connected, non-bipartite, $d$-regular graphs with $d=o(n)$, non-backtracking mixing is asymptotically at least as fast as simple random-walk mixing.
• The same work shows the improvement ratio can approach $2(d-1)/d$.
• For dense graphs with $d=\Theta(n)$, including $K_n$, ordinary simple random walk can be faster, so the analogous non-lazy universal claim fails.
• For random regular graphs, a 2015 paper records that simple random walk takes a factor $d/(d-2)$ longer than non-backtracking walk to mix.

Announced solution noted in 2015

A 2015 paper says that a solution to a related non-regular-graph comparison problem had been announced during finalization, but the retrieved material does not identify the solution or show that it addresses the exact lazy universal statement. No later retrieved source supplies verification, a counterexample, or a correction.

Current status (as of August 2026): The exact lazy universal comparison remains open in the retrieved record; only partial results and a non-lazy dense-graph obstruction are documented.