0
votes
1answer
15 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
41 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
75 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
46 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
83 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
53 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
55 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
30 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
47 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. ...
1
vote
0answers
64 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
78 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
117 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
51 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
75 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
62 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
147 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
241 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
182 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
149 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
253 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
18 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
38 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
70 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
647 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
125 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
92 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
445 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 ...
1
vote
0answers
56 views

Lower bound on the minimum entry of the stationary distribution

Let $\phi$ be the stationary distribution vector (Perron vector) arrising from a stochastic (not doubly stochastic) matrix $P$. Can you think of a way to lower-bound $\min\phi$ in terms of $\parallel ...
0
votes
2answers
390 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
158 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
130 views

Issue with calculating the cholesky decomposition

I am trying to calculate the cholesky decomposition of the matrix Q= ...
13
votes
1answer
400 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
153 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
236 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
923 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
1k 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 ...