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 $(...
- 1
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, ...
- 148k
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, ...
- 155
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 ...
- 243
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,446
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 ...
- 201
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,...$ ...
- 161
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 ...
- 123
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$ ...
- 111
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{...
- 433
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 ...
- 121
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,657
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 ...
- 13
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 ...
- 646
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\}$....
- 1,657
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 $...
- 1,657
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 ...
- 179
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 ...
- 607
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"...
- 95k
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$, ...
- 1,008
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 ...
- 19k
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 ...
- 91
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_{...
- 1,117
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 ...
- 81
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 ...
- 531
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 ...
- 607
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 ...
- 9,492
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 ...
- 701
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$.
...
- 694
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
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=\...
- 2,278
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)
$$ $$ \...
- 65
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}$.
...
- 3,036
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)....
- 723
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 ...
- 103
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 ...
- 694
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$, ...
- 73
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
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:
...
- 85
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 ...
- 21
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 &...
- 31
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 ...
- 469
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 ...
- 723
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 ...
- 4,334
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 ...
- 87