# Tag Info

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, ...
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 (...

### 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 ...

### 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 ...
Accepted

### Effect of self loops on mixing time?

Your question is essentially covered by Cor 9.5 in  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 ...
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 ...
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 ...
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\}...
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 ...

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