Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [random-walks]

The tag has no usage guidance.

8
votes
2answers
503 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
80 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
109 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 $...
0
votes
0answers
49 views

Self-correcting Random Walks

Vincent Granville, in his $Analytic\ Bridge$ blog posed a problem on self-correcting random walk. Quoting from the post: Let's start with $X(1)=0$, and define $X(k)$ recursively as follows, for $...
1
vote
0answers
57 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
105 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
63 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
0answers
118 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
0answers
43 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
164 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
98 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
246 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
160 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
141 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
81 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
271 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 ...
3
votes
2answers
335 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
78 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
92 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 $\...
0
votes
1answer
201 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
74 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 ...
0
votes
1answer
85 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} \...
2
votes
2answers
169 views

Random walk and isoperimetric constant

I assume that a result of the following kind is known, and I would really appreciate a reference for it... Or at least, some hints as to where to start looking. Theorem(?): Let $\varepsilon>0$ ...
4
votes
1answer
76 views

Expected time of distinguishability of a series of Poisson processes bounded by each other

Consider a system of $n$ "bounded" Poisson processes over the integers, $X_1, \ldots X_n$, all incrementing at rate $\lambda$. Initially all the processes begin at $0$. The process $X_i$ is inactive ...
0
votes
2answers
148 views

Solving the Poisson equation using a random walk on $\mathbb Z ^d$

How do I solve the Poisson equation with the help of a discrete random walk on $\mathbb Z ^d$?
0
votes
0answers
46 views

Polynomial growth of random walks: critical values?

