Skip to main content

# Tag Info

## Hot answers tagged random-walks

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 ...
• 451
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,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 ...
• 325

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