Stochastic processes (with either discrete or continuous time dependence) on a discrete (finite or countably infinite) state space in which the distribution of the next state depends only on the current state. For Markov processes on continuous state spaces please use (markov-process) instead.

learn more… | top users | synonyms

3
votes
1answer
33 views

Application of diagonalization of matrix - Markov chains

Problem: Suppose the employment situation in a country evolves in the following manner: from all the people that are unemployed in some year, $1/16$ of them finds a job next year. Furthermore, from ...
0
votes
0answers
12 views

Solving a quadratic vector/tensor equation arising from connected Markov chains

I have a discrete-time finite-state aperiodic irreducible Markov chain, which is composed of $m$ identical component sub-chains. With probability $1-\mu$, in each time step each of these chains ...
4
votes
1answer
110 views

When the sum of independent Markov chains is a Markov chain?

I try to find as much as possible cases, when the chain $Z(t) = |X_1(t)-X_2(t)|$ is Markov, where $X_1(t)$ and $X_2(t)$ are independent, discrete-time and space, preferably non-homogeneous Markov ...
1
vote
0answers
17 views

Markov-Chain Monte-Carlo: Are transformations on the inputs valid?

The problem: I am trying to solve a high dimensional (up to ~50) class of data fitting & modelling problems. The user specifies the problem, so I would like to make the configuration as easy as ...
1
vote
0answers
22 views

Determanistically skipping through time of a time homogeneous Markov chain

Suppose I have an infinite number of time steps $X_0,\ldots,X_i,\ldots$, where each $X_i$ is an infinite dimensional random vector consisting of 0's and 1's. I now specify $P(X_i|X_{(i-1)})$ and an ...
0
votes
0answers
60 views

From one-dimensional to two-dimensional Markov chains

I have a $M/M/1$ queueing system that is described below: There are two types of customers in the system with different arrival rates, $\lambda_{sg}$ and $\lambda_{sb}$. Service rate is $\mu$. Type ...
1
vote
2answers
52 views

Behavior of transient states as $n \rightarrow \infty$

Let $(X_n)_{n \geq 0}$ be a discrete time-homogeneous Markov chain on the state space $E$. Suppose $T \subseteq E$ is the set of transient states. Can it be that we stay forever in $T$, with ...
0
votes
1answer
20 views

Expected Number of Visits - why is $E_x[N_x]=\sum_{n \geq 1} p_{x,x}^{(n)}$

Suppose $(X_n)_{n \geq 0}$ is a discrete-time time-homogeneous Markov chain with transition probabilities $$P[X_{n+1}= y \mid X_{1}=x] = p_{x,y}^{(n)}.$$ Let $$N_x:=\sum_{n \geq 1} 1( X_n=x)$$ denote ...
0
votes
1answer
40 views

Does aperiodicity needed for ergodic theorem to hold true?

Given a irreducible and positive recurrent countable state Markov Chain with unique stationary distribution $\pi$, is the following true $$\frac{1}{n}\sum_{i=1}^{n}X_i \to \sum j \pi_j$$ Or, to ...
3
votes
1answer
35 views

Doubly stochastic matrix proof

A transition matrix $P$ is said to be doubly stochastic if the sum over each column equals one, that is $\sum_i P_{ij}=1\space\forall i$. If such a chain is irreducible and aperiodic and ...
1
vote
2answers
28 views

Find the expected frequency of some state in a state sequence of length N given a transition matrix M

I can represent stochastically-articulated sequences of states using a transition matrix M where a given entry in cell (i,j) corresponds to the probability of state j given that the current (or, most ...
1
vote
2answers
35 views

Proof that state can be reached

Prove that if the number of states in a Markov Chain is $M$, and if state $j$ can be reached from state $i$, then it can be reached in $M$ steps or less. To me it just seems the definition of ...
0
votes
1answer
37 views

Finding the stationary distribution for an absorbing Markov Chain

I have an absorbing Markov Chain that has 5 states, that can be envisioned as 5 nodes in a straight line. The left and right most nodes are the absorbing states. Everything starts at the middle node ...
2
votes
1answer
22 views

Use and interpretation of the first and second right eigenvectors of a right Markov matrix?

Let M be a Markov matrix with rows summing to 1. The interpretation of the left eigenvectors of M is clear. For instance, the first left eigenvector is the stationary distribution of M. And the left ...
1
vote
1answer
34 views

Calculating a stochastic matrix with multiple states

I am struggling with how to calculate the values of a Markov matrix which has multiple states. For example, Imagine an unfair 6 sided dice. The chance of rolling a 1,2,3,4,5 or 6 is 0.3, 0.25, 0.2, ...
1
vote
0answers
65 views

Understanding the formula

Let $P$ the transition probability matrix and $\mu$ the row vector of initial distribution. $$P_\mu(X_n=j)=\sum_j\mu(i)p^n(i,j)=\mu p^n(j)$$ I don't want to make a proof of that, I want to ...
2
votes
0answers
45 views

Unique stationary distribution (or measure?) of a Markov Chain

Let $(X_n)_{n \geq 0}$ be a irreducible, positive recurrent Markov chain. We have a theorem that states that the unique stationary distribution is then given by $$\pi(x)= \frac{1}{E_x[H_x]},$$ where ...
0
votes
1answer
25 views

Simple or Strong Markov Property when conditioning on value of stopping time?

Suppose I have a discrete-time Markov Chain $(X_n)_{n \geq 0}$ with the hitting time $H_x:= \inf \{n \geq 0 \colon X_n = x\}$ for some $x \in E$, where $E$ is a countable state space. Consider now ...
0
votes
1answer
36 views

Is {$X_n,n\geq 0$} a markov chain?

Consider a process {$X_n,n=0,1,\dots$}, which takes on the values $0,1,2$. Suppose $$P(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},\dots,X_0=i_0)$$ $$=P_{ij}^I,\text{when n is even}$$ ...
3
votes
1answer
52 views

