Say I have a discrete-time Markov process (and let's say discrete states too, for simplicity). If $\mathbf p_t$ is a vector of probabilities over states at time $t$, then the probability distribution in the next time step $\mathbf p_{t+1}$ can be obtained by multiplying by the transition matrix $\mathbf T$:

$$ \mathbf p_{t+1} = \mathbf T \mathbf p_t $$

$\mathbf T$ is a stochastic matrix, and is normalized such that its columns sum to 1. This ensures that one unit of probability mass at time $t$ is conserved as it is distributed to states at time $t+1$. In the special cast that $\mathbf T$ is doubly-stochastic, all its rows and columns sum to 1, and we can also define an adjoint process which propagates states backwards in time, again conserving probability.

$$ \mathbf q_{t} = \mathbf T^\top \mathbf q_{t+1} $$

Furthermore, if $\mathbf T$ is doubly-stochastic, we know that the stationary distribution (the leading eigenvector of $\mathbf T$) of the forward-time process is uniform.

My question: Say we have a $\mathbf T$ which is only left stochastic (columns sum to 1, but not rows). The Sinkhorn-Knopp algorithm can be applied (iteratively, and alternatingly, normalizing the rows/columns to 1), and converges to a doubly-stochastic matrix $\tilde{\mathbf T}$ in this case. How should we interpret $\tilde{\mathbf T}$ in relation to the original process with transition probabilities $\mathbf T$?

How I got here: I have a Markov process with a non-uniform stationary distribution. I want to know whether it is possible to define an adjusted process with a uniform stationary distribution that is in some sense "as close as possible" to the original, and related to it in some clear way. Reason being: I want a process which will sample a maximum-entropy coverage of the state space, but is still close and clearly related to the original process. Is there some deeper definition of "as close as possible" and "clearly related to" for which the doubly-stochastic matrix generated by Sinkhorn-Knopp is the solution? (Or is there another way of generating a doubly-stochastic $\tilde{\mathbf T}$ which has a cleaner interpretation?)



You must log in to answer this question.