The random-walk tag has no usage guidance.

**1**

vote

**2**answers

185 views

### Speed and absence of non-constant bounded harmonic functions

For a (symmetric) random walks on countable groups generated by $\mu$, there is a "brute-force computation" argument of Avez (1974) that shows that if the entropy $h_\mu$ is trivial then there are no ...

**5**

votes

**1**answer

447 views

### Harmonic Crystal using Random Walk

Me and my advisor were looking for a specific proof of the disorder in $2d$ harmonic crystals. We could not find a paper or a textbook with it, so I thought trying my luck here.
Basically, it is a ...

**2**

votes

**1**answer

223 views

### Random walks with exponential decreasing steps

Let $g$ be the golden number (or another algebraic integer in $(0,1)$ that fullfills an equation with coefficients $\pm 1$). Consider the random walk on $\mathbb{R}$ starting with $0$ and walking ...

**2**

votes

**0**answers

68 views

### Controlling fluctuations in a Markov chain

For $N>0$, consider the Markov chain $x_n$ on $\{0,1/N,...,1\}$ that moves up by $1/N$ at rate $(c-x_n/2)N$ and down by $1/N$ at rate $(c+x_n/2)N$. As $N\rightarrow\infty$ sample paths approach ...

**1**

vote

**0**answers

35 views

### Is there an effective algorithm for finding “minimal discovery times” for large graphs?

Consider a large, probably sparse graph with Markovian random walkers on it.
Define the discovery time as the expected time to first reach a vertex by
random walk from a uniform start. Are there ...

**4**

votes

**1**answer

141 views

### hitting time of the first quadrant for a 2-d random walk

Suppose $(S_n)_{n=1}^{\infty}$ is a simple random walk in $\mathbb{R}^2$. Let $\tau_{(a,b)}$ be the hitting of the first quadrant when $S_0 = (a,b)$. Is there a way to compute or estimate the ...

**10**

votes

**3**answers

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

**2**

votes

**2**answers

253 views

### Distribution of a random walk on a directed line

Is there a closed formula for the distribution of $x_t$ in the following random process, describing a random walk on a directed line?
$x_0 = n$
$x_t$ is a uniformly random integer between 1 and ...

**10**

votes

**1**answer

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

**1**

vote

**1**answer

353 views

### Brownian motion of every point in the plane

Suppose every point in the plane undergoes brownian motion for a time t. What is the probability n particles ended up at 0? For n finite, countable or uncountable?
What proportion of the plane does ...

**4**

votes

**0**answers

230 views

### Why is the density function of a sum of many iid random variables (i.e., the Gaussian) self-dual?

In the usual proof of the central limit theorem via characteristic functions, we note that if $X_1, \dots, X_n$ are independent and identically distributed, with probability density function $f(x)$, ...

**1**

vote

**1**answer

116 views

### N random walkers that hit node v in a graph

Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...

**17**

votes

**1**answer

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

**7**

votes

**1**answer

227 views

### First Collision Time for k Random Walkers on a Torus

I consider $k$ random walkers on $\mathbb{Z}^{d}/n \mathbb{Z}^{d}$, the $d$-dimensional torus of side length $n$. More precisely, I will define a Markov chain $Z_{t} = (X_{t}[1], \ldots, X_{t}[k])$ ...

**5**

votes

**1**answer

455 views

### Stopping time of two dimensional random walk

Let $U_n=\sum_{i=1}^n X_i,V_n=\sum_{i=1}^n Y_i$, $n\geq 1$, be a two-dimensional random walk with i.i.d. increments $(X_n, Y_n)$, where $X_n, Y_n$ are discrete random variables with joint pmf ...

**6**

votes

**2**answers

222 views

### Random walk in a convex body or convex polytope

Let $\Delta$ be a convex body (i.e. a compact convex subset) or a convex polytope in
$\mathbb{R}^n$. Let $x$ be a point inside $\Delta$ and consider a (uniform) random walk starting at $x$ inside ...

**3**

votes

**1**answer

175 views

### Diameter of $n$-unit-vector closed scribble

