# Tagged Questions

The markov-chains tag has no usage guidance.

**1**

vote

**0**answers

14 views

### Unique Stationary Distribution of A Markov Chain

I have a Markov Chain like $Y_i=\sum_n\pi_{n,i}(Y)Y_n$, i=1,2,3...N.
So the Markov chain has N states and the transition matrix depends on the vector $\textbf{Y}$. I am wondering what conditions $\pi$ ...

**2**

votes

**2**answers

91 views

### Asymptotic Growth of Markov Chain

I asked the following question one week ago at math.stackexchange but didn't receive a response, so I want to give it here another try:
I'm interested in the following problem: We have got a time-...

**7**

votes

**0**answers

188 views

+50

### Hierarchical (Recursive) Random Walk (also known as Hierarchical Hidden Markov Model)

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/...

**0**

votes

**1**answer

34 views

### Convergence of an inhomogeneous markov chain

A markov chain is defined as $X_t=F(X_{t-1})X_{t-1}$, where $X_t$ and $X_{t-1}$ are both vector. So the transition matrix depends on the current states. I want to show that for any given initial ...

**10**

votes

**3**answers

292 views

### How to sample a uniform random polyomino?

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, ...

**2**

votes

**1**answer

260 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 ...

**0**

votes

**0**answers

22 views

### showing that a matrix has repetitive values?

Here my primary aim is to calculate the stationary distribution of a DTMC using left-eigen values i.e, $ \pi = \pi*P$.
But for some matrices, I observe that some states a same stationary probability. ...

**5**

votes

**2**answers

171 views

### Frequency of visiting states in Markov chains

Given a finite, ergodic Markov $\{X_i\}$, and two natural numbers $a>b$. Let
$$p=P\left[\forall n, \sum_{k=n}^{n+a-1} \mathbf{1}_m(X_k)\leq b\right]$$
where $\mathbf{1}_m(X_k) =1$ if $X_k=m$ and 0 ...

**5**

votes

**2**answers

1k 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 ...

**6**

votes

**1**answer

110 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)$ ...

**0**

votes

**1**answer

101 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\}$...

**0**

votes

**0**answers

76 views

### Looking for an exposition of a certain theorem of Talagrand

The following is a theorem by Talagrand (as stated here, http://arxiv.org/pdf/1511.08609v1.pdf),
Let $(X, \mu)$ be a probability space. Let $F : X \rightarrow \{0,1\}$
be a family of functions ...

**1**

vote

**1**answer

63 views

### Uniqueness of invariant measure for equivalent transition probabilities

Suppose $P(x,dy)$ and $Q(x,dy)$ are two Markov transition kernels on a topological space $E$ equipped with Borel $\sigma$-algebra $\mathcal B(E)$. Suppose for every $x \in E$, $P(x,\cdot)$ and $Q(x, \...

**0**

votes

**0**answers

26 views

### Dependency of the error term on the states, in the definition of the transition rates of a continuous time Markov chain

I think this is certainly not a research or graduate level question. But I didn't get any answer from math.stackexchange.com.
I'm studying G.F.Lawler's stochastic process book. There he defines the ...

**1**

vote

**2**answers

69 views

### How can I efficiently approximate the stationary distribution of an infinite CTMC with a sparse rate matrix?

I am looking for methods to approximate the stationary distribution of an infinite CTMC with a sparse rate matrix. Each row and column of the rate matrix has a finite number of non-zero elements. ...

**4**

votes

**3**answers

374 views

### Why does the overhand shuffle converge to the uniform distribution on $S_n$?

Pemantle 1989 proves, among other things, that the Markov chain on $S_n$ induced by repeatedly and independently performing an overhand shuffle on a deck of $n$ cards is ergodic and has limiting ...

**2**

votes

**0**answers

132 views

### markov processes and ergodic theory

For an ergodic Markov Chain
$$
\frac{1}{N}\sum_{i=1}^n f(X_i) \rightarrow E_\pi[f]
$$
where $\pi$ is the invariant distribution. I am also dealing with a Markovian process (a state space model to ...

**3**

votes

**2**answers

168 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 ...

**-1**

votes

**1**answer

39 views

### Discrete time hidden markov process [closed]

I am dealing with a hidden Markov model for variable $X_{t+1}$ where
$X_{t+1}$ = $\alpha_{t}$$X_{t}$ + $(1-\alpha_{t})$$Z_{t}$
$X_{t}$ is an indicator variable indicating wether an individual is ...

**1**

vote

**1**answer

130 views

### Neat definition of Harris Ergodicity

I can't find any reference where the definition of Harris Ergodicity for Continuous time Markov processes is defined.
a) What would be exactly the definition?
b) What reference could be helpful?
...

**6**

votes

**1**answer

325 views

### Does every (generalized?) Markov chain admit transition probabilities?

To pose the question let us start by recalling the following notions:
Transition Probabilities. A transition probability matrix between two measurable spaces $(S,\mathcal{S})$ and $(V,\mathcal{V})$...

**1**

vote

**1**answer

70 views

### Is there an easy way to convert a non-deterministic optimal policy to a deterministic optimal policy for a given MDP?

For a MDP (Markov Decision Process) is there an easy way to convert a non-deterministic optimal policy into a deterministic optimal policy?
The trivial way will take $O(|\mathcal{A}|^{|\mathcal{S}|}$...

**2**

votes

**0**answers

153 views

### Must rows of a transition matrix be distinct?

Is it true that for all continuous time Markov processes on a countable state space $S$, we have
all rows of the transition matrix $\mathbf{P}_t$ are distinct for all time $t\in[0,\infty)$ ?
This ...

**5**

votes

**0**answers

69 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) \...

**1**

vote

**1**answer

60 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}$ ...

