11 votes

Random walk and mean hitting time in a simple undirected graph

I have decided to ask David Wilson himself, soon thereafter got a reply: For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the barbell graph, ...
arekolek's user avatar
  • 311
9 votes

Graph that maximizes minimum hitting time?

It is well known that a barbell graph (two cliques of size $n/3$ connected by a path of length $n/3$) has average hitting time $\Omega(n^3)$, but I believe the same applies to minimum hitting time (...
David Eppstein's user avatar
5 votes

Random Cerny Conjecture

I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any ...
domotorp's user avatar
  • 14k
3 votes

Random walk and mean hitting time in a simple undirected graph

In a recent paper, we found an mn upper bound (no big O) on the expected number of "cycles popped" by Wilson's algorithm and it is tight up to constants. It doesn't directly answer the question of ...
Heng Guo's user avatar
  • 375
3 votes

Effect of self loops on mixing time?

Your question is essentially covered by Cor 9.5 in [1] which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is ...
Yuval Peres's user avatar
3 votes

Probability of two vertices being connected by some path in a random directed graph

Consider a BFS exploration process, which proceeds in $k$ stages. Put $V_0 = \{u\}$. Given $V_0,\ldots,V_i$, explore all edges from $V_i$ to $V \setminus \bigcup_{j=0}^i V_j$ (where $V$ is the set of ...
Yuval Filmus's user avatar
  • 14.2k
1 vote

Entries of the Inverse Laplacian

I originally wanted to pose the question, but then I started investigating and found a few very helpful interpretation that haven't been collected anywhere (to my knowledge). Hence, I will write my ...
Zuza's user avatar
  • 141
1 vote

Find an approximate argmax using only approximate max queries

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}...
usul's user avatar
  • 7,525
1 vote

Applications of Quantum Walks?

Quantum statistics are also recreated in Maximal Entropy Random Walk, which has lots of known applications: "MERW is used in various fields of science. A direct application is choosing probabilities ...
Jarek Duda's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible