# Questions tagged [random-walks]

The random-walks tag has no usage guidance.

364
questions

**0**

votes

**0**answers

46 views

### Concentration (or two sided tail bounds around expectations) of maximum and minimum of $n$ iid, subgaussian random variables

I asked this on MSE, but got no answer, hence asking here now. Help appreciated!
My question is motivated by this question and this question, where the first was aimed for giving a one sided tail ...

**1**

vote

**0**answers

47 views

### Support of random closed walk in arbitrary graph

Researching a question related to closed walks on graphs, I have come across the following problem. Let $G$ be a connected graph on $n$ vertices and $k=O(\log(n))$. Pick a random closed walk on $G$ as ...

**2**

votes

**1**answer

61 views

### Reference request: Donsker's theorem for non-identical, independent random variables

The central limit theorem can be generalized to independent but not iid random variables, provided they satisfy the Lyapunov condition (which looks something like a variance bound), see https://en....

**13**

votes

**2**answers

761 views

### How long for Brownian motion to “fill-out” a torus in d-dimensions?

I've been taken by the concise result1
that (roughly!), on a $2$-dimensional torus $\mathbb{T}^2$, the time it takes
to visit nearly every point (within $\epsilon$, as $\epsilon \to 0$) is: $\frac{2}{\...

**3**

votes

**0**answers

44 views

### Algebraic property of a transition matrix

Consider the simple random walk on $\mathbb{Z}^2$. Given a finite $\Sigma \subset \mathbb{Z}^2$, one can induce the random walk on $\Sigma$: set $\tau_0 = 0$, and define recursively $\tau_{n+1} := \...

**2**

votes

**0**answers

21 views

### probability a negative drift random walk is positive after certain time

Suppose I have a simple continuous time random walk starting at $0$ at time $0$ with Poisson transition rate 1 and probability $p$ the jump is $+1$ and probability $1-p$ thejump is $-1$. Suppose $p &...

**1**

vote

**1**answer

97 views

### Asymptotically tight concentration of norms of subgaussian random vectors with independent coordinates, as the dimension $n \to \infty?$

Let $X=(X_1 \dots X_n)\in \mathbb{R}^n,$ be a subgaussian random vector so that $X_i$'s are independent, $\mathbb{E}X_i = 0, \mathbb{E}X_i^2=1.$ Before we pose our question, let's state the following:
...

**7**

votes

**2**answers

159 views

### Support of closed random walk on $\mathbb Z$

I am researching closed random walks on graphs and have the following problem that I haven't been able to find a reference for.
Consider a random walk on $\mathbb Z$ starting at 0 and at each step ...

**1**

vote

**0**answers

54 views

### Spitzer's condition, a slowly varying function and its behavior

Let $S$ denote a random walk that satisfies Spitzer's condition $$ \frac{1}{n} \sum _{k=1}^n P (S_k > 0 ) \to \rho$$ for some $\rho \in (0,1)$. From the book Regular Variation (Bingham, Goldie, ...

**6**

votes

**1**answer

149 views

### Random walks on infinite directed regular graphs

Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).
Assume that $\Gamma$ is bi-regular, that is ...

**2**

votes

**1**answer

47 views

### Marcenko-Pastur and Tracy-Widom laws for sample covariance and Gram matrices when the “features” are correlated: references

Let us assume we've a rectangular data matrix $X=[x_1 \dots x_n] \in \mathbb{R}^{p \times n}$, where the $x_i \in \mathbb{R}^{p \times 1}$ are iid column vectors. I'm not assuming here that the ...

**1**

vote

**0**answers

77 views

### Minima of a random walk and an equality for a fraction

Let $S_n := X_1 + \dots + X_n$ denote a random walk with zero mean and finite variance and write $L_n := \min \{ 0, S_1, \dots, S_n\}$. The tail distribution of $L_n$ are well-known and in particular,
...

**1**

vote

**0**answers

34 views

### Tracy Widom type results for asymptotic distribution of the $k$-th largest eigenvalue of the sample covariance when $n, p \to \infty$?

Earlier I asked a question: Distribution of the $k$-th largest eigenvalue of in the sample covariance matrix?, but I forgot to mention that I'd like results for asymtotic regime. So, I'm posting here ...

**0**

votes

**0**answers

44 views

### Distribution of the $k$-th largest eigenvalue of in the sample covariance matrix?

Let us assume we've a rectangular data matrix $X=[x_1 \dots x_n] \in \mathbb{R}^{p \times n}$, where the $x_i \in \mathbb{R}^{p \times 1}$ are iid column vectors. I'm not assuming here that the ...

**1**

vote

**0**answers

103 views

### Probability of m crossings of 0 before time 1 of a standard Brownian motion

