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

0
votes
0answers
429 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 $\pi$...
2
votes
1answer
84 views

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 ${\...
3
votes
0answers
57 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 ...
1
vote
1answer
99 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 X_n=5\vee ...
1
vote
0answers
20 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
1answer
134 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 &...
1
vote
1answer
110 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)$ give ...
8
votes
2answers
174 views

$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
2answers
168 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
57 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 ...
1
vote
1answer
123 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 ($n$ is the sink state) ...
0
votes
1answer
97 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 $S=(S_{...
2
votes
1answer
91 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
215 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 ...
2
votes
0answers
67 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 ...
1
vote
1answer
58 views

Existence of limiting distribution of product of Markov chains

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 is ...
0
votes
0answers
36 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} & ...
2
votes
1answer
151 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 ...
1
vote
0answers
62 views

Construction of pure birth process

I am considering a Markov chain $\lbrace X(t) \rbrace_{t≥0}$ in continunous time on the countable state space $S=\lbrace 0 \rbrace\cup \lbrace (i,j) \mid i \in \mathcal{A} , j \in \mathbb{N} \rbrace, ...
1
vote
1answer
200 views

Variance on the number of steps in an absorbing Markov chain

I've been looking for a proof for the variance on the number of steps before being absorbed in an absorbing Markov chain. The theorem is given on Wikipedia without citation. Following the references ...
1
vote
1answer
83 views

Markov Chains where Time Spent in State Matters

I have done a good bit of research on the subject, and cannot seem to find many materials. I was just wondering if you all knew of a good resource regarding chains which are Markov excepting the fact ...
1
vote
0answers
101 views

Explosion of a Markov chain

I am considering a Markov chain i continunous time on the countable state space $S=\lbrace 0 \rbrace\cup \lbrace (i,j) \mid i \in \lbrace A,B,C,D,E,F \rbrace , j \in \mathbb{N} \rbrace$. The ...
0
votes
0answers
26 views

Transience question for Markov Chains

Let's suppose I have a countable state discrete time MC that is known to be transient, irreducible and reversible with respect to some measure that assigns positive finite mass to each singleton, but ...
1
vote
0answers
57 views

How would I find this constant?

I have this equation, and I'm not sure how to solve for the constant $\nu$, since everything else is known: $$\begin{equation} a + \sqrt{a_i + 4 b_i \nu} + \sum^N_{j=1} (\sqrt{a_j + 4 b_j \nu}) p_{i,...
2
votes
1answer
113 views

Rational Thief Problem, optimal stopping strategy

A thief goes out stealing every day and has a chance of $p_j$ of stealing a sum $j$ with $0\leq j \leq N$. But there's also a chance $p$ of getting caught, in which case he loses everything he got ...
2
votes
2answers
182 views

Equilibrium distribution of Ehrenfest's urn

(I'll post my own answer to this, but others may be of interest, so post your own if you have one.) (PS: In reply to comments posted below: Stackexchange encourages posting an answer to one's own ...
1
vote
0answers
38 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 ...
2
votes
0answers
62 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
2answers
557 views

What are “Filtering” and “Smoothing” with regards to Hidden Markov Models?

The Wikipedia article about Hidden Markov Models mentions "filtering" and "smoothing" tasks, see here: http://en.wikipedia.org/wiki/Hidden_Markov_model#Filtering. It gives a brief explanation but no ...
0
votes
2answers
97 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
47 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
58 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
259 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 ?
5
votes
0answers
165 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
58 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
516 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
1answer
31 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 X$....
0
votes
1answer
58 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
58 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 $...
3
votes
2answers
230 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
102 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 S={0%,30%,40%,...
4
votes
1answer
104 views

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 $ z=(z_0,...
0
votes
1answer
233 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
159 views

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
68 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)$ ...
1
vote
1answer
38 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
1k 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
90 views

Solve Unknown Matrix Variables

I have a markov chain matrix with probabilities as such, on finding the steady state.. ...
0
votes
1answer
82 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
221 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 ...