Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
4answers
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
1answer
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
0answers
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
2answers
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
0answers
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
3answers
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
1answer
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
1answer
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
0answers
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\...

1
2 3 4 5
8