Let $B$ be a standard Brownian motion. Could anyone show some hints and reference about how to compute the following probability?
Let $N(n) = \sum_{i=1}^n \mathbb{1}_{\{0 \in B[\frac{i-1}{n},\frac{i}{...

**1**

vote

**0**answers

74 views

### Probability of m crossings of 0 before time n of a Gaussian random walk

Let $S_n = \sum_{n=1}^n X_n$ be a Gaussian random walk where $X_n$ are i.i.d random variables with distribution $\mathcal{N} (0,1)$. Could anyone show some hints and reference about how to compute the ...

**8**

votes

**1**answer

194 views

### How often a random walk with irrational increments is close to 0?

Let $\omega$ be an irrational number, and $X$ a random variable taking values $1,-1,\omega,-\omega$ each with probability $1/4$. Let then $X_i$ be iid variables with the same law as $X$ and $S_n=\sum_{...

**1**

vote

**1**answer

71 views

### Multidimensional random walk falling pointwise below some threshold

Consider a random walk $X_t = \sum_{s=1}^t D_s$ with i.i.d. increments $D_t \in \mathbb{R}^n$,such that $X$ is a martingale $\mathbb{E}[D_t]=\vec{0} \in \mathbb{R}^n$, the support of $D_t$ is bounded, ...

**0**

votes

**0**answers

27 views

### hypergraph product that preserve expansion properties

I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2.
The expansion property I am looking at is HD-random walk.
The product I am looking for is ...

**5**

votes

**1**answer

194 views

### Random walks: How many times does the largest component change?

My understanding is that for an unbiased random walk (starting at the origin) on $\mathbb R$ with $N$ steps that the expected number of sign changes is $O(\sqrt N)$. For a biased walk I believe the ...

**5**

votes

**0**answers

78 views

### Intuition behind the local limit theorem in hyperbolic groups

Let $\Gamma$ be a finitely generated group and let $\mu$ be a probability measure on $\Gamma$. Denote by $X_n$ the induced random walk. Finally, let $p_n=\mu^{*n}(e)=P_e(X_n=e)$. The local limit ...

**0**

votes

**1**answer

122 views

### Symmetric random walks - bounds on the amount of time spent in a subset $A$?

For a symmetric random walk $S_n$, if we have a bound $P(S_n \in A) < \delta$, do we get a bound on the amount of time $S_n$ spends in $A$?
Let $S_n$ be a symmetric random walk on the integers. ...

**4**

votes

**1**answer

187 views

### Strategy for finding each other in a crowd

Looking for a strategy for finding each other in a crowd, is it better to have one person move and one person stay put, or have both people move?
Suppose we have a $n$ by $n$ grid of squares. Each ...

**1**

vote

**3**answers

175 views

### expectation of random walk with barriers

Suppose we are flipping a coin with probability $p$ of coming up heads and $q$ of coming up tails. We start with $n$ dollars, and the game is over when we either lose all our money or win $m$ dollars. ...

**1**

vote

**0**answers

45 views

### hitting probabilities of oriented random walk

Consider a random walk on $\mathbb{Z}^2$, starting at $(0,0)$. Each step it moves rightwards with probability $p$ and upwards with probability $q=1-p$. The random walk terminates when it hits the ...

**2**

votes

**1**answer

152 views

### Equivalence of harmonic measures on hyperbolic groups

Consider a Gromov-hyperbolic group $\Gamma$ and let $\mu$ be a finitely supported probability measure on $\Gamma$. Assume that the support of $\mu$ generates $\Gamma$ as a semi-group, in other words, ...

**2**

votes

**1**answer

85 views

### Smooth transformation of a curve with fixed ends and length [duplicate]

I am simulating polymers of fixed length and fixed ends. I would like to search the phase space of all possible conformations quickly. Is there anyway I can generate efficiently a lot of (rather) ...

**3**

votes

**1**answer

261 views

### Probability that random walk stays in quadrant

Let $S_n = \sum_{i=1}^n X_i$ where $X_i \in \mathbb R^d$ are iid. random vectors with $E[X_i]=0$.
We want to lower-bound the probability that
$$
\begin{align}
\forall_{n=1}^m S_n \le k
\end{align}
$$...

**5**

votes

**1**answer

192 views

### Random walk on the hypercube with deleted edges

Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a ...

**5**

votes

**2**answers

312 views

### Is random walk drift rational?

(Question mildly edited for clarity by request of Matt F.)
If $G$ is a finitely presented group, let $|\cdot|$ denote the word metric with respect to a finite set of generators. Suppose $\nu$ is a ...

**3**

votes

**0**answers

105 views

### Shannon-McMillan-Breiman theorem for expander graphs: rate of convergence?

Is the following uniform SMB theorem for random walks on expander graphs true?
For simplicity, I will state it for a finite group $G=\langle S \rangle$ and a uniform probability measure $\mu$ on the ...

**0**

votes

**0**answers

18 views

### Approximate method to extract behavior of a Laplace transform in an intermediate region

In the theory of random walks, Tauberian type theorems are often applied to extract the small or large-time behavior from a difficult equation. For example, the Montroll-Weiss formula describing a ...

**5**

votes

**0**answers

126 views

### Continuity of the Green function with respect to the measure

Let $G$ be a finitely generated group and let $\mu$ be a finite measure on $G$. Define the Green function as
$$G(\mu)=\sum_{n\geq 0}\mu^{*n}(e),$$
where $\mu^{*n}$ is the $n$th convolution power of $\...

**12**

votes

**2**answers

273 views

### Random Walk on Pentagonal Tiling

I’ve recently been looking at closed walks on tilings of the plane in which the “player” can move from one tile to any of its edge-adjacent neighbors. In particular, I’m trying to find asymptotic ...

**4**

votes

**0**answers

175 views

### Dyck paths weighted by height profile

We are interested in a question concerning a weight function on Dyck paths that penalizes visits to higher heights.
Let $\rho$ be a parameter. Let $D_k$ be the set of all nearest neighbor random walk ...

**1**

vote

**1**answer

67 views

### Transition matrix for shortest path walk

Consider a directed, weighted graph $G$.
Let $s$ and $t$ be two distinct vertices of $G$ and consider a walker that starts at $s$ and traverses a random shortest path from $s$ to $t$, chosen uniformly ...

**3**

votes

**1**answer

106 views

### WIll a proliferating 3D random walk a.s. revisit the origin?

The concept of a "proliferating random walk" on a lattice is that at any time $t \in \Bbb N \cup 0$, there is some set consisting of at least one particle, each of which is on its own lattice point. ...

**9**

votes

**2**answers

555 views

### A comprehensive list of random walk inequalities?

I am interested in finding a comprehensive list of all noticeable random walk inequalities.
ie. $S_n = \sum_{k\leq n} X_i$ for i.i.d symmetric $X_i$
I can only seem to find books/papers that list ...

**3**

votes

**1**answer

213 views

### Quadratic variation of sum of random variables

Let $N = (N_t)_{t\geq 0}$ be a Poisson process and consider random variables $Z_n$, $n\in N$. Compute the quadratic variations $[X]_t$ where $X_t = \sum_{n=1}^{N_t}Z_n$.
What I did was plugging $X_t$ ...

**11**

votes

**1**answer

355 views

### Growing a chain of unit-area triangles: Fills the plane?

Define a process to start with a unit-area equilateral triangle,
and at each step glue on another unit-area triangle.
$50$ ...

**1**

vote

**0**answers

101 views

### Entropy of endpoints of a random walk in a dense graph

Let $p\in[0,1]$ be a constant and let $G$ be a graph with $n$ vertices and $\approx p\binom{n}{2}$ edges. If you'd like, consider $p=1/2$.
Let $X$ be a random vertex of $G$ chosen proportional to ...

**33**

votes

**4**answers

1k views

### How many random walk steps until the path self-intersects?

Take a random walk in the plane from the origin,
each step of unit length in a uniformly random direction.
Q. How many steps on average until the path self-intersects?
My simulations suggest ~$8....

**1**

vote

**1**answer

89 views

### Figuring out a consistent definition for the percolation backbone

In the context of percolation, e.g., bond/site percolation, random graph connectivity in 2-3 dimensions, etc., once the percolation threshold is reached, that is the system is spanned by an infinite ...

**2**

votes

**0**answers

104 views

### Graph pattern matching

Given a weighted, oriented, connected graph with $10^7$ vertices and $10^{10}$ edges I need to implement the algorithm for searching various patterns on this graph for less than polynomial time.
...

**3**

votes

**2**answers

643 views

### Expected distance from the origin for a recurrent 1D random walk in a random environment

It is well known that for a discrete random walk on the integers with a fair coin, the expected distance of the walker from the origin after $N$ time steps is $\sqrt{\frac{2N}{\pi}}$ if $N$ is large. ...

**6**

votes

**0**answers

125 views

### Random walk on $\mathbf{Z}_d$ with Jacobi $\theta$ transition probabilities

In the context of a finite-dimensional quantum mechanical problem, I was led to study the random walk on $\mathbf{Z}_d$ (i.e the integers modulo $d$), $d$ odd with transition probabilities given by:
$...

**10**

votes

**3**answers

767 views

### Random Walks on high dimensional spaces

I've read on a paper that, in the two dimensional case, if you start from the origin and take steps of length one in arbitrary directions (uniformely on the unit sphere $S^1$, not left-right-up-down), ...

**5**

votes

**1**answer

108 views

### What is the pdf of Laplace distribution conditioned on a plane? How can I sample from it?

Our goal is to sample from the Laplace distribution conditioned on a linear subspace. Here are the details of this problem.
Let
$$p(x) \propto \exp(-\|x\|_1/\sigma)$$
be the pdf of the Laplace ...

**2**

votes

**1**answer

159 views

### About a pattern of hitting times for a simple random walk

Let $\omega_1, \omega_2, \ldots$ be uniform iid on $\{-1,1\}$, and let $X_n = \sum_{i=0}^n \omega_i$ be the corresponding simple random walk. Fix some integer $N$, and let $h^+_N$ be the first time $...

**1**

vote

**0**answers

61 views

### Discrete Markov process on finite interval

Consider an contiguous array of $N$ states, numbered from $1$ to $N$.
At every time step $t$, the process should transition to an adjacent state.
The probability of moving to the right (from state $n\...