A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.
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, ...


7

I'm not sure if I'm interpreting your question correctly, but it sounds to me that you're asking not about simulating self-avoiding random walks, but about enumerating self-avoiding random walks. I say this because you talk about exponentiating an adjacency matrix, which will give you a (weighted) enumeration of random walks. I'm not sure if there is much ...


5

I think only knowing the graph is an expander does not fix the value you are asking. If you are doing random walk naively then when the graph has bounded degree there is constant probability that the walk will reach the same vertex after just 2 steps, and therefore the expected number of steps is constant. I guess you want to exclude that case by saying the ...


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


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

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