All Questions
Tagged with markov-chains random-walks
16 questions with no upvoted or accepted answers
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
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
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
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
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 ...
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
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
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
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
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. ...
