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
2answers
38 views

Asymptotic behaviour of mean absorption time at the Moran model

In the Moran model, a model from population genetics, the mean time until absorption is given by $$ \tau _i =N \left( \sum_{j=1}^i \frac{N-i}{N-j} + \sum_{j=i+1}^{N-i} \frac{i}{j} \right),$$ where ...
3
votes
1answer
34 views

Markov Chain with two components

I am trying to understand a question with the following Markov Chain: As can be seen, the chain consists of two components. If I start at state 1, I understand that the steady-state probability of ...
15
votes
2answers
468 views

Knight returning to corner on chessboard — average number of steps

Context: My friend gave me a problem at breakfast some time ago. It is supposed to have an easy, trick-involving solution. I can't figure it out. Problem: Let there be a knight (horse) at a ...
0
votes
0answers
13 views

Log moment generating function from two state transition matrix of markov process

How to find the log moment generating function of two state Markov process where the distribution is gamma distribution. The transition matrix is $$ P=\begin{pmatrix}1-\sigma & \sigma\\ \tau ...
1
vote
0answers
40 views

Gambler's ruin problem - expected time

I have troubles seeing the following. Consider the classical gambler's ruin problem, betting 1 at each time $t\in \mathbb{N}$, and losing or winning -1 respectively +1 at each time till the fortune of ...
0
votes
0answers
21 views

Problem in an example of Introduction to stochastic processes by Lawler page 25

Example. page 25: Consider the two-state Markov chain with $S=\{0,1\}$ and P= $\begin{pmatrix} 1-p & p \\ q & 1-q \\ \end{pmatrix}$ where $0< p,q< 1 $ Asuume the chain starts in ...
1
vote
1answer
17 views

Finite, irreducible Markov chains - Is the mean arrival time at $j$ always finite?