Random Walk Threshold Problem with a Time-Dependent Threshold

For any constant threshold in a random walk, the probability we cross the threshold at some time goes to 1 as time goes to infinity. But how can we approach the problem if the threshold is time ...
0
votes
0answers
34 views

Using Mathematica to calculate expected time to absorption

I am trying to solve a standard ETA on a birth-death process with $n$ states $\in \{0,\cdots,n-1\}$ where state $n-1$ is absorbing. Also $\mu_i$ is the expected time to absorption starting at state ...
4
votes
0answers
63 views

Simplifying Chain of Conditional Variances given a Markov Chain

$\newcommand{\Var}{\operatorname{Var}}$Suppose $X,Y,W$ form a Markov chain $X \to Y \to W$. Can we simplify the following expression? \begin{align*} E [ \Var ( \Var (X\mid Y) \mid W)] \end{align*} ...
1
vote
1answer
21 views

Characteristic Polynomial of transition matrix of $n$-cycle

Let $P$ be the transition matrix of the deterministic random walk on the cycle $C_n$, i.e. $P \in \{0,1\}^{n \times n}$ with $$P_{i,j}=1\quad \text{ iff }\quad j=i+1 \mod n.$$ My guess is that ...
1
vote
1answer
26 views

Example of a markov chain with transient and recurrent states

As the title says, I can't come up with an example of a markov chain with all possible states (transient, positive recurrent and null recurrent). I know that the state space must be infinite, ...
3
votes
1answer
24 views

Arguing a stationary distribution exists

I am trying to show that there exists a stationary distribution when $q>p$ for the Markov process with one-step transition matrix $$ \begin{bmatrix} q & p & 0 & 0 & ...
0
votes
1answer
38 views

why does $P(X_{n+m} = j \mid X_m = k, X_0 = i) = P(X_{n+m}= j \mid X_m = k)$ follows from the Markov Property

I've learned that the Markov property says the following: $$P(X_{n+1} = i \mid X_n = j, X_{n-1}= j_1,\dots, X_0 = j_n) = P(X_{n+1}= i \mid X_n = j)$$ For me it is not clear how you can derive the ...
1
vote
3answers
62 views

Combining Markov chains

If the following Markov chain relations hold: $$X \rightarrow Y \rightarrow Z,$$ $$Z \rightarrow W \rightarrow Y,$$ can we combine them to have $$X \rightarrow Y \rightarrow Z \rightarrow W ...
2
votes
0answers
19 views

Likelihood that two markov chains are derived from the same transition matrix

Forgive me for my weak statistic background, hopefully what I'm asking makes sense. So some quick background, I have one markov chain from a data set and many additional chains that I'm producing from ...
1
vote
1answer
59 views

Proving that a process is not a Markov chain.

I want to prove that the queue length at a store is not a Markov Chain. $Q_k$ is the queue length at time instant $k$, $V_k$ is the number of arrivals. At every time instant one customer is ...
3
votes
1answer
51 views

Fano's Inequality Proof

For an information theory class, I am studying the proof for Fano's inequality, i.e.: $H(P_e) + P_elog(|X|) \geq H(X|\hat{X}) \geq H(X|Y)$ Where $H(X)$ is the entropy of the random variable X ...
1
vote
1answer
33 views

Proving technique used to show an equivalence to the definition of a Markov process

Let $X=(X_t)_{t\in I}$ be Markov process with values in a Polish space $E$. I want to show, that there exists a stochastic kernel $\kappa:E\times\mathcal{B}(E)^{\otimes I}\to [0,1]$ such that ...
0
votes
0answers
22 views

Algorithm for identifying Markov chain communicating classes

Let $P$ be a transition matrix of a time-homogeneous Markov chain with at least one closed communication class. Is there an algorithm / optimization problem that outputs the identification of the ...
0
votes
1answer
48 views

Assume a die is rolled repeatedly. Find the markov matrix $P$ for the random variable of the time until the next $6$.

