The tag has no wiki summary.

learn more… | top users | synonyms

14
votes
2answers
666 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 ...
20
votes
5answers
3k 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 ...
1
vote
1answer
84 views

Large deviations for maximizer of random walk with drift

Is it easy to write down the large deviations rate for the maximizer of a random walk with negative drift? Let $X_i$ be the (iid, mean $-\mu$, variance $\sigma$, arbitrarily nice tails) jumps of a ...
6
votes
3answers
363 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 ...
1
vote
2answers
132 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
1answer
165 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 ...
5
votes
1answer
367 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
0answers
161 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
0answers
56 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
1answer
100 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 ...
0
votes
0answers
21 views

Is there effective algorithm for finding “minimal discovery time” for large graphs?

Consider a large, probably sparse graph with Markovian random walkers on it. Define discovery time as time to first reach a vertex by random walk from uniform start. Are there effective ways to find ...
3
votes
0answers
83 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
3answers
450 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
2answers
244 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
1answer
281 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 ...
11
votes
1answer
300 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 ...
1
vote
2answers
326 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 ...
11
votes
1answer
320 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 \mod 3$, we place, with equal probability, one of these six patterns:       The result ...
6
votes
1answer
189 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
0answers
311 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 ...
3
votes
1answer
153 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
2answers
183 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 ...
2
votes
0answers
79 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 ...
8
votes
1answer
172 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
2answers
772 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
2answers
652 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 ...
9
votes
3answers
387 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
0answers
147 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
5answers
460 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 ...
6
votes
0answers
115 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
2answers
207 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
1answer
118 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
1answer
248 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
2answers
219 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
0answers
335 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
0answers
174 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 ...
3
votes
0answers
54 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
2answers
561 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 ...
0
votes
0answers
91 views

Modification of a state in a random walk to be partially absorbing after a walker's position is well-approximated by a stationary distribution

Consider a random walk $(X_0, X_1, X_2, ...)$ on the interval $[0, N]$ starting from some position $k$, where $0$ and $N$ are reflecting barriers. The forward $+1$ transition probability is $p$, the ...
7
votes
1answer
747 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 ...
1
vote
1answer
573 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
0answers
119 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?
2
votes
1answer
377 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
1answer
207 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 ...
4
votes
1answer
185 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
1answer
498 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
1answer
87 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
0answers
68 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 ...
4
votes
2answers
246 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 ...
12
votes
0answers
524 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, ...