Consideremos el conjunto de todas las funciones de $\{1,2,...,m\}$ $\{1,2,...,n\}$donde $n > m$. Si una función es elegido a partir de este conjunto al azar, ¿cuál es la probabilidad de que esté estrictamente creciente?
Respuestas
¿Demasiados anuncios?
Permítanos pick $m$ elementos de $\{1,\dotsc,n\}$, que nos llame a estos $a_1 < a_2 < \dotsc , a_m$. Claramente estos definen estrictamente creciente en función $f$ $\{1,\dotsc,m\} \to \{1,\dotsc,n\}$ a través de la regla de $f(i) = a_i$. Además, cualquier estrictamente creciente en función definida en el anterior establece es de esta forma.
Por lo tanto, no son exactamente ${n \choose m}$ estrictamente creciente funciones. Por otro lado, son en total $n^m$ funciones de asignación entre estos dos conjuntos. Suponiendo que por "azar" el OP significa que el uniforme de la medida en la $n^m$ funciones anteriormente, entonces la probabilidad de seleccionar una función es estrictamente creciente:
$$ \frac{{n \choose m}}{n^m} $$
Por ejemplo, para $n >> m$, una aplicación de Stirling aproximación, muestra que el lado derecho es $ \approx \frac{1}{m!}$.
Aaron
Puntos
36
Deje $S(n,m)$ el número de sub-matrices de $1 \leqslant k_1 < k_2 < \cdots < k_m \leqslant n$ contiene $m$ valores enteros que van en aumento y están delimitadas por los valores de uno y $n$. Este binario función está bien definida para todos los números enteros $1 \leqslant m \leqslant n$, dando un triangular de la matriz de valores. Con un simple combinatoria argumento de$^\dagger$ podemos establecer las siguientes ecuaciones recursivas que definen esta función binaria:
$$S(n+1,m) = S(n,m) + S(n,m-1) \quad \quad \quad \quad S(n,1) = n.$$
La solución de esta ecuación recursiva nos da la fórmula explícita:
$$S(n,m) = {n \choose m} = \frac{n!}{m!(n-m)!}.$$
(Hay otros argumentos combinatorios que también conducen a este resultado. Por ejemplo, la elección de un aumento de la función es equivalente a la elección de $m$ valores en el co-dominio, que se colocan en orden creciente.) Ahora, para obtener el resultado que debemos tener claro exactamente cómo una "función random" en este dominio y co-dominio es elegido. La especificación más simple es decir que cada asignación posible es elegido con igual probabilidad, lo que significa que hay $n^m$ equiprobables funciones. Por lo tanto, la probabilidad es de interés:
$$\mathbb{P}(\text{Increasing Function}) = \frac{n!}{m!(n-m)! \cdot n^m}.$$
Tomar un primer orden de aproximación de Stirling para un gran $n$ da $\mathbb{P}(\text{Increasing Function}) \approx 1/m!$, lo cual es una estimación aproximada que es adecuado al $n$ es sustancialmente mayor que $m$. Así que, básicamente, vemos que una vez que el co-dominio en este problema es grande, la probabilidad de conseguir un aumento de la secuencia al azar es pequeño; esto concuerda con la intuición.
$^\dagger$ Si $m=1$ entonces tenemos un solo valor en la asignación y cada asignación a cualquiera de las $n$ lugares da un aumento de mapa. Por tanto, tenemos $S(n,1)=n$ todos los $n \in \mathbb{N}$. Por otra parte, el número de sub-matrices de $S(n+1,m)$ incluye todas las sub-matrices donde los valores se produce en la primera $n$ lugares (hay $S(n,m)$ de estos) y todos los sub-matrices donde el último valor que se produce en el último lugar y el resto de los valores ocurrir antes de esto (hay $S(n,m-1)$ de estos).
