All Questions
Tagged with markov-chains random-walks
62 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
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
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
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
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
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
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
0
votes
1
answer
110
views
Skip-free random walks: recurrence and transience
Let us define a one dimensional random walk: for all $n\in\mathbb{N}$
$$
X_n:=\sum_{i=1}^nZ_i
$$
with $Z_i$ i.i.d. random variables taking values in $\{-1,0,1,2,\dots\}$. This process is sometimes ...
- 59
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
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
0
votes
1
answer
112
views
Recurrence criterion for non-reversible random walks on general infinite (locally finite) graph with unequal edge weights
Can someone please provide a reference (starting point) for analysing recurrence/transience of random walks on graphs with general edge weights? Looking into random walks that are known to be NOT ...
- 15
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 ...
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
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
0
votes
1
answer
324
views
Mixing time for random walk on graph with $k$ loops on each vertex
I try to find an upper bound for the mixing time of a random walk $S$ on a connected graph $L=(V,E)$ which has $k<\min_{v\in V}d(v)$ loops at every vertex. The transition probabilities of this ...
- 91
1
vote
0
answers
181
views
Random walk on 2d lattice with obstacles
Consider a random work on $L=\mathbb Z^2$ endowed with obstacles (i.e each cell $(x,y)$ of $L$ may contain a obstacle, i.e the random walk halts whenever it hits such a cell). Let $P(x,y) = 1$ if cell ...
- 6,853
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
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
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
0
answers
79
views
Discrete Markov process on finite interval
Consider an contiguous array of $N$ states, numbered from $1$ to $N$.
At every time step $t$, the process should transition to an adjacent state.
The probability of moving to the right (from state $n\...
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
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
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
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
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
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
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
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
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
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
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
0
votes
1
answer
613
views
2 Random Walkers on 2d square lattice, Torus
I am looking for the probability that two random walkers initially at different sites, meet at step t if they are moving on a 2-dimensional torus(Square Lattice)
Any help would be appreciated.
- 53
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
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
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
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
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
0
votes
1
answer
414
views
Exact formula for computing n-step transition probability of random walks with self-transitions
Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...
- 1
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
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
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
0
answers
56
views
Expected number of forward jumps to reach a given quantile of a rv [closed]
I'm a noob in randomized algorithm and ran into a problem(definitely not home work. I'm doing a self study out of my interest with help of my friends. I'm pursuing research career in a machine ...
- 221
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
0
votes
1
answer
1k
views
Mixing time of lazy random walk on the directed cycle $C_n$
Briefly: A hint (if this is easy), reference or derivation would be of great help.
The question
Let $C_n$ be the directed cycle with loops in each of its $n$ vertices, and consider the random walk ...
- 188
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
0
votes
0
answers
111
views
Markov chains on a polyhedron
A modification of a question from Gerard Letac (1976): A m-sided q-adjacent-faced polyhedron has one of its faces "up." Each round, the polyhedron rolls so that any of the adjacent faces is now up. ...
1
vote
0
answers
46
views
Is there an effective algorithm for finding "minimal discovery times" for large graphs?
Consider a large, probably sparse graph with Markovian random walkers on it.
Define the discovery time as the expected time to first reach a vertex by
random walk from a uniform start. Are there ...
- 355
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