# Questions tagged [random-walks]

The random-walks tag has no usage guidance.

461
questions

1
vote

1
answer

233
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

280
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)
$$ $$ \...

0
votes

0
answers

12
views

### Adjust edge weights via heading on hexagon

I wish for a way to adjust weights based on the edges / directions of a hexagon. If a heading agrees with a certain edge (perpendicular to an edge), then the weights should be distributed as such: ...

2
votes

1
answer

124
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

231
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

45
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

81
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

286
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

96
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

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

0
votes

0
answers

68
views

### Concentration of $\mathbf{x}^TA\mathbf{x}$, with $\mathbf{x}$ a Rademacher sequence

Let $\mathbf{x}$ be a Rademacher sequence of length $n$, i.e., $\mathbf{x} \in \{-1,1\}^n$ uniformly at random. Let $A \in \mathbb{R}^{n \times n}$ symmetric, with $A_{jj} = 0$, and $|A_{jk}| \leq 1$, ...

0
votes

0
answers

39
views

### Return probabilities for heavy tailed random walks

I need a reference to an explicit asymptotic formula for the return probabilities for random walks on $\mathbb Z$ with heavy tailed symmetric step distributions. More specifically, for an explicit ...

2
votes

1
answer

207
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

96
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

44
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

135
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

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

1
vote

2
answers

96
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

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

0
votes

4
answers

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

0
votes

1
answer

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

2
votes

1
answer

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

5
votes

1
answer

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

1
vote

0
answers

77
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

121
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$.
$\...

4
votes

1
answer

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

0
votes

0
answers

79
views

### Length of walking on a graph

Given a finite directed connected graph $G$,
let $P_{circle}$ be the set of finitely long circle paths on $G$
(a circle path is a path with identical starting and ending vertex).
It is well known that ...

2
votes

0
answers

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

8
votes

2
answers

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

0
votes

0
answers

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

1
vote

1
answer

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

1
vote

2
answers

69
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)$, ...

19
votes

0
answers

1k
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, ...

0
votes

1
answer

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

1
vote

1
answer

55
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:=\...

1
vote

0
answers

32
views

### Hitting distribution of a sub-lattice

Let $\{X_n\}$ be the simple random walk in dimension $d=2$. Consider the distribution
$$
p^M(0,y)=\mathbb{P}_0[X_{\tau_{M}}=M \cdot y]
$$
where $\tau_M:=\inf \{n \ge 1: X_t \in M \cdot \mathbb Z^d \}$ ...

1
vote

1
answer

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

2
votes

1
answer

124
views

### Discrete random walk on polytope via involutions

Let $P$ be a convex polytope (or more generally convex body, I suppose) in $V=\mathbb{R}^n$. For each $v\in \mathbb{P}V$, we define an involution $\tau_v\colon P\to P$ by setting $\tau_v(p)$ to be the ...

2
votes

1
answer

153
views

### Random walk always stays below a level $a$

Suppose we have a random walk $S_n$ with i.i.d. steps $X_i$. We assume that
$$\mathbb{E}[X_i] = -\mu, \text{Var}[X_i] = 1,$$
where $\mu$ is close (or going) to zero. We also assume that the moment ...

1
vote

0
answers

86
views

### A random process with conserved momentum: 'particle decay'?

Consider a particle $p_1$ moving at unit speed along a straight line in $\mathbf{R}^2$, directed by some vector $v_1 \in \mathbf{S}^1$. Equid this particle with a Poisson clock $\tau_1$, with ...

1
vote

1
answer

174
views

### Random walks on Galton–Watson trees

I am working on a paper of Elie Aidekon : ‘Speed of the biased random walk on a Galton–Watson tree’ and have a question about one transformation in a proof:
\begin{align}
& 1+\frac{1}{1-\lambda}+\...

2
votes

1
answer

144
views

### Occupation time of non-stationary random walk

Assume $\varepsilon \in [0,1/2]$. Consider the discrete-time random walk $X_0 = 0$, $X_{t+1} - X_t \sim f(X_t) \delta_0 + (1-f(X_t))\operatorname{Rademacher}$, where $\delta_0$ is the Dirac delta on ...

3
votes

0
answers

65
views

### Probability of filling a small ball before exiting a big one for $d=2$

Let $S_n$ be the simple random walk in dimension $d=2$. Let $0<r<R$ and $\alpha \in (0,1)$. Let $B_r$ denote the $\{x \in \mathbb Z^2: \|x\|\le r\}$ where $\|\cdot\|$ is the Euclidean norm. ...

4
votes

0
answers

94
views

### A random walk/ruin theory problem with steps whose distribution has infinite mean

In what follows, I will make liberal use of the notations and terminology from ruin theory, just because I think it makes matters more intuitive. However, the problem I'm posing does not depend on its ...

6
votes

1
answer

115
views

### Uniform upper bounds for the return probability of random walks on $ \mathbb{R}$

Let $\mu$ be a probability measure with finite support on integers or the real line with the property that $\mu( 0) \le p$ for a fixed $0<p <1$. Let $S_n$ denote the random walk starting at $0$,...

0
votes

1
answer

98
views

### Mixing time for random walk on graph with $k$ loops on each vertex

I try to find an upper bound for the mixing time of a random walk $S$ on a connected graph $L=(V,E)$ which has $k<\min_{v\in V}d(v)$ loops at every vertex. The transition probabilities of this ...

1
vote

0
answers

129
views

### Random walk on 2d lattice with obstacles

Consider a random work on $L=\mathbb Z^2$ endowed with obstacles (i.e each cell $(x,y)$ of $L$ may contain a obstacle, i.e the random walk halts whenever it hits such a cell). Let $P(x,y) = 1$ if cell ...

9
votes

1
answer

345
views

### Random walk on infinite graph

Let $G$ be an infinite countable non-oriented connected graph with bounded degrees. Let $X(n)$ be the lazy random walk on $G$ and let $u,v$ be two vertices. Does the ratio
$P(X(n)=v)/P(X(n)=u)$
tend ...

0
votes

1
answer

85
views

### Probability of random crossing a specific value any time

Let $x(t+1) = x(t) + e(t)$, $e(t)$ iid $\mathcal{N}(0,1)$. What is the probability of $x(s)> c$, for any $0<s<T$?
Calculation for any specific $s$ is easy. But I am looking for the ...

1
vote

1
answer

37
views

### Random linear map contracting distances on the projective line

Let $P^1$ be the real projective line, identified with lines of $\mathbb{R}^2$. Let $\mu$ be a probability measure on invertible linear map of $\mathbb{R}^2$ and let $(A_i)$ be i.i.d. random variables ...