11
votes
Accepted
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, ...
- 311
9
votes
Accepted
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 (...
- 50.8k
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 ...
- 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 ...
- 375
3
votes
Accepted
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 ...
- 441
3
votes
Accepted
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 ...
- 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 ...
- 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\}...
- 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 ...
- 327
Only top scored, non community-wiki answers of a minimum length are eligible