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

4
votes
0answers
36 views

Weak convergence of a sequence of stationary distributions to another stationary distribution

Let $\{X_n(t) \in \mathbb{Z}^+\}$ for each $t \in (0,1)$ denote a discrete time Markov chain (with time index $n$ and parameterized by $t$). For each $t$, the Markov chain $\{X_n(t)\}$ has a unique ...
0
votes
1answer
32 views

What is wrong with matrix [[1,.5,0] [0,0,0] [0,.5,1]] steady state?

I know that Markov matrices have steady state since they always have eigenvalue $\lambda = 1$. We just solve the system of equations $A\vec x = 1 \cdot \vec x$ or $$\begin{cases} k_{a\to a} a + ...
1
vote
0answers
23 views

Transition density of an AR(1) process?

If we have an AR(1) process, i.e: $X_{t+1} = \alpha X_t + e_{t+1}$ with $X_0=0$ then what is its Markov Chain transition density? We know that for a Markov chain, the following holds: $P(X_{t+1}\leq ...
1
vote
0answers
13 views

Relaxation time and Mixing time of Markov chains

The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer. Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...
1
vote
1answer
64 views

Expected Value of a Mosquito

A mosquito is walking at random on the nonnegative number line. She starts at $1$. When she is at $0$, she always takes a step $1$ unit to the right, but, from any positive position on the line, she ...
-1
votes
1answer
51 views

Billingsley Exercise 8.8 (Markov Chains)

I am studying from Billingsley and would like some hints on the following exercise. Suppose $S = \{0,1,2,...\}$, $p_{00} = 1,$ and $f_{i0} > 0$ for all $i$. Here, $S$ represents the state ...
2
votes
0answers
19 views

Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
0
votes
2answers
30 views

When to stop checking if a transition matrix is regular?

The definition that I have of a Transition Matrix for a Markov Chain is: A transition matrix is regular if some power of it is positive. Doesn't this mean though that in theory, you could keep ...
0
votes
1answer
37 views

Expected time until reaching absorbing state of Markov chain

I currently try to model nucleation as an absorbing Markov chain. I have an idea how to do that but, however, I cannot convince myself that it is correct. The state space consists of the number of ...
0
votes
0answers
16 views

Reference for General state space Markov chain

What is a good reference for general state space Markov chains? Is there a reference which assumes only familiarity with finite/countable state space Markov chains and then extends the results (e.g., ...
1
vote
2answers
35 views

Confusion regarding Burke's theorem

Arrivals occur at rate $\lambda$ according to a Poisson process the service time have an exponential distribution with parameter $1/\mu$ in an M/M/1 queue, where $\mu$ is the mean service rate where ...
1
vote
0answers
46 views

When the sum of Markov chains is a Markov chain: “dumb” algorithm

Suppose I have two (independent) discrete-time and space, preferably non-homogeneous Markov chains $\Gamma^{(i)}=\{\gamma_1^{(i)},\gamma_2^{(i)},...\}, \ i=1,2$ and I want to find a way to check when ...
0
votes
1answer
18 views

Closed communicating class

Let $P_{ij}$ a transition matrix, a class $C$ is closed if given two different states $i$ and $j$ $$i\in C, i\rightarrow j\Rightarrow j\in C$$ If a Markov Chain is irreducible the transition matrix ...
0
votes
2answers
63 views

Probability in a fixed die

I have that transition matrix is ...
0
votes
0answers
18 views

Chernoff-type bounds for Markov chains

I found the following result adapted from "Chernoff-type bound for finite Markov chains" by Pascal Lezaud, The Annals of Applied Probability, 1998, Vol. 8, No. 3, 849-867. Theorem: Let $P$ be the ...
2
votes
2answers
76 views

Probability returning to initial state

Let $P=\begin{bmatrix}0&\frac{1}{2}&\frac{1}{2}\\\frac{1}{2}&0&\frac{1}{2}\\\frac{1}{2}&\frac{1}{2}&0\end{bmatrix}$ and $P^{(n+1)}=P^{(n)}P.$ I know that if you start in any ...
2
votes
0answers
22 views

Expected response time of Continuous time Markov chain

I'm studying CTMC (Continuous Time Markov Chains). I came across the following slide I don't understand how they got $M(t+h) = M(t) + \alpha h + M(t)\lambda h - M(t) \mu h +o(h)$ Could anyone ...
0
votes
2answers
34 views

Markovian systems: Why must controls be independent of state?

I am currently working my way through Probabilistic Robotics by Thrun, Burgard, and Fox. On p. 91, I encountered the following statement: The Markovian assumption implies independence between ...
0
votes
0answers
12 views

Joint Markov Chain (Two Correlated Markov Processes)

I have two Markov Chains, and they exhibit some correlation between them. For instance, when Chain A moves to state i, there is a high likelihood that Chain B moves to state j. How would I go about ...
0
votes
0answers
20 views

Probability of random walk visit in nonameanable graphs

Consider a vertex-transitive nonameanable graph. Consider a site $x$ having a graph distance $d$ from the origin and let $X(n)$ be a random walk starting from $x$. Is there a general upper bound as a ...
0
votes
1answer
16 views

Model Complexity for higher order markov model

I do not understand why is there an increase in parameters when moving from first to second order markov model For example considering a feature space of (a - z) For first order markov model, the ...
1
vote
2answers
46 views

Tricky Markov Chain

I found this problem a bit tough and was wondering if you could give it a go (especially the last part). This goes as follow : A gambler wins $1$ dollar at each round, with probability $p$, and ...
1
vote
0answers
40 views

Defining a function over time in terms of a random variable that is undefined at a certain time

Let $X_n$ be a random variable taking on one of three values $a,b$ or $c$ over time. That is, for each $n \in \mathbb{N}$, we have $X_n \in \{a,b,c\}$. Also, for each $n \in \mathbb{N}$, let $F_n$ be ...
2
votes
0answers
36 views

Why is the stationary distribution a distribution?

Suppose we have a time-homogeneous, discrete-time, aperiodic, positive recurrent, irreducible Markov chain $(X_t)_{t \geq 0}$ on a discrete state space $E$. It is known that its stationary ...
3
votes
1answer
28 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
88 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
49 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
51 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
18 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
39 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
32 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
27 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
32 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
31 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
32 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
63 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
42 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
24 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
33 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
50 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
31 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
60 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
24 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 ...