The random-walk tag has no usage guidance.

**37**

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

**31**

votes

**1**answer

1k views

### Prime Number Races in 2 Dimensions

Is the mapping $$f: \ \mathbb{N} \rightarrow \mathbb{Z}[i], \ \ \ n \ \mapsto
\sum_{2 < p \leq n \ {\rm prime}} e^{\frac{p-1}{4} \pi i}$$ surjective?
In 1999, when I was an undergraduate student, ...

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

**22**

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

**21**

votes

**5**answers

3k views

### A random walk with uniformly distributed steps

The following problem has bothered me for a long time.
Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly in the ...

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

**20**

votes

**0**answers

608 views

### Time for Langton's ant to cover a “square” torus

Langton's ant is a cellular automaton running as follows:
Squares on a plane are colored variously either black or white. We
arbitrarily identify one square as the "ant". The ant can travel ...

**18**

votes

**2**answers

873 views

### Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and “Reflective” Boundary at Origin

A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...

**17**

votes

**1**answer

512 views

### Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...

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

**15**

votes

**2**answers

840 views

### Randomly walking a leashed dog

Let a human $h(t)$ random walk on $\mathbb{Z}^2$ by taking a unit-length step at every
time step $t$. A dog $d(t)$ on a leash of length $\lambda$ follows $h(t)$, also
taking a unit-length step at ...

**14**

votes

**1**answer

881 views

### In how many steps a random walk visits all the elements of a finite group, with a probability 1/2?

