La coincidencia de Sombreros Y Abrigos Problema

Question

Supongamos $N$ hombres lanzan sus sombreros en una habitación Y sus abrigos en otro cuarto. Cada hombre, a continuación, elige aleatoriamente un sombrero y un abrigo. ¿Cuál es la probabilidad de que:

• Ninguno de los hombres de seleccionar su propio sombrero y su abrigo
• Exactamente $k$ de los hombres de seleccionar su propio sombrero y su abrigo.

Más generalmente, si en lugar de $2$ elementos (el sombrero y el abrigo), el $N$ hombres arrojaron $n$ artículos, cómo encontrar la función de masa de probabilidad $P(k=0,1,2,\ldots,n)$ el número de completar coincidencias ($k$ hombres seleccione su $n$ propios elementos)?

Answer 1

Usted puede obtener la probabilidad de una manera similar a la de los habituales de la derivación de la alteración de las probabilidades (probabilidad de que ninguno de los $N$ a los hombres tener su propio sombrero de la espalda).

Hay un total de $N!^n$ maneras en que todos los elementos pueden ser distribuidas entre las $N$ hombres, de modo que cada uno tiene exactamente uno de cada tipo de elemento. Deje $A_i$ denotar el caso de que el $i$th hombre obtiene el $n$ elementos que pertenecen a él. El número de maneras en que esto puede suceder es $|A_i| = (N-1)!^n$, ya que esto implica la distribución de todos los elementos, pero los que pertenecen a la $i$th hombre entre los otros $N-1$ hombres. Del mismo modo, $|A_i \cap A_j| = (N-2)!^n$, y, en general, $|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j}| = (N-j)!^n$. También hay $\binom{N}{j}$ formas de elegir que $j$ hombres recibirán sus propios $n$ artículos.

Deje $D(N,n,k)$ denotar el número de maneras en que exactamente $k$ de la $N$ hombres reciben todos los $n$ de sus artículos de nuevo. Por el principio de inclusión/exclusión, $$D(N,n,0) = \sum_{j=0}^N (-1)^j \binom{N}{j} (N-j)!^n = N! \sum_{j=0}^N (-1)^j \frac{(N-j)!^{n-1}}{j!}.$$

Ahora, $D(N,n,k) = \binom{N}{k} D(N-k,n,0)$, ya que este es el número de maneras de elegir a $k$ de la $N$ a los hombres a recibir la totalidad de sus elementos veces el número de maneras en que ninguno de los restantes $N-k$ de los hombres reciben la totalidad de sus artículos de nuevo. Por lo tanto $$D(N,n,k) = \binom{N}{k} (N-k)! \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!} = \frac{N!}{k!} \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!}.$$

Dividiendo por $N!^n$, tenemos que la probabilidad de que exactamente $k$ de la $N$ hombres reciben todos los $n$ de sus artículos de nuevo es $$\frac{1}{k! N!^{n-1}} \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!}.$$

Tenga en cuenta que esta fórmula está de acuerdo con los valores obtenidos por Henry para el caso $N = 4$, $n=2$.

Añadido: En efecto, la aproximación de Poisson sugerido por Henry parece coincidir con los valores exactos proporcionados por la fórmula aquí para valores pequeños de a $k$. La exactitud de la aproximación de Poisson parece deteriorarse, relativamente hablando, como $k$ aumenta. Sin embargo, la distribución de Poisson enfoque todavía da una buena absoluta aproximación al $k$ es grande, porque las probabilidades son muy pequeñas.

Answer 2

Es más fácil la espera que el número de hombres con todos sus elementos, es decir, $N^{-1}$ en el sombrero y el abrigo caso y $N^{1-n}$ en el caso más general.

Este es el muestreo sin reemplazo, pero como $N$ incrementa me sería de esperar que esto se distribuye asintóticamente como una distribución de Poisson con los mismos valores esperados.

Esta aproximación asintótica no es malo, incluso para pequeñas cantidades. Para 4 hombres y 2 elementos de la previsión del número de hombres con los elementos correctos es de 0,25. La real y probabilidades de Poisson, redondeado a cuatro decimales, se

Correct actual  Poisson
0       0.7865  0.7788
1       0.1806  0.1947
2       0.0313  0.0243
3       0.0000  0.0020
4       0.0017  0.0001
5+      0       0.00001