Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [stochastic-matrices]

A stochastic matrix (also termed probability matrix, transition matrix, substitution matrix, or Markov matrix) is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability.

0
votes
1answer
114 views

Pre-garbling does not improve capacity of a channel

Suppose ABC=B for some column stochastic matrices A, B, and C. Can the following implication be made without further restrictions: There necessarily exists a column stochastic matrix D such that DB=BC?...
4
votes
0answers
150 views

Birkhoff – von Neumann for “$k$-stochastic matrices”

Recall that a doubly-stochastic matrix is a square matrix with non-negative elements such the sum of the elements in every row, as well as in every column, is $1$. The set of doubly-stochastic ...
2
votes
4answers
245 views

Apply doubly stochastic matrix M to a probability vector, then entropy increases?

Consider a vector $p =(p_1,...p_n)$, $p_i>0$, $\sum p_i = 1$ and a matrix $M_{ij}$, which is doubly stochastic: $\sum_i M_{ij} = 1, \sum_j M_{ij} = 1, M_{ij} > 0$. Question 1 Just apply ...
1
vote
1answer
59 views

On the eigenvalue of the expectation value of a random matrix in quadratic form

When we handle with some dynamic input-output mappings, there occurs a question as follows: Let $M$ be a random matrix, of which each element contains random terms. Consider the two expectation ...
1
vote
0answers
132 views

Sufficient conditions for all eigenvalues simple in stochastic matrix

The "largest" eigenvalue $1$ of a stochastic matrix is well-characterized by the classical Perron-Frobenius theorem. In particular, it gives sufficient conditions for the eigenvalue $1$ to be simple. ...
3
votes
1answer
77 views

Bounds on $\|(P+\Delta)^n - P^n\|_F$ for stochastic matrices

Let us suppose that $P$ is a stochastic matrix (non-negative matrix with $P \mathbf{1} = \mathbf{1}$). Let $\Delta$ such that $P + \Delta$ is a stochastic matrix (which means $P + \Delta$ is non-...
8
votes
1answer
267 views

On the limit of partial sum of infinite doubly stochastic matrix

Let $A=(a_{ij})$ be an infinite doubly stochastic matrix. Does there necessarily exist a subsequence $\{n_k\}_{k=1}^\infty$ such that $$ \lim_{k\to\infty}\frac{1}{n_k}\sum_{i=1}^{n_k}\sum_{j=1}^{n_k}...
2
votes
1answer
150 views

A question on the partial sum of infinite doubly stochastic matrix

Let $A=(a_{ij})$ be an infinite doubly stochastic matrix. Is the following statement true ? $$ \lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^n\sum_{j=1}^na_{ij} >0 $$ Any reference or comment on this is ...
1
vote
0answers
151 views

Constraint involving a stochastic matrix and its inverse

Consider the following feasibility problem: Find an $n \times n$ stochastic matrix $L$ such that $L^{-1} M L x$ is a non-negative vector, where $M$ is a known $n \times n$ positive matrix and $x$ ...
0
votes
0answers
348 views

How to solve this row-stochastic matrix problem?

Let $$\alpha ={{[{{\alpha }_{1}},{{\alpha }_{2}}\cdots {{\alpha }_{n}}]}^{T}}$$ $$\beta ={{[{{\beta }_{1}},{{\beta }_{2}}\cdots {{\beta }_{n}}]}^{T}} $$ be 2 positive probability vectors. Where for ...
12
votes
2answers
407 views

The expected square of the determinant of a random row stochastic matrix

In this question Anthony Quas asks about the expected absolute value of the determinant of an $n\times n$ row stochastic matrix $A$, where the rows are independently selected from the uniform ...
4
votes
1answer
315 views

Determinant of a random row stochastic matrix

Does anyone know anything about the determinant of a random $n\times n$ row stochastic matrix? What I have in mind is that the rows are independently selected from the uniform distribution on the unit ...
4
votes
0answers
220 views

Spectral radius of the product of a right stochastic matrix and a block diagonal matrix

Let us define the following matrix: $C=AB$ where $B$ is a block diagonal matrix with $N$ blocks, $B_1$, $B_2$ … $B_N$, each of dimensions $M \times M$. I know that $B_k = I_M - \mu R_k$ with $R_k$ ...
2
votes
1answer
181 views

Eigenvectors of a perturbed reducible stochastic matrix

Let $Q$ be a $n\times n$ reducible stochastic matrix. Let $J$ be such that $[J]_{ij}={1 \over n}$. Now for a small positive constant $\alpha\in [0,1]$, consider the matrix $$\tilde{Q}\,=\,(1-\alpha)...
3
votes
2answers
961 views

Convergence of iterated stochastic matrices

It is well-known that for a stochastic aperiodic matrix $M$, the sequence $(M^n)_n$ converges. Here I would like to a have a more precise analysis. Consider now a sequence of stochastic matrices $(...
5
votes
1answer
433 views

The minimal norm of a shifted stochastic matrix

Given a row-stochastic matrix $M$ with singular values $\sigma_{1} \geq \cdots \geq \sigma_{n}$, I am looking for an upper bound on the expression $$\min_{\alpha} \left\| M- \frac{\alpha}{n}J_{n} \...
15
votes
3answers
3k views

Non-diagonalizable doubly stochastic matrices

Are there constructive examples of doubly stochastic matrices (whose rows and columns all sum up to $1$ and contain only non-negative entries) that are not diagonalizable?
14
votes
1answer
668 views

Which doubly stochastic matrices can be written as products of pairwise averaging matrices?

A matrix $A$ is called doubly stochastic if its entries are nonnegative, and if all of its rows and columns add up to $1$. A subset of doubly stochastic matrices is the set of pairwise averaging ...