The markov-chains tag has no wiki summary.

**1**

vote

**1**answer

78 views

### Variation of Markov Chain Convergence Theorem

Assume the chain $\{X_n\}_{n\in\mathbb{N}}$ on the statespace $(S,\mathcal{F})$ (we may assume it is countable) is aperiodic, irreducible and positive recurrent. We denote with $\pi$ its (unique) ...

**0**

votes

**0**answers

26 views

### How do I compute the variance of expected number of fair coin flips for HTH sequence using linear system of equations? [migrated]

Assuming fair coin flips, I know how to compute the expected number of coin flips to see HTH sequence by writing out the linear system of equations from the state transition diagram below.
...

**1**

vote

**0**answers

58 views

### How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...

**1**

vote

**0**answers

45 views

### Spectral radius of a column stochastic matrix perturbed by a rank-1 matrix

$P\in \mathbb{R}^{n\times n}$ is an irreducible column stochastic matrix. $P$ is also diagonally dominant. $w \in \mathbb{R}^{n} $ is a strictly positive vector satisfying $w^T \mathbf{1} = 1$ where ...

**0**

votes

**0**answers

19 views

### Practical Way to Detect a Markov Chain is Regular Given the Transition Matrix [migrated]

I understand that a Markov Chain is reducible if, given its transition matrix $P$, there exists $n$ such that every element of $P^n$ is greater than 0.
However, I am wondering that if there is an ...

**0**

votes

**0**answers

30 views

### Reference request for specific POMDP examples

Following is strictly for discrete-time discrete-space Markov chain.
Consider a partially observed Markov decision process (POMDP) $P = \{X,O,A,P,B_a\}$.
Here $X = \{x_1, \cdots, x_n\}$ refers to ...

**1**

vote

**0**answers

34 views

### Theorems on stochastic Lyapunov function

Let $X_n$ be a sequence of random variables such that
$$P(X_{n+1} \in A|X_m,x_m,m\leq n)= \int_A p(dw|X_n,x_n)$$
It is called a controlled Markov process.
Now, suppose there exist $\epsilon_0$, ...

**1**

vote

**0**answers

96 views

### Is the stationary distribution of this Markov chain uniform?

First, a little bit of background: Since 2012, Canada has decided to phase out the penny for its coinage system. Product prices may still use arbitrary cents, especially since prices do not typically ...

**1**

vote

**0**answers

65 views

### A sequence of Dirac Measure converging to stationary distribution of a Markov Chain