This question is a variation of the return to the origin problem.
Let $G$ be the finite group $\mathbb{Z}/n \times \mathbb{Z}/n$ and let the random transformation $T: G \to G$ such that $T(a,b) = (...

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

**14**

votes

**2**answers

899 views

### What is the maximum diameter of $N$ steps of a random walk?

Since probability is quite far away from my daily buisiness, please forgive me if my use of terminology is wrong or the question is too trivial. However, I was not able to find the right keyword to ...

**14**

votes

**1**answer

711 views

### Distribution of maximum of random walk conditioned to stay positive

I have an $n$ step random walk which starts at zero $X_0 = 0 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$, but the walk is conditioned on the hypothesis that it ...

**13**

votes

**5**answers

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

**12**

votes

**3**answers

496 views

### An “inchworm-like” random walk on an integer interval

Imagine I place $k$ stones on an infinite one-dimensional integer interval $Z$ s.t. no stone is more than some distance $d$ from any other stone. For example, if $d=1$ and $k = 5$, we might place the ...

**12**

votes

**3**answers

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

**12**

votes

**0**answers

258 views

### Self-avoiding random walks that always turn

I am wondering if the statistics of self-avoiding random lattice-walks
on $\mathbb{Z}^2$
that turn left or right at each step (i.e., they cannot continue the
direction of the preceding step) have been ...

**11**

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

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

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

**11**

votes

**2**answers

927 views

### Random walks on Coxeter groups

Let $G_N$ be the group generated by elements $a_1,\ldots,a_N$ subject to the relations $a_i^2=1$ and $(a_ia_j)^3=1$. The growth function of $G_N$ is then
$$f_N(t)=\frac{1+2t+2t^2+t^3}{1-Mt-Mt^2+\frac{...

**11**

votes

**1**answer

720 views

### How far can a particle travel from its origin if it exhibits self-avoiding Brownian motion in two-dimensions?

Let's say I have a point-like Brownian particle undergoing two-dimensional diffusion on an infinite plane with the caveat is that the particle can never return to a coordinate that it previously ...

**11**

votes

**1**answer

380 views

### Wander distance of self-avoiding walk that backs out of culs-de-sac

Suppose a self-avoiding walk on $\mathbb{Z}^2$, with random steps each one unit long,
backs out of culs-de-sac, but retaining the lattice points on which it stepped
marked as unavailable for future ...

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

**10**

votes

**3**answers

470 views

### Hitting time for two out of three random walk particles

I'm imagining a simple random walk on $\mathbb{Z}$ with three independent particles (maybe add laziness so they don't jump over each other). Suppose the particles are initially placed at, say, $-10$, $...

**10**

votes

**3**answers

662 views

### Square filling self avoiding walk

I want to create an algorithm that fills a square grid with a random Hamiltonian path starting at a particular point. See this example.
One approach is to try a free direction as a next step, and ...

**10**

votes

**1**answer

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

**10**

votes

**1**answer

358 views

### Elephant populations (and Dyck words)

Hello,
I'm relatively new to this forum so apologies if I have tagged my
question incorrectly.
I have been in contact with a wildlife biologist recently concerning
counting elephant populations and ...

**10**

votes

**2**answers

1k views

### Markov chains: invariant measures and explosion

The following seems like such an elementary question, but I didn't get anywhere with it.
Suppose you are considering a Markov chain in continuous time which is transient and has an invariant measure (...

**10**

votes

**1**answer

295 views

### Trapping a particle

A particle starts a brownian walk in the middle of a long tunnel in the plane, at one end of the tunnel is a region Y of given area A.
Does the shape of region Y affect average time for the particle ...

**9**

votes

**1**answer

361 views

### Lattice random walk under gravity

Suppose a random walk on $\mathbb{Z}^2$ takes a step left or right with
probability $\frac{1}{4}$, but up with probability $\frac{1}{2} p$
and down with probability $\frac{1}{2} (1-p)$, where $p \in [...

**9**

votes

**5**answers

996 views

### Combinatorial\Probabilistic Proof of Stirling's Approximation

Stirling's approximation is the following well-known asymptotic result:
$$n! \approx \left(\frac{n}{e}\right)^n \sqrt{2 \pi n}$$
This result has several analytical proofs, for example via Laplace's ...

**9**

votes

**1**answer

1k views

### Pólya's Random Walk Constants at infinity

Let be the probability that a random walk on a d-D lattice returns to the origin. In 1921, Pólya proved that $p(1)=p(2)=1$
but $p(d)<1$ for $d>2$.
http://mathworld.wolfram.com/...

**9**

votes

**2**answers

353 views

### Adaptive version of the Azuma–Hoeffding inequality

The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition:
$$|X_k - X_{k-1}| \leq c_k$$
Then:
$$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 ...

**9**

votes

**1**answer

283 views

### Random walk on a Penrose tiling

Pólya proved that a random walk on $\mathbb{Z}^2$ almost surely returns to the
origin, or, equivalently, returns to the origin infinitely often.
It was subsequently established that in $\mathbb{Z}^3$, ...

**9**

votes

**2**answers

442 views

### Limit shape for fixed-perimeter lattice polygons

Let $P$ be a simple polygon defined by $n$ unit-length segments
connecting lattice points of $\mathbb{Z}^2$.
I have two operations that preserve the perimeter of $P$.
The first is the "pop" of a ...

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

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

**8**

votes

**2**answers

275 views

### Distribution of $\max_{n \ge 0} S_n$, random walk

Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...

**8**

votes

**2**answers

347 views

### Area covered by Brownian motion of 2D disc

I would like to know the expected value for the area covered by a disc of radius $R$ whose center undergoes Brownian motion (diffusion).
Specifically, let $\mathbf{X}_t$ represent a two-dimensional ...

**8**

votes

**2**answers

557 views

### A discrete random walk that avoids previously visited vertices for an exponentially distributed time interval

Imagine a discrete random walk on an infinite one-dimensional lattice where, for every unit interval of time, $(t_1, t_2, ...)$, the walker takes a step with uniform probability to its left or right. ...

**8**

votes

**1**answer

442 views

### Width of a random convex polygon

Consider a planar (2D) random walk comprised of N steps.
Consider the minimum convex polygon enclosing the N points visited by the random walker.
Assume the definition of the width of a convex polygon ...

**8**

votes

**1**answer

359 views

### Twisted random walks

Suppose the points of two random walks in $\mathbb{R}^2$ are given the
step number (or time) as a third coordinate, so that they become paths in $\mathbb{R}^3$.
Here are several pairs of walks of $n=...

**8**

votes

**1**answer

1k views

### random walk and Brownian motion on Riemannian manifold

As we know, the random walk on $\mathbb{Z}/n$ will converge(in some sense) to the Brownian motion on $\mathbb{R}$ when $n\to\infty$. I would like to know is there some higher dimensional analogy ...

**8**

votes

**1**answer

325 views

### Mixing time of unitary Brownian motion

Let $B_t$ be the unitary Brownian motion, i.e. Brownian motion on the unitary group $U(N)$. What is known about the mixing time of $B_t$, that is, how fast does the measure $B_t(\delta_{\{Id\}})$ ...

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

**8**

votes

**1**answer

135 views

### Finite-index iff positive density?

Let $G$ be a finitely generated group and $S$ a symmetric generating set. Define density (lower density, say) with respect to the sequence of balls $S^n$.
Is it true that a subgroup of $G$ has ...

**8**

votes

**0**answers

165 views

### How much do the classes of geodesic metrics and Green metrics on a Gromov hyperbolic group differ?

Background
Let $G$ be a Gromov hyperbolic group. If $G$ acts properly discontinuously and cocompactly on a proper geodesic metric space $X$, then any bijective identification of $G$ with its orbit ...