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
4k 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 ...
15
votes
1answer
590 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
157 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 ...
2
votes
1answer
3k 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
5
votes
1answer
574 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 ...
2
votes
2answers
69 views

Under what conditions does $(I-N)^{-1}$ exist?

Given an nxn matrix N and $I=I_n$, under what conditions does $(I-N)^{-1}$ exist? On one hand $(I-N)(I + N + N^2 + ...) = (I + N + N^2 + ...) - (N + N^2 + ...) = I?$ On the other hand, $(I-N)(I + N ...
13
votes
2answers
3k 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
5k 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 ...
4
votes
1answer
286 views

Conditional return time of simple random walk

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, \, S_t =k \}$, the hitting time of $k \in \mathbb{N}$. Call $\tau^* = \min\{t ...
3
votes
2answers
477 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 ...
3
votes
1answer
2k 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} ...
1
vote
1answer
64 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
867 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
482 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
3answers
174 views

Characterize stochastic matrices such that max singular value is less or equal one.

By a stochastic matrix, I mean any non-negative square real matrix with rows summing to one. It is well-known that singular values of stochastic matrices can be more than one. Is there a ...
3
votes
2answers
260 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 ...
3
votes
2answers
385 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
489 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$, ...
2
votes
1answer
488 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
2answers
65 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
118 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 ...
0
votes
1answer
56 views

Markov chain: join states in Transition Matrix

I need to merge two states in the Transition Matrix: For example: I have the matrix below ...
0
votes
1answer
35 views

If the entries of an invertible matrix N are between -1 and 1, is its operator norm less than 1?

For Euclidean norm. If so, why? If not, might $(I-N)^{-1}$ exist some other way? This spins-off from here.
0
votes
1answer
78 views

probability, random walk, Markov chain question

Let $P$ be a transition matrix for a regular Markov chain and let $w$ be it’s equilibrium vector. Show that $w$ has no zero entries.
0
votes
0answers
63 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
424 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
129 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 ...
17
votes
5answers
4k views

Good introductory book for Markov processes

Which is a good introductory book for Markov chains and Markov processes? Thank you.
10
votes
2answers
1k 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 ...
5
votes
2answers
245 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 ...
4
votes
2answers
115 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$ ...
4
votes
1answer
4k 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
1answer
460 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 ...
7
votes
2answers
4k 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 ...
6
votes
2answers
179 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
142 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
1answer
261 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 off-diagonal entries.) As explained for ...
4
votes
1answer
194 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
288 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} ...
3
votes
1answer
284 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
43 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
824 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
69 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
3answers
609 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
578 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
0answers
158 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 ...
5
votes
3answers
134 views

A recursive formula to approximate $e$. Prove or disprove.

Let the sequence $\{x_n, n=1,2,...\}$ be defined as follows: Let $x_2=x_1=1$ and for $n>2$ let $$x_{n+1}=x_n-\frac{1}{n}x_{n-1}.$$ This sequence, generated by the recursion above, tends to zero ...
4
votes
1answer
95 views

Find the Stationary Distribution of an infinite state Markov chain

A Markov Chain on states 0,1,..... has transition probabilities $P_{ij}=1/(i+2)$ for j=0,1,....,i,i+1. I'm supposed to find the stationary distribution. So do I take the limit as n goes to ...
4
votes
2answers
122 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
107 views

Frog on infinitely many lily pads (Markov chain)

A frog on pad $i$ hops to one of the pads $(1,2,...,i,i+1)$ with equal probability. I know that if the frog starts on pad $k$ the expected number of times the frog jumps, before returning for the ...