Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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: ...
  • 101
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)....
  • 723
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 ...
  • 115
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 ...
  • 664
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: ...
  • 85
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 ...
  • 15.6k
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 ...
  • 21
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 ...
  • 723
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 ...
  • 4,244
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 ...
  • 107
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 ...
  • 15
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 ...
  • 927
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 ...
  • 85
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$. $\...
  • 139
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 ...
  • 107
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 ...
  • 909
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 ...
  • 4,244
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....
  • 1,296
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 ...
  • 139
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)$, ...
  • 5,870
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, ...
  • 309
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| \...
  • 65
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:=\...
  • 65
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 \}$ ...
  • 406
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 ...
  • 19.6k
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 ...
  • 363
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 ...
  • 2,949
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. ...
  • 406
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$,...
  • 5,802
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 ...
  • 103
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 ...
  • 5,870
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 ...
  • 723
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 ...

1
2 3 4 5
10