All Questions
12 questions
1
vote
0
answers
41
views
Asymptotic mixing time and Euclidean probability distance for path graphs
We are given a simple path graph $P(V,E)$ with vertex set $V$ and edge set $E$, having $n=|V|$ nodes. Given an initial distribution $\mathbf{\mu}$ over $V$, let $d_t(\mathbf{\mu},\pi)$ be defined as $\...
- 1,677
4
votes
1
answer
518
views
Probability that two walkers will meet on a graph
Consider two independent continuous random walks on a graph $G$ with adjacency matrix $A$. I am interested in the probability that the two walkers will ever meet.
When the graph is a $k$-regular ...
- 117
6
votes
1
answer
361
views
Random walks on infinite directed regular graphs
Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).
Assume that $\Gamma$ is bi-regular, that is ...
- 26k
2
votes
1
answer
232
views
If the diameter of a bounded degree, directed graph is polynomial in the degree of the graph, is the mixing time also polynomial?
Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting ...
- 2,185
2
votes
0
answers
114
views
Hyperbolic decay of transition probability for random walks on infinite graphs
Consider a nearest-neighbor (or say simple) random walk on a connected graph $G$ with infinite vertices where each vertex has a finite degree. Let $P^n_{o,o}$ be the probability of the random walk ...
- 87
3
votes
0
answers
151
views
Sequential generation of any random graph
The high-level question is: can we generate any random graph with size $d$ using a Markov chain?
For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
- 1,127
1
vote
1
answer
242
views
Two types of random walkers on square lattice
Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index $1$...
user82424
1
vote
0
answers
46
views
Is there an effective algorithm for finding "minimal discovery times" for large graphs?
Consider a large, probably sparse graph with Markovian random walkers on it.
Define the discovery time as the expected time to first reach a vertex by
random walk from a uniform start. Are there ...
- 355
1
vote
1
answer
128
views
N random walkers that hit node v in a graph
Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...
- 111
1
vote
1
answer
951
views
Stationary distribution for directed graph
I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
- 13
1
vote
1
answer
249
views
Distributions induced by (weighted) random walks on the integer lattice
Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ ...
- 3,059
2
votes
2
answers
1k
views
probability distribution of hitting nodes on a finite graph random walk
Consider a finite, undirected, scale-free graph $\{G}$, with uniform edge weights. We define a truncated random walk on $\{G}$ as a random walk that continues for exactly $\{k}$ steps. For an ...
- 23