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 ...
14
votes
1answer
514 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 ...
4
votes
0answers
124 views

6-digit password - a special decoding method

Consider the situation of decoding a 6-digit password that consists of the symbols A to Z and 0 to 9, where all possible combinations are tried randomly and uniformly. Consider the ...
5
votes
1answer
469 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 ...
11
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
4k 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
392 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
45 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
708 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 ...
4
votes
2answers
353 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 ...
2
votes
2answers
113 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 ...
2
votes
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
376 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
352 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
55 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
113 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
390 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
0answers
50 views

Show that every finite closed class is positive recurrent

Let $C$ be a finite closed class. Prove or disprove that $C$ is positive recurrent. Note 1: In our lecture we proved that every finite closed class is recurrent. Note 2: (Positive) recurrence is ...
0
votes
1answer
327 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 ...
16
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
207 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 ...
9
votes
2answers
801 views

Expected number of turns for a rook to move to top right-most corner?

Suppose a rook starts on the lower left-most square of a standard $8 \times 8$ chess board. The board contains no other pieces. The rook randomly makes a legal chess move with every turn (directly ...
2
votes
1answer
313 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
166 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
122 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
191 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
283 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
229 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
83 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
273 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
727 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
1answer
52 views

Bound spectral radius of a certain matrix.

Consider a stochastic matrix $P$, i.e. real, non-negative, square, rows sum to one. Consider $\Xi = \text{diag}(\xi)$ to be a diagonal matrix with a principal left eigenvector $\xi$ of $P$ (i.e. ...
1
vote
0answers
141 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
477 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
75 views

Counterexample for $\| (\Phi^\top \Xi \Phi)^\dagger \Phi^\top \Xi P \Phi \|_2 \leq 1$

All matrices are real. Let $P$ be any stochastic matrix (i.e. square, non-negative, rows summing to one). Let $\Xi$ be a diagonal matrix containing on its diagonal any left eigenvector of $P$ ...
2
votes
1answer
47 views

Find conditions on the distribution on $X$, but what is meant by $X$?

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ ...
2
votes
1answer
1k 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 ...
2
votes
1answer
4k views

Expected number of steps/probability in a Markov Chain?

Can anyone give an example of a Markov Chain and how to calculate the expected number of steps to reach a particular state? Or the probability of reaching a particular state after T transitions? I ...
1
vote
1answer
60 views

How to show positive recurrence/ null recurrence?

Suppose that you have a Markov chain with state space $E$ containing $0$. Assume that $$ p_{00}^{(2n)}=\binom{2n}{n}\left(\frac{1}{2}\right)^{2n-1}~~~\text{ and ...
1
vote
0answers
37 views

Find condition on $X$ so that $P(\exists n\in\mathbb{N}: N_n=0)=1$

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. $X$ is identically distributed as all $X_{n,k}$. Define $N_0:=1$ and for ...
1
vote
0answers
45 views

Check if $(N_n)$ is a Markov chain

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ ...
1
vote
1answer
136 views

Periodicity of a communicating class

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with discrete state space $E$ and transition matrix $P$. Let $C\subseteq E$ be a communicating class. Prove or disprove the following ...
1
vote
1answer
39 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} & ...