# Tagged Questions

The random-walk tag has no usage guidance.

**9**

votes

**1**answer

671 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

740 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

264 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

**1**answer

770 views

### A random walk on natural numbers

We are taking a random walk on the set of natural numbers. If we are at $M$, then with probability 1/4, we stay at $M$, with probability 5/12 we move to some random number less than or equal to $M/2$, ...

**3**

votes

**1**answer

950 views

### Intersection Probabilities for Random Walk in d>2

I'd like to get asymptotics on the probability that n independent random walks coalesce. Start with n independent walks. As soon as two walks intersect they become one walk and continue evolving as ...

**3**

votes

**1**answer

251 views

### Self Avoiding Walk Pair Correlation

Let $\gamma(i)$ be a self avoiding walk (SAW) on a 2D lattice $L$ (a square lattice for example) starting at a predefined origin ( $\gamma(0)=(0,0)$ ) and having length $n:=\ell(\gamma)$. Furthermore, ...

**21**

votes

**2**answers

683 views

### Random permutations of Z_n

In http://www.springerlink.com/content/y19u81675243r237/fulltext.pdf, the author states the following without proof (equation 3.1):
"Consider a random permutation $\pi$ of $\mathbb{Z}_n$. What is the ...

**2**

votes

**0**answers

288 views

### Self-avoiding Walk with next-nearest neighbors

Background
I study polymer physics and am doing experiments testing the model outlined in this paper. Basically, the polymers fall into an integer number of pits, and we create a partition function ...

**3**

votes

**1**answer

864 views

### Self Avoiding Walk Enumerations

Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic ...

**11**

votes

**1**answer

590 views

### Perimeters of random-walk polygons

I have a random walk on $\mathbb{Z}^2$ that takes a step
with equal probability in the three directions that avoid
retracing the previous step.
The walk proceeds until it returns to a lattice point
...

**6**

votes

**2**answers

544 views

### Optimally directing switches for a random walk

If you are sometimes called upon directing a random walk in a directed graph, how should you direct it so as to maximize the probability it goes where you want?
Formal statement
More specifically, ...

**8**

votes

**2**answers

529 views

### Random walks on graphs: Cover time and blanket time

Winkler and Zuckerman conjectured that the blanket time is within a constant factor of the cover time. The conjecture was recently proved. The cover time $C$ is the expectation of the first time $t$ ...

**0**

votes

**2**answers

2k views

### Two dimensional brownian motion first passage time

Hello,
I am looking for information on how to solve/compute first passage time for two dimensional Brownian motion.
any papers, references, books or web links for study will be helpful.
thanks
...

**4**

votes

**0**answers

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

**15**

votes

**4**answers

638 views

### Sweep-segment bot: Will this random walk sweep the plane?

This model is inspired by the random behavior of the
Roomba sweeping robot.
Let a unit segment $ab$ in the plane be placed
initially with $a=(0,0)$ and $b=(1,0)$.
The segment is first rotated a ...

**11**

votes

**5**answers

8k views

### When do 3D random walks return to their origin?

The probability of a random walk returning to its origin is 1 in two dimensions (2D) but only 34% in three dimensions: This is Pólya's theorem. I have learned that in 2D the condition of returning to ...

**0**

votes

**1**answer

936 views

### Random walk question on 2D grid, probability of vertical line vs horizontal line hit

Hi,
I have a problem
(1) where I need to compute the ratio of probabilities of hitting and stopping at a positive vertical barrier x vs hitting and stopping at a negative horizontal barrier y ...

**6**

votes

**2**answers

883 views

### Expectation of first positive value in random walk

Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in
$\lbrace -1, \frac{1-p}{p} \...

**8**

votes

**3**answers

1k views

### How to characterize a Self-avoiding path.

I cannot find any answer to that apparently simple problem :
On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}.
Is there a rule ...

**24**

votes

**1**answer

1k views

### Random walk inside a random walk inside…

Let $G=(V,E)$ be a graph and consider a random walk on it. Let $G'=(V',E')$ be a subgraph consisting of the vertices and edges that are visited by the random walk.
Question 0: Is there a standard ...

**11**

votes

**3**answers

1k views

### A random walk on random lines

I am wondering if this random walk remains finite with positive probability.
Start with three lines $A,B,C$ that are extensions of an equilateral triangle.
Let $p_0$ be one corner. Generate a line $...

**14**

votes

**2**answers

767 views

### self-avoidance time of random walk

How many steps on average does a simple random walk in the plane take before it visits a vertex it's visited before?
If an exact formula does not exist (as seems likely), then I'm interested in good ...