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


8

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


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


4

this ref covers it. In sections 5 & 6 we use the elliptic integral to express the probability, less than one, that certain biased random walks return to the origin. The probability of a return to the origin for these walks can then be computed accurately and easily using Gauss' arithmetic-geometric mean (AGM) method to evaluate the elliptic integral. ...


4

from Q&A with you in the comments you seem to be interested in studying something defined as the stack distance in this set of slides, On the mathematical modelling of caches define the stack distance of a reference to be the number of unique block addresses between the current reference and the previous reference to the same block number. it has ...


4

A comment: I recently attended a talk by Bruce Reed with the title Catching a Drunk Miscreant, which was joint work with Natasha Komorov and Peter Winkler. If you can get a hold of the results from this work, maybe that might help you in some direction. In general, they prove an upper bound on the number of steps a cop need in a general graph to be able ...


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

This isn't really a proper answer to your question, but is a bit too long for a comment. The quantity you are after will vary from graph to graph, and will depend on the initial site of the walker. The expected number of distinct intermediate nodes will depend strongly on clustering within the graph, and I would expect the expected number of distinct ...


2

Colin Cooper and Alan Frieze have a set of results in the context of random digraphs that might be of interest. They study the properties of a simple random walk on the random directed graph $D_{n,p}$ when $np=d \log n, d>1$. They have proved that: For $d > 1$, whp the cover time of $D_{n,p}$ is asymptotic to $d \log (d/(d-1)) n \log n$. If $d=d(n) \...


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