# 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.

25
questions

**1**

vote

**0**answers

80 views

### Upper and lower bounds on the entries of a matrix power

Say I have a non-negative square $n\times n$ irreducible stochastic matrix $A$ (i.e., each column sums to 1), for which the following holds:
$$A_{ij} > 0 \iff A_{ji} > 0.$$
I know that no more ...

**2**

votes

**1**answer

107 views

### Diagonalizable stochastic matrix that satisfies an equation

Given an arbitrary discrete probability distribution $a = (a_1, ..., a_n)$ and another arbitrary discrete probability distribution $b = (b_1, ..., b_n)$, what is the easiest known way to find a ...

**2**

votes

**1**answer

82 views

### Is the Wasserstein kernel positive definite?

Define a point cloud $X=\{x_i\}_{1\leq i\leq n}$, for $x_i\in\mathbb R^d$. Define the Wasserstein kernel as $$W(X,Y)=\max_{T}\frac{1}{n}\sum_{kl}T_{kl}\langle x_k,y_l \rangle$$
where $T$ is any doubly ...

**2**

votes

**0**answers

53 views

### Completeness results for Categorical Quantum Mechanics restricted to one $\dagger$-Frobenius Algebra?

I've seen the various completeness results for Categorical Quantum Mechanics (CQM) axiom systems involving two interacting Frobenius algebras with various restrictions of phase-nodes. For example, the ...

**0**

votes

**0**answers

45 views

### Singular values of a rectangular stochastic matrix

I have a question related to rectangular stochastic matrix, ie for example a n x K matrix W such that the sum of the coefficients of a row is equal to one. Is there anything we can tell about the ...

**4**

votes

**2**answers

137 views

### Frobenius normal form of a doubly stochastic matrix

If $A \in M_n(\mathbb{C})$, then $A$ is called reducible if there is a permuation matrix $P$ such that
$$
P^\top A P =
\begin{bmatrix}
A_{11} & A_{12} \\
0 & A_{22}
\end{bmatrix}, $$
in ...

**8**

votes

**0**answers

245 views

### Eigenvalues of cyclic stochastic matrices

Let's consider the following $n \times n$ cyclic stochastic matrix
$$ M= \begin{pmatrix}
0 & a_2 & & & &b_n \\\
b_1 & 0& a_3& &&& \\\
& b_2 & ...

**11**

votes

**0**answers

648 views

### What properties characterize the function $L(x) = x+\exp(x) \log(x)$?

As might be known, the function $L(x) = x+\exp(x)\log(x)$ plays a prominent role in the Lagarias formulation of the Riemann hypothesis:
$$\sigma(n) \le H_n + \exp(H_n) \log(H_n)$$
My question is, ...

**0**

votes

**1**answer

124 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

**0**answers

172 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

**4**answers

557 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

**1**answer

113 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

**0**answers

200 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

**1**answer

83 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

**1**answer

292 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

**1**answer

162 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

**0**answers

273 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$ ...

**12**

votes

**2**answers

469 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

**1**answer

382 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

**0**answers

257 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

**1**answer

243 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

**2**answers

1k 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

**1**answer

481 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

**3**answers

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?

**16**

votes

**1**answer

794 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 ...