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

1
vote
1answer
13 views

Random Walk With Absorbing Barrier

Consider a random walk $S_{t}$ with a lower absorbing barrier at $0$, and no upper absorbing barrier. $$ {\mathbb P}\left(\, S_{t + 1} - S_{t} = 2.5\,\right) =0.5\,,\quad\mbox{and}\quad{\mathbb ...
0
votes
0answers
4 views

What is the state space of this markov chain?

Consider a system where two persons sit at a table and share three books. At any point in time both are reading a book, and one book is left on the table. When a person finishes reading his/her ...
1
vote
0answers
13 views

Estimating the discrete laplacian to prove recurrence of simple random walk for d=2

Given a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}$ we define the discrete laplacian of $f$, $\triangle_df$, by the following rule $\triangle_df(x,y)= \dfrac{f(x + 1, y)+f(x, y + ...
0
votes
0answers
4 views

what are “filtering” and “smoothing” mentioned in hidden Markov model wikipedia article?

the article mentions "filtering" and "smoothing" tasks, see here http://en.wikipedia.org/wiki/Hidden_Markov_model#Filtering . It gives brief explanation but no motivating examples and no references to ...
0
votes
2answers
23 views

Are these transient or recurrent states in a Markov chain?

I have the following transition matrix for a Markov chain with states $A, B, C, D, E$ $ \left| \begin{array}{ccc} 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & ...
0
votes
1answer
23 views

How to define a transition matrix mathematically?

I'm writing my master thesis. Given the adjacency matrix of a graph, I need to define the transition matrix formally. I'm not able to figure out how to define it in mathematical notation. Can you help ...
1
vote
1answer
22 views

Can a chain with repeated nodes still be considered a Markov chain?

The well-known Markov Property is that $$P(X_n = i | X_{n-1} = k_1, \dots, X_{n-j} = k_n ) = P(X_n = i | X_{n-1} = k_1) $$ Suppose we lay out some stochastic model in the following transition ...
0
votes
2answers
38 views

Markov chain steady state existence

Is it possible for a Markov chain to have no steady state solution ? What is an example of such system ?
4
votes
0answers
19 views

Harmonic functions and null recurrence

Let $(X_n)_{n \geq 0}$ be a irreducible Markov chain defined on a countable state space $S$. It is known some ways to figure out if this chain is recurrent or not looking for superharmonic functions ...
1
vote
1answer
14 views

Understanding the proof of an Ergodic theorem for Markov chains

An ergodic theorem for Markov chains is as follows. If a Markov chain $(X_n)_{n \ge 0}$ is irreducible and has an invariant distribution $\pi$, then $$\frac{1}{n} \sum_{k=0}^{n-1} f(X_k) \to ...
0
votes
1answer
38 views

How to find transition probability matrix $P$ by using transition rate matrix $T$?

Let $$T = \left(\begin{matrix} -2 & 1 & 1&0 \\ 2 & -3 & 1&0 \\ 1 & 2 & -4 & 1\\ 1 & 3 & 1 & -5\end{matrix} \right) $$ be a transition rate matrix of ...
1
vote
0answers
17 views

Robustness of Markov Chains

A Markov Chain on a measurable space $X$ is uniquely determined by a stochastic kernel $P$ on $X$. Let $\mathsf P_x$ denote the probability on paths generated by $P$ and the initial condition $x\in ...
0
votes
1answer
31 views

Expected number of lines in use in call centre (markov process: queuing theory)

Suppose we have a call centre with infinitely many lines to be able to call to. Calls come in a rate of $\lambda$ and customers are served with rate $\mu$. It is easy to see that the $Q$-matris looks ...
0
votes
0answers
27 views

probability of hitting state $i$ in random walk

We have a random walk on the integers with probability of going to the right is $\lambda$ and to the left is $\mu$. Suppose we start at 0. I want to find the probability of ever hitting a fixed state ...
2
votes
2answers
44 views

Limiting probability that the sum of the values of a die is a multiple of 13

A fair die is thrown repeatedly. Let $X_n$ denote the sum of the $n$ first throws. I have to find $\lim_{n\rightarrow \infty}P(X_n \text{ is multiple of 13})$. Now follows what I tried, which I don't ...
0
votes
0answers
22 views

Markov Chain bonus-malus system

I'm having some troubles with this problem because I don't know how to construct the transition matrix, because they are talking about "more than 1 step". I think that the State space is ...
0
votes
0answers
32 views

Transition matrix of a double induced Markov chain

Here is how we defined induced Markov chains: Suppose that $(X,E,P)$ is an irreducible Markov chain, where $X=(X_i)_{i\in\mathbb{N}_0}$, $E$ is the state space and $P=(p_{i,j})_{i,j\in E}$ is the ...
2
votes
1answer
45 views
+50

Applying MCMC Metropolis algorithm

I'm interested in all possible paths (on the grid $\mathbb{N}^2 $) that goes from $ (0,0) $ to $ (n, n) $. At each step there are two possibilities: go right or go up. The path is a sequence $ ...
0
votes
0answers
11 views

Period ground state 1-dim Ising model

Good morning! I'm at the beginning of my study about the Ising model and it has been proposed to me this problem: Find all periodic ground-state configuration for the following one-dimensional Ising ...
0
votes
1answer
90 views

How to solve a discrete SIR epidemic model?

Let $(S(t), I(t), R(t))$ be a continuous time Markov chain SIR model with discrete space, where $S(t)$ stands for the number of susceptible people at time $t$; $I(t)$ stands for the number of ...
2
votes
0answers
49 views
+50

Induced Markov chain - verify Markov property and another property

First, here is how we defined induced Markov chains: Suppose that $(X,E,P)$ is an irreducible Markov chain, where $X=(X_i)_{i\in\mathbb{N}_0}$, $E$ is the state space and $P=(p_{i,j})_{i,j\in E}$ is ...
1
vote
1answer
24 views

Show that the space of superharmonic functions is not a linear space

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with state space $E$ and transition matrix $P=(p_{i,j})_{i,j\in E}$. A real valued function $h$ on $E$ is called superharmonic if $h(x)\geq Ph(x)$ ...
0
votes
0answers
29 views

Minimizing cost by state elimination in a Markov chain

Consider a discrete time, homogeneous, finite state Markov chain given by a stochastic $n\times n$ matrix $M$. Assume $M$ has "nice" properties: irreducible, no transient states (i.e. a single ergodic ...
0
votes
1answer
9 views

Irreducible Markov chain and finite sets

Let $(X_n)_{n\geq 0}$ be a irreducible Markov chain defined on a countable state space $S.$ Let $F \subset S$ a finite set and $\tau=inf\{n \geq 1; X_n \notin F\}$. If $x \in F$ how to prove that ...
0
votes
1answer
17 views

Markov Chain Steady State 3x3

I have been learning markov chains for a while now and understand how to produce the steady state given a 2x2 matrix. For example given the matrix, ...
0
votes
1answer
23 views

Solve Unknown Matrix Variables

I have a markov chain matrix with probabilities as such, on finding the steady state.. ...
0
votes
1answer
30 views

Markov chain modes of convergence

This is continuation of the question stated here. Let $\left( {{X_\alpha }:\alpha \in A} \right)$ be a finite space Markov chain (discrete or continuous), consisting of only transient and absorbing ...
1
vote
1answer
29 views

Estimate the speed of convergence to the stationary distribution for a ergodic Markov process

I have encountered a Markov process with following transition matrix $P= \begin{bmatrix} 0.6 & 0.4 \\ 0.2 &0.8\end{bmatrix} $. This is an ergodic Markov matrix since all the elements are ...
0
votes
2answers
25 views

Show $P(X(t)=0 | X_{0}=2)= P(X(t)=0 | X_{0}=1)^{2}$

Question: Let $X(t)$ be a continuous-time Markov chain on all non-negative integers with generator matrix $Q$ having for all $i\geq 0:$ $$ q_{i,i}=-i(\lambda +\mu ) \qquad q_{i,i+1}=\lambda i \qquad ...
0
votes
1answer
44 views

Limit for a Markov chain

I am considering a Markov chain on S = {1, . . . , 21} with transition matrix given by: $ 1 =p_{1,2} = p_{2,1}= p_{13,14} = p_{18,14} = p_{15,16} = p_{16,3} = p_{17,16}\\ 1/2 =_{p5,5} =p_{5,7}=p_{7,7} ...
1
vote
1answer
37 views

Two definitions of the strong Markov property

In Durrett's textbook, the strong Markov property is defined as follows: For every bounded and measurable $\varphi$ and stopping time $N$: ...
0
votes
0answers
28 views

Finding invariant probability of discrete time Markov Chain

Suppose that $\alpha$ gives a rate for an irreducible cont. time Markov chain on a finite state space. Then suppose the invariant probability measure is $\pi$. Then let $p(x,y)=\alpha(x,y)/\alpha(x)$ ...
0
votes
0answers
19 views

Steady state state distributions.

I am looking for a less "proofy" explanation of how a finite, irreducible, aperiodic Markov chain has a unique steady state $\pi$. No need define terms or include proofs of Bezout's lemma or number ...
1
vote
0answers
38 views

Compute transition probability in n step in infinte markov chain

I want to calculate the probability of transition in n step from state 0 to state 0 ($p_{00}^{(n)}$) in below Markov-Chain : if self loop in state 0 doesn't exist, probability computed with Catalan ...
-1
votes
2answers
86 views

Are irreducible, positiv-definite Markov chains aperiodic?

If $M$ is the transition matrix of a discrete Markov chain, and $M$ is both irreducible, symmetric and positiv-definite, is the resulting Markov chain necessarily aperiodic? In my intuition, ...
2
votes
0answers
36 views

Invariant Probability of Discrete Time MC from Continuous Time Markov Chain

Given rates α of an irreducible continuous-time MC on finite state space and told that π is the invariant probability measure of this chain, we define a discrete time MC as having transition ...
0
votes
0answers
12 views

Stochastic Matrix with two steady states

Is it possible for a stochastic matrix to have a 2-dimensional eigenspace associated to the eigenvalue of 1? In other words, is it possible to have a stochastic process where the steady "space" is any ...
2
votes
1answer
41 views

Prove matrix is positive semi-definite

$P$ is a stochastic matrix (square, non-negative, rows sum to 1). $\Xi$ is a diagonal matrix with a left principal eigenvector of $P$ on the diagonal and zeros elsewhere (stationary distribution if ...
0
votes
0answers
23 views

Poison Process Dance Marathon Question

The Dance Marathon is a 30 hour event during which people can make online or cash donations. Assume that 80 percent of the donations are made online and all other donations are made by cash. Donations ...
1
vote
1answer
35 views

Random Walk on Clock Hands

We do a random walk on a clock. Each step the hour hand moves clockwise or counterclockwise each with probability 1/2 independently of previous steps. If you start at 1 what is the expected number ...
0
votes
0answers
21 views

HMM walk through for backward algorithm with given example

This pdf file is a resource that walk through a simple HMM algorithm of two states http://www.indiana.edu/~iulg/moss/hmmcalculations.pdf, I have question in step 4.1 of the algorithm Specifically ...
2
votes
1answer
23 views

Why can a Markov chain having two states and no self-loop have a stationary distribution?

Why does a Markov chain having two states and no self-loop can have a stationary distribution? Lets consider a markov chain with two nodes = $\{A, B\}$ and the transition matrix: $P = ...
2
votes
0answers
53 views

How to prove a matrix norm inequality?

$P$ is a stochastic matrix i.e. square, non-negative, rows sum to one. Let $\Phi$ be a real matrix of size $n \times k$ with independent columns and $k < n$. Let $\Xi$ be the diagonal matrix with a ...
1
vote
1answer
38 views

Prove $\Xi (I - P)$ has eigenvalues in the non-negative real half-plane.

Let $P$ be a stochastic matrix (square, non-negative,rows sum to one). Let $\Xi$ be a diagonal matrix with any left principal eigenvector of $P$ on the diagonal and zeros elsewhere (stationary ...
3
votes
0answers
82 views

Prove or disprove: If $h$ is harmonic on $E$, then $h$ is constant on each $C_i$

For a general finite Markov chain $(X_n)_{n\in\mathbb{N}_0}$ with state space $E$ and transition matrix $P=(p_{x,y})_{x,y\in E}$, not necessarily irreducible, we define the linear space of ...
0
votes
0answers
19 views

Prove or disprove: A statement about generating functions of Markov chains

For a given Markov chain $(X,E,P)$ ($X=(X_n)_{n\in\mathbb{N}_0}$, $E$ is the state space, $P=(p_{x,y})_{x,y\in E}$ the transition matrix), prove or give a counterexample to the following ...
0
votes
1answer
17 views

Convergence of the number of visits in a Markov Chain

Suppose we have an irreducible and recurrent discrete-time Markov chain with states over the finite set $\mathcal{X}$. Let $N_t (x)$ denote the number of visits to state $x$ up to time $t$. Let ...
1
vote
2answers
39 views

Stationary probability in an M/M/$1$ queue with a lazy server

Customers arrive to a single server queue according to a Poisson process with rate $\lambda$. Each customer requires Exponential($\mu$) service time. In the beginning when there are $0$ ...
5
votes
1answer
100 views

Conditions for birth and death process having only finitely many deaths.

Consider a birth and death process on $\mathbb{N}=\left\{0,1,2,\ldots\right\}$, given by the transition probabilities $p(n,n+1)=\lambda_n$ and $p(n,n-1)=\mu_n$ (those are the birth and death rates, ...
1
vote
1answer
30 views

Determining invariant probability measure and calculating $\lim_{n}p_{ij}^{(n)}$

Consider the Markov chain $(X_n)_{n\in\mathbb{N}_0}$ with state space $E=\left\{1,2,3\right\}$ and transition matrix $$ P=\frac{1}{2}\begin{pmatrix}0 & 1 & 1\\1 & 0 & 1\\1 ...