# Tag Info

22

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls. First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ queries. Then, start from the entrance and walk $n+1$ steps to get to a node $X$ of distance $n+1$ from the entrance. We will try to reach the exit from this node....

11

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, which consists of two cliques of size $n/3$ connected by a path of length $n/3$. I don’t know what the worst constant is. The [Brightwell-Winkler] paper looks ...

9

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 (for uniform or stationary distribution). Whatever vertex you choose as the one that you think is easiest to hit, you have constant probability of starting in the ...

9

With the exception of cryptography applications like Shor's algorithm and quantum key distribution, I think engineering 'killer-apps' are not the norm for quantum computing, and nobody expects them to be. As such, quantum walks are a natural generalization of random walks and thus worth studying in their own right. However, to avoid side-stepping any longer, ...

5

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 pair of states. An exponential lower bound on $f$ can be given as follows. Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that ...

4

Roughly speaking, the mixing time is the worst-case hitting time of the half the vertices. Cover time is a stopping time when ALL subsets of vertices are hit. In other words, it is always larger than the the mixing time. Thus is your example one cannot have mixing time $n^{1000}$ and cover time $n^2$. Making this intuition precise requires a bit of ...

3

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 Wilson's algorithms' running time as the average size of popped cycles does not seem obvious. On the other hand, I don't have enough "reputation" to leave a ...

3

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 all vertices), and set $V_{i+1}$ to consist of all vertices reached in this fashion; their number has a binomial distribution which can easily be calculated. ...

3

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 equivalent (up to constants) to the mixing time of the lazy walk on $G_1$. [1] Peres, Yuval, and Perla Sousi. "Mixing times are hitting times of large ...

1

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\}$. Consider drawing the input by picking a permutation of these values uniformly at random. The idea should be that if we fix the indices of all values except ...

1

You can make a state machine from this as follows. Let the set of points generated be $V$. Add extra dummy start node $s$. Add edges $(s, v)$ for all $v \in V$. And add edge from $(u, v)$ where $u, v \in V$ are nearest neighbors. Assuming points to visit are chosen uniformly assign probability $1/|V|$ to edges $(s,v)$ and probability of \$1/\text{...

1

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 to maximize transmission rate through a constrained channel, analogously to Fibonacci coding. Its properties also made it useful for example in analysis of ...

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