# Questions tagged [random-walks]

The random-walks tag has no usage guidance.

428
questions

**2**

votes

**1**answer

113 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

131 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

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

**1**answer

147 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

90 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

**0**answers

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

**0**answers

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}}{ \...

**4**

votes

**0**answers

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

**6**

votes

**1**answer

97 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

63 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

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

**0**answers

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

**9**

votes

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**

votes

**1**answer

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

**3**

votes

**2**answers

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

**0**answers

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

**16**

votes

**3**answers

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

**7**

votes

**0**answers

101 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

**1**answer

121 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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

68 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 = \...

**4**

votes

**1**answer

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

**0**

votes

**1**answer

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

**1**

vote

**1**answer

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

**1**

vote

**0**answers

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

**3**answers

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

**4**

votes

**3**answers

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

**1**answer

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

**0**

votes

**1**answer

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

**1**

vote

**0**answers

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

**0**answers

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

**0**

votes

**2**answers

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

**5**

votes

**0**answers

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

**1**

vote

**0**answers

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?

**1**

vote

**1**answer

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

**0**

votes

**0**answers

35 views

### 2d interpolation minimizing the integral of the norm of the Hessian

It is well known that cubic interpolation is the solution of the interpolation problem that minimizes the integral of the square of the second derivative:
$$ min_{f \text{ s.t. } f(x_i)=y_i} \int (f''(...

**3**

votes

**1**answer

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

**2**

votes

**2**answers

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

**0**

votes

**1**answer

77 views

### Coalescence of random walks in 3D

I'm starting to work in random walks and I have two big questions I would like to have suggestions about.
(1) Consider a system of N point particles undergoing Brownian motion (random walks) on a 3D ...

**0**

votes

**0**answers

15 views

### Integrate a high dimensional multivariate polynomial distribution over some convex region

I am reading the Foundation of Data Science By Blum, John Hopcroft, and Ravindran Kannan.
The question in the chapter of random ...

**5**

votes

**1**answer

185 views

### Random walk on $\mathbb{Z}^2$ going forward with probability $p$

Consider a random walk on $\mathbb{Z}^2$ which goes forward (i.e. takes a step in the same direction as the last step) with probability $p$ and turns right and left with probability $\frac{1-p}{2}$ ...

**9**

votes

**4**answers

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

**11**

votes

**1**answer

2k views

### Biased random Fibonacci sequences

I have recently been toying (very superficially) with the random Fibonacci sequence, i.e., defined by $F_0=1=F_1=1$ and
$$
F_{n} = F_{n-1} + \varepsilon_n F_{n-2}
$$
where $(\varepsilon_n)_{n\geq 2}$ ...

**1**

vote

**0**answers

261 views

### Growth rate of exponential sum of $S_j$

Let $X_j$, $1 \leq j \leq n$ be chosen i.i.d. uniform over $[0,2\pi)$. Denote $S_j \triangleq X_1 +X_2+\cdots+X_j$ and suppose that $c_j$, $1 \leq j \leq n$ are some constants such that $|c_j|=1$.
I'...