# Questions tagged [random-walks]

The random-walks tag has no usage guidance.

**8**

votes

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**4**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**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} \...

**2**

votes

**2**answers

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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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