Consider a sequence of i.i.d. random variables $(X_n)_{n\geq 0}$, and set $S_N = \sum_{n=1}^N X_n$. For which $p> 0$ do we have that \begin{equation} \lim \inf \frac{|S_N|}{N^{1/p}} > 0 \text{ ...
0
votes
0answers
63 views

Suppressed Branching Random Walk

We are interested in the behavior of a branching random walk on the integers which has a linearly growing region where branching does not occur. Consider a branching random walk on $\mathbb Z$ that ...
4
votes
2answers
218 views

Probability question about random shuffling of piles of rocks

I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the ...
2
votes
0answers
79 views

Expected length of a random path in a graph

Let $G$ be a graph and $v$ one of its vertices. Are there any known formulas or fast algorithms for calculating the expected length of a random path in $G$ starting in $v$? In each step we choose a ...
6
votes
0answers
187 views

Calculate the expectation of the maximum of averaged random walks

Let $X_1, X_2, \ldots$ be iid random variables with bounded second moment. The question is to calculate the exact value of $$\mathbb{E} \max_{1 \le j < \infty} \frac{X_1 + \cdots + X_j}{j}.$$ Is ...
4
votes
0answers
88 views

Who proved the reflection principle in random walks and Brownian motion?

I've heard Henry McKean say that the reflection principle is due to Désiré André. But the wikipedia page seems to say that André did not use a reflection principle. Does anyone know where the "modern" ...
0
votes
0answers
59 views

Stochastic Extension to Fubini's Theorem

Fubini's theorem tells us when we can exchange the order of integration - however, does this apply in a stochastic setting? What are the rules for changing the order of integration in stochastic ...
0
votes
0answers
37 views

random walk in power set configuration space

I found a special random walk process description in context of artificial intelligence. The GenI process basically simulates decision taking in teams. It describes a time-discrete stochastic process $...
2
votes
0answers
155 views

Random walk on a finite group, converging modulo a function

Let $G$ be a finite group, and let $Q$ be a probability measure on $G$. Suppose that $Q$, as a function on $G$, is supported on a conjugacy class $C$. We denote by $Q^{*k}$ the $k$-fold convolution of ...
2
votes
1answer
66 views

Expectation of a function evaluated on a random walk in a group

Let $G$ be a finite group, and let $Q$ be a probability measure on $G$. Suppose that $Q$, as a function on $G$, is a class function. We denote by $Q^{*k}$ the $k$-fold convolution of $Q$ with itself - ...
4
votes
2answers
335 views

Random walk uniformly hitting a compact set

Suppose $G$ is a locally compact compactly generated group. Let $\mu$ be a probability measure that is: Adapted to $G$, i.e. there is no proper subgroup $H$ such that $\mu(H)=1$. Symmetric, i.e. $\...
4
votes
2answers
164 views

Divergence of Green function of random walks at spectral radius

Let $P=(p(x,y))_{x, y\in N}$ be the transition matrix over countable states $N$. Consider the generating Green function $G(x, y|t)=\sum_{0}^{\infty} p^n(x, y) t^n$, where $p^n(x,y)$ is the $(x,y)$-...
15
votes
1answer
203 views

Annihilating random walkers

Suppose there are several walkers moving randomly on $\mathbb{Z}^2$, each taking a $(\pm 1,\pm 1)$ step at each time unit. Whenever two walkers move to the same point, they annihilate one another. ...
0
votes
1answer
77 views

Harmonicity of the Martin kernels

Let $\Gamma$ be a finitely generated group and let $\mu$ be a probability measure on $\Gamma$. Consider the Green function $G(x,y)=\sum_{n\geq 0}\mu^{*n}(x^{-1}y)$, where $\mu^{*n}$ is the $n$th ...
3
votes
1answer
143 views

A bound on the square distance of a random walk on undirected graph

Fact: Let $G$ be an $n$-vertex undirected graph and $(X_s)_{s\in \mathbb N}$ a stationary random walk on $G$. Then for every $s\in \mathbb{N}$, $ \mathbb{E}[d_G(X_s,X_0)^2] \le C s \log n $, for some ...
2
votes
1answer
195 views

Walker whose Velocity is a Brownian Bridge

Consider a continuous random walk $x (t) $, in which the velocity $v (t) = \mathrm dx/\mathrm dt $ rather than the position is described by Brownian motion, so that $v (t) = B_t $ where $B_{t+\epsilon}...
3
votes
1answer
151 views

Walk with randomised boosts

The classical random walk can be described as the evolution of the position $X_t$ of a walker for integers $t \geqslant 0$, where $X_0 = 0$ and $X_t = X_{t-1} + V_t$ for $t \geqslant 1$, where the "...
3
votes
1answer
140 views

Radon-Nikodym derivative of the group action on the Furstenberg-Poisson boundary of lamplighter groups

Let $G_d$ be the Lamplighter group $G_d = \mathbb{Z}^d \wr \mathbb{Z}_2 $ and $\Gamma =\{(\bar{\eta},\tilde{0}),(\bar{0},\tilde{e_1}), \cdots,(\bar{0},\tilde{e_d})\}$ be the generator set of $G_d$ (...
1
vote
0answers
70 views

If the diameter of a bounded degree, directed graph is polynomial in the degree of the graph, is the mixing time also polynomial?

Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting ...
1
vote
0answers
47 views

Hypercontractive inequality for random walks on sets

Let $k<N$ be natural numbers. In this question we consider graphs whose vertices are size-$k$ subsets of a size-$N$ universe. Consider the following random walk in the graph: Starting from a set $...
5
votes
0answers
122 views

Random Up-walk on Young's Lattice

Starting from the empty partition, $\varnothing$, follow a random up-walk of length $n$ on Young's Lattice, where an edge's transition probability is 1/updegree. For a particular partition, $\lambda$, ...
14
votes
0answers
189 views

A symmetry of lattice paths

The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity. ...
7
votes
2answers
332 views

One dimension random walk. Is hitting time Lipschitz with respect to target?

Consider a random walk $S_t = \sum_{i=1}^{t} X_i$, with $X_i$ i.i.d.. Assume that $X_i \in [0,1]$. Define $\tau(y) := \inf\{t: S_t\geq y\}$, i.e., $\tau(y)$ is the hitting time of $[y,\infty)$. Is ...
1
vote
1answer
67 views

diffusion coefficient derived from simple random walk in a 1D semi-infinite domain

Suppose we have a 1D domain $x\in[0,\infty)$ and particles released at $x=0$ are doing simple random walks along the domain with reflecting boundary conditions at x=0. Then we can write down the ...