Questions tagged [random-walks]
The random-walks tag has no summary.
543 questions
1 vote
1 answer
264 views
References for this law?
Let $S$ be a symmetric simple random walk starting at $0$ and denote by $p_{n,k}$ the probability $S$ occupes $k$ at time n. Denote also $q_n=\left(q_{n,k}\right)_{0\leq k \leq n}$ by $$ q_{n,k}=\frac{...
- 61
3 votes
1 answer
129 views
Proving that $\Phi \left(\frac{j}{\sqrt{n}}\right)\leq \mathbb{P}(S_n\leq j)$ for $j\geq-2$, where $S_n$ is a symmetric simple random walk
Let $S_n$ be a symmetric simple random walk starting at $0$. Numerically, I verified that for any $j\geq -2$ such that $n+j$ is even, we have $$\Phi \left(\frac{j}{\sqrt{n}}\right)\leq \mathbb{P}(S_n\...
- 763
1 vote
0 answers
68 views
Lifting of non-reversible Markov chains for convergence acceleration
Background and motivation Let $(\Omega, \pi)$ be a finite state space with a stationary distribution $\pi$. Consider an ergodic Markov chain on $\Omega$ with transition matrix $P$ that is irreducible ...
- 313
1 vote
1 answer
142 views
maximal displacement of a branching random walk
Consider a branching random walk given by the collection of i.i.d random variables $X(i_{0},\ldots,i_{t})$. Here $t \in \mathbb{N}$ and $i_{k} \in \{1,\ldots,n\}$ for any $k \in \mathbb{N}$. Each $X(...
11 votes
0 answers
485 views
Distribution of the range of a 2d random walk excursion
For SSRW on $\mathbb{Z}^2$, let $R$ be the number of distinct sites visited by a random walk starting at the origin before it revisits the origin. Can we say anything about the asymptotic behavior of $...
- 179
6 votes
2 answers
415 views
Finite entropy probability measures on discrete groups
Recall that for a probability measure $\mu$ on a finitely generated group $G$, the entropy $H(\mu)$ is defined as $$ H(\mu) = - \sum_{ g \in G} \mu(g) \log (\mu(g)). $$ In a paper by Kaimanovich-...
- 61
1 vote
0 answers
152 views
Approximation of characteristic functions of two dimensional random walks
Let $p,q,r,$ and $s$ be nonnegative real numbers satisfying $p+q+r+s=1$. Define $\varphi \colon \mathbb{R}^2 \to \mathbb{C}$ by $$ \varphi(\theta_1,\theta_2)=pe^{i\theta_1}+qe^{-i\theta_1}+re^{i\...
- 817
9 votes
1 answer
427 views
Hitting time of the ball for a simple random walk in a Cayley graph
Consider the Cayley graph of an infinite [finitely generated discrete] group. Consider a simple random walk $(\gamma_n)_{n \in \mathbb{N}}$ on this graph. Let $S_k$ be set of elements at distance ...
- 4,706
0 votes
0 answers
85 views
Upper bound for n-step probability of a random walk-like Markov chain
Consider a Markov chain $X_n$ on $\mathbb{Z}$ with transition probability matrix $S$. Let $C$ be a parameter representing the length of one step. We assume that in each step, we move to a point with ...
- 95
0 votes
1 answer
447 views
Expected number of steps for a random walk to return with a single barrier
Here is the problem and a possibly noobie question I am trying to figure out. You have a biased random walk on $\mathbb{Z}$ with jump to the left probability $p=0.7$ and jump to the right $q=1-p=0.3$. ...
- 342
1 vote
1 answer
123 views
Probability that a sequence of random edits applied to a string returns to the original string after $n$ edits
Start from a string; go ahead and pretend that it's a genetic sequence, but any string of $\left|A_0\right|$ characters drawn from an alphabet $\mathscr{A}$ will do. An edit includes: Insert ...
- 319
3 votes
1 answer
168 views
Is there a canonical way to assign a metric to the Poisson boundary of a finitely generated group?
The Poisson boundary of a finitely generated group $(G,\mu)$ is the set of ergodic components of the time shift in the path space of the associated random walk and therefore, it has a natural measure ...
- 422
0 votes
0 answers
61 views
Number of closed walks in trace monoids
Let $G=(V, E)$ be a graph on $L$ nodes. To each vertex $i\in V$, we associate a symbol/generator $g_i$. Two generators $g_{i}, g_{j}$ commute if $\{i, j\}\in E$. Let $\Sigma$ denote the set of all ...
- 371
1 vote
0 answers
114 views
Edge-avoiding walks: displacement after n steps
this post is about a model of random walks where we have the constraint that the walk cannot repeat edges but can visit the same vertex multiple times, and I would like to know the state of our ...
- 966
1 vote
2 answers
190 views
Closed-form distribution function for Gaussian-exponential mixture
Please advise how useful would be knowing in the closed-form a distribution function F(x) for Gaussian-exponential mixture for a random variable X, as specified below? $$X \sim N(\mu \cdot T, \sigma \...
2 votes
0 answers
88 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,707
4 votes
1 answer
276 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
138 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,...
- 304
2 votes
0 answers
78 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
4 votes
0 answers
149 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)...
- 41
0 votes
1 answer
135 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(...
- 304
5 votes
1 answer
217 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
634 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 ...
- 283
3 votes
1 answer
390 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
228 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 +...
- 893
4 votes
1 answer
443 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,417
1 vote
0 answers
169 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
190 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 ...
- 26.3k
1 vote
1 answer
1k 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
102 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
93 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
164 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 ...
- 2,148
3 votes
2 answers
345 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
147 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
67 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,406
6 votes
1 answer
608 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 ...
- 19.3k
6 votes
0 answers
173 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
134 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_{...
- 775
3 votes
1 answer
203 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
1k 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 ...
- 393
1 vote
0 answers
199 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 ...
- 26.3k
2 votes
0 answers
223 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 ...
- 190
1 vote
0 answers
247 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 ...
- 26.3k
1 vote
0 answers
139 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
170 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
438 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
573 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
196 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,483
2 votes
0 answers
153 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
538 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