All Questions
Tagged with random-walks stochastic-processes
124 questions
1
vote
0
answers
41
views
Asymptotic mixing time and Euclidean probability distance for path graphs
We are given a simple path graph $P(V,E)$ with vertex set $V$ and edge set $E$, having $n=|V|$ nodes. Given an initial distribution $\mathbf{\mu}$ over $V$, let $d_t(\mathbf{\mu},\pi)$ be defined as $\...
- 1,677
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
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
0
votes
0
answers
85
views
Does a 2d random walk hit 0 for increasing distances AND time spans?
Question: For a simple symmetric random walk $(Z_t)_{t\geq 0}$ in $\mathbb{Z}^2$, does
$$\lim_{\beta\rightarrow 0}\mathbb{P}^{x_\beta}(Z_t=0\text{ for some }t\leq h(\beta)T)=0\quad (2.8)$$
where $|x_\...
- 31
2
votes
0
answers
80
views
Bound from above and from below the probability that a 1-D centered random walk remains at each step inside a square root boundary
Let $W_n = \sum_{i = 1}^{n}X_i$ be a random walk on $\mathbb{R}$, where the increments $X_i$ are i.i.d., symmetric around the origin ($X\sim -X$), such that $-1\leq |X(\omega)| \leq 1$ $\forall\omega\...
- 63
2
votes
0
answers
114
views
Asymptotic Independence of random walks from increments?
Suppose we have two random walks $(S_n:n\geq 1)$ and $(T_n:n\geq 1)$ building from independent identically distributed increment vectors $\{(X_k,Y_k):k\geq 1\}$, i.e. $S_n=\sum_{k=1}^n X_k, T_n=\sum_{...
- 715
3
votes
1
answer
164
views
Simple linear asymptotics for leaving time of particle in open-boundary TASEP
EDIT: It appears the hypothesis may not be true - I am not sure. I therefore changed my question.
ORIGINAL QUESTION:
Consider a system $n$ linked discrete cells numbered $1 \ldots n$. Particles are ...
- 133
2
votes
0
answers
193
views
If the operators $B_i'$ satisfy an inequality, prove that $B_1'+\dotsb+ B_n'$ also satisfies the same inequality
Related: On a deceptively tricky calculus problem.
The way that Leonard Gross proves the log Sobolev inequality is in the following stages:
He proves that for any operator $B$ that satisfies the log ...
- 90
0
votes
1
answer
335
views
How far does a random walker travel before returning to the origin?
Consider a (continuous time) simple symmetric random walk on $\mathbb Z$, starting from the origin. Let us denote this random walk by $\{X_t: t\geq 0\} $. It is well known that this random walk is ...
- 59
2
votes
0
answers
78
views
A question on the convex hull of independent random walks
Consider $m$ independent random walks $X^1_n, \dots, X^m_n$ driven by a probability measure $\mu$ in $ \mathbb{Z}^d$. Assume that the $\mu$ has no drift, that is, the expected value of a $\mu$-...
- 6,224
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
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
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
2
votes
2
answers
167
views
Example of random walk in a random environment (RWRE) saying things on the environment
I was wondering if anyone is aware of works/articles/examples where random walks in a random environment (RWRE) are actually used for obtaining information on the random environment.
To clarify a bit, ...
- 59
1
vote
1
answer
284
views
Rate of convergence to uniform distribution
Let $p=(p(1),\ldots,p(N))$ be a discrete distribution on $[N]:=\{1,2,\ldots,N\}$ with full support (i.e all the $p(i)$'s are strictly positive and sum to $1$). Let $i_1,i_2,\ldots,i_T$ be an iid ...
- 6,853
2
votes
1
answer
184
views
A question about convergence of stochastic processes converging to a random walk
Consider the following random walk $(y_t)_{t \in \mathbb Z_+}$:
$$y_t = y_{t-1} + u_t,\quad (u_t)_{t \in \mathbb Z_+} \overset{iid}{\sim} N(0,1), \quad (t \in \mathbb Z_+)$$
where $y_0, u_1, u_2,...$ ...
- 13
2
votes
1
answer
115
views
Randomly chosen walk of fixed length
Let $G=(V, E)$ be the graph on vertices $V = \{0, \cdots, k\}^n$, where vertices $(v_1, \cdots, v_n)$ and $(w_1, \cdots, w_n)$ share an edge iff $\lvert v_i - w_i\rvert \leq 1$ for all $i$.
A walk of ...
- 138
1
vote
1
answer
109
views
Phase space Brownian bridge
I understand the concept of the 1 dimensional Brownian bridge with the form of:
$$dx_t=\frac{-1}{1-t}x_t \, dt + dw_t$$
s.t. $x_0=0$ and $x_1=0$
where $dw_t$ is a Wiener process.
I am thinking about ...
- 13
0
votes
1
answer
77
views
Reference request: $\mathbb{E}|X_t| \to \infty$ as $t \to \infty$ when $\{X_t\}_{t\geq 0}$ is a continuous-time (symmetric) random walk
Let $\{X_t\}_{t\geq 0}$ be a one dimensional continuous-time (symmetric) random walk on $\mathbb Z$ defined via $$X_t = X_0 + \sum_{i=1}^{N_t} Y_i,$$ where $X_0 \in \mathbb{Z}_+$ is a non-negative ...
- 730
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
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
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
1
vote
2
answers
169
views
Asymptotic properties of weighted random walks / infinite convolutions of random variables
Let $(X_n)_{n\in\mathbb{N}}$ be a sequence of i.i.d. real-random variables. Let further $0<c<1$. I'm interested in the asymptotic properties of
$$
\sum_{k=1}^n c^k X_k.
$$
I can prove that this ...
3
votes
1
answer
340
views
Importance resampling with exponential weighting
Suppose that we have
$$
\frac{p(x)}{q(x)} \propto \exp(\tau f(x)),
$$
where we can sample from $q$ but not from $p$. Our goal is to generate a set of particles $\{x_i\}_{i=1}^n$ such that $n^{-1}\sum_{...
- 1,127
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
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
0
votes
1
answer
110
views
Skip-free random walks: recurrence and transience
Let us define a one dimensional random walk: for all $n\in\mathbb{N}$
$$
X_n:=\sum_{i=1}^nZ_i
$$
with $Z_i$ i.i.d. random variables taking values in $\{-1,0,1,2,\dots\}$. This process is sometimes ...
- 59
1
vote
1
answer
385
views
How fast does this Gaussian random walk move away from the origin?
Suppose $z_i$ are IID zero-centered $d$-dimensional Gaussian random variables with unit-trace covariance $\Sigma$ and $g(z_i)$ is the sum of its components.
Consider the following random walk:
$$x_s=\...
- 2,242
1
vote
1
answer
215
views
Bernoulli trials with small dependencies: asymptotics (central limit theorem, law of the iterated logarithm)
Let $\{X_k\}$ be a sequence of random variables, with $X_k\in\{+1, -1\}$ for $k>0$, generated as follows.
First, define $S_n=X_1+\dots +X_n$, with $X_0=S_0=0$, and let $0<\beta<\frac{1}{2}$.
...
- 3,098
1
vote
1
answer
425
views
Invariance principle: Brownian bridge and random walk conditioned on end point
Let $\{X_i, i \in \mathbb{N}\}$ be a sequence of non-lattice i.i.d. centered random variables, $\mathbb{E} |X_1| ^3 < 0$. Let $S_n = \sum\limits _{i=1} ^n X_i$ be the corresponding random walk and ...
- 724
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
2
votes
1
answer
847
views
Probability that a symmetric random walk returns to $0$ exactly $k$ times in $2n$ steps
I'm trying to find a formula to find the probability of exactly k returns in 2n steps of a symmetric random walk. More specifically, I am trying to show that the probability of 2 returns is exactly ...
- 21
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
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
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
1
vote
2
answers
88
views
Lower-bound on zero-crossing probability of the nonstationary gaussian process $X(t) = tU+(1-t^2)^{1/2}V$, with $(U,V) \sim N(0,I_2)$
Let $(X(t))_{t \in [-1,1]}$ be a centered non-stationary smooth gaussian process with covariation function $\rho(t,s) = \mathbb E[X(t)X(s)]$. For $t_0 \in (-1,1)$ and $\epsilon \in (-1-t_0,1-t_0)$, ...
- 6,853
1
vote
0
answers
91
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 ...
- 5,038
1
vote
1
answer
233
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}+\...
- 39
2
votes
1
answer
192
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 ...
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
1
vote
0
answers
181
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 ...
- 6,853
0
votes
1
answer
599
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 ...
- 51
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
0
votes
1
answer
160
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 ...
- 5
1
vote
1
answer
120
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 = \...
- 568
0
votes
1
answer
183
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: ...
- 5
1
vote
0
answers
44
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{...
- 11
0
votes
2
answers
266
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 =...
- 724
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
10
votes
4
answers
680
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