All Questions
Tagged with random-walk or random-walks
529 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
2
votes
0
answers
58
views
Inclusion-Exclusion formulae for number of SAWs on $\mathbb{Z}^d$ of length $n$ [closed]
Here is my attempt at lower bounding the number of SAWs on $\mathbb{Z}^d$ of length $n$: In $\mathbb{Z}^d$, consider the $2^{d-1}$ lines of the form $\epsilon_1 x_1 = \epsilon_2 x_2 = \epsilon_3 x_3 \...
- 21
3
votes
0
answers
101
views
Divergent/Unbounded random walks techniques
I want to prove the following biased random walk will be diverge. Suppose I have a random walk $S_n = X_1 + ... + X_n$, but $X_1,...,X_n$ are dependent variables. $X_1 \sim$ Bernoulli($\sigma(\theta_1)...
- 31
0
votes
1
answer
62
views
Probability of random walk on confined lattice with reflective boundaries
Consider a simple random walk in one dimension with reflective boundaries at $n=1$ and $n=N$. We can express it via the master equation:
\begin{equation}
P(n,t) = \frac{1}{2}P(n-1,t-1) + \frac{1}{2}P(...
- 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
5
votes
1
answer
139
views
Dispersion of random walk with scaled step sizes
Let $Y_j$ be a sequence of independent Gaussian random variables with mean zero and unit variance ($\mathbb{E} Y_j = 0$ and $\mathbb{E} Y_j^2 = 1$) and let $\sigma:\mathbb{R}\to [1,2]$.
We define the ...
- 452
7
votes
5
answers
513
views
Probability of $\operatorname{Bin}(n,p)=\operatorname{Bin}(n,q)$ is decreasing when $n$ increases
$\newcommand{\Bin}{\operatorname{Bin}}$I would like to show that $\mathbb P(\operatorname{Binomial}(n,p) = \operatorname{Binomial}(n,q))$ decreases when $n$ increases for a fixed pair $(p,q)$. This ...
- 243
3
votes
1
answer
279
views
Bounds on hitting time of sum of i.i.d. random variables
I have a sequence $(X_i)_{i\geq 1}$ of i.i.d. random variables taking values in $\mathbb Z$. I know that each $X_i$ has mean $0$ and finite variance $\sigma^2$. Let $S_n=X_1+\cdots+X_n$. Then I can ...
- 135
4
votes
0
answers
110
views
MGFs of sum of (Rademacher) independent variables and (hyperbolic/spherical) Pythagorean theorem
Consider a set of iid random variables $X_1, X_2, \ldots$ (distribution to-be-specified later). For real numbers $a_1, a_2, \ldots$ (with $\sum_{k} a_k^2 < \infty$) define
$$X = a_1 X_1 + a_2 X_2 +...
- 637
3
votes
1
answer
209
views
A few points of clarification on the Martin boundary
Let $\Gamma$ be a finitely generated group, and let $M$ be the Martin boundary of $\Gamma$. I was reading the article on Martin boundary on Encyclopedia of Math, and I have a few questions about what ...
- 1,407
1
vote
0
answers
129
views
Have strictly superharmonic functions on graphs been studied?
Given a graph $G$ and a function $f:G\to\mathbb R$, we say that $f$ is harmonic if
$$f(x)=\frac{1}{|N(x)|}\sum_{y\in N(x)}f(y)$$
for every $x\in G$, where $N(x)$ denotes the set of neighbors of $G$. ...
- 111
2
votes
0
answers
167
views
How to choose N policemen positions to catch a drunk driver in the most effective way (on a Cayley graph of a finite group)?
Consider a Cayley graph of some big finite group. Consider random walk on such a graph - think of it as drunk driver. Fix some number $N$ which is much smaller than group size.
Question 1: How to ...
- 24.9k
1
vote
1
answer
345
views
Random walk on $\mathbb{Z}^3$. Expected number of visits and probability of return
I am working with the simple symmetric random walk on $\mathbb{Z}^3$. Using the Fourier identity I have been able to prove:
$$ P(S_n = 0) = \frac{1}{(2\pi)^3} \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} \...
2
votes
1
answer
67
views
Random pseudo-walk with 'disappearing' values
This question is a twist on a question I asked here Random pseudo-walk of Poisson variables, but with randomly 'disappearing' objects. I do not know how to generalize the (satisfactory) answer given ...
- 61
2
votes
0
answers
47
views
Random Walks on the natural numbers with self loops
I am looking at a random walk that starts at 0 and at every step, either increases or decreases by 1, or doesn't move.
More specifically, $\mathbb{P} (X_{t+1} = X_t) = 1-p,\mathbb{P} (X_{t+1} = X_t +1)...
- 31
3
votes
1
answer
108
views
Has this random process been studied on grid graphs?
As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
- 1,951
3
votes
2
answers
223
views
Measures with superexponential moments on finitely generated groups
Let $\Gamma$ be an infinite finitely generated group and let $\nu$ be a measure on $\Gamma$ which generates a transient random walk. I was reading this paper, and the authors prove many of their ...
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
0
votes
1
answer
34
views
Transience of the SRW on regular graphs of exponential growth
Let $G$ be a $d$-regular graph of exponential growth. By exponential growth I mean that
$$ \liminf_{r \to \infty} | B(o, r)|^{1/r} >1. $$
Here $B(o,r)$ is the ball of radius $r$ centered at a given ...
- 6,214
6
votes
1
answer
545
views
Balancing act for infinite walks
Think of a one-dimensional infinite walk as a map $$w\colon \mathbb{N}\to \{-1,1\}.$$ (If it is more convenient, you can think of a walk as a subset of $\mathbb{N}$, or as a binary word, or as any ...
- 18.7k
6
votes
0
answers
149
views
Running minimum of exponential random walks
Let $\{X_i\}$ be a collection of i.i.d. Exp$(1)$ random variables. For $k \in \mathbb{Z}_{>0}$, define
$$S_k = \sum_{i=1}^k X_i$$
and note that $\mathbb{E}[S_k] = k$.
I was wondering if there is ...
- 485
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
4
votes
3
answers
769
views
Winning game probability
At each round of a game with two players Alice and Bob, Alice can win with a fixed probability $a$ and Bob can win a fixed probability $b$, such that $a+b < 1$, otherwise there is a draw.
The game ...
- 383
1
vote
0
answers
164
views
Locally "unshortable" paths in graphs
Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
- 24.9k
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
1
vote
0
answers
175
views
Random walk on N-Rubik cube group is going like sqrt(number of moves) or linear (number of moves) or? "commutative" vs. "free"(like) group pattern?
Consider higher (NxNxN) Rubik's cube group, with specific set of generators described below.
What is important - that there are huge COMMUTING subsets of generators.
Question: Consider a random walk ...
- 24.9k
1
vote
0
answers
100
views
Conditioned random walk over a graph
I want to solve for a conditioned random walk over a graph. I have a directed graph $G$. The random walkers start at a fixed node, Source. They all need to end up at fixed node, Sink. So the random ...
- 111
3
votes
0
answers
133
views
An analogue of Kolmogorov's law of the iterated logarithm
Let $X_1,\dots,X_n$ be independent random variables, each with mean zero and finite variance. Let $S_n = \sum\limits_{k=1}^n X_k$ and $s_n^2=ES_n^2$. We say the sequence obey the law of iterated ...
- 153
3
votes
1
answer
376
views
Random pseudo-walk of Poisson variables
Suppose there is a pool that can contain any non-negative number of objects. At time $t$ it contains $n_t$ objects. Time is discrete.
Before time $t+1$ two things happen, in this order:
Unless the ...
- 61
1
vote
3
answers
371
views
Probability that a 1-D zero mean 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
3
votes
0
answers
150
views
How to sample uniformly over a polytope knowing its vertex presentation?
Say that a convex polytope $P$ is presented as $P = \mathrm{Conv}(v_1, \dots , v_m)$.
I would like to sample over $P$, without generating the facet presentation of the polytope.
How can I do that?
I ...
- 1,435
2
votes
0
answers
126
views
Random walk with same directions and different step sizes
Let $X\sim e^{iU}$, where $U$ is uniformly distributed on $(0, 2\pi]$. Define $\chi_1, \cdots, \chi_t$ as i.i.d. random variables with the same distribution as $X$.
Consider the following two random ...
- 499
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,214
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,214
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
0
answers
110
views
Defining a metric on $\mathbb Z^n$ using Green's function for the simple random walk
Let $G$ be Green's function for the simple random walk on $\mathbb Z^n$ for $n\ge 3$, i.e., $G(x)$ is the expected number of visits to $x$ when the walk starts at the origin.
Define $d(x,y)=G(x-y)^{1/(...
- 2,555
13
votes
2
answers
1k
views
Optimal search puzzle
Consider the following puzzle: On the integer line from 1 to $t$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $t$, and subtract 1. What is the optimal ...
- 265
4
votes
1
answer
518
views
Probability to return to the origin for a uniform random walk
Consider a uniform random walk on $\mathbb{R}$, with stepsize chosen uniformly from the interval $(-1,1)$. The random walk start at $x=0$. Denote by $\rho_p dx$ the probability that the random walk ...
- 188k
-1
votes
1
answer
148
views
Strong law of large numbers for a sequence of random variables in different probability spaces
Is it known whether the following version of the strong law of large numbers holds?
For each $k\in\mathbb{N}$, let $\Omega_k$ be a finite set and $\mu_k$ be a probability measure on $\Omega_k$. Let $(...
- 1
3
votes
2
answers
204
views
Random walk to visible lattice points
Consider a random walk from the $\mathbb{Z}^2$ origin $(0,0)$ to visible
(not blocked) lattice
points $p$, with a parameter $r$ a given radius of a circle centered
on $p$.
With $p$ the previous point, ...
- 151k
2
votes
2
answers
166
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
8
votes
0
answers
170
views
Random walk on matrix until singularity
Consider a random walk on matrices, where one starts with the matrix $M=I_n$ and at each step randomly chooses an entry of $M$ to increase by $1$.
I’m interested in two things about this walk:
What’s ...
- 541
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
7
votes
1
answer
382
views
Diameter bound for graphs: spectral and random walk versions
This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and ...
4
votes
1
answer
250
views
Does a subset with small cardinality represent the whole set?
Assume that we have heavy-tailed distribution $F(x)$ such that
\begin{align}
F(x)=\mathbb{P}[X\geq x]=x^{-0.5}.
\end{align}
Then, we produce $N$ independent samples $X_1,X_2,\ldots,X_N$ from this ...
- 287