¿Cómo puedo Generar Doblemente Estocástico Matrices Uniforme al Azar?

Question

Una doblemente estocástica de la matriz es una $n\times n$ matriz $P$ tal que

$\displaystyle\sum_{i=1}^n{p_{ij}}=1$

y

$\displaystyle\sum_{j=1}^n{p_{ij}}=1$

donde $p_{ij}\ge 0$.

Puede alguien sugerir un algoritmo para la generación de estas matrices uniforme al azar?

Answer 1

Lo que queremos es generar un bistochastic matriz de acuerdo a la medida de Haar, que es la única distribución que es invariante a la multiplicación por bistochastic matrices de ambos lados.

El algoritmo estándar es tomar algunos iid de la matriz (cada entrada es elegido iid de algunos de distribución sobre los números negativos) y, a continuación, en repetidas ocasiones hacen fila estocásticos y la columna estocástico - esto es como la proyección de la matriz de la aplicación lineal subespacio de las matrices estocásticas. El proceso converge muy rápido, y tenemos un poco de azar bistochastic de la matriz, aunque no según la quería de distribución.

Un estudio reciente analiza estos temas en el contexto de la estimación de la medida de todas las bistochastic matrices (un problema abierto).

Answer 2

En primer lugar puede generar al azar unitario de la matriz y, a continuación, la plaza de los valores absolutos de todas las entradas. Aquí es Mathematica código que hace esto:

(* Random real and complex numbers with normal distribution *)
RR := RandomReal[NormalDistribution[0, 1]];
RC := RR + I*RR;
(* Random matrix from Ginibre ensemble *)
RG[n_] := Table[RC, {n}, {n}];
(* Random unitary matrix *)
RU[n_] := Orthogonalize[RG[n]];
(* Random doubly stochastic matrix *)
RDS[n_] := Abs[RU[n]]^2;

Ejecutar RDS[5] para generar un $5 \times 5$ random doblemente estocástica de la matriz.

Answer 3

Supongamos que usted desea al azar racional punto en el Birkhoff polytope (conjunto de doble matrices estocásticas), con denominadores dividiendo $N$. Esto es equivalente al azar a una tabla de contingencia con todos los de la fila y la columna de cantidades iguales a $N$. Reversible de la cadena de Markov existe en el conjunto de tablas y rápidamente la mezcla. Esto puede ser usado para el muestreo aproximada por la siguiente cadena para un gran número de pasos. El límite de distribución de la cadena es prácticamente uniforme, porque lejos de los limites de la polytope, todos los vértices de la cadena tienen el mismo grado. Exacto de muestreo desde el límite de distribución de la cadena es posible, pero debido a que el límite de distribución no es uniforme, esto no es lo mismo como la obtención de una exacta de la muestra de la distribución uniforme en tablas de contingencia. El último es un duro problema sin resolver por lo que yo sé.