All Questions
Tagged with random-walks stochastic-processes
124 questions
18
votes
2
answers
1k
views
Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and "Reflective" Boundary at Origin
A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...
- 313
14
votes
2
answers
2k
views
Markov chains: invariant measures and explosion
The following seems like such an elementary question, but I didn't get anywhere with it.
Suppose you are considering a Markov chain in continuous time which is transient and has an invariant measure (...
13
votes
1
answer
1k
views
How far can a particle travel from its origin if it exhibits self-avoiding Brownian motion in two-dimensions?
Let's say I have a point-like Brownian particle undergoing two-dimensional diffusion on an infinite plane with the caveat is that the particle can never return to a coordinate that it previously ...
- 599
12
votes
3
answers
666
views
An "inchworm-like" random walk on an integer interval
Imagine I place $k$ stones on an infinite one-dimensional integer interval $Z$ s.t. no stone is more than some distance $d$ from any other stone. For example, if $d=1$ and $k = 5$, we might place the ...
- 121
11
votes
2
answers
1k
views
Is there a differentiable random walk?
Is there a random walk which is differentiable or smooth? Like brownian motion except smoothed out on small distances. I was wondering if there is a "natural" or "canonical" analogue of brownian ...
- 111
10
votes
4
answers
679
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). ...
- 773
10
votes
1
answer
351
views
Trapping a particle
A particle starts a brownian walk in the middle of a long tunnel in the plane, at one end of the tunnel is a region Y of given area A.
Does the shape of region Y affect average time for the particle ...
- 101
9
votes
1
answer
488
views
Mixing time of unitary Brownian motion
Let $B_t$ be the unitary Brownian motion, i.e. Brownian motion on the unitary group $U(N)$. What is known about the mixing time of $B_t$, that is, how fast does the measure $B_t(\delta_{\{Id\}})$ ...
- 3,323
8
votes
2
answers
259
views
Particularities about the honeycomb lattice for the computation of connectivity constant
After reading the paper The connective constant of the honeycomb lattice equals $\sqrt{2+\sqrt{2}}$ by Hugo Duminil-Copin and Stanislav Smirnov (arXiv:1007.0575) published some time ago in Annals Math....
- 1,561
8
votes
2
answers
853
views
A discrete random walk that avoids previously visited vertices for an exponentially distributed time interval
Imagine a discrete random walk on an infinite one-dimensional lattice where, for every unit interval of time, $(t_1, t_2, ...)$, the walker takes a step with uniform probability to its left or right. ...
8
votes
2
answers
655
views
Random walks on graphs: Cover time and blanket time
Winkler and Zuckerman conjectured that the blanket time is within a constant factor of the cover time. The conjecture was recently proved. The cover time $C$ is the expectation of the first time $t$ ...
- 121
7
votes
2
answers
468
views
One dimension random walk. Is hitting time Lipschitz with respect to target?
Consider a random walk $S_t = \sum_{i=1}^{t} X_i$, with $X_i$ i.i.d.. Assume that $X_i \in [0,1]$. Define $\tau(y) := \inf\{t: S_t\geq y\}$, i.e., $\tau(y)$ is the hitting time of $[y,\infty)$. Is ...
- 103
7
votes
1
answer
2k
views
Generating function for Random Walk Hitting Time, taking the wrong root
In a calculation of the hitting time for a Bernoulli random walk we have to calculate the hitting time $\tau(1)=\inf\{n\ge 0:S_n=1\}$ to reach $+1$ and the generating function has the recursion ...
- 71
7
votes
0
answers
144
views
Random walk on $\mathbf{Z}_d$ with Jacobi $\theta$ transition probabilities
In the context of a finite-dimensional quantum mechanical problem, I was led to study the random walk on $\mathbf{Z}_d$ (i.e the integers modulo $d$), $d$ odd with transition probabilities given by:
$...
6
votes
2
answers
2k
views
Random walk to stay in an interval forever
Consider a random walk on the real time, starting from $0$. But this time assume that we can decide, for each step $i$, a step size $t_i>0$ to the left or the right with equal probabilities.
To ...
- 502
6
votes
2
answers
241
views
Recurrence of Poisson binomial distributed random walk
Let $X_n$ be the outcome of a Bernoulli trial where the probability of getting 1 is $p_n$ and the probability of getting 0 is $1-p_n$, and let $S_n = \sum_{i=1}^n \left(X_i - \textrm{E} X_i \right)$. ...
- 965
6
votes
1
answer
310
views
Random walk with decreasing steps
I have a random walk $$R(t)= \sum_{n<t} X_n,$$ with $X_n \sim U(-\tfrac{1}{n^\alpha}, \tfrac{1}{n^\alpha}),$ where $X_n$ are independant and $\alpha >0$.
I think that someone must have studied ...
- 95
6
votes
1
answer
355
views
Probabilistic problem on random spanning trees
Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
- 1,677
6
votes
1
answer
170
views
Basic Definition and Notations in RWRE
From the definition of Zeitouni's lecture notes on RWRE: $(V, E)$ is a special graph, and $N_v:= \{k \in V: (v,k) \in E\}$ is the neighborhood of $v \in V$. $\Omega = \prod_{v \in V} M_1(N_v)$ ...
- 61
6
votes
0
answers
183
views
Distribution of the stopping time of an autoregressive sequence
Consider $e_t$ being i.i.d. uniformly chosen from $\pm 1$. Let $\eta$ be a small positive constant. What is the distribution of $T$ such that $\eta^{0.5} (1+\eta)^T W_T$ first hits $\pm 1$, in which
$$...
- 1,127
5
votes
1
answer
297
views
Random walk with continuously distributed steps on [-1,1]
A simple random walk $S_n = X_1 +\cdots +X_n$, where $P(X_i = 1) = p \not = 0.5$ and $P(X_i=-1)= q \triangleq 1-p$, admits the following probability
$$P(S_n \textrm{ reaches } a \textrm{ before} -b) =...
- 108
5
votes
1
answer
111
views
Expected time of distinguishability of a series of Poisson processes bounded by each other
Consider a system of $n$ "bounded" Poisson processes over the integers, $X_1, \ldots X_n$, all incrementing at rate $\lambda$. Initially all the processes begin at $0$. The process $X_i$ is inactive ...
- 133
5
votes
2
answers
423
views
A coupon collector-ish question
Imagine we are in the coupon collector setting: every time step we get independently one coupon out of $n$ coupons uniformly at random. However, unlike the coupon collector problem, we stop the at the ...
- 63
5
votes
1
answer
523
views
Scaling of First-passage times for Random Walk on integer lattices
Consider simple symmetric random walk $S_{n} = (S_{n}^{(1)},\dots,
S_{n}^{(d)})$ on the d-dimensional integer lattice with starting point the origin.
Let $\tau_{N}$ be the first time $S_{n}$ exits ...
- 61
5
votes
1
answer
421
views
Memory of Uniformly Random Dyck Paths
Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have $S(0)...
- 4,952
5
votes
0
answers
112
views
Discrete random walk in an expanding cage (i.e. in a growing domain)
In the book "A guide to First-Passage Processes" by Sidney Redner, a section is dedicated to the survival probability of a random walker in a growing domain.
For a fixed-length interval $[0,...
- 274
5
votes
0
answers
130
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 ...
- 83
5
votes
0
answers
485
views
Hierarchical Random Walk (also known as Hierarchical Hidden Markov Model)
Let us consider the following hierarchical (recursive) random walk model, which is also known as the hierarchical hidden Markov model in computer science (https://en.wikipedia.org/wiki/...
- 1,127
5
votes
0
answers
95
views
Most visited vertex in a random walk with place dependent drift
Consider the following Markov chain on $\mathbb{Z}$:
$$
P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}}
$$
Do there exist constants $c,C>0$ such that
$$
c\cdot P^t(z,z) \...
- 527
4
votes
1
answer
368
views
Self Avoiding Walk Pair Correlation
Let $\gamma(i)$ be a self avoiding walk (SAW) on a 2D lattice $L$ (a square lattice for example) starting at a predefined origin ( $\gamma(0)=(0,0)$ ) and having length $n:=\ell(\gamma)$. Furthermore, ...
- 4,952
4
votes
2
answers
480
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)$ ...
- 17k
4
votes
3
answers
620
views
Averaging over random walk on binary lattice
I have a function $f$ defined over a bit vector of length $n$. Equivalently, this is a function defined on the set of integers $[0,\ldots,2^n-1]$. I would like to compute the mean or variance or some ...
- 757
4
votes
1
answer
469
views
Derive the solution of the diffusion equation from the solution of a random walk
Summary
The probability distribution (pdf) of a random walk in 1 dimension is represented by a Bessel function. On the other hand, the pdf of a Brownian motion in free space is represented by a ...
- 274
4
votes
1
answer
176
views
Random Walk with "Forward Dependency"
Let $\{X_t\}_{t=-\infty}^{\infty}$ be a sequence of random variables. We are interested in a "random walk" (or more generally, a random field) that can be characterized by
$$
X_t ~|~ X_{t-k}, \ldots, ...
- 1,127
4
votes
1
answer
150
views
Convex order between Gamma distributions and Exponential distributions
Let $ (b_1, \dots, b_n) $ be a tuple of positive integers. Define independent random variables $ Y_i \sim \text{Gamma}(b_i, b_i) $ (shape and rate parameter both equal to $ b_i $) for $( i = 1, \dots, ...
- 55
4
votes
1
answer
829
views
Probability that a "closable" self-avoiding random walk forms a polygon
Consider a self-avoiding random walk on an infinite graph (for concreteness, the grid of 2-dimensional lattice points $\mathbb{Z}^2$), in which on each step, the next position is chosen uniformly at ...
- 141
4
votes
1
answer
189
views
Sign of error in the central limit theorem
Let $X_n$ and $Y_n$ be independent copies of two random variables $X$ and $Y$ with domain $\{-1,0,1\}$ for $n\in \mathbb{N}$. For a given $k\in \mathbb{N}$, I would like to find conditions on $X$ and $...
- 53
4
votes
1
answer
385
views
General ballot theorem: sum of independent but not identically distributed random variables?
Is there ANY ballot-type result for random walk $S_n:=\sum_{i\le n}X_i$ that allows for independent but not identically distributed random variables $X_i$, up to some uniform concentration conditions ...
- 715
4
votes
1
answer
518
views
Probability that two walkers will meet on a graph
Consider two independent continuous random walks on a graph $G$ with adjacency matrix $A$. I am interested in the probability that the two walkers will ever meet.
When the graph is a $k$-regular ...
- 117
4
votes
1
answer
187
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/...
- 121
4
votes
2
answers
255
views
The necessary sufficient condition for recurrence of a Markovian random walk
Suppose $\sigma_{1},\sigma_{2},...$are i.i.d random variables.$S_{0}=0$. Define $S_{n}=S_{0}+\sum_{i=1}^{n}\sigma_{i}$, then ${S_{n}}$ is a Markovian random walk.
I want to figure out the necessary ...
- 41
4
votes
0
answers
73
views
Small angles between independent centred random walks in $ \mathbb{Z}^d$
Let $W_n$ and $W'_n$ denote two independent random walks in $ \mathbb{Z}^d$ defined using a finitely supported centred (mean zero) probability measure on $\mathbb{Z}^d$.
For $N \ge 1$, let
$\theta_n$ ...
- 6,224
4
votes
0
answers
142
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 ...
- 141
4
votes
0
answers
229
views
Self-adjusting random walk
Let $X_t$ be a random process such that
\begin{eqnarray}
X_1 &=& 0\\
X_t &=& X_{t-1} + \left\{\begin{array}{ll}
A_t, & X_{t-1} \geq 0\\
B_t, & X_{t-1} < 0
\end{array}\...
- 93
4
votes
0
answers
158
views
Using Crump-Mode-Jagers processes to get logarithmic bound on a random tree height
I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I ...
- 41
3
votes
2
answers
478
views
Random spanning trees probability problem
We are given a simple connected graph $G(V,E)$ with vertex and edge set $V$ and $E$ respectively. For any vertex $v\in V$, let $D_T(v)$ the degree of $v$ in a uniformly generated random spanning tree $...
- 1,677
3
votes
2
answers
250
views
Elementary cellular automata in stochastic modes
There are several ways to run a given elementary cellular automaton in a stochastic way:
by giving for each of the eight local configurations 000,100,010 and so on a probability by which the rule is ...
- 9,720
3
votes
2
answers
3k
views
Quadratic variation for discrete Martingale
Is there any analogue of continuous martingale quadratic variation for the discrete case? If so, are there any theorems which characterize simple random walk using quadratic variation - similar to ...
- 133
3
votes
1
answer
968
views
Expected visits to the origin by a symmetric random walk on the integers
Consider the first $2n$ steps of a simple random walk on the integers, starting at the origin. A simple binomial argument shows that regardless of $n$, the origin gets visited the most (in expectation)...
- 527
3
votes
1
answer
201
views
Simple random walk with an extra condition
Consider a simple random walk $$\mathcal{X}_t= \sum_{n<t} X_n,$$ where $P(X_n=1)= P(X_n=-1)= 1/2.$
If I put an extra condition that excludes cases with more than 5 consecutive +1, or -1 in the sum:
...
- 95