Suppose one creates a random, closed, likely self-crossing polygon
from $n$ unit-length vectors arranged head-to-tail,
randomly oriented except for the requirement
that their sum is zero (so the ...

**2**

votes

**0**answers

108 views

### 1d random walk probability of previous n positions

I have the following question.
(May be it is very simple, but I cannot find the answer).
Suppose I have a 1d random walk on integer numbers with equal pobabilities of unit step in either direction ...

**9**

votes

**1**answer

261 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$, ...

**14**

votes

**2**answers

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

**11**

votes

**1**answer

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

**4**

votes

**2**answers

817 views

### Do Random Walks on the Hexagonal Lattice have a limit?

For every positive integer $n$, consider a regular hexagon $\mathrm{H}_n$ such that
the distance of each vertex from the center is $\frac{1}{\sqrt{n}}$. That in turn
induces a tiling of ...

**4**

votes

**0**answers

157 views

### Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice.
Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...

**7**

votes

**5**answers

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

**4**

votes

**1**answer

137 views

### Connection between degree of growth and return probabilities of random walks on Lie groups

Let $G$ be a finitely generated group of polynomial growth, let $\mu$ be a non-degenerate symmetric probability measure with finite support on $G$, and let $d$ be the degree of growth of $G$. ...

**6**

votes

**0**answers

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

**3**

votes

**2**answers

238 views

### Nonmonotonicity of expected distance of a random walk

What's the simplest example of a reversible random walk $X_n$ on an infinite vertex-transitive graph such that the expected distance from the origin is not increasing, i.e. there exists $n$ such that:
...

**9**

votes

**3**answers

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

**8**

votes

**2**answers

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

**5**

votes

**2**answers

602 views

### Random walk by simplex vertices

I apologize if this question is well-known, but I was unable to find it mentioned anywhere.
There exists a bug which moves around in $r$-space. The bug begins at the origin of this $r$-space. If the ...

**4**

votes

**0**answers

88 views

### Using Crump-Mode-Jagers processes to get logarithmic bound on a random tree height

I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I ...

**7**

votes

**0**answers

121 views

### Speed on recurrent graphs

Suppose that $G$ is a (locally finite) graph such that the simple random walk on $G$ is recurrent. Does this imply any upper bound on the speed $\mathbb{E}d(X_t,X_0)$ of such random walk?

**4**

votes

**1**answer

604 views

### Expectation of Maximum of Uniform Multinomial Distribution

Suppose we have a uniform multinomial distribution with $k$ buckets, i.e. we put $n$ items uniformly at random in $k$ buckets leading to $n_1, \dots, n_k$ items in each bucket respectively. Let $m = ...

**1**

vote

**2**answers

415 views

### Quadratic variation for discrete Martingale

Is there any analogue of continuous martingale quadratic variation for the discrete case? If so, are there any theorems which characterize simple random walk using quadratic variation - similar to ...

**8**

votes

**1**answer

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

**2**

votes

**1**answer

651 views

### Random walk in a circle

Suppose we have a circle of radius $R$ centered in the origin of a $x,y$ cartesian reference frame. A particle starting from the center of the circle is moving with a speed given by:
...

**0**

votes

**1**answer

92 views

### Joint law for number of visits in transient simple random walk

Consider a simple $1$-dimensional random walk $X_n$.
Let $p$ and $q$ (with $p+q=1$) be the probability of transitions from $n$ to $n+1$ and from $n$ to $n-1$ respectively, and suppose that $p>q$ ...

**4**

votes

**0**answers

76 views

### Estimates for simple random walks in groups of intermediate growth

I'm looking for references for the rate of escape and return probability for a group of intermediate growth.
Let $0<\alpha < 1$. If the volume growth is $\succeq \mathrm{exp}(n^\alpha)$, then ...

**5**

votes

**2**answers

397 views

### Methods to approximate the betweenness centrality on large networks

To calculate the between centrality wiki def:
$g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
of a node in a graph/network;$\sigma_{st}$ is the ...

**5**

votes

**1**answer

291 views

### Random walk with positive uniformly distributed steps

Let $U_1,U_2,\ldots$ be iid random variables distributed uniformly on $[0,1]$. I am interested in the random walk $X_i = \sum_{j \leq i} U_j$. In particular,
What is the expected number of points ...

**1**

vote

**0**answers

79 views

### Discretization model for Dirac equation in higher dimensions

I'm wondering if there are cases of discretization models (in lattices or graphs) that converge toward the non-linear Dirac equations? While there is a paper on the 2-d and 3-d cases ...

**4**

votes

**2**answers

293 views

### Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:
...

**6**

votes

**1**answer

397 views

### Random walk over a function

Let $\{X_n\}_{n\geq 0}$ be a random walk. Let us assume that $\mathbb{E}X_1 =0$ and $\mathbb{E}X_1^2=1$. Let also $\mathbb{E}\exp(c|X_1|)<+\infty$ for some $c>0$ and $X_1$ has a law with ...

**7**

votes

**1**answer

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

**8**

votes

**1**answer

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

**3**

votes

**1**answer

256 views

### Speed of random walks in groups

I've seen some estimates for the decay in $d$ of the probability a SRW makes a distance $d$ in time $n$, but is there any reference for the "speed" of a random walk in a group? I'm interested mostly ...

**6**

votes

**1**answer

324 views

### Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...

**17**

votes

**2**answers

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

**6**

votes

**1**answer

364 views

### The number of lattice paths below y=n/m x for gcd(m,n) = 1

The motivation of my question is the recent preprent of Armstrong, Rhoades and Williams http://arxiv.org/abs/1305.7286 on rational Catalan combinatorics.
An important starting point of this paper is ...

**12**

votes

**3**answers

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