I have seen in a paper(http://www.sciencedirect.com/science/article/pii/S0167691105001040) Page 143 lemma 3.1, the following :
Let $X_n$ be an ergodic markov chain taking values in a complete ...

**1**

vote

**0**answers

22 views

### Effects of merging states on the limiting distribution of a Markov Chain

Consider a discrete time, homogeneous, finite state Markov chain given by a stochastic $n\times n$ matrix $M$.
We also have a cost vector $w$ of size $n$ with non-negative integer costs. The cost of ...

**1**

vote

**1**answer

112 views

### Deterministic finite-state automaton driven by a Markov chain

I've stumbled on some problem, and I have the feeling that this is closed to something well-studied in dynamical systems. The problem is the following. Consider a finite-state automaton with state ...

**5**

votes

**1**answer

296 views

### Can ergodic theory help to prove ergodicity of general Markov chain?

I am a beginner in ergodic theory. I have read some lecture notes(such as this and this) about it in hope that I could find something which helps to prove the ergodicity of some Markov chain taking ...

**-2**

votes

**2**answers

84 views

### Convergence of series made out of Markov Chain

$\{X_n\}$ be a ergodic Markov Chain taking values in $\Bbb Z$. Can I find some sufficient condition under which the $E[e^{\sum_{i} |X_i|}] < \infty$ (or say with some high probability).

**3**

votes

**0**answers

108 views

### Worst-Case Solution to (Stochastic) Matrix Inequality

EDIT: Some specific conjectures added.
This problem comes with an associated stochastic process, but I phrase everything as linear algebra in case somebody from a non-probability community has seen ...

**4**

votes

**0**answers

120 views

### minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...

**1**

vote

**1**answer

104 views

### Mixing time of a continuous time Markov chain with arbitrary rate matrix

I would like to calculate the mixing time of a continuous time starting from the rate matrix and not necessarily assuming that the time in between jumps have rate 1 - all I have is the (finite ...

**0**

votes

**1**answer

112 views

### On the inverse problem of Dobrushin

Dobrushin, in this paper, looked into the following problem. Suppose We are given a Markov kernel (conditional distribution) $P_{Y|X}$. Information theorist usually call $W$ a channel. It is known ...

**0**

votes

**0**answers

21 views

### Is there effective algorithm for finding “minimal discovery time” for large graphs?

Consider a large, probably sparse graph with Markovian random walkers on it. Define discovery time as time to first
reach a vertex by random walk
from uniform start. Are there effective ways to find ...

**0**

votes

**1**answer

73 views

### Does a irreducible set of states necessarily need to be closed in a Markov chain?

I have come across two different definitions for a 'irreducible set of states' of a Markov chain.
Definition 1: A subset of states $A$ of a Markov chain is irreducible if it is possible to access ...

**0**

votes

**0**answers

131 views

### A doubt on Balaji Meyn's ergodic theorem paper

I have a question regarding the classic paper by Balaji and Meyn: "Multiplicative ergodicity and Large Deviations for an Irreducible Markov Chain".
Consider a recurrent aperiodic irreducible Markov ...

**1**

vote

**0**answers

79 views

### Conditional probabilities in epidemic model

I was contemplating an epidemic model where infection and recovery rates are determined by links. Here node $i$ is infected first and recovers at a rate $\mu_i$. For all other nodes, the recovery is ...

**2**

votes

**1**answer

172 views

### Stationary distribution of Markov chain

Suppose I have a discrete time Markov chain $\boldsymbol{X}$ with state space $\mathbb{R}^+$. The chain is $\psi$-irreducible, aperiodic, atomless and has an invariant measure $\pi$.
If $\pi$ is ...

**1**

vote

**0**answers

102 views

### An optimization problem for a Markov Chain

Consider a Markov Chain $\{X_n\}$ whose transition probability depends on some parameter $\theta$ ($p_{ij}(\theta)$). Now I want to optimize the following quantity
$$\lambda(\theta) = ...

**1**

vote

**1**answer

167 views

### Can ergodic theorem be used here [closed]

Suppose I have an ergodic Markov Chain $\{X_n\}$ where $X_n$ are bounded. Now, Can I say anything on the limit
$$ \lim_{n\to\infty} \frac{1}{n}\ln E\left[e^{\sum_{i=0}^{n} X_i}\right]$$
I don't ...

**1**

vote

**1**answer

189 views

### Double Markovity

Suppose we have a double Markov relation for three random variables $X$, $Y$ and $W$ as follows
$$X\to W\to Y,$$ and $$X\to Y\to W.$$
How to prove that there exist functions $f$ and $g$ such that
...

**0**

votes

**1**answer

48 views

### Constructing a transition matrix of a time-homogeneous, finite Markov chain with full support stationary distribution

is there a way to construct a transition matrix of a time-homogeneous, finite Markov chain such that the stationary distribution always has full support (this is equivalent to all states of the chain ...

**0**

votes

**1**answer

47 views

### DTMC random walk model [closed]

For a discrete Markov chain random walk with p < 0.5 with state space S= {0,1,2..}
What is the stationary distribution?
I could use any help.
Thank you

**5**

votes

**0**answers

140 views

### Maximal inequalities for square of partial sums

Let $S_n = \sum_{i \leq n} X_i$ be the partial sums of a nice sequence of random variables $X_i$. In my application, $X_i$ is a functional of a finite-state, irreducible, aperiodic Markov chain, so ...

**1**

vote

**0**answers

58 views

### Simultaneous multiple perturbations in Markov chain Monte Carlo

I'm coding a McMC algorithm for geophysical applications.
Using the Metropolis-Hastings scheme to accept/reject the proposed models is smth that i thought i completely understood, but i don't. To be ...

**3**

votes

**1**answer

147 views

### Approximating Markov chains by Brownian motion

I would like a result along the following lines to be true, but haven't been able to locate it in the literature; pointers would be welcome.
Let $X_t$ be a finite-state, irreducible, aperiodic Markov ...

**1**

vote

**1**answer

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

**0**

votes

**0**answers

65 views

### Nonstationary Markov chain maximal inequality

Let $X_i$ be a (finite-state, irreducible, aperiodic) Markov chain, not necessarily stationary. (That is, it doesn't start from the invariant distribution; I'm happy to have it be time-homogeneous if ...

**1**

vote

**0**answers

234 views

### random walk with reflecting barriers [closed]

Consider a random walk on the line 1,...,d. You start at point 1. At each step you flip a coin: heads means go left, tails means go right. If you're at 1 and get a heads, just stay where you are (same ...

**1**

vote

**1**answer

135 views

### Gibbs sampler with linear constraints

My problem concerns the estimation of truncated multivariate normal distributions under constraints.
Let $X_1$ and $X_2$ two random variables following normal distributions ...

**4**

votes

**3**answers

542 views

### How to explain “Feller process” to an undergraduate student?

I had to explain in informal terms what a Feller process was, to undergraduate students who understand Markov property, Poisson processes and such. It was easy to define Levy process as generalisation ...

**6**

votes

**1**answer

194 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])$ ...

**2**

votes

**0**answers

36 views

### Markov decision processes: action set revealed at point of decision

I have a problem which looks like a finite horizon Markov decision process (MDP), except the action space at each time is revealed at the decision making point. There is no way to know before hand the ...

**6**

votes

**2**answers

547 views

### References for a physicist migrating to stochastic processes

I've studied "Markov Chains" - Norris and "Measure, Integral and Probability" - Capinski, Kopp. Now, I'm looking for a couple of books (or other references) that help me bridging these two topics. ...

**2**

votes

**0**answers

75 views

### Mixing time for dimers on the square-octagon graph

Consider the "fortress graph" of order $n$ (see Figure 9 of http://faculty.uml.edu/jpropp/tiling/www/mdblum/arctic.html). It's been known empirically for twenty years that if one turns the set of ...

**4**

votes

**3**answers

1k views

### Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...

**0**

votes

**0**answers

26 views

### Examples of POMDPs where the actions impact the transitions of the underlying markov Chain

I am not sure if the following is a legitimate question for this board.
I am looking for examples of Partially observed Markov decision processes (preferably infinite horizon, Discrete time, Discrete ...

**0**

votes

**1**answer

115 views

### Monte Carlo estimator with autocorrelated samples

Given an integration problem $I=\int{f(x)dx}$, we can construct an ordinary Monte Carlo estimator as
$E[I]=\sum\limits_i\frac{f(x_i)}{p(x_i)}$
where the samples $x_i$ are usually i.i.d. and drawn ...

**0**

votes

**1**answer

119 views

### Is any invariant, ergodic measure with full support on an irreducible Markov shift a Markov measure?

I have this question I have been struggling with for a while. It seems rather intuitive, however, I was not able to proof it yet:
Let $\Omega = \{1,2,\cdots,N\}$ a finite alphabet, $\Sigma \subset ...

**4**

votes

**3**answers

253 views

### Invariant measure of Euler-Maruyama Discretisation of an Ito diffusion

Let $(X_t)_{t \geq 0}$ be a diffusion process with dynamics governed by the stochastic differential equation
\begin{equation}
dX_t = b(X_t)dt + \sigma(X_t)dW_t, ~~ X_0 = x_0,
\end{equation}
where ...

**2**

votes

**1**answer

139 views

### convergence rate of occupation measure of ergodic Markov Chain

Given an ergodic Markov chain $(X_n)_{n\geq 1}$ in $R^d$with $\pi$ as the invariant distribution of the transition kernel, under good conditions we have that the empirical occupation measure converges ...

**1**

vote

**1**answer

157 views

### forward algorithm Hidden Markov Model

I am studying the the forward-backward algorithm used in Hidden Markov Models. I understand that that you are trying to propagate through a sequence (and the available states) to find the most ...

**3**

votes

**0**answers

96 views

### Nonlinear Markov process

Consider the following nonlinear $\mathbb{R}$-valued stochastic recursive sequence:
$ X_{n+1} = F(X_n) + W_{n+1}, \quad (W_n)_{n\ge1} \stackrel{ \scriptsize \mathrm{i.i.d.} }{ \sim } \phi. $
How can ...

**3**

votes

**2**answers

179 views

### Markov Partitions for toral automorphisms

I know that my question is more practical than theoretical. But, I do know where to look for the theoretical sources.
I want to find a program in the case that it exists (does it?), or to program it. ...

**1**

vote

**0**answers

111 views

### segmental k-means hmm algorithm

I'm trying to determine the state parameters for an hmm with a minimum of 9 states. I'm running chunks of my data through hmmtrain on MATLAB which I think uses the Baum/Welch aka forward/backward ...

**2**

votes

**0**answers

303 views

### Closed-form solution to a system of linear equations

Consider the following $n \times n$ matrix with a particularly nice structure:
\begin{equation}\mathbf{P}=\begin{pmatrix}
0 & 0& \dots&0 & 0 &1\\
0 & 0& \dots&0 & ...