The tag has no usage guidance.

learn more… | top users | synonyms

36
votes
1answer
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 ...
30
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, ...
24
votes
1answer
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 ...
21
votes
5answers
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
2answers
677 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
5answers
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 ...
19
votes
0answers
563 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 ...
17
votes
1answer
508 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
2answers
842 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, ...
15
votes
4answers
635 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 ...
14
votes
1answer
827 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
824 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
2answers
746 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 ...
13
votes
5answers
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
3answers
487 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
3answers
479 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
2answers
806 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 ...
11
votes
4answers
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
2answers
906 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 ...
11
votes
1answer
690 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
1answer
352 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
1answer
577 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 ...
11
votes
1answer
467 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 ...
10
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 ...
10
votes
3answers
599 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
1answer
577 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
1answer
355 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
2answers
959 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
1answer
290 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 ...
10
votes
0answers
186 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 ...
9
votes
3answers
451 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$, ...
9
votes
5answers
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 ...
9
votes
1answer
338 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
5answers
885 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
1answer
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$. ...
9
votes
2answers
312 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
1answer
260 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
2answers
431 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
1answer
666 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
3answers
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
2answers
313 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
2answers
527 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
1answer
397 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 ...
8
votes
1answer
951 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
1answer
300 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
2answers
524 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
0answers
959 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 ...
7
votes
5answers
769 views

Reference requested: Random walk on groups

I am looking for a good reference to learn about random walks on groups (either finite groups or Lie groups). Ideally, I would like a reference for general theory of random walks on groups that is ...
7
votes
1answer
713 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 ...
7
votes
2answers
254 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 ...