# Questions tagged [random-walks]

The random-walks tag has no usage guidance.

491
questions

-1
votes

1
answer

57
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

154
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

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

7
votes

0
answers

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

0
votes

1
answer

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

6
votes

1
answer

183
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

239
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

136
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

92
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

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

4
votes

1
answer

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

2
votes

0
answers

66
views

### Random walks on randomly evolving graphs

I am interested in analyzing a random walk on a growing tree with vertices labelled on a tree with following properties.
The number of nodes at depth $k$ is a an exponential function of $k$. One can ...

0
votes

0
answers

73
views

### Convergence bounds for ergodic random walk

We are given a simple connected graph $G(V,E)$, where $V$ and $E$ denote the vertex and edge sets respectively. Let $G'(V,E')$ be the graph generated by $G$ by adding one self-loop edge for each ...

1
vote

1
answer

86
views

### Phase space Brownian bridge

I understand the concept of the 1 dimensional Brownian bridge with the form of:
$$dx_t=\frac{-1}{1-t}x_t \, dt + dw_t$$
s.t. $x_0=0$ and $x_1=0$
where $dw_t$ is a Wiener process.
I am thinking about ...

0
votes

1
answer

70
views

### Reference request: $\mathbb{E}|X_t| \to \infty$ as $t \to \infty$ when $\{X_t\}_{t\geq 0}$ is a continuous-time (symmetric) random walk

Let $\{X_t\}_{t\geq 0}$ be a one dimensional continuous-time (symmetric) random walk on $\mathbb Z$ defined via $$X_t = X_0 + \sum_{i=1}^{N_t} Y_i,$$ where $X_0 \in \mathbb{Z}_+$ is a non-negative ...

5
votes

1
answer

273
views

### Probabilistic problem on random spanning trees

Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....

3
votes

2
answers

309
views

### Random spanning trees probability problem

We are given a simple connected graph $G(V,E)$ with vertex and edge set $V$ and $E$ respectively. For any vertex $v\in V$, let $D_T(v)$ the degree of $v$ in a uniformly generated random spanning tree $...

4
votes

1
answer

181
views

### Derive the solution of the diffusion equation from the solution of a random walk

Summary
The probability distribution (pdf) of a random walk in 1 dimension is represented by a Bessel function. On the other hand, the pdf of a Brownian motion in free space is represented by a ...

0
votes

0
answers

27
views

### Upper bound of probability for random walk ending in an interval while hitting a wall in the past

The title of this problem may sound weired. Formally what I want to bound from above is the following. Let $X_k$ be independent random walk increments with finite variances and their means are bounded ...

0
votes

0
answers

163
views

### The meaning of random number generator test failing

I have a random number generator (number theoretic) that passes all of the NIST tests except the random excursions test. Is there any deep dark meaning to this? To amplify "deep dark meaning"...

1
vote

2
answers

134
views

### Asymptotic properties of weighted random walks / infinite convolutions of random variables

Let $(X_n)_{n\in\mathbb{N}}$ be a sequence of i.i.d. real-random variables. Let further $0<c<1$. I'm interested in the asymptotic properties of
$$
\sum_{k=1}^n c^k X_k.
$$
I can prove that this ...

1
vote

1
answer

77
views

### A question about the square root error of one dimensional random walks

Consider a one dimensional random walk, in which the probability of moving left along a line is $q=1/2$ and the probability of moving right is $p=1/2$. The square root error $\langle d_N \rangle$, ...

7
votes

1
answer

207
views

### Counting returns in null-recurrent random walk

Consider two independent copies of IID random walk on ${\bf Z}$ starting from $0$, and let $N_1(t)$ (resp. $N_2(t)$) denote the number of times, up to time $t$, that the first (resp. second) walker ...

4
votes

1
answer

235
views

### Random walk visiting a cylinder infinitely often