Assume a die is rolled repeatedly. Find the markov/transition matrix $P$ for the random variable $X_r$ = the time until the next six at time $r$. My solution was: For $i,j \geq 0$, $P$ is given ...
1
vote
0answers
20 views

Transient discrete time Markov chain on integers: can direction of flow be proven?

I'm not very familiar with the theory of Markov chains, and I'd like to learn how complicated the following problem actually is. Let there be a discrete time Markov chain on $\mathbb{Z}$, where the ...
0
votes
0answers
25 views

The difference in entropy rates between a hidden process and its observation

Let $S$ be a finite state space and $o:S\to S$ an observation function. Given a distribution $p$ on $S\times S$, consider the following optimization problem: $$\max \left[ EntropyRate(\{x_t\}) - ...
0
votes
0answers
20 views

Markov Chain with dependence between users

I am looking for a Markov Chain model that describes the following problem. I have $N$ indifferent users in the system, each of them has three states: $A$, $B$, $C$, and I know the transition ...
0
votes
1answer
31 views

Algorithm for getting Markov chain given the complex eigenvalues

Given real and complex eigenvalues (occurring in conjugate pairs) how to get a single instance of a Markov Chain which has these eigenvalues. I know the Markov chain is not unique as eigenvectors are ...
3
votes
2answers
73 views

Markov Chains - Strong Markov Property

I'm struck with an exercise. I tried, but the results don't seem to fit to those proposed. Exercise: Two players play the following game. The one who begins draws two cards from a deck of 40 cards ...
0
votes
1answer
27 views

Why do all steady state probabilities have the same denominator?

I have noted that the steady state probabilities of an irreducible Markov chain can be written as fractions that have the same denominator. Is there any result about this property? What does this ...
0
votes
0answers
17 views

Markov chain state reached earlier than other state

Consider a Markov chain with $S={1, 2, 3, 4}$ and transition Matrix: $P=\begin{bmatrix} 0 & 1/2 & 1/2 & 0 \\ 0 & 0 & 1/2 & 1/2 \\ 1/2 & 0 & 0 & 1/2 \\ 1/2 & ...
0
votes
0answers
18 views

model a system with finite users as a Markov Chain

I have to model a system M/M/2 with finite users (4 users) as a Markov Chain (and then find the probality an incoming users would enter the queue being the servers busy but that's not the problem). I ...
2
votes
0answers
35 views

MLE for CTMC parameters

Let the data set be $$D = \{(s_0, t_0), (s_1, t_1), ..., (s_{N-1}, t_{N-1})\}$$ where $N=|D|$. Each $s_i$ is a state from the state space $S$ and during the time $[t_i,t_{i+1}]$ the chain is in state ...
0
votes
0answers
7 views

Looking for resources on Harris recurrence

I'm working on a problem (in a not countable space) and it seems that I could get much further with it if I can prove that a certain Markov chain is Harris recurrent (I strongly suspect that it is). I ...
0
votes
1answer
27 views

How to understand this kind of Markov chain?

There are two unidirectionally coupled processes $X_t$ and $Y_t$. The coupling is $Y_t=g(X_{t-\delta},\dots)$. The Bayesian network of the two process is described in the following figure: Now this ...
0
votes
2answers
45 views

Convergence of a particular fixed point iteration scheme

Setup I have the following non-linear system of equations: $$ \mathbf{x} P(\mathbf{x}) = 0 $$ where $\mathbf{x} \in \mathbb{R}_{>0}^n$ is a probability distribution, i.e., $\sum_i x_i = 1$, and ...
0
votes
0answers
15 views

How does one estimate the order of a Markov chain empirically (given the data)?

I have a string of symbols $x_1, x_2, ...., x_n$, ($n$ very large), belonging to a finite alphabet. I know that they are a result of a Markov process, but I want to find out the order of the process. ...
0
votes
1answer
20 views

Solving for max () in Viterbi algorithm

In simple terms, what is the proper way to solve for max. I am working with the Viterbi algorithm and am now stuck on how to solve this part of the equation. pc(G,2) = 0.3 + ...
1
vote
1answer
23 views

Determining the population size of a branching process

Suppose that I have the following branching process. Each parent can have up to two children, the number of which is determined by two independent fair coin flips. I know that this branching process ...
1
vote
0answers
32 views

Gibbs sampling truncation for contrastive divergence

I am following Yoshua Bengio's Learning Deep Architectures for AI and at page 31 there is a phrase that confuses me. Starting by lemma 7.1 in the same page: Lemma 7.1. Consider the Gibbs chain ...
1
vote
0answers
39 views

Maximum likelihood estimate of Gaussian parameters (1st-order Markov Chain)

Let us assume the availability of a time series $x_1, \ldots, x_N$ (where $x_i \in \mathbb{R}$, $0 \leq x_i \leq 1$). If we assume each variable to be independent of all previous observations except ...