All Questions
Tagged with markov-chains random-walks
62 questions
14
votes
2
answers
2k
views
Markov chains: invariant measures and explosion
The following seems like such an elementary question, but I didn't get anywhere with it.
Suppose you are considering a Markov chain in continuous time which is transient and has an invariant measure (...
11
votes
4
answers
3k
views
What is the cover time of a random walk on a cube?
I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the ...
- 241
9
votes
0
answers
239
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 ...
- 891
7
votes
1
answer
337
views
First Collision Time for k Random Walkers on a Torus
I consider $k$ random walkers on $\mathbb{Z}^{d}/n \mathbb{Z}^{d}$, the $d$-dimensional torus of side length $n$. More precisely, I will define a Markov chain $Z_{t} = (X_{t}[1], \ldots, X_{t}[k])$ ...
- 71
6
votes
2
answers
2k
views
Random walk to stay in an interval forever
Consider a random walk on the real time, starting from $0$. But this time assume that we can decide, for each step $i$, a step size $t_i>0$ to the left or the right with equal probabilities.
To ...
- 502
6
votes
1
answer
482
views
Average and max. hitting time to a specific vertex
Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes.
Let
$H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
- 73
6
votes
1
answer
361
views
Random walks on infinite directed regular graphs
Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).
Assume that $\Gamma$ is bi-regular, that is ...
- 26k
6
votes
1
answer
170
views
Basic Definition and Notations in RWRE
From the definition of Zeitouni's lecture notes on RWRE: $(V, E)$ is a special graph, and $N_v:= \{k \in V: (v,k) \in E\}$ is the neighborhood of $v \in V$. $\Omega = \prod_{v \in V} M_1(N_v)$ ...
- 61
5
votes
1
answer
7k
views
Expected Hitting Time for Simple Random Walk from origin to point (x,y) in 2D-Integer-Grid
Consider a simple random walk on the lattice $\mathbb Z^2$ starting at the origin $(0,0)$ where in each step, one of the four adjacent vertices in chosen uniformly at random, i.e. with probability $1/...
- 53
5
votes
2
answers
1k
views
Expectation of first positive value in random walk
Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in
$\lbrace -1, \frac{1-p}{p} \...
- 621
5
votes
0
answers
485
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/...
- 1,127
5
votes
0
answers
95
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) \...
- 527
4
votes
2
answers
261
views
Probability question about random shuffling of piles of rocks
I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the ...
- 41
4
votes
1
answer
247
views
Random walk visiting a cylinder infinitely often
I wonder whether a $d$-dimensional random walk $S_n$, generated by the infinite i.i.d. copies of X given by:
$X=e_1=(1, 0, 0, ..., 0)$ (with probability $p_1$)
$X=e_2=(0, 1, 0, ..., 0)$ (with ...
- 91
4
votes
1
answer
176
views
Random Walk with "Forward Dependency"
Let $\{X_t\}_{t=-\infty}^{\infty}$ be a sequence of random variables. We are interested in a "random walk" (or more generally, a random field) that can be characterized by
$$
X_t ~|~ X_{t-k}, \ldots, ...
- 1,127
4
votes
1
answer
126
views
Dynamic site percolation of independent random walkers on 2-dimensional square lattice
I am stuck in a part of my research which I am not expert in.
I have a 2-dimensional square lattice with periodic boundary conditions(torus). I am placing one walker at each node at the beginning. It ...
- 53
4
votes
1
answer
555
views
Approximating a hitting time for some state using the stationary distribution?
Provided a random walk on a bounded interval, with step probabilities, $p$ and $q$ and a stationary distribution $\pi$, how "bad" of an approximation is to assume that the hitting time for a position $...
- 41
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
4
votes
2
answers
255
views
The necessary sufficient condition for recurrence of a Markovian random walk
Suppose $\sigma_{1},\sigma_{2},...$are i.i.d random variables.$S_{0}=0$. Define $S_{n}=S_{0}+\sum_{i=1}^{n}\sigma_{i}$, then ${S_{n}}$ is a Markovian random walk.
I want to figure out the necessary ...
- 41
3
votes
2
answers
277
views
Is there something like a "self-avoiding Markov chain" on a continuous space?
If stumbled accross self-avoiding walks. They seem to be deterministically generated, but from a quick google search term seem to be randomly generated variants.
However, as far as I can see they are ...
- 167
3
votes
1
answer
2k
views
Hitting time probability in a Random Walk with possibility to die.
A Random Walker can move of one unit to the right with probability $p$, to the left with probability $q$ and it can jump again to the starting point with probability $r$ and die. Naturally $p+q+r=1$. ...
- 295
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
3
votes
1
answer
220
views
Carne-Varopoulos bound and stationary measure
Let $\Gamma$ denote the Cayley graph for a finitely generated group $G$, and let $p_n(x, y)$ denote the transition probability that a random walk starting at $x$ reaches $y$ at time $n$. A famous &...
- 31
3
votes
0
answers
63
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} := \...
- 581
3
votes
0
answers
115
views
Approximating the *conditional* probability of 1D discrete random walk not having revisited the origin given last position
I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees.
Consider a 1D random walk on the integers, starting at the origin, ...
- 101
3
votes
0
answers
151
views
Sequential generation of any random graph
The high-level question is: can we generate any random graph with size $d$ using a Markov chain?
For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
- 1,127
2
votes
1
answer
232
views
If the diameter of a bounded degree, directed graph is polynomial in the degree of the graph, is the mixing time also polynomial?
Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting ...
- 2,185
2
votes
1
answer
412
views
Does random walk have more concentration surrounding the origin?
Consider a simple random walk $S_n$ on one dimension, starting at $0$. In this case, $S_n$ fluctuates between $-\infty$ and $\infty$, but intuition says that it might stay more often in an interval ...
- 502
2
votes
2
answers
1k
views
probability distribution of hitting nodes on a finite graph random walk
Consider a finite, undirected, scale-free graph $\{G}$, with uniform edge weights. We define a truncated random walk on $\{G}$ as a random walk that continues for exactly $\{k}$ steps. For an ...
- 23
2
votes
1
answer
168
views
Random Walk 2D with dependent weights [closed]
I have spent a lot of time trying to solve this problem but have had no luck so far! Any help would be highly appreciated!
Suppose I have a 3x3 grid as shown below.
(3,1) (3,2) (3,3)
(2,1) (2,2) (...
- 23
2
votes
1
answer
421
views
Extending Wald's equation to two classes of i.d. random variables?
I try to adopt Wald's equation to a slightly more complex problem. In fact, after a full day, I found some solution now, but it has a confusing argument in the middle. Perhaps somebody can help me at ...
- 340
2
votes
1
answer
447
views
MCMC with progressive demollification of delta distributions
Edit: I simplified the example to a canonical case for clarity.
Given an integral $\int_{\Omega}{g(\mathbf{x})}$ with a well-posed integrand $g(\mathbf{x})$ defined on some multidimensional space $\...
2
votes
0
answers
700
views
Simple random walk on a discrete torus - the eigensystem, reference
My problem concerns finding a reference in which the formulae for the eigenvalues and the corresponding eigenvectors ($n$ linearly independent eigenvectors!) for the transition matrix of a simple ...
user83658
2
votes
0
answers
114
views
Hyperbolic decay of transition probability for random walks on infinite graphs
Consider a nearest-neighbor (or say simple) random walk on a connected graph $G$ with infinite vertices where each vertex has a finite degree. Let $P^n_{o,o}$ be the probability of the random walk ...
- 87
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} \...
1
vote
1
answer
4k
views
First passage time of a 1D simple random walk in a discrete time infinite markov chain [closed]
If we consider a simple Random Walk on the positive integers (discrete Markov chain), with symmetric transition probabilities. We start at time $0$ at the integer $i_0 = m$ and at each time step $P(...
- 53
1
vote
2
answers
302
views
how to derive stationary distribution of maximal entropy random walk
I was reading the paper 0810.4113v2, burda, which analyzed the stationary distribution maximal entropy random walk on the irregular lattice. I am confused on some of the steps.
Description:
The ...
- 211
1
vote
1
answer
951
views
Stationary distribution for directed graph
I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
- 13
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
1
vote
1
answer
284
views
Symmetric random walks - bounds on the amount of time spent in a subset $A$?
For a symmetric random walk $S_n$, if we have a bound $P(S_n \in A) < \delta$, do we get a bound on the amount of time $S_n$ spends in $A$?
Let $S_n$ be a symmetric random walk on the integers. ...
user145350
1
vote
1
answer
2k
views
Simple finite random walks with reflective boundaries
Let us take the 1D case: for an n-step random walk on a line confined between two boundaries at positions t and s, can we determine the average time (number of steps) the walker spends off the ...
user88381
1
vote
1
answer
431
views
Properties of moment generating function of random walk on unit sphere
Question in brief
Let $a$ and $b$ be unit vectors in $\mathbb{R}^d$. Let $f$ be the $1-step$ transition function of a random walk on the $d$ dimensional unit sphere.
I am interested in evaluating $\...
- 720
1
vote
1
answer
276
views
Number of deaths in birth-death process conditioned on start and end points
Say I have a simple linear continuous time birth-death process with state space the non-negative integers, where there are parameters $b$ and $d$, with the rate (as you'd see in a $Q$ matrix) of going ...
- 11
1
vote
1
answer
92
views
Choose uniformly from fixed-length paths in $[0,n]\cap\mathbb{Z}$ with fixed start and end
Let $X_k$ be a symmetric (discrete time) random walk on $\mathbb{Z}$ and let $m,n\in\mathbb{N}$. I want to chose uniformly from the paths of $X_k$, which
start at $0$
stay in $[0,n]\cap\mathbb{Z}$ ...
- 113
1
vote
1
answer
242
views
Two types of random walkers on square lattice
Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index $1$...
user82424
1
vote
1
answer
128
views
N random walkers that hit node v in a graph
Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...
- 111
1
vote
1
answer
249
views
Distributions induced by (weighted) random walks on the integer lattice
Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ ...
- 3,059
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
1
vote
0
answers
73
views
Reference for the asymptotic mixing time of the random walk on the cycle
In Diaconis's book Group Representations in Probability and Statistics, Chapter 3C, there are explicit computations for the mixing time of the random walk on the cycle graph $\mathbb{Z}_{p}$, with $p$ ...
- 111
1
vote
0
answers
89
views
Understanding the statements of Theorem 5.5 and Lemmas 5.6, 5.7 and 5.8 from a French paper by Yves Guivarc’h and Émile Le Page
I would like to understand the statement and the proof Theorem 5.5 just for the special case when $X$ is a single point from the paper “Simplicité de spectres de Lyapounov et propriété d’isolation ...