**0**

votes

**0**answers

30 views

### Sufficient moment conditions to make $E[\sup_n |X_n|]< \infty$ for Markov process $X_n$

Is there any Markov process $X_n$ for which we can impose sufficient moment condition which will imply $E[\sup_n |X_n|]< \infty$

**0**

votes

**0**answers

34 views

### Strong Markov vector-valued process from component strong Markov process and independence

I want to prove that if $X$ and $Y$ are (continuous time) independent strong markov $\mathbb{R}$-valued processes w.r.t. their natural filtrations $\mathcal{F}^X_t$ and $\mathcal{F}^Y_t$, that the ...

**1**

vote

**0**answers

46 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 ...

**0**

votes

**1**answer

30 views

### Does an infinite chain of a.s. eventual transitions between states necessarily implies a.s transitions along the whole chain?

Given a Markov process among a (possibly infinite) set of states $S$, with possibly infinite depth (that is, the transition probabilities from $s_i \to s_j$ at time $t$ are permitted to depend not ...

**2**

votes

**1**answer

111 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) (...

**0**

votes

**0**answers

57 views

### Maximal inequality for Markov process

For a Markov process $\{X_n\}$ is there any inequality available for
$$ E[\sup_{0 \leq n \leq k} X_{n}]$$
in terms of moments of $E[X_n], 0 \leq n \leq k$

**0**

votes

**0**answers

19 views

### Can MDPs over functions be solved?

I understand that dynamic programs are difficult to be solved in general. However I have an MDP, for which intuitively I have a solution, I am curious to know if there is a formal approach to get a ...

**-2**

votes

**1**answer

34 views

### how to resolve the infinite nesting of interactive POMDP

I am reading papers about I-POMDP. I cant understand the finitely nested I-POMDPs given in these papers.
The belief update of the algorithm has a problem that agents' belief updates mutually depend ...

**1**

vote

**0**answers

101 views

### Markov Chains and Simple Machine Learning [closed]

Suppose I have a large training set consisting of many strings of symbols.
$TS = \{Str_0, Str_1, ..., Str_n\}$
$Str_i = \{Sym_0 ... Sym_{len}\}$
These strings of symbols are each generated by the ...

**1**

vote

**0**answers

23 views

### Properties of a map regarding the space of invariant probability measures for controlled Markov process

Let us consider a controlled Markov process with the transition kernel $p(dy|x,\theta)$ ($\theta$ being the control parameter. Now, consider the map
$\theta \to I(\theta)$ where $I(\theta)$ is the ...

**0**

votes

**0**answers

30 views

### Markov Modulated Markov Chain

Consider a discrete time Markov chain $X_t$ on some finite state space $\mathcal{S}$ with transition matrix $P$. Now consider a process $Y_t$ also on $\mathcal{S}$, which conditioned on $X_{t}=s$ ...

**2**

votes

**1**answer

80 views

### Eigenvectors of a perturbed reducible stochastic matrix

Let $Q$ be a $n\times n$ reducible stochastic matrix. Let $J$ be such that $[J]_{ij}={1 \over n}$. Now for a small positive constant $\alpha\in [0,1]$, consider the matrix $$\tilde{Q}\,=\,(1-\alpha)Q+\...

**0**

votes

**0**answers

56 views

### Circular process ergodic?

Let us define a continuous-time Markov process on a circle consisting of $m-$ equally spaced points, i.e. every point has two neighbours.
Now, we define a space of functions $S:= \{-1,1\}^{\{1,...,m\}...

**0**

votes

**1**answer

176 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 ...

**1**

vote

**0**answers

17 views

### Bounding Hidden Markov model Bayesian filter error with inexact models

In context of a hidden Markov model, I am interested in bounding the error of a Bayesian filter when using inexact state transition and observation models.
Consider a hidden Markov model (HMM) with ...

**0**

votes

**0**answers

48 views

### Regularity of the entrance measure of SRW

Let $S(n)$ be the discrete sphere of radius $n$ (i.e., the internal boundary of the Euclidean discrete ball $B(n)$) centered in the origin, and consider a simple random walk starting at some $x\in\...

**0**

votes

**0**answers

68 views

### Order statistic of Markov chain sample path and related probabilities

Consider a 1D sample path, denoted as $\{X(1), ..., X(t), ..., X(n)\}$, generated from a discrete time finite state (time homogeneous) Markov chain over states $\{1,...,m\}$, with transition ...

**1**

vote

**0**answers

37 views

### steady state of a continuous-time birth-death process

we consider a continuous-time birth-death process $\{X(t),t\geq 0\}$ with discrete state space taking non0negative integer values $\{0,1,2,3,...\}$. The transition rates of the process $\{X(t)\}$ are ...

**3**

votes

**1**answer

101 views

### Similarity transformation of transition matrix of reversible Markov chain (reference request)

If $P$ is the transition matrix of a reversible Markov chain, and $\pi$ is its stationary distribution, and let $R$ be defined by:
$$R_{ij} = \sqrt{\frac{\pi_i}{\pi_j}}P_{ij}~.$$
By reversibility, ...

**2**

votes

**0**answers

46 views

### Spectral gap of two step Markov chain

Suppose $X_1,X_2,\ldots$ is a reversible Markov chain with state space of size $k$ and absolute spectral gap $\gamma_*.$ What is the spectral gap of the (non-reversible) Markov chain $Y_1,Y_2,\ldots,$ ...

**0**

votes

**0**answers

32 views

### steady state distribution for a jump Markov chain

Consider a queueing process with the following transition matrix:
$\mathbf{P}=\left( \begin{smallmatrix}
1-\lambda & \lambda & & & & & & &\\
\mu & 1-\...

**0**

votes

**1**answer

88 views

### Finite hitting time implies hits at any finite time?

I was wondering about the following problem:
Assume we have a state space $S:=\mathbb{Z}$ and a Markov chain, such that we can go from any state $x$ to some state $y$ with positive probabilities, i.e....

**0**

votes

**0**answers

27 views

### steady state distribution of the following infinite-state Markov chain

Given the following state transition equation:
$P_0(n+1)=P_0(n)(1-\lambda \Delta t)+ P_1(n)\mu \Delta t$
$P_j(n+1)=P_{j}(n)(1-\lambda \Delta t-\mu \Delta t)+\lambda \Delta t P_{j-1}(n)+ \mu \Delta t(...

**0**

votes

**1**answer

111 views

### Markov chain with Feller property

Does anybody know whether there is an analysis of when the monotone decreasing chain has the Feller-property?
The monotone decreasing is defined as a chain on $\mathbb{N}$ and the rate of going down $...

**0**

votes

**0**answers

223 views

### Calculate the KL divergence between two transition matrices

I want to calculate how different two markov transition matrices are.
For example:
$\begin{pmatrix} .2 & .8 \\ .1 & .9 \end{pmatrix}$
and
$\begin{pmatrix} .3 & .7 \\ .1 & .9 \...