Questions tagged [random-walks]
The random-walks tag has no usage guidance.
137
questions with no upvoted or accepted answers
19
votes
0
answers
2k
views
xkcd's "Unsolved Math Problems", straight lines in random walk patterns
STEM student's favourite source of amusement posted a comic titled "Unsolved Math Problems" one of which looks like something that could actually be tackled.
If I walk randomly on a grid, ...
16
votes
0
answers
819
views
Self-avoiding random walks that always turn
I am wondering if the statistics of self-avoiding random lattice-walks
on $\mathbb{Z}^2$
that turn left or right at each step (i.e., they cannot continue the
direction of the preceding step) have been ...
14
votes
0
answers
264
views
A symmetry of lattice paths
The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity.
...
9
votes
0
answers
237
views
Is the P.M.F. of the first return time of a random walk monotone?
Suppose $X_1,X_2,\ldots$ are i.i.d. $\mathbb Z$-valued random variables such that the random walk
$$S_n=\sum_{i=1}^nX_i$$
is recurrent with some period $k\geq1$ (i.e., $\Pr[S_n=0]>0$ if and only if ...
8
votes
0
answers
148
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 ...
8
votes
0
answers
207
views
Superharmonic functions and amenability
Let $G$ be a group generated by a finite set $S$. Let $P$ be a Markov operator defined by the uniform measure on $S$. A function is superharmonic if $Pf\leq f$.
Assume that there is a set of non-...
8
votes
0
answers
763
views
Asymmetric random walk on the line with barriers
The most commonly considered random walk on the line takes one step left or right with equal probability until a barrier is reached (if there are any barriers).
More generally, suppose we fix any ...
7
votes
0
answers
150
views
Sum of variables uniformly distributed on a circle: a cyclic property
Consider a random walk starting at the origin in the plane, walking $n$ steps in independent uniformly random directions with step lengths $a_1,\ldots,a_n$, and observing the distance from the origin. ...
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:
$...
7
votes
0
answers
749
views
Calculate the expectation of the maximum of averaged random walks
Let $X_1, X_2, \ldots$ be iid random variables with bounded second moment. The question is to calculate the exact value of $$\mathbb{E} \max_{1 \le j < \infty} \frac{X_1 + \cdots + X_j}{j}.$$
Is ...
7
votes
0
answers
354
views
Fixed radius mean value property implies harmonicity?
Let $f$ be a continuous real-valued function on $\mathbb{R}^n$. It is well known that the following are equivalent:
$f$ is harmonic.
$f$ satisfies the ball mean value property
$$
f(x)=\frac{1}{|B(x,r)...
7
votes
0
answers
129
views
Speed on recurrent graphs
Suppose that $G$ is a (locally finite) graph such that the simple random walk on $G$ is recurrent. Does this imply any upper bound on the speed $\mathbb{E}d(X_t,X_0)$ of such random walk?
6
votes
0
answers
189
views
Random Up-walk on Young's Lattice
Starting from the empty partition, $\varnothing$, follow a random up-walk of length $n$ on Young's Lattice, where an edge's transition probability is 1/updegree. For a particular partition, $\lambda$, ...
6
votes
0
answers
180
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
$$...
6
votes
0
answers
458
views
Any approximation algorithms for self-avoiding walks?
I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
5
votes
0
answers
75
views
Logarithmic speed walks on trees
Let $T$ be the infinite $3$-regular tree, equipped with the shortest path metric $d_T$. An infinite walk on $T$ is a map $f:\mathbb{N}\to T$ such that $d_T(f(a),f(a+1))\leq 1$ for all $a$.
An infinite ...
5
votes
0
answers
129
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 ...
5
votes
0
answers
101
views
Intuition behind the local limit theorem in hyperbolic groups
Let $\Gamma$ be a finitely generated group and let $\mu$ be a probability measure on $\Gamma$. Denote by $X_n$ the induced random walk. Finally, let $p_n=\mu^{*n}(e)=P_e(X_n=e)$. The local limit ...
5
votes
0
answers
148
views
Continuity of the Green function with respect to the measure
Let $G$ be a finitely generated group and let $\mu$ be a finite measure on $G$. Define the Green function as
$$G(\mu)=\sum_{n\geq 0}\mu^{*n}(e),$$
where $\mu^{*n}$ is the $n$th convolution power of $\...
5
votes
0
answers
149
views
Random walks in arrangements of lines in the plane
Let $\cal{A}_n$ be a simple arrangement of $n$ lines in $\mathbb{R}^2$.
(Simple: each pair of lines meet in a distinct point, i.e.,
no three lines pass through the same point.)
Start a random walk at ...
5
votes
0
answers
133
views
Chains of right annihilators in group rings
See the update below
This problem emanates from a question on not-so-simple random walks on finitely generated groups. But to explain the connections would require an extremely long essay.
Let $G$ be ...
5
votes
0
answers
469
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/...
5
votes
0
answers
93
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) \...
5
votes
0
answers
200
views
hitting time of a subset
Suppose you have the simple random walk on $L=\mathbb{Z}^n,$ and $A \subset L$ is a subset (in my case, the subset is a union of hyperplanes, so in particular infinite). There is a random variable $T(...
5
votes
0
answers
1k
views
Compute the expected value of the next step of a sorted random walk
Here's what I'm thinking about. If you have a random walk (move +1 or -1 at each step) of some fixed length, then if you're at the maximum of the walk, the next step you take is -1 with probability 1. ...
4
votes
0
answers
70
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$ ...
4
votes
1
answer
250
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 ...
4
votes
0
answers
130
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 ...
4
votes
0
answers
150
views
Random walks on the Poincaré disk
Let $G$ be the group of isometries of the Poincaré disk. Let $\mu$ be a probability measure on $G$, and consider $g_1,..,g_n$ i.i.d. random variables on $G$ distributed according to $\mu$. For $z\in \...
4
votes
0
answers
144
views
Ihara zeta function and closed paths and trails
Let $\Gamma$ be a finite graph. There seem to be two definitions of closed path in the literature. In one, a closed path is just a walk whose starting vertex is the same as the ending vertex. (Let us ...
4
votes
0
answers
180
views
Shannon-McMillan-Breiman theorem for expander graphs: rate of convergence?
Is the following uniform SMB theorem for random walks on expander graphs true?
For simplicity, I will state it for a finite group $G=\langle S \rangle$ and a uniform probability measure $\mu$ on the ...
4
votes
0
answers
278
views
Dyck paths weighted by height profile
We are interested in a question concerning a weight function on Dyck paths that penalizes visits to higher heights.
Let $\rho$ be a parameter. Let $D_k$ be the set of all nearest neighbor random walk ...
4
votes
0
answers
176
views
Who proved the reflection principle in random walks and Brownian motion?
I've heard Henry McKean say that the reflection principle is due to Désiré André. But the wikipedia page seems to say that André did not use a reflection principle. Does anyone know where the "modern" ...
4
votes
0
answers
161
views
average probability for an edge be a in random spanning tree of a weighted graph
any cofactor of a Laplacian of a weighted graph will give the sum of all weighted spanning trees, lets denote it by $A$. The same can be calculated for spanning trees which avoid certain edge $e$, ...
4
votes
0
answers
105
views
Do the normal forms for braid groups really conceal information about better than randomly applying the braid relations?
In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the ...
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}\...
4
votes
0
answers
146
views
What is the influence of unreliable comparisons on the results of sorting
Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when ...
4
votes
0
answers
88
views
Is the family of probabilities generated by a random walk on a finitely generated amenable group asymptotically invariant?
Is the family of probabilities $\mu^n$ (convolution) generated by a random walk $\mu$ on a finitely generated amenable group $G$ asymptotically invariant ($\|g\mu^n-\mu\|_{L^1}\to 0$ for any $g\in G$)?...
4
votes
0
answers
298
views
Why is the density function of a sum of many iid random variables (i.e., the Gaussian) self-dual?
In the usual proof of the central limit theorem via characteristic functions, we note that if $X_1, \dots, X_n$ are independent and identically distributed, with probability density function $f(x)$, ...
4
votes
0
answers
156
views
1d random walk probability of previous n positions
I have the following question.
(May be it is very simple, but I cannot find the answer).
Suppose I have a 1d random walk on integer numbers with equal pobabilities of unit step in either direction (...
4
votes
0
answers
177
views
Does the concept of connective constant make sense for any tiling of the plane?
First let me define what is the "connective constant" of a two dimensional lattice.
Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...
4
votes
0
answers
156
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 ...
4
votes
0
answers
1k
views
Random walk on the hypercube
Let $H_N=\{0,1\}^N$ the N-dimensional hypercube. We define the following random walk $X_n$ on $H_N$:
start from a point $x \in H_N$
pick at random an integer $k$ in $[1,N-1]$ and exchange $x(k)$ and $...
4
votes
0
answers
574
views
Monotonic properties of harmonic functions on graphs
I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...
3
votes
0
answers
119
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 ...
3
votes
0
answers
155
views
Conditional distribution of steps of random walk given the sum
Set-up. Consider a random walk $S_n=\sum_{i=1}^n X_i$, where $\{ X_i, 1\leq i < \infty \} $
is a sequence of i.i.d. random variables with distribution $\mu$, $\mathbb{E}X_1 = 0$. Let $a > 0$.
...
3
votes
0
answers
74
views
Probability of filling a small ball before exiting a big one for $d=2$
Let $S_n$ be the simple random walk in dimension $d=2$. Let $0<r<R$ and $\alpha \in (0,1)$. Let $B_r$ denote the $\{x \in \mathbb Z^2: \|x\|\le r\}$ where $\|\cdot\|$ is the Euclidean norm. ...
3
votes
0
answers
117
views
Hitting measure/overshoot for random walk in $\mathbb{Z}$ with heavy-tail
Let $\alpha \in (0,2)$, (or for simplicity just $\alpha \in (1,2)$) and let $X_1,X_2,\dots$ be an i.i.d collection of random variables with common distribution
$$
p(x,y)= \frac{c_\alpha}{|x-y|^{1+\...
3
votes
0
answers
78
views
Random walk in a switching scenery
For each $x \in \mathbf{Z}$ let $(\eta_t(x))_{t\geq0}$ denote independent copies of a process $(\eta_t(0))_{t\geq0}$ defined as follows. The process $\eta_t(0)$ takes values in $\{-1,1\}$, where $-1$ ...
3
votes
0
answers
60
views
Algebraic property of a transition matrix
Consider the simple random walk on $\mathbb{Z}^2$. Given a finite $\Sigma \subset \mathbb{Z}^2$, one can induce the random walk on $\Sigma$: set $\tau_0 = 0$, and define recursively $\tau_{n+1} := \...