Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
44
votes
1answer
4k 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 ...
36
votes
1answer
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, ...
33
votes
1answer
2k 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 ...
33
votes
4answers
1k views

How many random walk steps until the path self-intersects?

Take a random walk in the plane from the origin, each step of unit length in a uniformly random direction. Q. How many steps on average until the path self-intersects? My simulations suggest ~$8....
26
votes
6answers
20k 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 ...
24
votes
5answers
6k 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 ...
22
votes
4answers
5k 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 ...
22
votes
1answer
2k 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 in ...
21
votes
2answers
732 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 ...
18
votes
2answers
1k 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
4answers
798 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 ...
17
votes
1answer
581 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 ...
17
votes
1answer
2k 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 ...
16
votes
3answers
997 views

Does a random walk on a surface visit uniformly?

Let $S$ be a smooth compact closed surface embedded in $\mathbb{R}^3$ of genus $g$. Starting from a point $p$, define a random walk as taking discrete steps in a uniformly random direction, each step ...
16
votes
2answers
993 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 ...
16
votes
3answers
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 $...
15
votes
2answers
1k 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 ...
15
votes
1answer
247 views

Annihilating random walkers

Suppose there are several walkers moving randomly on $\mathbb{Z}^2$, each taking a $(\pm 1,\pm 1)$ step at each time unit. Whenever two walkers move to the same point, they annihilate one another. ...
14
votes
5answers
2k 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 ...
14
votes
1answer
1k 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
2answers
1k 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{...
14
votes
2answers
1k views

A random walk on an infinite graph is recurrent iff ...?

Q. Is there a master theorem that can be used to determine whether or not a simple random walk (choose a random neighboring vertex as the next step) on a given infinite graph leads to ...
14
votes
2answers
2k 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 (...
14
votes
2answers
1k 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
0answers
232 views

A symmetry of lattice paths

The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity. ...
14
votes
0answers
552 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 ...
13
votes
2answers
760 views

A comprehensive list of random walk inequalities?

I am interested in finding a comprehensive list of all noticeable random walk inequalities. ie. $S_n = \sum_{k\leq n} X_i$ for i.i.d symmetric $X_i$ I can only seem to find books/papers that list ...
13
votes
2answers
848 views

How long for Brownian motion to "fill-out" a torus in d-dimensions?

I've been taken by the concise result1 that (roughly!), on a $2$-dimensional torus $\mathbb{T}^2$, the time it takes to visit nearly every point (within $\epsilon$, as $\epsilon \to 0$) is: $\frac{2}{\...
13
votes
1answer
857 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$, ...
13
votes
1answer
996 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 ...
13
votes
1answer
2k views

Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4

Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of $...
13
votes
1answer
512 views

Identity involving the probability that a random walk stays below a curve

I'm looking for a direct proof of the following identity: Let $W_n$ be a simple random walk with $W_0=0$. For all $x>0$ we have $$ \lim _{N\to \infty} \sqrt{N} \cdot \mathbb P \Big( \forall n \le ...
13
votes
1answer
723 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 ...
12
votes
1answer
660 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 [...
12
votes
3answers
619 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
2answers
354 views

Random Walk on Pentagonal Tiling

I’ve recently been looking at closed walks on tilings of the plane in which the “player” can move from one tile to any of its edge-adjacent neighbors. In particular, I’m trying to find asymptotic ...
12
votes
1answer
3k 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 ...
12
votes
3answers
528 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 ...
11
votes
4answers
3k 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
3answers
577 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 ...
11
votes
2answers
1k views

The mean square distance of a random walk from the origin

I'm wondering whether the following type of problem is a standard one that has been studied by probabilists. The particular case needed (as a lemma that would help with a Polymath project) isn't quite ...
11
votes
2answers
831 views

Is there a differentiable random walk?

Is there a random walk which is differentiable or smooth? Like brownian motion except smoothed out on small distances. I was wondering if there is a "natural" or "canonical" analogue of brownian ...
11
votes
1answer
377 views

Growing a chain of unit-area triangles: Fills the plane?

Define a process to start with a unit-area equilateral triangle, and at each step glue on another unit-area triangle.                     $50$ ...
11
votes
3answers
994 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 ...
11
votes
1answer
2k views

Biased random Fibonacci sequences

I have recently been toying (very superficially) with the random Fibonacci sequence, i.e., defined by $F_0=1=F_1=1$ and $$ F_{n} = F_{n-1} + \varepsilon_n F_{n-2} $$ where $(\varepsilon_n)_{n\geq 2}$ ...
11
votes
1answer
567 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 ...
10
votes
3answers
729 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
3answers
1k views

Random Walks on high dimensional spaces

I've read on a paper that, in the two dimensional case, if you start from the origin and take steps of length one in arbitrary directions (uniformely on the unit sphere $S^1$, not left-right-up-down), ...
10
votes
5answers
2k 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 ...
10
votes
1answer
790 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 ...

1
2 3 4 5
9