Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
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
1answer
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
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
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
1answer
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
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}}{ \...
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 ...
6
votes
1answer
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
1answer
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
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
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
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 ...
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 ...
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$. ...
16
votes
3answers
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
0answers
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
1answer
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
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
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
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-}\}$...
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: ...
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 ...
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
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
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 \...
0
votes
1answer
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
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 ...
0
votes
2answers
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
0answers
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
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?
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 ...
0
votes
0answers
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
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 ...
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 ...
0
votes
1answer
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
0answers
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
1answer
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
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). ...
11
votes
1answer
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
0answers
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'...

1
2 3 4 5
9