# Questions tagged [random-walks]

The random-walks tag has no usage guidance.

346
questions

**5**

votes

**1**answer

168 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

66 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

99 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

182 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

165 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

42 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

143 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

70 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

248 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

182 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

305 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

94 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

120 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

254 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

153 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

58 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

88 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

515 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

170 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

351 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

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

**2**

votes

**1**answer

72 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

74 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

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

**0**

votes

**0**answers

45 views

### Finite time version of “A pattern of hitting times for a simple random walk”

The question below was asked and answered here:
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 ...

**6**

votes

**0**answers

124 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

691 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

95 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

145 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\...

**3**

votes

**2**answers

158 views

### Expectation of the exitpoint distance for the symmetric random walk

Let $\nu(x)$ be a symmetric probability measure with respect to the origin on $x\in[-1,1]$ such that $\nu(\{0\})\neq 1$.
Consider a random walk started at $S_0=0$, denoted $S_n=X_1+\dotsb+X_n$, ...

**1**

vote

**1**answer

78 views

### Maximum of sums of iid $X_i$'s where $X_i$ is the difference of two exponential r.v

Given $X_i = A_i - B_i$ where $A_i\sim \text{ Exp}(\alpha)$ and $B_i \sim \text{ Exp}(\lambda)$. Define $S_k = \sum_{i=1}^k X_i$ with $S_0 = 0$, and
$$M_n = \max_{1\leq k \leq n} S_k.$$
Is it ...

**3**

votes

**1**answer

205 views

### Large deviation of random walk

1) Let $\{X_i\}_{i=1}^n$ be i.i.d. such that $\Pr(X_i=1 )=1-\Pr(X_i=-1)=p$. Define the random walk
$$
S_i = \sum_{j=1}^iX_j
$$
for $i=1,2,\ldots,n$.
I am looking for "good" exponential upper bounds ...

**1**

vote

**1**answer

99 views

### Is there a transient graph whose spectral dimension two?

Let $G = (V(G), E(G))$ be an infinite connected simple graph.
Let $((S_n)_n, (P^x)_{x \in V(G)})$ be the simple random walk on $G$.
Let $p_n (x,y) = P^x (S_n = y)$.
A spectral dimension of $G$ is ...

**5**

votes

**4**answers

178 views

### Concentration of closed random walks

Consider a random walk $S_n=\sum_{i=1}^n X_i$ where $P(X_i=+1)=P(X_i=-1)=1/2$ with $n$ large. By Chernoff's bound we know that, for example, $\sum_{i=1}^{n/2} X_i=O(\sqrt{n})$ with high probability.
...

**2**

votes

**0**answers

123 views

### Random walk and comparing sums of Exponential random variables

Let $\sigma$ be the time a nearest neighbor random walk started at 1 that has probability $p>1/2$ of moving left reaches $0$. Let $\sigma'$ be an independent copy of $\sigma$. Let $(X_k)_1^\infty$ ...

**0**

votes

**2**answers

558 views

### Sum of independent random walks

Given two independent random walks $S$ and $S'$ with different distributions for the random variables $X_1$ and $X_1'$, I am interested in studying the conditions that make their sum either a ...

**3**

votes

**1**answer

184 views

### Concentration of a modified random walk

Let $\varepsilon$ be a number in $(0, 1)$, consider the following random walk on the real line $X^{(0)}, X^{(1)}, \dots$, where
$X^{(0)}=0$
If $X^{(t)} > 0$, then with probability $.5$, $X^{(t+1)...

**2**

votes

**1**answer

210 views

### Irreducible but not completely irreducible

Consider a product of i.i.d. $d\times d$ random matrices $A_{i}$
(with $\mathbb{E}\log\left\Vert A_{i}\right\Vert <\infty$).
Let $F:M\times \mathbb R^d\to M\times \mathbb R^d$ be a linear cocycle, ...

**2**

votes

**1**answer

102 views

### stationary measure for linear cocycle(random transformation matrices)

Let $(M,\mathcal B, \mu)$ be a probability space which $M=\{A_{1},A_{2},...,A_{N}\}^{\mathbb{N}}$ ($A_{i} \in GL(d ,\mathbb{R})$) and $\mu=p^{\mathbb{N}}$. Let $F:M\times \mathbb R^d\to M\times \...

**3**

votes

**0**answers

288 views

### Random walk on $\mathbb{R}$ with “sticky” origin

Let $P_i$, $N_i$, and $Z_i$, $i\in\mathbb{N}$ be r.v.'s with the $P_i$, $N_i$, and $Z_i$ being identically distributed with known pdf's $f_P$, $f_N$, and $f_Z$, respectively; and with no dependence ...

**4**

votes

**2**answers

581 views

### Number of self avoiding paths on a grid graph?

Let $G$ be an $n \times n$ grid graph. Is there anything known about the asymptotic growth rate of the number of self avoiding paths from $(0,0)$ to $(n,b)$ (from the lower left corner to some ...

**5**

votes

**0**answers

98 views

### Random walks in arrangements of lines in the plane

Let $\cal{A}_n$ be a simple arrangement of $n$ lines in $\mathbb{R}^2$.
(Simple: each pair of lines meet in a distinct point, i.e.,
no three lines pass through the same point.)
Start a random walk at ...

**2**

votes

**1**answer

95 views

### Convergence of a stochastic sequence?

I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\...

**1**

vote

**1**answer

325 views

### How to find a random cycle in a large graph?

Suppose we have a large directed graph $G$ with no self-cycle and no more than one edge between two nodes, for example, containing about 2000 nodes and about 10 edges per node. Now we need to achieve ...

**0**

votes

**1**answer

81 views

### Proof of reduction from random walks to martingales - why $T\le k$?

I'm trying to understand the proof of theorem 1.6 from the paper "A Matrix Expander Chernoff Bound".
In the proof they say: "Iterating this construction on the remainder a total of $T ≤ k$ times" and ...

**1**

vote

**1**answer

127 views

### how to derive stationary distribution of maximal entropy random walk

I was reading the paper 0810.4113v2, burda, which analyzed the stationary distribution maximal entropy random walk on the irregular lattice. I am confused on some of the steps.
Description:
The ...

**4**

votes

**1**answer

173 views

### Is this a random walk? Does it have a name?

By combining two methods I've stumbled into a rather messy random walk situation. I have the typical random walk setup
$$\theta_{i+1} = \theta_{i} + \hat{\theta}_{i+1}$$
Where $\hat{\theta}_{i+1} \...