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

6
votes
2answers
3k views

Equilibrium distributions of Markov Chains

I often get confused about when a Markov chain has an equilibrium distribution; when this equilibrium distribution is unique; which starting states converge to the equilibrium distribution; and ...
8
votes
2answers
2k views

Nice references on Markov chains/processes?

I am currently learning about Markov chains and Markov processes, as part of my study on stochastic processes. I feel there are so many properties about Markov chain, but the book that I have makes ...
14
votes
1answer
449 views

Eigenvalues for $3\times 3$ stochastic matrices

This is a plot of the non-real eigenvalues of 10000 randomly generated $3\times3$ stochastic matrices. It's pretty clear that they lie in the convex hull of the three cube roots of unity. The ...
5
votes
3answers
3k views

What is the difference between all types of Markov Chains?

I have been looking for some good material covering Markov Chains but everything seems so difficult to me... After reading about the subject, I figured out that there is basically three kinds of ...
3
votes
1answer
1k views

Calculating stationary distribution of markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\{0\dots,n\}$ and transition matrix below: \begin{bmatrix} 0 & 1 \\ \frac{1}{n} ...
3
votes
2answers
350 views

How can I compare two Markov processes?

There is a discrete-time irreductible Markov process with $r$ possible states. $k$ observations were performed. At each observation a state of process was determined. $T_0 = \lbrace 0,1,\dots ...
1
vote
2answers
540 views

Perron-Frobenius theorem

In the proof of the Perron-Frobenius theorem why can we take a strictly positive eigenvector corresponding to the eigenvalue $1$? Before that, why can we even take a non-negative eigenvector? Books ...
2
votes
2answers
56 views

Transition Matrix eigenvalues constraints

I have a Transition Matrix, i.e. a matrix whose items are bounded between 0 and 1 and either rows or columns sum to one. I would like to know if it is possible that in any such matrices the ...
5
votes
1answer
375 views

Probability distribution for the position of a biased random walker on the positive integers

I initialize a biased one-dimensional random walk on the positive integers at the origin, $x = 0$, which also serves as a reflecting boundary blocking steps onto the negative integers. Let's say that ...
3
votes
2answers
280 views

How can a Markov chain be written as a measure-preserving dynamic system

From http://masi.cscs.lsa.umich.edu/~crshalizi/notabene/ergodic-theory.html irreducible Markov chains with finite state spaces are ergodic processes, since they have a unique invariant ...
3
votes
2answers
368 views

Expectation of a stopping time uniquely determined by a function

Let $(X_t)_{t\ge0}$ be a Markov chain on a finite state space $\Omega$, with transition probability $P$. Let $T$ be a stopping time such that $T=\min \{t\ge 0;X_t \in A \subset \Omega \}$.  If ...
2
votes
2answers
292 views

Finding the exact stationary distribution for a biased random walk on a bounded interval

Imagine we have a biased random walk on an interval $[0, L]$, where the probability of taking a $+1$ step is $p$ and the probability of taking a $-1$ step is $(1-p)$. At the reflecting boundary $0$, ...
1
vote
1answer
109 views

Markov Chain transitional probability query.

Say I have the transitional probability matrix P= $\begin{bmatrix}.8 & .2\\.6 & .4\end{bmatrix}$ And the entry (1,1) denotes the probability that I stay in state 0, (1,2) I move from state 0 ...
1
vote
1answer
1k views

Irreducible, finite Markov chains are positive recurrent

I am under the impression that an irreducible, finite Markov chain is necessarily positive recurrent. How might I show this? Regards, Jon
0
votes
1answer
221 views

Random walk with single absorbing boundary

There is a random walk on a linear lattice of size $\{0,N\}$, where $0$ is the origin and a reflecting boundary and $N$ is the absorbing boundary. It moves forward or backward one step at a time with ...
0
votes
1answer
123 views

Determining computational complexity of stochastic processes

I have an program which implements a Markov chain Monte Carlo process on a system of N bits, stopping when the process converges. Let's use T to denote the average number of steps made by the Markov ...
15
votes
5answers
3k views

Good introductory book for Markov processes

Which is a good introductory book for Markov chains and Markov processes? Thank you.
1
vote
1answer
220 views

If $P$ is a regular transition probability matrix then $P^{n^2}$ has no zero element

A transition probability matrix $P\in M_{n\times n}$ is regular if for some $k$ the matrix $P^k$ has all of its elements strictly positive. I read that this can be tested by using the following ...
6
votes
2answers
161 views

