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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
26 views

Compressing covariance matrix from 3X3 to 2X2

thanks for answering my question. My question is, Let $v_3=[a,b,c]^T$ is a probabilistic 3-D vector variable which is distributed by zero mean Gaussian of dense covariance matrix $\Sigma_{3\times3}$. ...
user avatar
7 votes
2 answers
205 views

On permanent of a square of a doubly stochastic matrix

Let $A = (a_{i,j})$ be a double stochastic matrix with positive entries. That is, all entries are positive real numbers, and each row and column sums to one. A permanent of a matrix $A = (a_{i,j})$ is ...
user avatar
-1 votes
2 answers
131 views

How to generate constant row and column sum matrices?

How can we randomly generate matrix $A \in \mathbb{R}^{n \times m}_{\geq 0}$ that satisfies $A 1_n = m1$ and $A^T 1_m = n1$.
user avatar
2 votes
0 answers
84 views

Maximum volume submatrices of a Khatri-Rao product of matrix exponentials

My question requires quite a bit of setup, which leads to a conjecture. So I split my question into three parts, Setup, Conjecture, and Question. Setup: Pick any two right stochastic matrices $\...
user avatar
2 votes
0 answers
63 views

Pagerank Markov chain reductions

In short: if a Markov chain models a (generalized) pagerank, is it always possible to remove any of its state and obtain a Markov chain that models a pagerank close to the initial one? Full details. ...
user avatar
1 vote
1 answer
226 views

Generalization of Sinkhorn’s theorem to stochastic tensors?

Is there an algorithm for mapping a nonnegative tensor / kD array into stochastic form? i.e. assume we have a tensor of unnormalized counts, $c: ℕ^{n^k}$, can we derive a function $f: ℕ^{n^k} → ℝ^{n^k}...
user avatar
  • 113
3 votes
1 answer
124 views

Existence of a specific stochastic matrix

Let $0\le x_1\le x_2\le \cdots\le x_n\le n-1$ be given. My question is as follows : Under which condition there exists a doubly stochastic matrix $M=(m_{i,j})_{1\le i,j\le n}$ s.t. $$\sum_{j=1}^n (j-1)...
user avatar
1 vote
1 answer
272 views

The integral of a Gaussian process on a unit sphere

Suppose there exist a zero-mean Gaussian process $\mathbb{G} f_u$ indexed by $u \in \mathcal{S}^{p - 1}$ with known covariance $\mathrm{E} \big[ \mathbb{G} f_u \mathbb{G} f_v \big]$ when both $u$ and $...
user avatar
  • 173
0 votes
1 answer
310 views

Follow up: Show that these vectors are linearly independent almost surely

I posted this question some time ago here. I started a bounty for it and received an answer which helped me a lot. However, I still have some issues I want to discuss regarding it. Unfortunately I can'...
user avatar
11 votes
1 answer
677 views

Show that these vectors are linearly independent almost surely

So I'm doing research in control theory and I have been stuck with this problem for a while. Let me explain my issue, then my proposal, and finally my concrete question. Problem: I have $m<n$ real $...
user avatar
5 votes
2 answers
274 views

Doubly-stochastic partial-isometric matrices

An $n\times n$ matrix $A$ with nonegative real entries $a_{ij}$ is said to be doubly stochastic if $\sum_{i=1}^na_{ij} = 1$, for all $j$, and $\sum_{j=1}^na_{ij}=1$, for all $i$. Much is known [1] ...
user avatar
  • 2,153
1 vote
0 answers
181 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 ...
user avatar
2 votes
1 answer
132 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 ...
user avatar
  • 23
2 votes
1 answer
124 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 ...
user avatar
  • 315
2 votes
0 answers
61 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 ...
user avatar
  • 21
4 votes
2 answers
234 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 ...
user avatar
8 votes
0 answers
342 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 & ...
user avatar
  • 181
11 votes
0 answers
704 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, ...
user avatar
3 votes
1 answer
194 views

Mixing time and spectral gap for a special stochastic matrix

Consider the following dimension stochastic matrix, \begin{bmatrix} p & q & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 &...
user avatar
  • 103
0 votes
1 answer
133 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?...
user avatar
  • 9
4 votes
0 answers
194 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 ...
user avatar
  • 21.4k
2 votes
4 answers
874 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 ...
user avatar
1 vote
1 answer
357 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 ...
user avatar
1 vote
0 answers
277 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. ...
user avatar
3 votes
1 answer
89 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-...
user avatar
  • 113
8 votes
1 answer
353 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}...
user avatar
2 votes
1 answer
177 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 ...
user avatar
1 vote
0 answers
333 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$ is ...
user avatar
  • 11
13 votes
2 answers
724 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 ...
user avatar
4 votes
1 answer
579 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 ...
user avatar
  • 21.5k
4 votes
0 answers
345 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$ ...
user avatar
2 votes
1 answer
317 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)...
user avatar
  • 1,351
3 votes
2 answers
2k 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 $(...
user avatar
5 votes
1 answer
569 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} \...
user avatar
  • 205
15 votes
3 answers
4k 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?
user avatar
19 votes
3 answers
1k 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 ...
user avatar
  • 385