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

7
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 ...
5
votes
1answer
425 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 ...
9
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 ...
6
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 ...
14
votes
1answer
479 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 ...
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
370 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
1answer
41 views

Symmetric random walk and the distribution of the visits of some state

I need help with this problem: Let $(S_n)_n$ a symmetric random walk in $\mathbb{Z}$ i.e $S_n=X_1 + \cdots + X_n$ with $(X_n)$ iid $\mathbb{P}(X_n=1)=\mathbb{P}(X_n=-1)=\frac{1}{2}$. Let $m \in ...
1
vote
2answers
618 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
71 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 ...
1
vote
1answer
2k 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
3
votes
2answers
319 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
371 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
312 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
2answers
38 views

$(S_0+\ldots + S_n)_{n\geq 0}$ not a Markov chain

Assume that $Y_0,\ldots , Y_n$ are independent random variables with the following identical distribution: $Y_i=1$ with propability $p$ and $Y_i=0$ with propability $1-p$. Also set $S_0=0$ and ...
1
vote
1answer
110 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
351 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 ...
0
votes
1answer
278 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.
5
votes
2answers
202 views

Generalization of the Jordan form for infinite matrices

Under what conditions is it the case that for a matrix $M$ whose rows and columns are indexed by a countably infinite set $S$ one has a Hamel basis consisting of generalized eigenvectors (i.e. $v \in ...
2
votes
1answer
267 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
163 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
114 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$. ...
5
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
189 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
280 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
1answer
221 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
76 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
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 ...
3
votes
1answer
268 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
36 views

On track Prerequisite for Statistics and Probability

I do not really have a solid mathematical background because of the range of courses i had back in high school/university that wasn't really scientific oriented. Presently i am doing an MSc in ...
2
votes
3answers
675 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
135 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
121 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
421 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
618 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
29 views

Literature request on Markov Chains which state transition probability matrix evolves over time

I want to know is there any literature on markov chains who's state transition probability matrix evolves over time? For instance, I have 2 states, 1 and 2. With $$P = \begin{bmatrix} p_{11} & ...
1
vote
0answers
22 views

Cereal boxes - Mean time spent in transient states

Problem: A cereal company gives 2 images in each cereal box it has. There are a total of 5 images. Once a buyer have 5 images she wins a prize. No box contains 2 images that are the same. What is the ...
1
vote
0answers
56 views

Follow-up on solution to Markov process equation

I asked a question here about solving a system related to an absorbing Markov chain. I now have a variation where there are $m$ types (of student, job seeker, etc) each of which applies to ...
1
vote
1answer
47 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
110 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
83 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
81 views

Are there open questions in Markov chains?

I would be curious to know if there's still open question about discrete markovian chains
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
161 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
389 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
328 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 ...