I wonder whether a $d$-dimensional random walk $S_n$, generated by the infinite i.i.d. copies of X given by:
$X=e_1=(1, 0, 0, ..., 0)$ (with probability $p_1$)
$X=e_2=(0, 1, 0, ..., 0)$ (with ...

3
votes

1
answer

314
views

### Importance resampling with exponential weighting

Suppose that we have
$$
\frac{p(x)}{q(x)} \propto \exp(\tau f(x)),
$$
where we can sample from $q$ but not from $p$. Our goal is to generate a set of particles $\{x_i\}_{i=1}^n$ such that $n^{-1}\sum_{...

2
votes

2
answers

212
views

### Is there something like a "self-avoiding Markov chain" on a continuous space?

If stumbled accross self-avoiding walks. They seem to be deterministically generated, but from a quick google search term seem to be randomly generated variants.
However, as far as I can see they are ...

5
votes

1
answer

103
views

### Asymptotic expansion for the number of self-avoiding random walks

This question is cross-posted from https://math.stackexchange.com/questions/4580314/asymptotic-expansion-for-the-number-of-self-avoiding-random-walks.
Let $c_n$ be the number of self-avoiding random ...

6
votes

1
answer

195
views

### Origin of the term "connective constant"

Let $G$ be a vertex-transitive locally finite graph and $c_n$ the number of self-avoiding walks in $G$ starting from some fixed vertex $v_0$. One can easily see that $c_{m+n} \leq c_m c_n$ and hence ...

2
votes

0
answers

105
views

### General ballot theorem: sum of independent but not identically distributed random variables?

Is there ANY ballot-type result for random walk $S_n:=\sum_{i\le n}X_i$ that allows for independent but not identically distributed random variables $X_i$, up to some uniform concentration conditions ...

3
votes

2
answers

219
views

### Elementary cellular automata in stochastic modes

There are several ways to run a given elementary cellular automaton in a stochastic way:
by giving for each of the eight local configurations 000,100,010 and so on a probability by which the rule is ...

4
votes

1
answer

269
views

### Minimum of random walks

Let $M$ independent and identical random walks that follow the chi-squared distribution, i.e. in each step, a $X^2_1$ random variable is added. I am interested in the minimum random walk at each step. ...

5
votes

0
answers

69
views

### Logarithmic speed walks on trees

Let $T$ be the infinite $3$-regular tree, equipped with the shortest path metric $d_T$. An infinite walk on $T$ is a map $f:\mathbb{N}\to T$ such that $d_T(f(a),f(a+1))\leq 1$ for all $a$.
An infinite ...

3
votes

0
answers

123
views

### Conditional distribution of steps of random walk given the sum

Set-up. Consider a random walk $S_n=\sum_{i=1}^n X_i$, where $\{ X_i, 1\leq i < \infty \} $
is a sequence of i.i.d. random variables with distribution $\mu$, $\mathbb{E}X_1 = 0$. Let $a > 0$.
...

0
votes

1
answer

52
views

### Skip-free random walks: recurrence and transience

Let us define a one dimensional random walk: for all $n\in\mathbb{N}$
$$
X_n:=\sum_{i=1}^nZ_i
$$
with $Z_i$ i.i.d. random variables taking values in $\{-1,0,1,2,\dots\}$. This process is sometimes ...

1
vote

1
answer

298
views

### How fast does this Gaussian random walk move away from the origin?

Suppose $z_i$ are IID zero-centered $d$-dimensional Gaussian random variables with unit-trace covariance $\Sigma$ and $g(z_i)$ is the sum of its components.
Consider the following random walk:
$$x_s=\...

6
votes

3
answers

333
views

### Parameterized simple asymmetric random walk

Let $ t>0 $, and we look at the random walk $S_{n}=\sum_{i=1}^{n}X_{n}$ on $\mathbb{Z}$ with $S_0=0$ where $$ \mathbb{P}\left(X_{n}=1\right) =\frac{1}{2}\left(1+\frac{1}{n^{t}}\right)
$$ $$ \...

2
votes

1
answer

163
views

### Bernoulli trials with small dependencies: asymptotics (central limit theorem, law of the iterated logarithm)

Let $\{X_k\}$ be a sequence of random variables, with $X_k\in\{+1, -1\}$ for $k>0$, generated as follows.
First, define $S_n=X_1+\dots +X_n$, with $X_0=S_0=0$, and let $0<\beta<\frac{1}{2}$.
...

7
votes

1
answer

252
views

### Local probabilities for lattice random walk

Let $\epsilon <1/2$. Let $X$ be a random variable in $\mathbb Z$ such that $\mathbb P (X=x)\le \epsilon $ for any $x\in \mathbb Z$ (you may add any moment or regularity conditions on $X$ if needed)....

1
vote

0
answers

103
views

### Distribution of a random summand conditional on the sum of independent identically distributed copies

The question is simple to state:
Let $S_n = \sum_{i=1}^n X_i$, where $X_i$ are independent random variables with a common distribution $F$. For simplicity, assume that $X_i \geq 0$ with prob. 1, and ...

0
votes

1
answer

194
views

### Invariance principle: Brownian bridge and random walk conditioned on end point

Let $\{X_i, i \in \mathbb{N}\}$ be a sequence of non-lattice i.i.d. centered random variables, $\mathbb{E} |X_1| ^3 < 0$. Let $S_n = \sum\limits _{i=1} ^n X_i$ be the corresponding random walk and ...

6
votes

1
answer

361
views

### Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes.
Let
$H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...

0
votes

1
answer

399
views

### Simple random walk return time

Let's take a simple random walk on $\mathbb{Z}$, $(S_n)_{n\geq0}$, started at zero. If $\tau^+_0 = \inf\{n \geq 1: S_n = 0\}$ is the first time the walk returns on zero, we know that $\mathbb{E}[\tau^+...

3
votes

1
answer

166
views

### Simple random walk with an extra condition

Consider a simple random walk $$\mathcal{X}_t= \sum_{n<t} X_n,$$ where $P(X_n=1)= P(X_n=-1)= 1/2.$
If I put an extra condition that excludes cases with more than 5 consecutive +1, or -1 in the sum:
...

2
votes

1
answer

450
views

### Probability that a symmetric random walk returns to $0$ exactly $k$ times in $2n$ steps

I'm trying to find a formula to find the probability of exactly k returns in 2n steps of a symmetric random walk. More specifically, I am trying to show that the probability of 2 returns is exactly ...

3
votes

1
answer

143
views

### Carne-Varopoulos bound and stationary measure

Let $\Gamma$ denote the Cayley graph for a finitely generated group $G$, and let $p_n(x, y)$ denote the transition probability that a random walk starting at $x$ reaches $y$ at time $n$. A famous &...

2
votes

0
answers

58
views

### Handling sums of correlated random variables with a directed path structure

Recently, I've been seeing random variables with the following correlation structure based on directed paths on a graph. For example, there are $16$ directed paths "directed downwards from the ...

5
votes

1
answer

176
views

### Second Skorokhod embedding in high dimensions

The first Skorokhod embedding theorem says that any random variable $X$ with $\mathbb E X=0$ and $\mathbb E X^2<\infty $ can be written as $X=B_{\tau }$ where $B$ is a Brownian motion and $\tau$ is ...

8
votes

2
answers

256
views

### Does entropy of the random walk control the return probability

Given an infinite connected graph $G$ of bounded degree with vertex set $X$, let $P_x^n$ the time $n$ distribution of the simple random walk started at the vertex $x$ (so $P^n_x(y)$ is the probability ...

2
votes

2
answers

136
views

### Which infinite random graphs with percolation threshold $p_c=0$ are transient?

I am interested in long-range percolation models with heavy-tailed degree distributions such as DHH13, GLM21, Y6. The simplest example is scale-free percolation in which vertices are elements $\mathbb{...

0
votes

1
answer

92
views

### Non-linear diffusion on networks

The diffusion equation with constant diffusion $D$ can be represented as:
\begin{equation}
\frac{\partial \phi(r, t)}{\partial t}=D \Delta \phi(r, t)
\end{equation}
where
$\Delta$ is the Laplace ...