1
vote
1answer
29 views

Proving Product of Transition Matrices is again a Transition Matrix.

Let $P = [p_{ij}]$ be an $n\times n$ transition matrix for an $n$-state markov chain. How do you prove that $P^2$, or even better, that $P^n$ is again a transition matrix? My approach leaves me ...
2
votes
1answer
21 views

Applying transition matrix to a probability vector seems to ruin its normalization

I had a little bit about stochastic processes during my "Statistical Physics" course and on my exam I got a problem with a Markov chain. My solution seems to be without computational mistakes (checked ...
0
votes
2answers
42 views

Proof that steady state is not affected by initial distribution in Markov chain.

I was following a proof provided in Gilbert Strang's book "Introduction to Linear Algebra". And I am confused by one step of the proof. Suppose we have a $n$ by $n$ stochastic matrix $A$, where all ...
1
vote
1answer
39 views

PRobability Markov chain, system of equations

I'm looking for techniques or tricks to solve a system of linear equations you get where you want to find the limiting probabilities. The system is this: $\pi_0 = 0.7\pi_0 + 0.2\pi_1 + 0.1\pi_2$ ( ...
4
votes
1answer
74 views

How is the Chapman-Kolmogorov Equation not a fancy name for matrix multiplication?

The Chapman-Kolmogorov Equation: $$p^{m+n}(i,j)=\sum_kp^m(i,k)p^n(k,j)$$ Matrix Multiplication (with $[A]_{i,j}=a_{i,j}$ where $A$ is a linear map "" for B) $$[AB]_{i,j}=\sum_ka_{i,k}b_{k,j}$$ In ...
2
votes
0answers
40 views

Markov Chain with Normal Transition Matrix

Consider a (sub)-stochastic matrix $P$, and the associated Markov chain $X$ with \begin{align*} \mathbf P [X_n =y | X_0 = x] = P_{xy}^n. \end{align*} Suppose we have the condition $P^T P = P P^T$, ...
0
votes
1answer
24 views

How many iterations are generally required when using the power iteration method?

Suppose I have an n x n matrix and I want to find the dominant eigenvalue and its associated eigenvector. Given these dimensions, what is the minimum number of iterations of the power iteration ...
0
votes
2answers
62 views

Find steps to reach absorbing markov chain state

How can I find the steps it takes or days or whatever the time variable is till the matrix reaches the absorbing state. e.g. take the matrix (The probability of each column adds to 1) $$ \left[ ...
5
votes
0answers
131 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
1
vote
2answers
90 views

Solving a linear equation to find a stationary matrix

I'm trying to solve the following system of linear equations derived from a transitional matrix for a regular Markov chain. I can't use matrix methods since that would involve finding the inverse of a ...
0
votes
1answer
130 views

Linear Algebra Stochastic Matrix and Markov Chains

I have a few true and false questions I need help with. Can someone please check my work? The product of two stochastic matrices is a stochastic matrix. This is false I found a counterexample. 2 ...
1
vote
1answer
59 views

Finding non-negative matrices, 0 on the main diagonal for which this positive vector is invariant.

This is a sort of reverse eigenvector problem. Usually, given a matrix, we want to describe its eigenvalues. Here -- given a vector, we'd like to determine matrices (satisfying some conditions) for ...
-1
votes
1answer
64 views

Proof that the square of a stochastic matrix is stochastic

We know that the square of a stochastic matrix is also stochastic, because the two-step transition matrix of a Markov chain is necessarily stochastic. However, in there another way to independently ...
1
vote
1answer
31 views

Markov process: characterize states which cannot arise naturally from a previous state

From an old qualifying exam: Assume that a particular electric switch has three states: left, middle, and right. Assume that the switch is programmed to follow these instructions at the start ...
2
votes
1answer
55 views

Can I invert a single row of a very large sparse matrix?

Problem I research electron behavior in organic solar cells and have found a way to recast this problem in terms of a large (n=~60 million) Absorbing Markov Chain that I represent as a sparse matrix. ...
0
votes
0answers
70 views

A matrix of size $n\times n$ with several properties like Markov matrices

Could you find a square matrix $A=[a_{ij}]$ of size $n$ such that satisfies to following properties 1) For all $1\le i\le n$, $\sum_{j=1}^n a_{ij}=0$ 2) For all $i$, $a_{ii}<0$ and for $1\le i\ne ...
1
vote
1answer
86 views

Prove that all Markov Chain have a unique state of equilibrium.

I have the following problem, for which i don't know how to start: Prove that all Markov Chain have a unique state of equilibrium. That is, if $P$ is the transition matrix of a Markov regular chain, ...
1
vote
1answer
127 views

Expected number of random binary vectors to make matrix of order n

I have the following problem: I pick random vectors from $\mathrm{F}_2^n$. The chance that position $i$ is $1$ equals $p_i$, $0$ otherwise (each position is picked independently). Let $X$ be a random ...
1
vote
0answers
61 views

A matrix-multiplication random walk

Let $x \in \mathbb{R}^n$. Consider an $n\times n$ matrix $A$. Suppose we're interested in how $||A^nx||$ grows with $n$, the answer (excluding pathological cases) is that it scales exponentially with ...
0
votes
2answers
78 views

Discrete Markov Transition Matrix

Well, I've been reading over the internet but I've been unable to find a straight answer. I've got a transition matrix for a Markov Discrete Chain. I've made the graph and according to my knowledge, ...
1
vote
1answer
70 views

Upper Bound of Markov Chain Convergence?

