Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7
votes
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
3answers
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
3answers
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
1answer
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
1answer
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
4answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
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 $...
0
votes
0answers
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
1answer
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
1answer
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....

1
2 3 4 5
9