What does it mean to observe a Markov Chain after a certain kind of transition?

I'm working on a problem concerning censoring of transitions in a Markov Chain. For example, take a Markov Chain that models a counter, it goes up or down but does not stay in position. A possible ...
5
votes
1answer
108 views

recurrence criterion for random-walk like Markov chain

Suppose we have a random-walk like Markov chain, i.e. state space is the set of all integers from $-\infty$ to $\infty$, the transition probability $P_{ij}$ is nonzero only when $j=i+1$ or $j=i-1$. ...
4
votes
1answer
180 views

Combinatory + Coding Theory

I am reading about an algorithm for finding minimum-weight words in large linear codes. Let $c$ be the codeword of weight $w$ to recover (with size $n$ and in $GF(2)$). Let $N = \left\{1, 2, \ldots, ...
4
votes
1answer
279 views

question involving Markov chain

Let $S_{2m}$ be the group of all permutations $\pi$ of $\{1, 2, \ldots, 2m\}$. The following transition kernel $S$ generates the random transposition walk $$ Ch(\pi, \pi')= \begin{cases} \frac{1}{2m} ...
4
votes
2answers
3k views

Is ergodic markov chain both irreducible and aperiodic or just irreducible?

As I find some definition says: Ergodic = irreducible. And then Irreducible + aperiodic + positive gives Regular Markov chain. A Markov chain is called an ergodic chain if it is possible to go ...
4
votes
1answer
211 views

Does every continuous time minimal Markov chain have the Feller property?

Consider a Q-matrix on a countable state space. (A Q-matrix is a matrix whose rows sum up to $0$, with nonpositive finite diagonal entries and nonnegative offdiagonal entries). As explained for ...
3
votes
1answer
69 views

When are stable continuous time Markov chains Feller? Always?

This is a question is similar to this 2 year-old one that never got answered (truthfully it's pretty much the same question except that I'm adding a bit more detail and the assumption that the $Q$ ...
3
votes
1answer
267 views

Expected number of runs

Let $S[16]$ be a binary array i.e, elements of $S$ are 0/1 with elements $S[i]$ are taken uniformly and independently form $\{0,1\}$. Let $k$ be a random element taken uniformly from $\{0,1\}$. I have ...
2
votes
1answer
3k views

How can I compare two matrices?

I have a matrice A. It is model probability matrice for some process (Markov chain). Then, I have estimated matrice B. I have to somehow compare these two matrices to tell whether process that gave ...
2
votes
3answers
591 views

How to show Martingale property for sum of $S_k-E(S_k)$-summands where $S_k$ is a function of two RV's

EDIT: new formulation of the question (old version below). In a paper I found the statement that a certain sum $M_n =Y_1+\dotsb Y_n$ is a martingale, $Y_i=f (X_k, Z_k) - E ( f(X_k, Z_k) | X_k)$. (The ...
1
vote
0answers
133 views

a problem on DTMC

For a Markov chain $\{X_n, n\ge0\}$ with transition probabilities $P_{i,j}$, consider the conditional probability that $X_n = m$ given that the chain started at time $0$ in state $i$ and has not ...
4
votes
2answers
118 views

Markov and independent random variables

This is a part of an exercise in Durrett's probability book. Consider the Markov chain on $\{1,2,\cdots,N\}$ with $p_{ij}=1/(i-1)$ when $j<i, p_{11}=1$ and $p_{ij}=0$ otherwise. Suppose that we ...
3
votes
1answer
379 views

Proof about Steady-State distribution of a Markov chain

Consider $A$ as a matrix, that when normalized represents an finite-state time-homogeneous Markov chain $M$ with entries $0\leq p_{i,j}\leq 1$, where each row sums up to $1$. We can also assume that ...
3
votes
1answer
2k views

Finding the stationary distribution of a markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\mathbb{N}_0$, $q_n >0$ for all $n \in \mathbb{N}_0$ and transition matrix below: \begin{bmatrix} q_0 ...
2
votes
1answer
382 views

Finding the steady state Markov chain?

I have drawn a certain Markov chain with a weird transition matrix. Here's the drawing: And here's the transition matrix: My problem is that I don't quite know how to calculate the steady state ...
1
vote
1answer
46 views

Stickers in a box Markov chain problem

I'm revising for exams in June and my university, very irritatingly, doesn't provide mark schemes for past questions. I'm stuck a few parts into a question and am not totally confident of my preceding ...
1
vote
0answers
25 views

showing a condition implies convergence to invariant distribution

For an arbitrary Markov chain, I'm trying to show that $\lVert{ P_{\mu}\circ \theta_n^{-1} - \nu \rVert}\to 0$ iff $\sum_j \lvert{ P_{ij}^n - \nu(j)\rvert}\to 0$, where $\theta_n^{-1}$ is a shift ...
1
vote
2answers
95 views

Expected number of steps between states in a Markov Chain

Suppose I am given a state space $S=\{0,1,2,3\}$ with transition probability matrix $\mathbf{P}= \begin{bmatrix} \frac{2}{3} & \frac{1}{3} & 0 & 0 \\[0.3em] \frac{2}{3} ...
1
vote
1answer
61 views

Given an invariant distribution is the (finite state) Markov transition matrix unique?

Doeblin's theorem states that for a given transition probability matrix there exists a unique invariant distribution for that chain. Is the converse true as well? Can two (finite state, discrete) ...
1
vote
1answer
45 views

makov chains and property

let $X_t$ for $t \in \{1,2,...,10\}$ be a sequence of independent tosses of a fair coin. We denote heads with 1 and tails with 0. Define the random variable $S_n=\sum_{t=1}^n X_t$ for $n \in ...
1
vote
1answer
123 views

Steady State Markov Chain

I was reading http://www.ams.org/bookstore/pspdf/mbk-58-prev.pdf and going through the first example for the frog jumping between the lily pads. I'm interested in find the steady-state probability for ...
1
vote
2answers
317 views

Estimating the transition matrix given the stationary distribution

Let's say we are given a Markov chain for variable $X = [x_1, ..., x_n]$; also we are given a desired stationary distribution for this graph $P_\infty = [p_1, ..., p_n]^\top$. How can we design an ...
1
vote
1answer
243 views

Finding Markov chain transition matrix using mathematical induction

Let the transition matrix of a two-state Markov chain be $$P = \begin{bmatrix}p& 1-p\\ 1-p& p\end{bmatrix}$$ Questions: a. Use mathematical induction to find $P^n$. b. When n goes to ...
1
vote
1answer
217 views

Transforming an inhomogeneous Markov chain to a homogeneous one

I fail to understand Cinlar's transformation of an inhomogeneous Markov chain to a homogeneous one. It appears to me that $\hat{P}$ is not fully specified. Generally speaking, given a $\sigma$-algebra ...
1
vote
1answer
129 views

Expected number of jumps in a regular pure-birth process with Malthusian parameter.

Consider a pure-birth process $X(t)$ with rates $\lambda_i$ that satisfies $$\sum_{i=0}^\infty \frac{1}{\lambda_i} = \infty.$$ By Reuter's criterion this is sufficient for $X(t)$ to be regular, ie ...
1
vote
1answer
309 views

Finite State Markov Chain Stationary Distribution

How does one show that any finite-state time homogenous Markov Chain has at least one stationary distribution in the sense of $\pi = \pi Q$ where $Q$ is the transition matrix and $\pi$ is the ...
1
vote
1answer
778 views

Proving a process is Markov chain

Could anyone give me an example of a problem where it is requested to prove rather than assume that a stochastic process forms a Markov chain. I can think of something like this: if $X_{n+1} = X_{n} + ...
1
vote
4answers
280 views

Figuring out probabilities with Hidden Markov Models

I'm really new to Math so sorry in advance if this question does not make sense. Also I cross posted this on stats.stackexchange.com also. Background: I'm trying to learn about hidden Markov models ...
1
vote
0answers
119 views

Expectation of an event

Let $S[4]$ be a binary array with elements of $S$ are taken uniformly and independently from $\{0,1\}$. Also take $k$ uniformly from $\{0,1\}$. Take $i=1$. Now run the following process: Take $a,b$ ...
0
votes
3answers
85 views

How fast does this Markov chain converge?

Observe the above a Markov chain and limiting matrix of it. Finding the limiting matrix if it exists is easy but I am curious as to how fast this given matrix converges to its limiting matrix. Is ...
0
votes
0answers
12 views

Struggling to prove Markov chain property / State machine property - I can see what I need to do just can't write it

First notation, I have created the shorthand: $$P_x(A)=\mathbb{P}(A|X_0=x)$$ just to save time. I wish to prove "Lemma 1.3" which states the following: If $0<\alpha\le P_x(T_y\le k) \forall x\in ...
0
votes
1answer
80 views

Asymmetric doubly stochastic matrix.

Can a doubly stochastic matrix be asymmetric ? It's a fairly simple question but I cannot find the answer to it anywhere.