# Questions tagged [random-walks]

The random-walks tag has no usage guidance.

410
questions

**7**

votes

**1**answer

92 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

40 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

54 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}^...

**-2**

votes

**0**answers

53 views

### Mean square displacement of self-avoiding walk in dimension 5 or more

What would be the best detailed written resource to study Mean square displacement of self-avoiding walk in dimension 5 or more?

**-1**

votes

**0**answers

8 views

### Coordinate expansion or multiple regressions

I was wondering if anyone could offer some advice on the most productive direction to head in when seeking to fit a regresion on the below data which is most entirely centered on zero.
Currently ...

**0**

votes

**1**answer

67 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

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

**0**

votes

**0**answers

128 views

### Continuous-time random walk on $\mathbb{R}$ that never stays still

Consider a walker on the real line $\mathbb{R}$ and two probability density functions $w$ and $j$ defined over $\mathbb{R}$.
A walker starts at $0$ and iterates the following: it samples a waiting ...

**1**

vote

**1**answer

60 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

77 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

100 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

102 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

27 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

189 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

217 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

225 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

103 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

78 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

97 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

120 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

112 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

108 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?

**0**

votes

**1**answer

150 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

33 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

265 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

134 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

67 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

14 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

177 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

407 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

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

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

**0**

votes

**0**answers

72 views

### Random walk in random enviroment

I am looking for a classical analogue of localization for quantum walks.
First, I draw for each point in $x \in \mathbb{Z}^2$ (with some distribution) the numbers $u_x,d_x,l_x,r_x$ such that $u_x+d_x+...

**1**

vote

**1**answer

58 views

### A scaled random walk on the number line

An agent $A$ is performing a random walk on the number line. Let $X_t$ be his position at time $t$. $X_{t+1}$ is calculated according to the following rules:-
$ X_{t+1} =$
\begin{cases}
...

**2**

votes

**0**answers

67 views

### Hitting measure/overshoot for random walk in $\mathbb{Z}$ with heavy-tail

Let $\alpha \in (0,2)$, (or for simplicity just $\alpha \in (1,2)$) and let $X_1,X_2,\dots$ be an i.i.d collection of random variables with common distribution
$$
p(x,y)= \frac{c_\alpha}{|x-y|^{1+\...

**10**

votes

**1**answer

377 views

### Smooth functions that resemble random walks

If the Riemann hypothesis holds, then the Mertens function $M(n)\equiv\sum_{x\leq n} \mu(n)$ behaves much like a 1D random walk. This includes the statements that
$M(n)$ changes sign infinitely often
...

**13**

votes

**1**answer

485 views

### Identity involving the probability that a random walk stays below a curve

I'm looking for a direct proof of the following identity:
Let $W_n$ be a simple random walk with $W_0=0$. For all $x>0$ we have
$$
\lim _{N\to \infty} \sqrt{N} \cdot \mathbb P \Big( \forall n \le ...

**3**

votes

**0**answers

71 views

### Random walk in a switching scenery

For each $x \in \mathbf{Z}$ let $(\eta_t(x))_{t\geq0}$ denote independent copies of a process $(\eta_t(0))_{t\geq0}$ defined as follows. The process $\eta_t(0)$ takes values in $\{-1,1\}$, where $-1$ ...

**1**

vote

**1**answer

161 views

### References for “second order” random walk on graphs (used in “node2vec” paper)?

The "word2vec" family of methods provided a great breakthrough in natural language processing.
The methods assign to each word a vector in $R^{n}$, such that the "similar" words ...

**1**

vote

**1**answer

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

**4**

votes

**1**answer

176 views

### Asymptotics of a quotient related to a simple random walk

Let $\lambda_0 < \lambda_1$ and $\lambda_0 \lambda_1 > 1$ (i.e. at least $\lambda_1 > 1$). Further, let $S_n$ denote a simple random walk with increment distribution $$ P(X = 0)= P(X= 1) = 1/...

**1**

vote

**1**answer

43 views

### Gaussian bounds for discrete (graph) Dirichlet heat kernel

(this is an attempt to refine a previous question; I was told that it would be better to create a new question than edit the previous one, I hope this is the correct ettiquete.)
Let $\Omega$ be a ...

**4**

votes

**0**answers

112 views

### Ihara zeta function and closed paths and trails

Let $\Gamma$ be a finite graph. There seem to be two definitions of closed path in the literature. In one, a closed path is just a walk whose starting vertex is the same as the ending vertex. (Let us ...

**2**

votes

**1**answer

98 views

### Gaussian bounds with exponential decay for discrete (graph) Dirichlet heat kernel

Let $\Omega$ be a finite, connected subset of $\mathbb{Z}^n$, $W_t$ a standard random walk on $\mathbb{Z}^n$ started at $x$, and $T_\Omega$ the first time at which $W_t$ leaves $\Omega$; consider
$$
P^...

**1**

vote

**1**answer

136 views

### Exit time estimate for a simple continuous-time random walk

Let $S = (S_t, t \geq 0)$ be a simple one-dimensional continuous-time random walk with total jump rate one, $S_0 = 0$. Denote by $T_k$ the time when $S$ exits the interval $I_k = [-k,k] \cap \...

**1**

vote

**2**answers

223 views

### Asymptotic behavior of a random geometric sum

Let $S_n$ denote a simple random walk with i.i.d. increments $X_i$ such that $P(X_1 = 0) = P(X_1=1) = 1/2$, i.e. $$S_0 = 0, \ S_n = X_1 + \dots + X_n.$$
The behavior of $S_n$ as $n \to \infty$ is ...

**2**

votes

**0**answers

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

**0**

votes

**0**answers

64 views

### Concentration (or two sided tail bounds around expectations) of maximum and minimum of $n$ iid, subgaussian random variables

I asked this on MSE, but got no answer, hence asking here now. Help appreciated!
My question is motivated by this question and this question, where the first was aimed for giving a one sided tail ...

**4**

votes

**1**answer

116 views

### Support of random closed walk in arbitrary graph

Researching a question related to closed walks on graphs, I have come across the following problem. Let $G$ be a connected graph on $n$ vertices and $k=O(\log(n))$. Pick a random closed walk on $G$ as ...

**2**

votes

**1**answer

142 views

### Reference request: Donsker's theorem for non-identical, independent random variables

The central limit theorem can be generalized to independent but not iid random variables, provided they satisfy the Lyapunov condition (which looks something like a variance bound), see https://en....