# Questions tagged [random-walks]

The random-walks tag has no usage guidance.

526
questions

3
votes

0
answers

82
views

### Divergent/Unbounded random walks techniques

I want to prove the following biased random walk will be diverge. Suppose I have a random walk $S_n = X_1 + ... + X_n$, but $X_1,...,X_n$ are dependent variables. $X_1 \sim$ Bernoulli($\sigma(\theta_1)...

0
votes

1
answer

49
views

### Probability of random walk on confined lattice with reflective boundaries

Consider a simple random walk in one dimension with reflective boundaries at $n=1$ and $n=N$. We can express it via the master equation:
\begin{equation}
P(n,t) = \frac{1}{2}P(n-1,t-1) + \frac{1}{2}P(...

0
votes

0
answers

79
views

### Does a 2d random walk hit 0 for increasing distances AND time spans?

Question: For a simple symmetric random walk $(Z_t)_{t\geq 0}$ in $\mathbb{Z}^2$, does
$$\lim_{\beta\rightarrow 0}\mathbb{P}^{x_\beta}(Z_t=0\text{ for some }t\leq h(\beta)T)=0\quad (2.8)$$
where $|x_\...

5
votes

1
answer

130
views

### Dispersion of random walk with scaled step sizes

Let $Y_j$ be a sequence of independent Gaussian random variables with mean zero and unit variance ($\mathbb{E} Y_j = 0$ and $\mathbb{E} Y_j^2 = 1$) and let $\sigma:\mathbb{R}\to [1,2]$.
We define the ...

7
votes

5
answers

488
views

### Probability of $\operatorname{Bin}(n,p)=\operatorname{Bin}(n,q)$ is decreasing when $n$ increases

$\newcommand{\Bin}{\operatorname{Bin}}$I would like to show that $\mathbb P(\operatorname{Binomial}(n,p) = \operatorname{Binomial}(n,q))$ decreases when $n$ increases for a fixed pair $(p,q)$. This ...

3
votes

1
answer

232
views

### Bounds on hitting time of sum of i.i.d. random variables

I have a sequence $(X_i)_{i\geq 1}$ of i.i.d. random variables taking values in $\mathbb Z$. I know that each $X_i$ has mean $0$ and finite variance $\sigma^2$. Let $S_n=X_1+\cdots+X_n$. Then I can ...

4
votes

0
answers

74
views

### MGFs of sum of (Rademacher) independent variables and (hyperbolic/spherical) Pythagorean theorem

Consider a set of iid random variables $X_1, X_2, \ldots$ (distribution to-be-specified later). For real numbers $a_1, a_2, \ldots$ (with $\sum_{k} a_k^2 < \infty$) define
$$X = a_1 X_1 + a_2 X_2 +...

3
votes

1
answer

163
views

### A few points of clarification on the Martin boundary

Let $\Gamma$ be a finitely generated group, and let $M$ be the Martin boundary of $\Gamma$. I was reading the article on Martin boundary on Encyclopedia of Math, and I have a few questions about what ...

1
vote

0
answers

126
views

### Have strictly superharmonic functions on graphs been studied?

Given a graph $G$ and a function $f:G\to\mathbb R$, we say that $f$ is harmonic if
$$f(x)=\frac{1}{|N(x)|}\sum_{y\in N(x)}f(y)$$
for every $x\in G$, where $N(x)$ denotes the set of neighbors of $G$. ...

2
votes

0
answers

164
views

### How to choose N policemen positions to catch a drunk driver in the most effective way (on a Cayley graph of a finite group)?

Consider a Cayley graph of some big finite group. Consider random walk on such a graph - think of it as drunk driver. Fix some number $N$ which is much smaller than group size.
Question 1: How to ...

1
vote

1
answer

239
views

### Random walk on $\mathbb{Z}^3$. Expected number of visits and probability of return

I am working with the simple symmetric random walk on $\mathbb{Z}^3$. Using the Fourier identity I have been able to prove:
$$ P(S_n = 0) = \frac{1}{(2\pi)^3} \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} \...

2
votes

1
answer

65
views

### Random pseudo-walk with 'disappearing' values

This question is a twist on a question I asked here Random pseudo-walk of Poisson variables, but with randomly 'disappearing' objects. I do not know how to generalize the (satisfactory) answer given ...

2
votes

0
answers

43
views

### Random Walks on the natural numbers with self loops

I am looking at a random walk that starts at 0 and at every step, either increases or decreases by 1, or doesn't move.
More specifically, $\mathbb{P} (X_{t+1} = X_t) = 1-p,\mathbb{P} (X_{t+1} = X_t +1)...

3
votes

1
answer

107
views

### Has this random process been studied on grid graphs?

As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...

3
votes

2
answers

213
views

### Measures with superexponential moments on finitely generated groups

Let $\Gamma$ be an infinite finitely generated group and let $\nu$ be a measure on $\Gamma$ which generates a transient random walk. I was reading this paper, and the authors prove many of their ...

2
votes

0
answers

67
views

### Bound from above and from below the probability that a 1-D centered random walk remains at each step inside a square root boundary

Let $W_n = \sum_{i = 1}^{n}X_i$ be a random walk on $\mathbb{R}$, where the increments $X_i$ are i.i.d., symmetric around the origin ($X\sim -X$), such that $-1\leq |X(\omega)| \leq 1$ $\forall\omega\...

0
votes

1
answer

32
views

### Transience of the SRW on regular graphs of exponential growth

Let $G$ be a $d$-regular graph of exponential growth. By exponential growth I mean that
$$ \liminf_{r \to \infty} | B(o, r)|^{1/r} >1. $$
Here $B(o,r)$ is the ball of radius $r$ centered at a given ...

6
votes

1
answer

537
views

### Balancing act for infinite walks

Think of a one-dimensional infinite walk as a map $$w\colon \mathbb{N}\to \{-1,1\}.$$ (If it is more convenient, you can think of a walk as a subset of $\mathbb{N}$, or as a binary word, or as any ...

6
votes

0
answers

145
views

### Running minimum of exponential random walks

Let $\{X_i\}$ be a collection of i.i.d. Exp$(1)$ random variables. For $k \in \mathbb{Z}_{>0}$, define
$$S_k = \sum_{i=1}^k X_i$$
and note that $\mathbb{E}[S_k] = k$.
I was wondering if there is ...

2
votes

0
answers

112
views

### Asymptotic Independence of random walks from increments?

Suppose we have two random walks $(S_n:n\geq 1)$ and $(T_n:n\geq 1)$ building from independent identically distributed increment vectors $\{(X_k,Y_k):k\geq 1\}$, i.e. $S_n=\sum_{k=1}^n X_k, T_n=\sum_{...

3
votes

1
answer

163
views

### Simple linear asymptotics for leaving time of particle in open-boundary TASEP

EDIT: It appears the hypothesis may not be true - I am not sure. I therefore changed my question.
ORIGINAL QUESTION:
Consider a system $n$ linked discrete cells numbered $1 \ldots n$. Particles are ...

4
votes

3
answers

681
views

### Winning game probability

At each round of a game with two players Alice and Bob, Alice can win with a fixed probability $a$ and Bob can win a fixed probability $b$, such that $a+b < 1$, otherwise there is a draw.
The game ...

1
vote

0
answers

163
views

### Locally "unshortable" paths in graphs

Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...

2
votes

0
answers

192
views

### If the operators $B_i'$ satisfy an inequality, prove that $B_1'+\dotsb+ B_n'$ also satisfies the same inequality

Related: On a deceptively tricky calculus problem.
The way that Leonard Gross proves the log Sobolev inequality is in the following stages:
He proves that for any operator $B$ that satisfies the log ...

1
vote

0
answers

164
views

### Random walk on N-Rubik cube group is going like sqrt(number of moves) or linear (number of moves) or? "commutative" vs. "free"(like) group pattern?

Consider higher (NxNxN) Rubik's cube group, with specific set of generators described below.
What is important - that there are huge COMMUTING subsets of generators.
Question: Consider a random walk ...

1
vote

0
answers

92
views

### Conditioned random walk over a graph

I want to solve for a conditioned random walk over a graph. I have a directed graph $G$. The random walkers start at a fixed node, Source. They all need to end up at fixed node, Sink. So the random ...

3
votes

0
answers

129
views

### An analogue of Kolmogorov's law of the iterated logarithm

Let $X_1,\dots,X_n$ be independent random variables, each with mean zero and finite variance. Let $S_n = \sum\limits_{k=1}^n X_k$ and $s_n^2=ES_n^2$. We say the sequence obey the law of iterated ...

3
votes

1
answer

369
views

### Random pseudo-walk of Poisson variables

Suppose there is a pool that can contain any non-negative number of objects. At time $t$ it contains $n_t$ objects. Time is discrete.
Before time $t+1$ two things happen, in this order:
Unless the ...

1
vote

3
answers

357
views

### Probability that a 1-D zero mean random walk remains at each step inside a square root boundary

Let $W_n = \sum_{i = 1}^{n}X_i$ be a random walk on $\mathbb{R}$, where the increments $X_i$ are i.i.d., symmetric around the origin ($X\sim -X$), such that $-1\leq |X(\omega)| \leq 1$ $\forall\omega\...

3
votes

0
answers

140
views

### How to sample uniformly over a polytope knowing its vertex presentation?

Say that a convex polytope $P$ is presented as $P = \mathrm{Conv}(v_1, \dots , v_m)$.
I would like to sample over $P$, without generating the facet presentation of the polytope.
How can I do that?
I ...

2
votes

0
answers

119
views

### Random walk with same directions and different step sizes

Let $X\sim e^{iU}$, where $U$ is uniformly distributed on $(0, 2\pi]$. Define $\chi_1, \cdots, \chi_t$ as i.i.d. random variables with the same distribution as $X$.
Consider the following two random ...

0
votes

1
answer

282
views

### How far does a random walker travel before returning to the origin?

Consider a (continuous time) simple symmetric random walk on $\mathbb Z$, starting from the origin. Let us denote this random walk by $\{X_t: t\geq 0\} $. It is well known that this random walk is ...

2
votes

0
answers

77
views

### A question on the convex hull of independent random walks

Consider $m$ independent random walks $X^1_n, \dots, X^m_n$ driven by a probability measure $\mu$ in $ \mathbb{Z}^d$. Assume that the $\mu$ has no drift, that is, the expected value of a $\mu$-...

4
votes

0
answers

72
views

### Small angles between independent centred random walks in $ \mathbb{Z}^d$

Let $W_n$ and $W'_n$ denote two independent random walks in $ \mathbb{Z}^d$ defined using a finitely supported centred (mean zero) probability measure on $\mathbb{Z}^d$.
For $N \ge 1$, let
$\theta_n$ ...

4
votes

1
answer

183
views

### Sign of error in the central limit theorem

Let $X_n$ and $Y_n$ be independent copies of two random variables $X$ and $Y$ with domain $\{-1,0,1\}$ for $n\in \mathbb{N}$. For a given $k\in \mathbb{N}$, I would like to find conditions on $X$ and $...

5
votes

2
answers

392
views

### A coupon collector-ish question

Imagine we are in the coupon collector setting: every time step we get independently one coupon out of $n$ coupons uniformly at random. However, unlike the coupon collector problem, we stop the at the ...

2
votes

0
answers

98
views

### Defining a metric on $\mathbb Z^n$ using Green's function for the simple random walk

Let $G$ be Green's function for the simple random walk on $\mathbb Z^n$ for $n\ge 3$, i.e., $G(x)$ is the expected number of visits to $x$ when the walk starts at the origin.
Define $d(x,y)=G(x-y)^{1/(...

13
votes

2
answers

1k
views

### Optimal search puzzle

Consider the following puzzle: On the integer line from 1 to $t$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $t$, and subtract 1. What is the optimal ...

4
votes

1
answer

509
views

### Probability to return to the origin for a uniform random walk

Consider a uniform random walk on $\mathbb{R}$, with stepsize chosen uniformly from the interval $(-1,1)$. The random walk start at $x=0$. Denote by $\rho_p dx$ the probability that the random walk ...

-1
votes

1
answer

143
views

### Strong law of large numbers for a sequence of random variables in different probability spaces

Is it known whether the following version of the strong law of large numbers holds?
For each $k\in\mathbb{N}$, let $\Omega_k$ be a finite set and $\mu_k$ be a probability measure on $\Omega_k$. Let $(...

3
votes

2
answers

203
views

### Random walk to visible lattice points

Consider a random walk from the $\mathbb{Z}^2$ origin $(0,0)$ to visible
(not blocked) lattice
points $p$, with a parameter $r$ a given radius of a circle centered
on $p$.
With $p$ the previous point, ...

2
votes

2
answers

142
views

### Example of random walk in a random environment (RWRE) saying things on the environment

I was wondering if anyone is aware of works/articles/examples where random walks in a random environment (RWRE) are actually used for obtaining information on the random environment.
To clarify a bit, ...

8
votes

0
answers

160
views

### Random walk on matrix until singularity

Consider a random walk on matrices, where one starts with the matrix $M=I_n$ and at each step randomly chooses an entry of $M$ to increase by $1$.
I’m interested in two things about this walk:
What’s ...

1
vote

1
answer

255
views

### Rate of convergence to uniform distribution

Let $p=(p(1),\ldots,p(N))$ be a discrete distribution on $[N]:=\{1,2,\ldots,N\}$ with full support (i.e all the $p(i)$'s are strictly positive and sum to $1$). Let $i_1,i_2,\ldots,i_T$ be an iid ...

7
votes

1
answer

359
views

### Diameter bound for graphs: spectral and random walk versions

This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and ...

4
votes

1
answer

249
views

### Does a subset with small cardinality represent the whole set?

Assume that we have heavy-tailed distribution $F(x)$ such that
\begin{align}
F(x)=\mathbb{P}[X\geq x]=x^{-0.5}.
\end{align}
Then, we produce $N$ independent samples $X_1,X_2,\ldots,X_N$ from this ...

2
votes

1
answer

177
views

### A question about convergence of stochastic processes converging to a random walk

Consider the following random walk $(y_t)_{t \in \mathbb Z_+}$:
$$y_t = y_{t-1} + u_t,\quad (u_t)_{t \in \mathbb Z_+} \overset{iid}{\sim} N(0,1), \quad (t \in \mathbb Z_+)$$
where $y_0, u_1, u_2,...$ ...

2
votes

1
answer

108
views

### Randomly chosen walk of fixed length

Let $G=(V, E)$ be the graph on vertices $V = \{0, \cdots, k\}^n$, where vertices $(v_1, \cdots, v_n)$ and $(w_1, \cdots, w_n)$ share an edge iff $\lvert v_i - w_i\rvert \leq 1$ for all $i$.
A walk of ...

1
vote

0
answers

72
views

### Reference for the asymptotic mixing time of the random walk on the cycle

In Diaconis's book Group Representations in Probability and Statistics, Chapter 3C, there are explicit computations for the mixing time of the random walk on the cycle graph $\mathbb{Z}_{p}$, with $p$ ...

5
votes

1
answer

172
views

### counting fixed-area closed walks on square 2d lattice

I want to count the number $N(n,A)$ of closed walks of length $2n$ on the square $2d$ lattice enclosing a signed area of $A$. These numbers refine $\sum_A N(n,A) = \left(\begin{array}{c}2n\\n\end{...