Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
3 votes
1 answer
321 views

Maximizer of random walk with very small drift

This is an extended question based on Large deviations for maximizer of random walk with drift. Let $$S_k = X_1 + \ldots + X_k,$$ where $X_i$ are i.i.d. with mean $-\mu < 0$ and unit variance. ...
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 ...
6 votes
3 answers
921 views

Probability that a self-avoiding walk on $\mathbb{Z}^3$ closes to a polygon

The probability that a random walk on $\mathbb{Z}^3$ returns to the origin is about 34%. This is (part of) Pólya's theorem. I have been looking for an analogous (numerical) result for the probability ...
2 votes
2 answers
362 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 ...
2 votes
1 answer
359 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 $g^{...
5 votes
1 answer
681 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 ...
4 votes
0 answers
298 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)$, ...
2 votes
0 answers
79 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
1 answer
126 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 ...
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 ...
2 votes
2 answers
268 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 $x_{...
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 ...
0 votes
1 answer
469 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 ...
7 votes
1 answer
326 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])$ ...
3 votes
1 answer
198 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 ...
6 votes
2 answers
408 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 $\...
4 votes
0 answers
156 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 (...
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 ...
4 votes
2 answers
2k 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 $\mathbb{R}^...
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$, $...
4 votes
0 answers
177 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. ...
6 votes
2 answers
405 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: ...
4 votes
1 answer
199 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$. ...
1 vote
1 answer
938 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 ...
8 votes
2 answers
865 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 ...
0 votes
0 answers
553 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 ...
3 votes
0 answers
237 views

criterion for deciding whether the product of a sequence of Givens rotations can reach the full special orthogonal group

By Givens' rotation $R(1,2;\theta)$ I mean a matrix which has the $$\begin{pmatrix} \hphantom{-}\cos \theta &\sin \theta \cr -\sin \theta & \cos \theta \end{pmatrix}$$ $2 \times 2$ block at ...
4 votes
0 answers
156 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 ...
5 votes
2 answers
804 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 ...
7 votes
1 answer
2k views

Generating function for Random Walk Hitting Time, taking the wrong root

In a calculation of the hitting time for a Bernoulli random walk we have to calculate the hitting time $\tau(1)=\inf\{n\ge 0:S_n=1\}$ to reach $+1$ and the generating function has the recursion ...
3 votes
1 answer
2k 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$. ...
7 votes
0 answers
129 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?
0 votes
1 answer
139 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$ ...
5 votes
2 answers
907 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 ...
6 votes
1 answer
822 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 ...
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 ...
1 vote
0 answers
122 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 http://arxiv.org/...
4 votes
2 answers
710 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: ...
7 votes
1 answer
508 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 ...
9 votes
1 answer
618 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 $n=...
5 votes
1 answer
402 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 $S(0)...
3 votes
1 answer
384 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
615 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 ...
2 votes
0 answers
240 views

$n$-th return of a random walk on $\Bbb Z^d$

Lets define $f_n = P(X_n =0 , X_k \ne 0, k< n)$ the first return distribution of the random walk $X_n$ on $\mathbb{Z}^d$, and lets go ahead and assume that $f_n \approx n^{-(1+\alpha)}$ for some $\...
7 votes
1 answer
853 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 ...
1 vote
1 answer
534 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}$: ...
5 votes
1 answer
737 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 ...
3 votes
1 answer
2k views

first passage time, brownian motion

Hi, If X(t) is Brownian motion in 2D, where X(0) = 0, then we can ask what is the expected time required to first hit a circle of radius R, centered at the origin. This is a First Passage Time ...
4 votes
0 answers
1k 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 $...