Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
45 votes
1 answer
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 ...
Joseph O'Rourke's user avatar
39 votes
1 answer
2k 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, ...
Stefan Kohl's user avatar
  • 19.5k
35 votes
1 answer
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 ...
Gjergji Zaimi's user avatar
33 votes
4 answers
2k 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....
Joseph O'Rourke's user avatar
27 votes
7 answers
28k 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 ...
Joseph O'Rourke's user avatar
27 votes
5 answers
7k 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 ...
TMM's user avatar
  • 713
23 votes
2 answers
905 views

Random permutations of Z_n

In "The maximum number of Hamiltonian paths in tournaments" by Noga Alon, the author states the following without proof (equation 3.1): "Consider a random permutation $\pi$ of $\mathbb{...
Jeremy H's user avatar
  • 375
23 votes
1 answer
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 ...
Sebastien Palcoux's user avatar
21 votes
4 answers
6k 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 ...
Lwins's user avatar
  • 1,531
19 votes
0 answers
2k views

xkcd's "Unsolved Math Problems", straight lines in random walk patterns

STEM student's favourite source of amusement posted a comic titled "Unsolved Math Problems" one of which looks like something that could actually be tackled. If I walk randomly on a grid, ...
Radost's user avatar
  • 309
18 votes
2 answers
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, ...
Nick Broderick's user avatar
17 votes
4 answers
818 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 ...
Joseph O'Rourke's user avatar
17 votes
1 answer
613 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 ...
Joseph O'Rourke's user avatar
17 votes
1 answer
3k 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 ...
Jason Cantarella's user avatar
16 votes
3 answers
1k 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 ...
Joseph O'Rourke's user avatar
16 votes
2 answers
1k 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 ...
Joseph O'Rourke's user avatar
16 votes
3 answers
2k 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 $...
Joseph O'Rourke's user avatar
16 votes
0 answers
819 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 ...
Joseph O'Rourke's user avatar
15 votes
1 answer
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) = (...
Sebastien Palcoux's user avatar
15 votes
1 answer
1k 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$, ...
Joseph O'Rourke's user avatar
15 votes
2 answers
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 ...
James Propp's user avatar
  • 19.4k
15 votes
1 answer
301 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. ...
Joseph O'Rourke's user avatar
14 votes
5 answers
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 ...
David White's user avatar
  • 29.4k
14 votes
2 answers
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{...
Richard's user avatar
  • 1,363
14 votes
2 answers
2k 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 ...
Joseph O'Rourke's user avatar
14 votes
1 answer
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 $...
Mike Spivey's user avatar
  • 3,253
14 votes
2 answers
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 (...
Nathanael Berestycki's user avatar
14 votes
2 answers
2k 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 ...
Dirk's user avatar
  • 12.3k
14 votes
0 answers
264 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. ...
Robin Houston's user avatar
13 votes
2 answers
1k 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 ...
Xiaomi's user avatar
  • 231
13 votes
2 answers
1k views

Optimal search puzzle

Consider the following puzzle: On the integer line from 1 to $t$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $t$, and subtract 1. What is the optimal ...
jackisquizzical's user avatar
13 votes
2 answers
1k 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}{\...
Joseph O'Rourke's user avatar
13 votes
1 answer
1k 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 ...
Rob Grey's user avatar
  • 599
13 votes
1 answer
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 ...
shu's user avatar
  • 1,091
13 votes
1 answer
686 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 ...
Dor's user avatar
  • 723
13 votes
1 answer
764 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 ...
Joseph O'Rourke's user avatar
12 votes
1 answer
772 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 [...
Joseph O'Rourke's user avatar
12 votes
3 answers
653 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 ...
AmberWave's user avatar
  • 121
12 votes
2 answers
438 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 ...
Franklin Pezzuti Dyer's user avatar
12 votes
1 answer
730 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 ...
Joseph O'Rourke's user avatar
12 votes
3 answers
544 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 ...
ARG's user avatar
  • 4,342
11 votes
4 answers
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 ...
zzzbbx's user avatar
  • 241
11 votes
3 answers
840 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$, $...
Eric Foxall's user avatar
11 votes
3 answers
650 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 ...
Joseph O'Rourke's user avatar
11 votes
2 answers
2k 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 ...
gowers's user avatar
  • 28.7k
11 votes
2 answers
1k 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 ...
user114084's user avatar
11 votes
1 answer
389 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$ ...
Joseph O'Rourke's user avatar
11 votes
3 answers
1k 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 ...
Prutser's user avatar
  • 221
11 votes
1 answer
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}$ ...
Clement C.'s user avatar
  • 1,342
11 votes
1 answer
1k views

Smooth functions that resemble random walks

If the Riemann hypothesis holds, then the Mertens function $M(n)\equiv\sum_{x\leq n} \mu(n)$ behaves much like a 1D random walk. This includes the statements that $M(n)$ changes sign infinitely often ...
Curt von Keyserlingk's user avatar

1
2 3 4 5
11