All Questions

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

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

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

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