Questions tagged [random-walks]
The random-walks tag has no usage guidance.
509
questions
4
votes
1
answer
242
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 ...
- 1,897
3
votes
1
answer
330
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
5
votes
1
answer
105
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 ...
- 541
3
votes
2
answers
237
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 ...
- 8,672
4
votes
1
answer
311
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. ...
CommunityBot
- 1
6
votes
1
answer
209
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 ...
- 178k
3
votes
2
answers
233
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 ...
- 8,979
14
votes
5
answers
2k
views
Simple random walk on a locally finite graph: when is it recurrent?
I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My ...
- 60.2k
5
votes
0
answers
75
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 ...
- 741
16
votes
0
answers
821
views
Self-avoiding random walks that always turn
I am wondering if the statistics of self-avoiding random lattice-walks
on $\mathbb{Z}^2$
that turn left or right at each step (i.e., they cannot continue the
direction of the preceding step) have been ...
3
votes
0
answers
158
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$.
...
- 704
0
votes
1
answer
84
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,172
1
vote
1
answer
353
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,380
8
votes
2
answers
234
views
Particularities about the honeycomb lattice for the computation of connectivity constant
After reading the paper The connective constant of the honeycomb lattice equals $\sqrt{2+\sqrt{2}}$ by Hugo Duminil-Copin and Stanislav Smirnov (arXiv:1007.0575) published some time ago in Annals Math....
- 2,490
6
votes
3
answers
415
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)
$$ $$ \...
- 117k
7
votes
1
answer
277
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)....
- 14k
1
vote
1
answer
195
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,088
1
vote
0
answers
268
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
300
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 ...
- 14k
6
votes
1
answer
434
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$, ...
- 812
0
votes
1
answer
789
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^+...
- 117k
3
votes
1
answer
196
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:
...
- 14k
4
votes
1
answer
445
views
Probability that two walkers will meet on a graph
Consider two independent continuous random walks on a graph $G$ with adjacency matrix $A$. I am interested in the probability that the two walkers will ever meet.
When the graph is a $k$-regular ...
CommunityBot
- 1
23
votes
2
answers
905
views
Random permutations of Z_n
In "The maximum number of Hamiltonian paths in tournaments" by Noga Alon, the author states the following without proof (equation 3.1):
"Consider a random permutation $\pi$ of $\mathbb{...
- 4,618
2
votes
1
answer
673
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
172
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 &...
- 1,900
6
votes
3
answers
2k
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 ...
- 337
5
votes
1
answer
214
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 ...
- 708
2
votes
0
answers
70
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
8
votes
2
answers
307
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 ...
- 685
2
votes
2
answers
162
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{...
- 685
0
votes
1
answer
108
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 ...
- 117k
3
votes
1
answer
265
views
References for irrational random walks
I am interested in the symmetric random walk on $\mathbb{R}$ which increments have the discrete law $$\mu=\sum_{i=1}^q p_i (\delta_{\omega_i}+\delta_{-\omega_i})$$
where the $p_i$ sum to $1/2$ and the ...
CommunityBot
- 1
0
votes
4
answers
1k
views
Expected number of games until bust
The game allows you to bet only \$1 at a time, and if you win, you end up \$1 richer, otherwise you end up \$1 poorer. Probability of winning is $p=0.45$. If you start with \$1 - what is expected ...
- 137k
0
votes
1
answer
89
views
Recurrence criterion for non-reversible random walks on general infinite (locally finite) graph with unequal edge weights
Can someone please provide a reference (starting point) for analysing recurrence/transience of random walks on graphs with general edge weights? Looking into random walks that are known to be NOT ...
- 14k
2
votes
1
answer
147
views
Asymptotics of the return probabilities of a random walk on a transitive graph
Consider a random walk on an infinite connected vertex-transitive graph. Let $f(t)=P_{o,o}^{2t}$ be the probability that the random walk is at its origin at time $2t$. What can be said about the ...
- 14k
1
vote
0
answers
91
views
Does Anderson localisation occur if the potential are equal in pairs?
Consider the Anderson model given by the Hamiltonian $H \in B(l^2( \mathbb{Z}^d)) $ defined by $H = - \Delta + V$ where the potential $V$ acts on a unit vector $ \vert x \rangle \in l^2( \mathbb{Z}^d)...
6
votes
1
answer
286
views
Random walk with decreasing steps
I have a random walk $$R(t)= \sum_{n<t} X_n,$$ with $X_n \sim U(-\tfrac{1}{n^\alpha}, \tfrac{1}{n^\alpha}),$ where $X_n$ are independant and $\alpha >0$.
I think that someone must have studied ...
- 95
1
vote
0
answers
86
views
Understanding the statements of Theorem 5.5 and Lemmas 5.6, 5.7 and 5.8 from a French paper by Yves Guivarc’h and Émile Le Page
I would like to understand the statement and the proof Theorem 5.5 just for the special case when $X$ is a single point from the paper “Simplicité de spectres de Lyapounov et propriété d’isolation ...
1
vote
1
answer
513
views
Number of walks on a graph passing through a specific vertex
Let $\mathcal{G}$ be a simple (no self-edges) undirected graph with $N$ vertices, and denote $\mathbf{A}$ its adjacency matrix: $A_{ij}=1$ if there exists an edge between vertex $i$ and vertex $j$.
$\...
- 30.6k
2
votes
1
answer
148
views
Inducing maps between Martin boundaries
This is a reworking of a question I asked on math.se.
Given two countable discrete metric spaces $X_{1}$ and $X_{2}$, each equipped with a (irreducible and transient)* random walk given by transition ...
CommunityBot
- 1
2
votes
0
answers
105
views
Moment of the hitting measure of a subgroup
Given a [finitely generated] group $G$ and a finite generating set $S$, a measure $\mu$ will have finite $\alpha$-moment if $\sum_{g \in G} \mu(g) |g|_S^\alpha$ is finite (where $|g|_S$ is the word ...
- 4,342
1
vote
1
answer
340
views
Reference: probability distribution of first meeting time of two random walks on a cycle graph
I am looking for a reference or derivation for the following question:
Consider a cycle graph $G$ with $N$ vertices (see example here). Let two independent continuous-time random walkers$^\star$ start ...
- 14k
0
votes
0
answers
243
views
Unexpected autocorrelations in sequence of primes modulo 4
It is well known that there is a little bias in the distribution of prime residues modulo 4. But the bias eventually vanishes. I looked at the first million primes, and the counts are as follows:
...
- 3,088
1
vote
2
answers
84
views
Lower-bound on zero-crossing probability of the nonstationary gaussian process $X(t) = tU+(1-t^2)^{1/2}V$, with $(U,V) \sim N(0,I_2)$
Let $(X(t))_{t \in [-1,1]}$ be a centered non-stationary smooth gaussian process with covariation function $\rho(t,s) = \mathbb E[X(t)X(s)]$. For $t_0 \in (-1,1)$ and $\epsilon \in (-1-t_0,1-t_0)$, ...
- 6,726
19
votes
0
answers
2k
views
xkcd's "Unsolved Math Problems", straight lines in random walk patterns
STEM student's favourite source of amusement posted a comic titled "Unsolved Math Problems" one of which looks like something that could actually be tackled.
If I walk randomly on a grid, ...
- 11.4k
0
votes
1
answer
67
views
Random walks on GW-trees (transformation)
Let $(X_n)_{n\in\mathbb{N}_0}$ be a biased Random Walk on Galton-Watson tree with $\lambda\in(\lambda_c,m)$.
How can I obtain the following equation:
$\sum_{k=0}^{n-1}\mathbb{E}_{e_*}[|X_{k+1}|-|X_k| \...
- 14k
1
vote
1
answer
61
views
Random walks on GW-trees (regeneration epochs/survival set)
Let $\Gamma_0,\Gamma_1,...$ be regeneration epochs.
If $(X_n)_{n \in \mathbb{N}}$ is a $\lambda$ biased random walk on a Galton-Watson tree, than the regeneration epochs are defined as:
$\Gamma_0:=\...
- 14k
7
votes
1
answer
1k
views
On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
- 6,571
1
vote
1
answer
181
views
Asymptotics of cumulative Liouville function under RH versus simple random walk
The expectation values of the 1D simple random walk $S_n$ can be shown to have the asymptotic behavior of
$$ \lim_{n\to\infty} \frac{a_n}{n^{1/2}} = \sqrt{\frac{2}{\pi}}, \tag{1}\label{1}$$
with $a_n =...
- 60.2k