Dicen que un azar matriz cuadrada $A\in\mathbb{R}^{n\times n}$, cada columna de $A$ tiene exactamente un elemento distinto de cero es 1, es decir, cada columna se parece a $e_i=\{0,\dots,1,\dots,0\}^\top$. Dicen que para cada columna, la posición de la 1 se yo.yo.d. dibujar a partir de la distribución uniforme sobre $\{1,2,\dots,n\}$. ¿Cuál será la distribución de $rank(A)$ ? ¿Cuál es su expectativa? Se concentran cerca de sus expectativas?
Respuestas
¿Demasiados anuncios?
user87023
Puntos
1
Las filas de $A$ son parejas ortogonal, por lo que el rango de $A$ es el número de distinto de cero filas. Cada fila es distinto de cero con una probabilidad de $1-(1-1/n)^n$, por lo que el espera de rango es $n(1-(1-1/n)^n)\approx n(1-1/e)\approx0.632\times n$ grandes $n$. Para las pequeñas $n$, tenemos los valores de $1,\frac32,\frac{19}{9},\frac{175}{64},\ldots$.
(Además de la expectativa, no estoy seguro de lo que el resto de la distribución se parece.)
awkward
Puntos
1740
El rango es el número de filas que contienen al menos un $1$. Vamos a utilizar el método de variables indicadoras para encontrar la media y la varianza de la clasificación. Resulta que el reparto se hace el concentrado cerca de la media.
Deja $$I_i = \begin{cases} 1 \qquad \text{if row } i \text{ contains at least one 1} \\ 0 \qquad \text{otherwise} \end{casos}$$ para $i = 1,2,3, \dots ,n$, y vamos a $$X = \sum_{i=1}^n I_i$$ por lo $X$ es el rango de la matriz. Tenemos $$P(I_i = 0) = \left( \frac{n-1}{n} \right)^n = (1-1/n)^n$$ por lo $P(I_i = 1) = 1- (1-1/n)^n$, y la media de $X$es $$\mu = E(X) = E \left( \sum_{i=0}^n I_i \right) = \sum_{i=0}^n E( I_i) = n [ 1- (1-1/n)^n]$$ Sabemos $(1-1/n)^n \to e^{-1}$ como $n \to \infty$, lo $\mu \sim (1-e^{-1})n$.
Para encontrar la varianza de $X$, primero tenemos que encontrar a $E(\sum_{i<j} I_i I_j)$. Así que aviso que $$\begin{align} P(I_i I_j = 0) &= P(I_i = 0) + P(I_j = 0) - P((I_i = 0) \cap (I_j=0)) \\ &= 2 (1-1/n)^n - (1-2/n)^n \end{align}$$ para $i < j$, lo $P(I_i I_j = 1) = 1 -2 (1-1/n)^n + (1-2/n)^n$. Por lo tanto $$E \left( \sum_{i<j} I_i I_j \right) = \sum_{i<j} E(I_i I_j) = \frac{n(n-1)}{2} [ 1 -2 (1-1/n)^n + (1-2/n)^n ] $$ Porque de la identidad $$\left( \sum_{i=0}^n I_i \right )^2 = \sum_{i=0}^n I_i^2 + 2 \sum_{i<j}I_i I_j = \sum_{i=0}^n I_i + 2 \sum_{i<j}I_i I_j$$ tenemos $$X^2 = X + 2 \sum_{i<j}I_i I_j$$ así $$\begin{align} E(X^2) &= E(X) + 2 \sum_{i<j} E(I_i I_j) \\ &= n [ 1- (1-1/n)^n] + n(n-1) [ 1 -2 (1-1/n)^n + (1-2/n)^n ] \end{align}$$ Por lo que la varianza de $X$es $$\begin{align} \sigma^2 &= E(X^2) - (E(X))^2 \\ &= n(1-1/n)^n - n^2(1-1/n)^{2n} + n(n-1)(1-2/n)^n \end{align}$$ después de la simplificación. Resulta que (ver más abajo) que $\sigma^2 \sim (e^{-1} - 2 e^{-2}) n$, por lo que $$\frac{\sigma}{\mu} \sim \frac{\sqrt{e^{-1}-2 e^{-2}}}{1-e^{-1}} \frac{1}{\sqrt{n}}$$ y el reparto se hace el concentrado cerca de la media para las grandes $n$.
El comportamiento asintótico de $\sigma^2$ grandes $n$:
Desde arriba, tenemos $$\begin{align} \frac{\sigma^2}{n} &= (1-1/n)^n - n (1-1/n)^{2n} + (n-1)(1-2/n)^n \\ &= (1-1/n)^n - (1-2/n)^n+ n[(1-2/n)^n-(1-1/n)^{2n}] \end{align}$$ así $$\lim_{n \to \infty} \frac{\sigma^2}{n} = e^{-1} - e^{-2} + \lim_{n \to \infty} n[(1-2/n)^n -(1-1/n)^{2n}] \tag{*}$$ Para evaluar el límite último de arriba, observe que $$\lim_{n \to \infty} n[(1-2/n)^n -(1-1/n)^{2n}] = \lim_{x \to 0} \frac{1}{x} [(1-2x)^{1/x} - (1-x)^{2/x}] $$ y $$\begin{align} (1-2x)^{1/x} &= \exp( (1/x) \ln(1-2x)) \\ &= \exp((1/x)(-2x -2x^2 +o(x^3)) \\ &= \exp(-2 -2x +o(x^2)) \\ &= e^{-2} \exp(-2x +o(x^2)) \\ &= e^{-2} (1-2x) + o(x^2) \end{align}$$ Del mismo modo, $$\begin{align} (1-x)^{2/x} &= \exp((2/x) \ln(1-x) \\ &= \exp((2/x) (-x -(1/2)x^2 +o(x^3)) \\ &= \exp(-2-x+o(x^2)) \\ &= e^{-2} \exp(-x +o(x^2)) \\ &= e^{-2} (1-x) + o(x^2) \end{align}$$ Así $$\begin{align} \lim_{x \to 0} \frac{1}{x} [(1-2x)^{1/x} - (1-x)^{2/x}] &= \lim_{x \to 0} \frac{1}{x} [e^{-2}(1-2x) +o(x^2) - e^{-2}(1-x) + o(x^2)] \\ &= \lim_{x \to 0} (-e^{-2} + o(x)) \\ &= -e^{-2} \end{align}$$ Sustituyendo en (*), tenemos $$\lim_{n \to \infty} \frac{\sigma^2}{n} = e^{-1} - e^{-2} - e^{-2} = e^{-1} -2 e^{-2}$$ por lo $\sigma^2 \sim (e^{-1} - 2 e^{-2}) n$, como se decía anteriormente.
