The random-walk tag has no usage guidance.

**5**

votes

**0**answers

487 views

### Compute the expected value of the next step of a sorted random walk

Here's what I'm thinking about. If you have a random walk (move +1 or -1 at each step) of some fixed length, then if you're at the maximum of the walk, the next step you take is -1 with probability 1. ...

**2**

votes

**0**answers

274 views

### Cover time for a biased random walk on an 'N'-dimensional integer lattice

Imagine that I have a random walk on an $N$-dimensional integer lattice, $Z^N$, of finite dimensions, $(d_1, ..., d_N)$, where boundaries are fully reflecting and the walker is initialized at some ...

**10**

votes

**1**answer

570 views

### exactly simulating a random walk from infinity

In diffusion-limited aggregation on the square lattice, one lets a particle do "random walk from infinity" until it hits the current aggregate, at which point the site occupied by the particle is ...

**21**

votes

**5**answers

4k views

### Probability of a Random Walk crossing a straight line

Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the ...

**36**

votes

**1**answer

3k views

### Rolling a random walk on a sphere

A ball rolls down an inclined plane, encountering horizontal obstacles, at which it
rolls left/right with equal probability. There are regularly spaced staggered gaps that let the ball
roll down to ...

**1**

vote

**4**answers

1k views

### Will a random walk on [0, inf) tend to infinity? [closed]

Consider a random walk on [0, inf) where you start at 0. With probability p = 0.5, you increase by 1. With probability (1-p) = 0.5, you decrease by 1, but not below 0.
As time goes to infinity, will ...

**5**

votes

**2**answers

1k views

### Probability of return at step $n$ of a Random walk to its starting vertex

Hi,
given a discrete simple Random walk on a symmetric graph, what is known about the probability of the random walker to return to a starting site at step $n$? Specifically, I am interested in the ...

**10**

votes

**4**answers

2k views

### What is the cover time of a random walk on a cube?

I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the ...

**2**

votes

**2**answers

536 views

### Second stage of elliptic curve factorization via random walk/Pollard's rho in constant (or low) memory?

The second stage of elliptic curve factorization has the drawback of large memory usage.
Let $n=pq$, $E(\mathbb{Z}/n\mathbb{Z})$ is elliptic curve and $P$ point on $E(\mathbb{Z}/n\mathbb{Z})$.
On ...

**3**

votes

**2**answers

306 views

### Hausdorff dimension of non-recurrent walks

Preface: I am fairly new to the concept of Hausdorff dimension, so I don't know how interesting a question this is.
Identify walks on $\mathbb{Z}$ with infinite binary sequences (say $0$ means moving ...

**9**

votes

**1**answer

664 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

701 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

**1**answer

727 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

887 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

242 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

676 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

285 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

807 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

572 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

532 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

517 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

1k 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

410 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

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

**9**

votes

**5**answers

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

902 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

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

**23**

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

**10**

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

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