Como nos ocupamos de funciones arbitrarias $f \colon A \to B$$g \colon B \to A$, no hay nada especial para ser adquirido por la toma de $\lvert A \rvert = \lvert B \rvert = n$, así que voy a responder a la pregunta más general: supongamos que tenemos $\lvert A \rvert = m$ de los hombres, y $\lvert B \rvert = w$ mujeres. Esto añade ninguna dificultad real para los cálculos, y en su lugar hace que algunas de las expresiones más claras. Para su caso, coloque $m = w = n$.
El azar modelo asumimos todo es que podemos elegir cualquiera de las $w^m m^w$ pares de funciones $(f, g)$, con igual probabilidad.
Vamos a demostrar a continuación que, bajo este modelo aleatorio,
el esperado número de puntos fijos de $f \circ g$ o $g \circ f$, o en otras palabras, se espera que el número de pares de los hombres y mujeres que les gusta el uno al otro, es $1$, y, más en general,
para cualquier $k$, la probabilidad de que este número de puntos fijos es exactamente $k$ es una cantidad que se puede calcular exactamente, y enfoques $\dfrac{1}{k!e}$$m, w \to \infty$. En otras palabras, la distribución del número de mutuo agrado pares se aproxima a una distribución de Poisson con una media de $1$.
-
"Si me gusta alguien, ¿cuál es la probabilidad de que ellos, como me de la espalda?"
Respuesta: $\dfrac1m$ si soy un hombre, $\dfrac1w$ si soy una mujer.
Para cualquier $f\colon A \to B$ y cualquier $a \in A$ si $f(a) = b \in B$, entonces la probabilidad más funciones aleatorias $g\colon B\to A$ que $g(b) = a$ es exactamente $\dfrac1m$ $g(b)$ toma en todas las $\left\vert{A}\right\vert = m$ valores con igual probabilidad. Y como la probabilidad es la misma para cada una de las $f$, sigue siendo el mismo al $f$ también es elegido al azar.
Lo mismo para las mujeres.
-
"¿Cuál es el número esperado de hombres que son del agrado de vuelta por las mujeres que les gusta?"
Respuesta: $1$.
Esto es por la linealidad de la expectativa: para cualquier $f$, tenemos
$$\operatorname{E}\left[\#\{a: g(f(a)) = a\}\right] = \sum_{a \in A} \Pr(g(f(a)) = m \frac1m = 1.$$
Y como la expectativa es la misma para cada individuo,$f$, también es la misma cuando se $f$ sí es elegido al azar.
-
"¿Cuál es el número esperado de mujeres que son del agrado de vuelta por los hombres que les gusta?"
Respuesta: $1$.
Por simetría / similar calcuation.
-
"¿Cuál es el número esperado de pares de (hombres, mujeres) que le gusta el uno al otro?"
Respuesta: $1$.
El número de mutuo agrado pares del curso es el mismo que el de cualquiera de los dos números considerado anteriormente.
Eso responde a tu pregunta original: el número esperado de pares $(a, b)$ tal que $f(a) = b$ $g(b) = a$ es exactamente $1$.
Queda por contestar la pregunta que se "redujo" a (que como veremos no es exactamente una reducción), sobre el número de pares de funciones $f \colon A \to B$ $g \colon B \to A$ tal que $g \circ f$ no tiene puntos fijos. Vamos a furtivamente por pulgadas.
-
"Para un conjunto dado de $k$ hombres, ¿cuál es la probabilidad de que todos ellos son gustó vuelta por las mujeres que les gusta?"
Respuesta: $\dfrac{\binom{w}{k}k!}{w^k m^k} = \dfrac{w^{\underline k}}{w^k m^k}$.
Dado $f$$a_1, a_2, \dots, a_k$, ¿cuál es la probabilidad de que $g(f(a_i)) = a_i$ todos los $1 \le i \le k$? Esta probabilidad depende de $f$. Claramente una condición necesaria para que todas las $a_i$'s como distintas mujeres: si dos de ellos como la misma mujer, no hay forma en que puede tanto ser del agrado de la espalda. Pero para cualquier $f$ donde esta condición se mantiene, entonces los eventos de cada una de ellas ha gustado de la espalda son independientes; cada uno de los hombres es del agrado de vuelta con una probabilidad de $1/m$, dando probabilidad de $\dfrac1{m^k}$, que ellos son todo lo que le gustaba de la espalda.
El número de funciones de $f$ satisfacer esta distinción condición es $\displaystyle \binom{w}{k}k! w^{m-k}$. Por lo tanto la probabilidad cuando se toma sobre todas las funciones de $f$ es
$$\frac{\frac{1}{m^k} \cdot \binom{w}{k}k! w^{m-k} + 0 \cdot \text{(the rest)}}{w^m} = \frac{\binom{w}{k}k!}{m^k w^k}$$
y así el número de pares de funciones $(f, g)$$w^{m-k}m^{w-k}\binom{w}{k}k!$.
(También podríamos haber calculado directamente: la función de $f$ $a_i$'s puede ser recogidas en $\binom{w}{k}k!$ formas, en el otro $a$'s $w^{m-k}$ formas, y $g$$m^{w-k}$).
También podemos utilizar la caída de los factorial notación: $w^{\underline k} = \binom{w}{k}k!$.
Finalmente, podemos responder a la pregunta:
- "¿Cuál es la probabilidad de que a nadie le gustaba la espalda?"
Es decir, ¿cuál es la probabilidad de que $g \circ f$ no tiene puntos fijos? Deje que el conjunto de $L \subseteq A$ denota el conjunto de puntos fijos de $g \circ f$: el conjunto de lpor suerte los hombres que son liked de la espalda. Hemos calculado, en la pregunta anterior, la probabilidad de que $A_k \subseteq L$, para cualquier subconjunto $A_k$ $A$ tiene un tamaño $k$. Por lo tanto, por la inclusión-exclusión en el principio,
$$\begin{align}
\Pr(L = \emptyset)
&= \Pr(\emptyset \subseteq L) - \binom{m}{1}\Pr(A_1 \subseteq L) + \binom{m}{2}\Pr(A_2 \subseteq L) - \binom{m}{3}\Pr(A_3 \subseteq L) + \dots \\
&= \sum_{k=0}^m (-1)^k \binom{m}{k}\binom{w}{k} k! m^{-k}w^{-k}
\end{align}$$
El uso de la caída de la notación factorial, el anterior también se puede escribir como
$$P_{m, w, 0} = \sum_{k=0}^{\infty} \frac{m^{\underline k}}{m^k} \frac{w^{\underline k}}{w^k} \frac{(-1)^k}{k!}$$
I changed the upper limit of the sum to $\infty$ instead of $m$, to highlight that the expression is symmetric in $m$ and $w$: note that when $k > m$ we have $m^{\underline k} = 0$, and when $k > w$ we have $w^{\underline k} = 0$, so the terms in the sum are nonzero only up to $k = \min(m, w)$.
For the particular case when $m = w = n$, the number of pairs of functions $(f, g)$ such that $g \circ f$ no tiene puntos fijos es
$$\begin{align}
T_n
&= n^{2n} P_{n,n,0} \\
&= n^{2n} \sum_{k=0}^n (-1)^k \binom{n}{k}^2 k! n^{-2k} \\
&= n^{2n} \sum_{k=0}^n \left(\frac{n^{\underline k}}{n^k}\right)^2 \frac{(-1)^k}{k!}
\end{align}$$
This number $T_n$, for $n = 0, 1, 2, \dots$, toma los valores
$$1, 0, 2, 156, 16920, 2764880, 650696400, 210105425628, 89425255439744, 48588905856409920, 32845298636854828800, 27047610425293718239100, 26664178085975252011318272, 31009985808408471580603417296, 42017027730087624384021945067520, 65618911142809749231767185516069500, \dots$$
y es sorprendentemente no en OEIS, ni son las probabilidades correspondientes a $P_{n,n,0} = \dfrac{T_n}{n^{2n}}$ cuales son
$$1, 0, \frac18, \frac{52}{243}, \frac{2215}{8192}, \frac{552976}{1953125}, \dots$$
$$\approx 1, 0, 0.125, 0.214, 0.258, 0.283, 0.299, 0.310, 0.318, 0.324, 0.328, 0.332, 0.335, 0.338, 0.340, 0.342, \dots$$
However, we will prove below that $P_{n, n, 0}$ approaches $\dfrac{1}{e} \approx 0.367879\dots$ as $n \to \infty$. Note that even before the proof, we can find this plausible, for two reasons:
- when the factor $\frac{n^{\underline k}}{n^k}$ (squared) which is close to $1$ is removed, the sum $\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ does indeed converge to $e^{-1}$ as $n \to \infty$ (esta será la forma en que nos demostrarlo), y
- cada una de las $a \in A$ es no un punto fijo con una probabilidad de $1 - \frac1n$, por lo que la independencia de la aproximación (el tratamiento de estos eventos independientes, aunque ellos no lo son) da la probabilidad de que no hay puntos fijos a ser $\left(1 - \frac1n \right)^n \to e^{-1}$, y tal vez esta independencia aproximación se obtiene mejor para un gran $n$.
Extender la anterior también podemos respuesta
- "¿Cuál es la probabilidad de que exactamente $k$ de los hombres son del agrado de vuelta?"
Su expresión para el número de pares de funciones (en el que las bisagras de llamar a la anterior problema de una reducción) se $\displaystyle \binom{n}{k}^2 k! T_{n-k}$, significó para contar el número de funciones de $(f, g)$ tal que $k$ pares son mutuamente gusto y no hay puntos fijos en los restantes $n-k$ de los hombres y las mujeres. Pero esto no es correcto, como (por ejemplo) de la función en el resto de las $m-k$ elementos de $A$ no está obligado a tomar en los valores del resto de las $w-k$ elementos de $B$ solo (también puede tomar los valores de la misma $k$ elementos ya seleccionado).
La expresión de la derecha está dada por la inclusión-exclusión principio: dado un conjunto particular $A_k$ $k$ de los hombres, la probabilidad de que estos son precisamente los hombres les gustaba la espalda es
$$\begin{align}
\Pr(L = A_k)
&= \Pr(A_k \subseteq L) - \binom{m-k}{1}\Pr(A_{k+1} \subseteq L) + \binom{m-k}{2}\Pr(A_{k+2} \subseteq L) - \dots \\
&= \sum_{r=0}^{m-k} (-1)^r \binom{m-k}{r} \binom{w}{k+r}\frac{(k+r)!}{m^{k+r}w^{k+r}} \\
&= \sum_{l=k}^m (-1)^{l-k} \binom{m-k}{l-k} \binom{w}{l} \frac{l!}{m^l w^l}
\end{align}$$
and the probability got by choosing all sets of size $k$ is $\displaystyle \binom{m}{k}$ times that:
$$\begin{align}
P_{m, w, k}
&= \sum_{l=k}^m (-1)^{l-k} \binom{m}{k} \binom{m-k}{l-k} \binom{w}{l}\frac{l!}{m^l w^l} \\
&= \sum_{l=k}^m (-1)^{l-k} \binom{l}{k} \binom{m}{l} \binom{w}{l} \frac{l!}{m^l w^l} \\
&= \frac{1}{k!} \sum_{l=k}^m \frac{m^{\underline l}}{m^l} \frac{w^{\underline l}}{w^l} \frac{(-1)^{l-k}}{(l-k)!} \\
&= \frac{1}{k!} \sum_{r=0}^{\infty} \frac{m^{\underline {k+r}}}{m^{k+r}} \frac{w^{\underline {k+r}}}{w^{k+r}} \frac{(-1)^r}{r!}
\end{align}$$
(otra vez hemos cambiado el límite superior de la suma, con ningún cambio en el valor).
Tenga en cuenta que cuando se $k=0$, podemos recuperar nuestra anterior expresión para $P_{m, w, 0}$. Vamos a demostrar a continuación que $P_{m, w, k} \to \frac{1}{k!e}$$m, w \to \infty$.
- "¿Cuál es el número esperado de hombres que son del agrado de vuelta?"
Ya hemos respondido a esto anterior ( $1$ ), pero con la anterior, es también igual a la
$$\begin{align}
\sum_{k=0}^m k P_{m, w, k}
&= \sum_{k=0}^m k \sum_{r=k}^{m} (-1)^{r-k} \binom{r}{k} \binom{m}{r} \binom{w}{r}\frac{r!}{m^rw^r} \\
&= \sum_{r=0}^m \binom{m}{r}\binom{w}{r}\frac{r!}{m^rw^r} (-1)^r \sum_{k=0}^r k\binom{r}{k} (-1)^{k}
\\ &= 1
\end{align}$$
(como el interior de la suma es distinto de cero sólo para $r=0$), como se esperaba.
Finalmente, el prometido de la prueba acerca de la $P_{m, w, k}$. Supongamos que $m$ $w$ tanto para ir hasta el infinito, en cualquier forma que - las velocidades relativas no importa. Podemos imaginar dada por una secuencia $(m_i, w_i)$, con la única propiedad que se necesita que el$m_i \to \infty$$w_i \to \infty$$i \to \infty$.
A continuación, para cada fijos $k$$r$, $\displaystyle \frac{m_i^{\underline {k+r}}}{m_i^{k+r}} \frac{w_i^{\underline {k+r}}}{w_i^{k+r}} \to 1$ $i \to \infty$ (y además está a menos de $1$ en valor absoluto), entonces por el teorema de convergencia dominada de la serie (ver aquí , por ejemplo, de la idea a través de usuario Etienne aquí), tenemos
$$\begin{align}
\lim_{i \to \infty} P_{m_i, w_i, k}
&= \lim_{i \to \infty} \frac{1}{k!} \sum_{r=0}^{\infty} \frac{m_i^{\underline {k+r}}}{m^{k+r}} \frac{w_i^{\underline {k+r}}}{w^{k+r}} \frac{(-1)^r}{r!} \\
&= \frac{1}{k!} \sum_{r=0}^{\infty} \frac{(-1)^r}{r!} \\
&= \frac{1}{k!e}
\end{align}$$
which proves our claims about the limiting distribution.
Some data: For $0 \le n \le el 7$, below is the number $n^{2n}P_{n, n, k}$ of pairs of functions $f,g$ for $m=w=n$, such that $f \circ g$ has exactly $k$ fixed points.
0 {0: 1}
1 {0: 0, 1: 1}
2 {0: 2, 1: 12, 2: 2}
3 {0: 156, 1: 423, 2: 144, 3: 6}
4 {0: 16920, 1: 33184, 2: 13968, 3: 1440, 4: 24}
5 {0: 2764880, 1: 4581225, 2: 2088800, 3: 316200, 4: 14400, 5: 120}
6 {0: 650696400, 1: 973830816, 2: 460350000, 3: 85521600, 4: 6231600, 5: 151200, 6: 720}
7 {0: 210105425628, 1: 293840040823, 2: 141537806928, 3: 29771976150, 4: 2849330400, 5: 116794440, 6: 1693440, 7: 5040}
Next, (some of) the corresponding probabilities $P_{n, n, k}$:
1 {0: 0.000, 1: 1.00}
2 {0: 0.125, 1: 0.750, 2: 0.125}
3 {0: 0.214, 1: 0.580, 2: 0.198, 3: 0.00823}
4 {0: 0.258, 1: 0.506, 2: 0.213, 3: 0.0220, 4: 0.000366}
5 {0: 0.283, 1: 0.469, 2: 0.214, 3: 0.0324, 4: 0.00147, 5: 0.0000123}
6 {0: 0.299, 1: 0.447, 2: 0.211, 3: 0.0393, 4: 0.00286, 5: 0.0000695, 6: 3.31e-7}
7 {0: 0.310, 1: 0.433, 2: 0.209, 3: 0.0439, 4: 0.00420, 5: 0.000172, 6: 2.50e-6, 7: 7.43e-9}
8 {0: 0.318, 1: 0.423, 2: 0.206, 3: 0.0471, 4: 0.00538, 5: 0.000303, 6: 7.70e-6, 7: 7.22e-8, 8: 1.43e-10}
9 {0: 0.324, 1: 0.416, 2: 0.204, 3: 0.0494, 4: 0.00638, 5: 0.000444, 6: 0.0000160, 7: 2.72e-7, 8: 1.74e-9, 9: 2.42e-12}
10 {0: 0.328, 1: 0.410, 2: 0.202, 3: 0.0511, 4: 0.00723, 5: 0.000586, 6: 0.0000269, 7: 6.62e-7, 8: 7.84e-9, 9: 3.59e-11}
100 {0: 0.364, 1: 0.372, 2: 0.186, 3: 0.0607, 4: 0.0146, 5: 0.00273, 6: 0.000419, 7: 0.0000539, 8: 5.94e-6, 9: 5.69e-7, ...}
1000 {0: 0.368, 1: 0.368, 2: 0.184, 3: 0.0613, 4: 0.0153, 5: 0.00303, 6: 0.000501, 7: 0.0000709, 8: 8.76e-6, 9: 9.59e-7, ...}
and for $n = 10000$:
10000 {0: 0.36784, 1: 0.36792, 2: 0.18396, 3: 0.061307, 4: 0.015321, 5: 0.0030623, 6: 0.00050997, 7: 0.000072781, 8: 9.0867e-6, 9: 1.0082e-6, ...}
Contrast this with the actual Poisson distribution $\frac{1}{k!e}$:
{0: 0.36788, 1: 0.36788, 2: 0.18394, 3: 0.061313, 4: 0.015328, 5: 0.0030657, 6: 0.00051094, 7: 0.000072992, 8: 9.1240e-6, 9: 1.0138e-6, ...}
Así que podemos ver que la convergencia es más lenta.
