Questions tagged [random-walks]
The random-walks tag has no usage guidance.
522
questions
7
votes
4
answers
326
views
Probability of $\operatorname{Bin}(n,p)=\operatorname{Bin}(n,q)$ is decreasing when $n$ increases
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 can be reformulated as $\mathbb P(X_n=0)$ ...
- 233
3
votes
1
answer
206
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 ...
- 93
4
votes
0
answers
56
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 +...
- 627
3
votes
1
answer
148
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,377
1
vote
0
answers
121
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
158
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.4k
1
vote
1
answer
166
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
60
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
41
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
98
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,877
3
votes
2
answers
211
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
55
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\...
- 53
0
votes
1
answer
28
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,162
6
votes
1
answer
534
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.3k
6
votes
0
answers
143
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