The random-walk tag has no usage guidance.

**7**

votes

**1**answer

221 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])$ ...

**4**

votes

**0**answers

380 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

215 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

174 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

98 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

252 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

818 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

342 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

796 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

156 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

710 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

135 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

142 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

232 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

436 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

296 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

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

**3**

votes

**0**answers

78 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

579 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

372 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

354 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

626 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

89 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

74 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

370 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

275 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

76 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

273 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

392 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

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

**7**

votes

**1**answer

859 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

309 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

833 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

351 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

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

**0**

votes

**1**answer

308 views

### Random walk on the hypercube

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...

**1**

vote

**1**answer

228 views

### Fundamental inequality of entropy in random walks

I'm looking for a reference for an inequality related to the "fundamental inequality" about entropy and rate of escape of random walks (on the Cayley graph of a group). Namely,
$\textbf{Question}$: ...

**4**

votes

**1**answer

404 views

### Probabilities of a random walk exiting a set

Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...

**5**

votes

**1**answer

250 views

### Memory of Uniformly Random Dyck Paths

Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have ...

**2**

votes

**1**answer

776 views

### Hitting time probability in a Random Walk with possibility to die.

A Random Walker can move of one unit to the right with probability $p$, to the left with probability $q$ and it can jump again to the starting point with probability $r$ and die. Naturally $p+q+r=1$. ...

**5**

votes

**1**answer

280 views

### The minimal norm of a shifted stochastic matrix

Hello,
Given a row-stochastic matrix $M$ with singular values $\sigma_{1}\geq\ldots\geq\sigma_{n}$, I am looking for an upper bound on the expression: $\min_{\alpha}\parallel M- ...

**2**

votes

**0**answers

506 views

### Random walk on the hypercube

Let $H_N=\{0,1\}^N$ the N-dimensional hypercube. We define the following random walk $X_n$ on $H_N$:
start from a point $x \in H_N$
pick at random an integer $k$ in $[1,N-1]$ and exchange $x(k)$ and ...

**1**

vote

**0**answers

1k views

### asymmetric random walk, hitting time probability

Let's consider an asymmetric Random Walk on $Z$, with transition probabilities $p_{i, i+1}=p$, $~~p_{i, i+1}=q$, $\forall i \in \mathcal{Z}$, $p+q=1$ and $p>q$.
I am interested in the probability ...

**0**

votes

**0**answers

393 views

### Probability density function of the node positions in a random walk after N time slots

Hello, my question basically is how do I find the probability density function of the position of the nodes in a given area after N discrete time slots when the nodes move following the 2D random walk ...

**1**

vote

**1**answer

75 views

### Spanning subgaph with trivial Poisson boundaries

Assume $\Gamma$ is the Cayley graph of an amenable$^{*}$ group and that the simple random walk has non-trivial Poisson boundary$^{**}$. Is there a spanning connected subgraph $\Gamma'$ of some ...

**1**

vote

**1**answer

400 views

### Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...

**12**

votes

**3**answers

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

**29**

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