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

2
votes
1answer
7 views

Could you find initial distribution of markov chain by looking at transition matrix?

Can you find out Probability of Initial distribution of markov chain? For example If you are given transition matrix, Can you determine P(x0=0) P(x0=1) and P(X0=2) where state space is {0.1.2} ??
1
vote
0answers
7 views

How long does it take two identical hidden Markov models run on same observations to forget their initial distributions (if ever)?

Let $H_1$ and $H_2$ be two instances of a finite Hidden Markov Model (HMM) $H$. That is, $H_1$ and $H_2$ have identical state spaces $Q$ as well as identical transition $A$ and emission probabilities ...
0
votes
0answers
8 views

Calculate $P(X_{16}=2|X_0=0)$

Given a Markov Chain with three states 0,1,2 with the following State Transition Probabilites: $$M = \left( \begin{array}{ccc} 0.3 & 0.3 & 0.4 \\ 0.2 & 0.7 & 0.1 \\ 0.2 & 0.3 ...
0
votes
0answers
13 views

Show recurrence of a class

I am a little bit confused with the definition of recurrence with respect to Markov chains. For example consider the transition matrix $$ P=\frac{1}{2}\begin{pmatrix}0 & 1 & 1 & 0 & ...
0
votes
0answers
8 views

Expected first return time of Markov Chain

Given the following Markov Chain: $$M = \left( \begin{array}{cccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 & 0 ...
1
vote
1answer
28 views

Intuition behind Stopping Times

I'm attending a stocahstic processes course. I have some trouble with the intuition behind a stopping time. I will consider the discrete case to make it simpler. a stopping time is given by ...
1
vote
0answers
7 views

How to find the long range transition matrix L of P

P is the transition matrix of a regular Markov chain. Find the long range transition matrix L of P. $$ P = \begin{bmatrix} 1/2 & 1/4 & 1/4\\1/2&1/2 &1/4\\0 &1/4 & ...
2
votes
1answer
27 views

Can two nodes in a Markov chain have transitions that don't total 1?

In all the Markov diagrams I see, the transitions from state A to B always total to one. Just one of many examples, this image ...
0
votes
0answers
15 views

Latest evolutionary algorithms

I am required to build an evolutionary algorithm to approach modelling optimization problems. More precisely, let $f:\mathbb{R}^{n} \longrightarrow \mathbb{R}^{m}$ be a model that is dependent from ...
0
votes
0answers
11 views

Dynamics of birth-death process with discouraged arrivals (alternatively, M/M/1 queue with balking customers)

Take a continuous-time birth-death process, where $k \in \{0,1,\ldots\}$ is the count and the arrival rate of death is $\mu \geq 0$ for $k = 1, 2, \ldots$ the arrival rate of births is $\alpha_k ...
2
votes
0answers
14 views

How do I integrate this master equation from a time-continuous Markov chain?

I hope the question is not too vague. My calculus courses are way in the past and I can't remember how to do it :-). I have this master equation for a time-continuous Markov chain I have a two ...
0
votes
1answer
16 views

Every finite closed class is recurrent

Let $(X,E,P)$ denote a Markov chain, where $X=(X_n)_{n\in\mathbb{N}_0}$, $E$ is finite state space and $P$ is the transition matrix. Claim: Every finite closed class is recurrent. Here is ...
1
vote
2answers
30 views

In Markov chains a limit distribution is invariant

Suppose we have a Markov chain $(X_n)_{n \geq 0}$ with state space $S$. Suppose that $(\pi_i)_{i \in S}$ is a limit distribution. Then is $(\pi_i)_{i \in S}$ an invariant distribution ? I know the ...
1
vote
1answer
18 views

Why does a process only satisfy the Markov property if and only if the random times are exponentially distributed?

Given, for example, a birth death process with a set of jump times. These jump times have to be exponentially distributed in order for this process to satisfy the Markov property. Why is this? Why ...
1
vote
0answers
4 views

Why does a Markov chain with one irreductible class has a lower triangular transition matrix?

Given a Markov chain on an infinite and countable set of states, with one irreductible class that has a finite number of states, why can its transition matrix be put in a lower triangular form ? ...
0
votes
0answers
20 views

Does a state which is passed at least 3 times had to be passed 5 times in Markov chain

Prove of disprove: Let $\{X_n\}_n$ be homogenous Markov chain. if we start from state $i$, there is a positive probability that we pass at least 3 times at state $j$. Does it follows that exists ...
1
vote
0answers
50 views

Exercise on Markov chains

I'm preparing my Probability exam and I'm having trouble with exercise 2 here. The question is to consider the random walk on $E$ with transition matrix $p$ and find the communication classes (or ...
0
votes
0answers
20 views

Proving criterion for a transient state in Markov Chain

Let $\{X_n\}_n$ be a homogenous Markov chain. Prove that if exist a connected subset of states (means set of states which exist positive probability to move between them), $S$ which is not closed, ...
0
votes
0answers
9 views

continuous markov chain generator

I am trying to learn Markov process with my own. I am a little confused about the generator of markov process. I understand that Markov process consists of embbedded Markov chain matrix and the ...
0
votes
0answers
22 views

Proof of “strong law of large numbers” in Markov Chains

I have been given a theorem stating an analogue of the strong law of large numbers for Markov chains. It states that if $X=(X_n)_{n\in\mathbb{N}}$ is a Markov chain with transition matrix $p$ and ...
1
vote
1answer
56 views
+100

Conditional independence given elementary events implies conditional independence given $\sigma $-algebra

Proposition: Let $X$ be a continuous markov chain with discrete state space $S$. Let $Z$ be the corresponding jump chain and $\left\{ {{W_i},i \in \mathbb{N}} \right\}$ its holding times. Let ...
2
votes
0answers
24 views

Periodicity of Markov chains under cartesian product

Suppose that you have a finite state Markov chain, with $n$ states and characterized by $p_{i,j}$ the probability of reaching state $j$ from state $i$. Consider the new Markov chain with $n^2$ states ...
0
votes
1answer
54 views

Markov chain doesn't sum up to 1

Let $\{X_n\}$ be a Markov chain on $S=\{1,2,3,4,5,6\}$ with the matrix suppose we define a new sequence $\{Y_n\}$ by $$Y_n=\cases{1\quad X_n=1\vee X_n=2\\2\quad X_n=3\vee X_n=4\\3\quad ...
1
vote
0answers
12 views

Marcov Chain confirmation

I am currently having some problems on the following question: Given is the function $f(x)$: $f(x) = 0,1,2$ with probability $\frac{1}{3}$ for each. I have to give the state space, transition ...
0
votes
0answers
14 views

Proof of theorem on markov chains

If $X=(X_n)_{n\in\mathbb N}$ is a Markov chain on a space $E$, it has an initial distribution $(\lambda_i)_{i\in E}$ such that $\sum\lambda_i=1$ and a transition matrix $(p_{ij})_{i,j\in E}$ such that ...
0
votes
0answers
16 views

Why does from Perron-Frobenius follow that that constant functions are the only harmonic functions here?

in our reading we had the following example for a Markov chain. State Space $E=\left\{1,2,3,4\right\}$ and Transition Matrix $$ P=\frac{1}{3}\begin{pmatrix}0 & 1 & 1 & 1\\1 ...
-2
votes
0answers
18 views

Calculate all harmonic functions

Let $E$ befinite and suppose that $P$ is irreducible and strictly sub-stochastic. Calculate all harmonic functions. To my understanding, $P$ strictly sub-stochastic means that $\sum_{y\in ...
0
votes
0answers
11 views

non-integer powers of transition matrices with complex eigenvalues and resulting negative probabilities

I am currently working on a Markov Chain model for transition probabilities of a certain set of states. I am trying to figure out how to scale my transition matrix to arbitrary time periods by raising ...
0
votes
0answers
12 views

Memory less property of a Markov chain- Validation methods

Are there any tests to check the memory less property of a discrete time homogeneous Markov chain? I found a chi squared test to verify the time homogeneity of a Markov chain constructed from a set of ...
0
votes
0answers
5 views

Hastings algorithm

Let $Q=\begin{pmatrix} 0 & 1 & 0 & 0 & 0\\0.5 & 0 & 0.5 & 0 & 0\\ 0 & 0.5 & 0 & 0.5 & 0\\ 0 & 0 & 0.5 & 0 & 0.5\\ 0 & 0 & 0 ...
0
votes
1answer
13 views

Transition probability matrix of Markov chain

Given that $g(x)=\begin{cases} 1/3 \quad\text{for } x=0\\ 1/3 \quad \text{for } x=1\\ 1/3 \quad \text{for } x=2\end{cases}$ Explain why independent draws $X_1,X_2,\dots$ from $g(x)$ ...
0
votes
0answers
21 views

Markov chain general help

If I have an absorbing state markov chain (with 2 absorbing states, graduate and dropout), and I know how many people I have in each state (say total for all states is 1000), how would I work out what ...
8
votes
2answers
105 views
+50

$L^2$ Bounds for Markov Chains.

Consider a non-negative, square stochastic $n \times n$ matrix $P$ (rows sum to one, $P$ is ergodic). We are interested in characterizing the set of $n \times n$ invertible matrices $A$ such that we ...
0
votes
1answer
38 views

Proof that there exists a non-negative eigenvector corresponding to eigenvalue 1 of stochastic matrix

Let $P \in [0,1]^{n \times n}$ be a [irreducible or reducible] stochastic matrix where its rows sum to 1 i.e. $$ \forall i \in \{ 1 , \dots n \} \quad \sum_{j=1}^{n} P_{ij} = 1 $$ It is easy to show ...
0
votes
0answers
36 views

Create a Martingale out of a Markov Chain.

Consider a homogeneous finite state Markov chain $\{X_n\}$ with transition matrix $P$ and state set $S$ consisting of real numbers. How to choose the elements of $S$ so that $\{X_n\}$ be a ...
0
votes
0answers
6 views

Condition under which Markov Chain remains in a compact set a.s.

Let $\{Y_n\}$ be a Marov chain. Is it good question to ask under what conditions this chain will take values from a compact set a.s. ?
-1
votes
0answers
32 views

Branching Processes

I would like to have some hints about the following problem: Imagine a descendant tree. We assume that each species can give birth to a new specie in a constant rate $\lambda$. (This rate is called ...
0
votes
0answers
11 views

Given stochastic matrices D and K, under what conditions can I find stochastic matrices that satisfy a given equality?

Let $D \in \Re^{n \times m}$ and $K \in \Re^{m \times n}$ be two stochastic matrices, with $n > m$. The problem is to determine under which conditions there exist stochastic matrices $P \in \Re^{m ...
1
vote
0answers
49 views

Couple/Compare two stochastic processes and prove an intuitive proposition

Consider a stochastic process (denoted $X$) $X_0, X_1, X_2, \ldots$ (not necessarily a Markov Chain) over state space $\{0, 1, \cdots, n \}$. The transition probabilities are $$P(X_{i+1} = 1 \mid ...
0
votes
0answers
10 views

Simple Random Walk; Proof hitting theorem; Ballot Theorem

Suppose that $(X_{n}:n\in\mathbb{N})$ is a $\pm1\mbox{-valued sequence.}$ Let $p\in(0,1)$ and $p=\mathbb{P}(X_{i}=1)\mbox{ and}\mathbb{P}(X_{i}=-1)=1-p=q$ . Define the simple random walk ...
0
votes
0answers
22 views

Stationary solution of a binary Markov chain of order m

Let $X$ be a binary Markov chain of order m. What is the stationary solution of X? In other words, find $\lim_{n\to \infty} P( (X_{n-m+1},X_{n-m},...,X_{n}) =(a_1,a_2,...,a_m))$, for arbitrary values ...
0
votes
0answers
23 views

Steady state of a specific Markov martirx

Let $n = 2^L$ for an arbitrary integer $L>0$ and let $A=(a_{i,j})$ be an $n \times n$ matrix with the following structure: For $1\leq i \leq \frac{n}{2}$, $a_{i,2i-1} = p_i$, $a_{i,2i} = 1- ...
2
votes
1answer
39 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...
1
vote
1answer
46 views

Probability of a time-dependent set of states in Markov chain

Consider a Markov matrix $P$ defining $m$ states. For each time $n$, define a set of states $S_n$ that contains a predefined subset of the states $\left\{ {1,...,m} \right\}$. For time $n=k$, I would ...
0
votes
0answers
9 views

hidden Markov model with multiple observations

I am wondering if HMM can be used for the case that in a particular state, there are more than one observations. For instance at time t, we can observe the position, velocity and acceleration at the ...
2
votes
0answers
29 views

Mixing time for metropolis chain on graph coloring

I'm reading the Markov Chains and Mixing Times by David Levin et al.. In section 5.4 page 71 a proof is given for a bound of mixing time for the Metropolis Chain on graph coloring. In the proof, such ...
0
votes
0answers
17 views

Problem related to variance of first passage matrix of a absorbing Markov chain

Consider the below computations taken from Kemeny/Snell Finite Markov Chains. Here $N=(I-Q)^{-1}$ calculated from some absorbing MC. $N_2$ is the variance matrix of $N$ and $N_{sq}$ is taken by ...
1
vote
1answer
25 views

Combination of Markov chains, existance of limiting distribution

I have two Markov chains described by the stochastic matrices $P_1$ and $P_2$ for which a limiting distribution exists. Now I combine the two stochastic matrices using the cartesian product, this ...
0
votes
0answers
22 views

How to prove that this stochastic matrix has a limiting distribution

I have the following stochastic matrix with $p_{ij} > 0$ and $\sum_j p_{ij} = 1$ $$ P = \begin{bmatrix} p_{11} & p_{12} & 0 & 0 & 0 & 0 \\ p_{21} & ...
0
votes
1answer
62 views

Countable state Markov chain with multiple transitions

I'm searching for hints on how to analyze the following Markov chain. I can solve for the steady state probabilities numerically by using a finite transition matrix. However, I would like to have an ...