# Tagged Questions

**0**

votes

**1**answer

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

**10**

votes

**0**answers

194 views

### Mixing properties of random walks on graphs [migrated]

I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs.
One of the main ideas of the paper is that random walks on graphs can be used to find sets with small ...

**4**

votes

**2**answers

608 views

### Do Random Walks on the Hexagonal Lattice have a limit?

For every positive integer $n$, consider a regular hexagon $\mathrm{H}_n$ such that
the distance of each vertex from the center is $\frac{1}{\sqrt{n}}$. That in turn
induces a tiling of ...

**4**

votes

**0**answers

141 views

### Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice.
Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...

**4**

votes

**2**answers

193 views

### Methods to approximate the betweenness centrality on large networks

To calculate the between centrality wiki def:
$g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
of a node in a graph/network;$\sigma_{st}$ is the ...

**4**

votes

**2**answers

159 views

### Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:
...

**5**

votes

**1**answer

271 views

### Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...

**1**

vote

**2**answers

198 views

### Random walk on the hypercube

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...

**4**

votes

**1**answer

273 views

### Probabilities of a random walk exiting a set

Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...

**1**

vote

**1**answer

69 views

### Spanning subgaph with trivial Poisson boundaries

Assume $\Gamma$ is the Cayley graph of an amenable$^{*}$ group and that the simple random walk has non-trivial Poisson boundary$^{**}$. Is there a spanning connected subgraph $\Gamma'$ of some ...

**1**

vote

**1**answer

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

**12**

votes

**3**answers

457 views

### Estimate on currents in Cayley graphs

Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...

**4**

votes

**2**answers

272 views

### How does a quasi-isometry affect Poisson or Martin boundaries?

Take two graphs (of bounded valency) or manifolds (f bounded geometry) $G$ and $G'$. Assume there is a quasi-isometry $f:G \to G'$, and assume the Poisson or Martin boundary of $G$ is known, what may ...

**1**

vote

**1**answer

177 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)$ ...

**12**

votes

**5**answers

901 views

### Simple Random Walk on a Locally Finite Graph - when is it recurrent?

I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My ...

**2**

votes

**2**answers

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

**5**

votes

**0**answers

228 views

### Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...

**1**

vote

**2**answers

743 views

### Probability of first return to starting vertex in Random walk on regular finite graph

Hi, this is related to this earlier question.
Given Random walk on a regular graph $G=(V,E)$. The Random walk is simple so that transition probabilities are $1/\text{deg}(v_i)$, and time is in ...

**9**

votes

**1**answer

654 views

### Probability of return vs. probability of return in minimal number of steps

Consider a random walk on a connected graph $G=(V,E)$. That is, associate to each neighbouring nodes $a,b\in V\ $ transition probabilities $\mathbb{P}(a\rightarrow b), \mathbb{P}(b\rightarrow a) $ ...

**7**

votes

**1**answer

638 views

### Random walk on a simple finite network

Consider a graph $\Delta_N = \lgroup (x,y)\in\mathbb{Z}^2| x+y\leq N-1, x\geq 0,\ y\geq 0 \rgroup$ (set of edges is defined in a natural way): see here ).
Take a random walker that wonders around ...

**1**

vote

**1**answer

261 views

### Winding number bijection on graphs

Let $G=(V,E)$ be an isoradial graph. In other words the graph can be imbedded into the plane such that each face (plaquette) can be circumscribed a circle of radius 1 with the circle's center ...

**4**

votes

**0**answers

386 views

### Monotonic properties of harmonic functions on graphs

I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...