Skip to main content
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
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 ...
Yuval Peres's user avatar
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,615
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