Reading about Markov Chain Monte Carlo in this book on Probability (DeGroot), it says In general, the distribution will get pretty close to the stationary distribution in finite time, but how ...
0
votes
1answer
169 views

Markov Chain with two states

A Markov Chain has two states, $A$ and $B$, and the following probabilities: If it starts at $A$, it stays at $A$ with probability $\frac13$ and moves to $B$ with probability $\frac23$; if it starts ...
1
vote
2answers
325 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
216 views

Reverse engineer transition matrix from steady state?

I had this open ended question. Is it possible to reverse engineer a transition matrix from the steady state. Is there a unique solution or could there be many? Basically given $P^{\infty}$ is there ...
0
votes
1answer
186 views

Relationship between an inhomogeneous Poisson process and Markov chain

What type of Markov process relates to an inhomogeneous Poisson process? A homogeneous Poisson process-- one where the rate, $\lambda$, is constant-- is a pure birth continuous time Markov chain ...
2
votes
2answers
288 views

The second largest eigenvalue for Perron-Frobenius matrix

The Perron-Frobenius theorem is about the largest eigenvalue and eigenvector of a non-negative (irreducible) matrix. My question: Is there any estimation of the difference between the first and ...
1
vote
0answers
21 views

Some questions about a “relaxed” invariant probability problem $|\mu(P-I)|\leq \epsilon$

Let's consider the set $\mathcal{M}=\{\mu:|\mu(P-I)|_1\leq \epsilon\}$ where $\mu$ is a probability vector, $P$ is the transition matrix of a discrete homogeneous Markov chain, $I$ is the identity ...
4
votes
2answers
2k views

Why Markov matrices always have 1 as an eigenvalue

Also called stochastic matrix. Let $A=[a_{ij}]$ - matrix over $\mathbb{R}$ $0\le a_{ij} \le 1 \forall i,j$ $\sum_{j}a_{ij}=1 \forall i$ i.e the sum along each column of $A$ is 1. I ...
1
vote
1answer
39 views

Finding the limiting distribution of a $3 \times 3$ Markov chain

This is a question from a book. Find $\lim_{n\rightarrow \theta}P^n$ where $$P=\begin{pmatrix}0 & 1 & 0\\ \frac{1}{6} & \frac{1}{2} & \frac{1}{3}\\ 0 & \frac{2}{3} & ...
0
votes
1answer
73 views

Bounding the smallest eigenvalue of an ergodic Markov Chain

I am trying to prove that the smallest eigenvalue of an ergodic Markov chain is greater than -1. Can we do that using proof by contradiction, i.e. assuming the smallest eigenvalue being -1, etc.? The ...
1
vote
1answer
711 views

Example of a Markov chain transition matrix that is not diagonalizable?

It is well-known that every detailed-balance Markov chain has a diagonalizable transition matrix. I am looking for an example of a Markov chain whose transition matrix is not diagonalizable. That is: ...
0
votes
1answer
128 views

Calculate the determinant of the matrix ad hence prove

By computing the determinant of $\lambda I-L$ where $L$ is the Leslie matrix, derive the Euler Lotka equation. $$L= \begin{bmatrix} b_{1} & b_{2} & \ldots & b_{w-1} & b_{w}\\ s_{1} ...
0
votes
1answer
94 views

The regularity of Markov chains with a threshold

I am studying Paz's "Introduction to Probabilistic Automata", and there is an exercise I cannot solve: Ex. 11, p. 170: Prove that the number of nonregular events of the form $\{x \mid p^A(x) > ...
3
votes
4answers
73 views

Determining vector equations

Let $A\in \Bbb R^{n\times n}$ be a matrix such that $\mathrm{rank}(A) = n-1$ and consider the equation $$ Ax = 0. $$ Clearly, its solutions span a $1$-dimensional space, thus an additional ...
1
vote
2answers
546 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 ...
0
votes
2answers
458 views

Why is every irreducible matrix with period 1 primitive?

In a certain text on Perron-Frobenius theory, it is postulated that every irreducible nonnegative matrix with period $1$ is primitive and this proposition is said to be obvious. However, when I tried ...
1
vote
1answer
167 views

Eigenvalues of a quasi-stochastic matrix

Quasi-stochastic In order not to make the title too long I used the term Quasi-Stochastic with this meaning: a quasi-stochastic matrix $Q$ is a square matrix $Q = ...
0
votes
2answers
135 views

Issue with calculating the cholesky decomposition

I am trying to calculate the cholesky decomposition of the matrix Q= ...
14
votes
1answer
451 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 ...
1
vote
1answer
158 views

Can you fit a Markov chain transition matrix to a series of vectors?

Given a set of column vectors $v_1, v_2,...,v_t$ is there a way to calculate a unique transition matrix? In other words, is there one and only one matrix $A$ such that $Av_{i} = v_{i+1}$? ...
2
votes
2answers
243 views

Looking for an example of a Markov Chain

I am looking for an example of a Markov Chain characterized by, say, 3 by 3 matrix that has more than one eigenvector (say a population distribution of birds, or something). I remember solving a ...
2
votes
1answer
935 views

Computing the similarity between two matrices / Monte Carlo analysis

I am studying the article at the following link, http://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf Which applies Monte Carlo analysis to a decryption problem. The math is admittedly over ...
0
votes
2answers
2k views

What is the eigenvalue of stochastic matrix?

I have a stochastic matrix $A \in R^{n \times n}$ whose sum of the entries in each row is 1. When I found out the eigenvalues and eigenvectors for this stochastic matrix, it always happens that one of ...