Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
116 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
1answer
134 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
0answers
78 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
1answer
148 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}+\...
1
vote
1answer
192 views

Symmetric random walks - bounds on the amount of time spent in a subset $A$?

For a symmetric random walk $S_n$, if we have a bound $P(S_n \in A) < \delta$, do we get a bound on the amount of time $S_n$ spends in $A$? Let $S_n$ be a symmetric random walk on the integers. ...
2
votes
1answer
92 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 ...
2
votes
0answers
57 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. ...
0
votes
0answers
16 views

Non linear random walk on 1D lattice

Consider a random walk on a $1$ dimensional lattice, where the probability $q_i(t)$ that the particle is at site $i$ at time $t$ obeys the following equation: \begin{equation} \frac{ \mathrm{d}}{ \...
1
vote
1answer
122 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 ...
4
votes
0answers
59 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 ...
1
vote
1answer
193 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 ...
6
votes
1answer
99 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
1answer
64 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 ...
26
votes
6answers
20k views

When do 3D random walks return to their origin?

The probability of a random walk returning to its origin is 1 in two dimensions (2D) but only 34% in three dimensions: This is Pólya's theorem. I have learned that in 2D the condition of returning to ...
1
vote
0answers
105 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 ...
0
votes
0answers
38 views

random walk on a bounded surface

apologies in advance for this under formed question. I'm trying to model a random walk process on some 2D surface (like a sphere or cylinder). I have been having some trouble finding literature on ...
0
votes
1answer
122 views

Random walk with exponential decay

A problem which arises in learning algorithms is $$x_{k+1}= \alpha x_k + \beta e_k$$ where $x_k$ is the scalar state variable at time $k$ and $e_k$ is an independent $\mathrm{Normal}(0,1)$ excitation ...
9
votes
1answer
263 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
0answers
54 views

Generalization of the Liouville function and its pseudorandomness

The Liouville function $\lambda(n)$ can be defined via the function $\Omega(n)$, that gives the number of not-neccessarily distinct prime factors of a positive integer $n$ as $$ \lambda(n):= (-1)^{\...
0
votes
1answer
84 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
1answer
34 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 ...
13
votes
2answers
760 views

A comprehensive list of random walk inequalities?

I am interested in finding a comprehensive list of all noticeable random walk inequalities. ie. $S_n = \sum_{k\leq n} X_i$ for i.i.d symmetric $X_i$ I can only seem to find books/papers that list ...
16
votes
3answers
998 views

Does a random walk on a surface visit uniformly?

Let $S$ be a smooth compact closed surface embedded in $\mathbb{R}^3$ of genus $g$. Starting from a point $p$, define a random walk as taking discrete steps in a uniformly random direction, each step ...
3
votes
2answers
268 views

Hitting probability of a line

Consider a simple (nearest neighbor) random walk on a lattice $\Bbb Z^2$ which starts at the origin, is constrained to $x\ge 0$ halfplane, and stops when it hits the line $x=n$. Denote by $p(n,k)$ ...
1
vote
0answers
34 views

Probability that a modified $c$-bounded lattice walk is also $c$-bounded

Let $\mathcal{B}_n^{(c)}$ be the set of $n$ step lattice bridges (starts at $(0,0)$ ends at $(n,0)$), taking steps $\{(1,1), (-1,1)\}$ bounded between $y = c$ and $y = -c$ for a constant $c \geq 0$. ...
7
votes
0answers
102 views

Sum of variables uniformly distributed on a circle: a cyclic property

Consider a random walk starting at the origin in the plane, walking $n$ steps in independent uniformly random directions with step lengths $a_1,\ldots,a_n$, and observing the distance from the origin. ...
7
votes
1answer
122 views

Uniqueness of stationary measures for $(G,\mu)$ boundaries

Let $G$ be a countable group acting minimally by homeomorphisms on a compact Hausdorff space $X$ and $\mu$ be a probability measure on $G$ whose support generates $G$ as a semigroup. Let $\nu$ is a $\...
0
votes
0answers
47 views

Moment generating function of a stopped process from Wald's identity

In an exercise I am asked to prove the following Wald's identities: let $S_n$ be a simple random walk and $T$ a stopping time. Then for all $\lambda \in \mathbb R,$ $$ \mathbb E(e^{\lambda S_1}) = 1 \...
1
vote
0answers
65 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 $ \mid {x} \rangle  \in l^2( \mathbb{Z}^...
0
votes
1answer
73 views

Probability to cross an envelopp for 1D random walk?

Imagine we have an evolving sequence composed of 1 and -1 (ex: -1-11-111...) where the probability to get -1 or 1 is 1/2. n is the lengh of my sequence. I can make an analogy with random walk: let ...
4
votes
0answers
73 views

Random walks on the Poincaré disk

Let $G$ be the group of isometries of the Poincaré disk. Let $\mu$ be a probability measure on $G$, and consider $g_1,..,g_n$ i.i.d. random variables on $G$ distributed according to $\mu$. For $z\in \...
1
vote
1answer
69 views

multi-time limit of a maximum of random walks

Suppose one has $N$ iid random walks $X^{(1)}_t,\ldots,X^{(N)}_t$ in discrete or continuous time $t$, let us say for example Poisson jump processes, and consider the stochastic process $Y^{(N)}_t = \...
0
votes
1answer
104 views

Probability to cross dynamic boundary for 1D-random walk?

context: Imagine we have an evolving bit sequence (ex: 001011...) where the probability to get 0 or 1 is 1/2. n is the lengh of my sequence (the number of bits) I can make an analogy with random walk: ...
4
votes
1answer
84 views

Meeting time lower bound for a random walks on a large finite graph of bounded degree

Let $X_t$ and $Y_t$ be independent continuous time random walks on the same connected undirected finite graph $G=(V,E)$. The meeting time $T$ is defined as $T:=\inf\{t>0:X_t=Y_t,X_{t-}\neq Y_{t-}\}$...
4
votes
2answers
483 views

How does a quasi-isometry affect Poisson or Martin boundaries?

Take two graphs (of bounded valency) or manifolds (f bounded geometry) $G$ and $G'$. Assume there is a quasi-isometry $f:G \to G'$, and assume the Poisson or Martin boundary of $G$ is known, what may ...
0
votes
1answer
108 views

Connective constant of a hexagonal lattice

The connective constant of the honeycomb lattice equals $\sqrt{2 + \sqrt{2}}$ by Hugo Duminil-Copin and Stanislav Smirnov (arXiv:1007.0575) is the research paper I have read. My only doubt is equation ...
4
votes
3answers
207 views

Does the Green's function of the simple random walk on $\mathbb Z^d$ always vary locally?

Let $G_0(x)=G(x,0)$ be the Green's function of the simple symmetric random walk on $\mathbb Z^d$, $d\geq 3$. The question is whether $G_0$ must always vary locally, i.e., whether $$ \sum_{\substack{y\...
1
vote
0answers
30 views

Small parameter expansion of probability density

I am trying to describe the motion of a particle that moves according to the Langevin equations \begin{align} \dot{x}&(t)=v_0\cos{\beta(t)},\tag{1}\\ \dot{y}&(t)=v_0\cos{\beta(t)},\tag{2} \end{...
4
votes
3answers
220 views

Does there exist a non-recurrent acyclic graph with sublinear expansion?

Let $\Gamma$ be a simple, locally finite, acyclic graph. Let $v_0$ be some vertex in $\Gamma$. We let $X_n$ denote the simple random walk on $\Gamma$ where $X_0 = v_0$. If we almost surely have $\...
7
votes
1answer
231 views

Local limit theorem for random walks on $\mathbb Z^d$

I'm looking for a reference for the following claim. Let $W(n)$ be a centered random walk on $\mathbb Z^d$ with $W(0)=0$. Suppose that $W(n)$ has a finite second moment. Let $n\ge 1 $ and $k \in \...
1
vote
0answers
81 views

Concentration for $\sum_{i=1}^n y_i \psi(x_i^\top u)$, for $y_1,\ldots,y_n \sim \{\pm 1\}$ and $x_1,\ldots,x_n$ uniform iid on hypersphere

Let $y_1,\ldots,y_n$ be drawn iid uniformly from $\{\pm 1\}$ and let $x_1,\ldots,x_n$ be drawn iid uniformly from the unit-sphere $(d-1)$-dimensional sphere $\mathbb S_{d-1}$, and independently from ...
0
votes
0answers
102 views

Closed non-backtracking walks and eigenvalues of the adjacency matrix in non-regular graphs

Let $\Gamma$ be an undirected finite graph. Write $M_r$ for the number of non-backtracking closed walks of length $r$ in $\Gamma$, i.e., walks where a step is never followed by its inverse. Let $A$ be ...
9
votes
4answers
418 views

The min of the mean of iid exponential variables

Let $X_1, \ldots, X_n, \ldots$ be iid exponential random variables with mean 1. It is well-known that $\min_{1\le j < \infty} \frac{X_1 + \cdots + X_j}{j}$ follows the uniform distribution U(0,1). ...
0
votes
2answers
134 views

Last crossing of a line by a random walk

Let $X_1, X_2, ...$ be i.i.d. random variables, $\mathbb{E} X_1 > 0$, and let $S_n = \sum\limits _{i = 1} ^n X_i$. Define $\tau = \max \{n \in \mathbb{N}: S_n \leq 0 \}$ with the convention $\tau =...
1
vote
0answers
111 views

Arcsine law for gaussian random walk

Consider the random walk $S_i=Z_1+\dots+Z_i$, where the $Z_i$'s are iid $N(0,1)$ and $i\in\{1\dots n\}$. Is there an arcsine law, similar to the one for the $\{\pm 1\}$ case?
5
votes
0answers
116 views

Random process on a sequence of rolls of an $n$-sided die

Let $\ X:=X_{k\,n}\ $ be a random variable of a $n$-sided die where $\Pr(X=i)=\frac{1}{n}$ for each $i\in\{1,2,\ldots,n\},\ $ where $\ k\in\{1, 2, \ldots,n\}\ $ and $\ n\ $ are fixed. Let $t$ be a ...
2
votes
0answers
121 views

Random walk with cyclic randomness

Let $S=\{0,1\}^n$ be a binary string of length $n$. Suppose you pick a number $r$ at random from any distribution on $\{1,\ldots,R\}$ of your choice and randomly generate $r$ boolean hash functions $...
2
votes
2answers
145 views

Discrete random walk and SDEs

My advisor has some vague ideas about the relation between discrete random walks and SDEs, and advise me to read a little bit about them. To be more precise, ( if I understand correctly what my ...
1
vote
1answer
169 views

Winning money from random walks?

The same question was posted on StackExchange. Informal problem description Assume that we have a stock whose price behaves exactly like a Wiener process. (There are multiple reasons why this is not ...
3
votes
1answer
315 views

proof that the covariance function for a fractional Brownian motion / fractional Gaussian free field is well defined

Given $0 < t_1 < \dots < t_n$, we can show that the matrix $\Omega$ whose entries are defined by $M_{i,j} = min(t_i,t_j)$ is symmetric definite positive. The proof is immediate once one ...

1
2 3 4 5
9