We consider an irreducible Markov chain $(X_0,X_1,...)$ with finite state space $S$ and transition probabilities $p_{ij}$. Then, for $j \in S$, we can define the random variable $$ T_j :=\min{\{ n \in ...
0
votes
0answers
23 views

Confusion in the defition of 'first passage time' (Markov Chains)

Consider a state $i$ from some state space $A$. First passage time to state $i$ is the random variable $T_i$ defined by $T_i(\omega) = inf$ { $n \geq 1: X_n(\omega) = i$ }. Does this means that ...
2
votes
0answers
37 views

Markov chain limit problem

Let $X_n$ be a Markov chain on a countable state space, $\mathbb{S}$. Let $N_n(x) = \sum_{k=1}^n\mathbb{1}_{\{X_k=x\}}$ denote the number of times the chain visits state $x\in \mathbb{S}$. Let ...
0
votes
0answers
10 views

Example of the strong Markov property

Can someone give me an example of strong Markov property? I have been looking Markov chains by J.R. Norris for this and the example given in that book is confusing. If anyone has read that example ...
0
votes
0answers
27 views

Convergence to equilibrium

Hi I have a question about the following proof. By definition then $\mathbb{P}$ should refer to the distribution of $X_n$, so something like $P_\lambda=\mathbb{P}$. What it confuse me a bit is the ...
0
votes
0answers
26 views

Markov chains: absorption time for upper-triangular state transition matrix

I have a (time-homogeneous, discrete-time) Markov chain with $K+1$ states $\{0,1,\ldots,K\}$. The last state $K$ is an absorbing state, all other states are transient states. Furthermore, from each ...
4
votes
1answer
40 views

Stopping time in Markov chains

A random variable $T : \Omega \rightarrow ${$1,2,3...$} $\cup$ {$ \infty$} is called a stopping time if the event {$T=n$} depends only on $X_0 , X_1 ,X_2 ,..., X_n$ for $n = 0,1,2,...$ I have trouble ...
1
vote
1answer
69 views

Understanding the random variable definition of Markov chains

Update This question is answered in section 3.2 of these notes. As a probability novice, I'm struggling to completely understand the definition of a Markov chain as a sequence of random variables. ...
0
votes
1answer
40 views

Has a Markov chain in compact metric space a stationary distribution (possibly non-unique)?

Let $Y_n$ be a Markov chain in a compact metric space. Is it true that it has a stationary distribution?
1
vote
0answers
36 views

Markov chain of transition probabilities

Let $P$ be a transition matrix on a discrete state space with $N$ elements. $P_{i,j}$ is the probability of going from state $i$ to state $j$. Let $\pi$ be the stationary distribution. Let $\{X_n\}$ ...
0
votes
1answer
23 views

What is does a steady state vector tell us if the matrix is irregular?

When a Markov chain is regular, the finding the steady state vector (i.e. the eigenvector corresponding to the eigenvalue $1$) will tell us the long term probability of ending up in any of the states, ...
0
votes
0answers
19 views

steady state distribution of the following Markov jump process?

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

Markov chain with dynamic higher orders

Let $X_i$ be the node visited by a random walk at step $i$, and the following equations be the transition probabilities. $Pr(X_n = x_n | X_{n-1} = x_{n-1}, \cdots, X_1 = x_1) = Pr(X_n = x_n | X_{n-1} ...
1
vote
1answer
27 views

Success-run on $\mathbb{Z}^+$

Let the walk on the positive integer axis $\{0,1,2,...\}$ with the following step probabilities. $p_i:=p_{i,i+1}=1-(1/2)^{i+1}$, $q_i:=p_{i,0}=(1/2)^{i+1}$. I know that the chain is transient. I want ...
0
votes
2answers
91 views

Random Walk on a Cube

A particle performs a randowm walk on the vertices of a cube. At each step it remains where it is with probability 1/4, or moves to one of its neighbouring vertices each having probability 1/4. Let ...
1
vote
1answer
27 views

optimal utility calculation for a simple discrete Markov chain

I am trying to calculate analytically the optimal decision rule for a simple discrete markov chain, following standard decision theory framework (slide 17 in ...
0
votes
0answers
30 views

Birth-Death process with shifted exponential distribution

In the general framework of $M/M/1$ queue we have rate $\lambda$ and an exponential service time $\mu$, we can set up the transition rate matrix intuitively. However, if the service times satisfy ...
1
vote
1answer
77 views

Show that the probability of never hitting 0 on a birth-death chain is $6/\pi^2$.

In the question we have a birth-death chain on $\{0,1,2,...\}$ whose only non-zero transitions from $i$ are to $i+1$ and $i-1$, with probabilities $p_i$ and $q_i$, respectively. I have that $p_i$ and ...
1
vote
2answers
16 views

A property of irreducible and aperiodic Markov chains

Let $P$ denote the $s\times s$ Markov transition matrix. We know that irreducibility and aperiodicity implies the following: There exists an integer $N\geq 1$, such that $[P^n]_{ij}>0$ for all ...
0
votes
0answers
11 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 ...
1
vote
1answer
56 views

How to simulate visits to a transient state of a Markov chain.

Consider a discrete-parameter Markov chain $\{X_n, n ≥ 0\}$ with state space $E$, transition probability matrix $P$ and initial-state probabilities $p(0)$ given by $E = \{0, 1, 2, 3\}$, P = ...
2
votes
1answer
43 views

Markov Process: predict the weather using a stochastic matrix

I have the following stochastic matrix $$ P = \begin{pmatrix} P(S \mid S) = 0.5 & P(F \mid S) = 0.2 & P(R \mid S) = 0.3 \\ P(S \mid F) = 0.2 & P(F \mid F) = 0.7 & P(R \mid F) = 0.1 ...
1
vote
1answer
78 views

A property of Poisson process

Let $Y_t$ be a centered Poisson process, why \begin{equation} \lim_{n \to \infty} \sup_{s<t} |n^{-1}Y(ns)| = 0 \qquad a.s. \qquad \forall t\ge 0 \end{equation} This is a fundamental step in the ...
2
votes
1answer
60 views

Find expected time to reach a state in a Markov chain

Consider a Markov chain $ (X_n)_{n\geq 0} $ with state space $E$, initial distribution $p(0)$ and transition probability matrix $P$ given by $E = \{0, 1, 2\}, p(0) = [1\;\; 0\;\; 0]$ and $$ P= ...
1
vote
0answers
18 views

Understanding a Markov decision process

We have an insect that is resting on a vertex of a square at each point of time $t=0,1,2..$. The vertices are labelled from 1 to 4. 1 is given to the lower left vertex, 3 to the upper left vertex, ...
2
votes
3answers
119 views

Find expected value of time to reach a state in Markov chain, by simulation

Consider a time homogeneous Markov chain $ (X_n)_{n=0} $ with state space $E$, initial distribution $p(0)$ and transition probability matrix $P$ given by $E = \{0, 1, 2\}, p(0) = [1\;\; 0\;\; 0]$ and ...
0
votes
1answer
16 views

Why accept worse samples in Metropolis–Hastings Algorithm?

In the Metropolis–Hastings algorithm you accept a new sample based on how probable the new proposed sample is with respect to the current sample. But what is wrong with only accepting when the new ...
2
votes
1answer
42 views

Find prob. to see $5$ people in hairshop

A hair shop, people arrives at the rate $1$ person/hour, and it spend $0.5$ hour to completely cut the hair. Find the probability to see $5$ peoples in the hair shop, including the person who are ...
2
votes
1answer
48 views

Find the period of a state in a Markov chain

Let $\{X_n:n=0,1,2,\ldots\}$ be a Markov chain with transition probabilities as given below: Determine the period of each state. The answer is "The only state with period $> 1$ is $1$, ...
2
votes
1answer
45 views

Find the steady state probability that both A and B catch a headache.

I have a question about Markov chain. Let A and B be patients, A has headache at the rate $1$ times/week and recovers from it at rate of $2$ times/week. The patient B has it at the rates $2$ and $4$ ...
0
votes
0answers
47 views

hitting time for a continuous time markov chain

Brad’s relationship with his girl friend Angelina changes between Amorous, Bickering, Confusion, and Depression according to the following transition rates when t is the time in months. They are ...
1
vote
1answer
76 views

Chuck Norris' Coupling of Markov Chains: An Invariant Distribution

I'm having some difficulty understanding a proof in James('Chuck') Norris book on markov chains. Let $P$ be irreducible and aperiodic, with an invariant distribution $\pi$. Let ...
0
votes
1answer
63 views

Solve a problem using Markov chains

We have the following problem: At the beginning of every year, a gardener classifies his soil based on its quality: it's either good, mediocre or bad. Assume that the classification of the soil ...
0
votes
1answer
44 views

Probability distribution in 7th steps

Let's assume that there is a markov chain with a transition matrix $P$: $\begin{bmatrix} 0 &0 &0 &\frac{1}{2} & \frac{1}{2} & 0\\ 0& 0& 0& \frac{1}{2}& ...
0
votes
0answers
40 views

Transient state of Markov chain

I have one exercise about state of Markov chain. The Markov chain is as shown below: The answer shows B and F are transient as they could reach to absorbing state. But how can I tell, for example, ...
1
vote
0answers
52 views

Finding a stationary distribution for a Markov chain with a binomially distributed transition matrix

The distribution isn't exactly binomial.. I'll explain what I mean: I am considering a Markov chain with N+1 states (denoted by $0,1,...,N$), the probability of going from state $i$ to state $j$ is ...
1
vote
1answer
34 views

Markov chain factorisation

Let $\{X_t\}_{t=1}^4$ be a Markov chain with $t$ denoting the time index. Simplify the following factorisation. $$\Pr(X_4)\Pr(X_3|X_4)\Pr(X_2|X_3,X_4)\Pr(X_1|X_2,X_3,X_4)$$ I really don't know ...
0
votes
0answers
5 views

Modified Propp-Wilson probabilities

I encountered the problem below: Here is the transition matrix from Figure 9: Problem 10.3 asks us to demonstrate why (84) is true. If you run Propp-Wilson with $N_1$ = 1, it seems clear ...
1
vote
2answers
64 views

When does a Markov chain not have a steady state?

I was asked this question on an oral qual, and eventually I seemed to conclude that there have to be eigenvalues of modulus 1. But I just realised every Markov matrix has one as an eigenvalue. So ...
0
votes
1answer
18 views

Confusion about Markov chains

If I understand correctly, Any Markov matrix $A$ has 1 as an eigenvalue $p$ is a steady state vector if $A^nq \to P$ $\forall$ $q$ My problem is, doesn't this mean that, if there is a steady ...
0
votes
0answers
76 views

Mean absorption time, two absorbing states

I have a transition matrix $$ P = \begin{Vmatrix} 1 & 0 & 0 &0\\ .3& 0 &.7& 0\\ 0& .1 & 0 & .9 \\ 0& 0 & 0 &1 \end{Vmatrix}$$ on states $\{0,1,2,3\}$. ...
0
votes
1answer
30 views

Proving identity of Markov chain.

I am in a need of proving the following identity. Hope someone can help me. Let $\{X_n, n\geqslant0\}$ be a homogeneous Markov Chain. Show that $$P(X_{n+1}=k_1,...,X_{n+m}=k_m \mid ...
0
votes
0answers
18 views

Stochastic calculus for continuous time Markov chains

I have absolved a course on stochastic analysis, i.e. integrals with respect to the brownian motion. Now I know that there is a theory of stochastic calculus for diskrete matringales, however I was ...
0
votes
0answers
15 views

Markov chain - limiting expectation

I would like to verify my logic. If $\{X_n\}_{n\ge0}$ DTCM with $S=\{0,1..,N\}$, the $P_{X_{n}}$ (in one step) is double stochastic. I want to compute $\lim_{n\to \infty} E[X_{n}|X_0 = 0]$. ...