Questions tagged [random-walks]

The tag has no usage guidance.

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