Saltar al contenido principal
LibreTexts Español

12.5: El problema del emparejamiento

  • Page ID
    151910
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\bs}{\boldsymbol}\)\(\newcommand{\var}{\text{var}}\)\(\newcommand{\cov}{\text{cov}}\)\(\newcommand{\cor}{\text{cor}}\)

    Definiciones y Notación

    El experimento de emparejamiento

    El experimento de emparejamiento es un experimento aleatorio que puede formularse de varias formas coloridas:

    • Supongamos que las parejas\(n\) macho-hembra están en una fiesta y que los machos y hembras se emparejan aleatoriamente para un baile. Un partido ocurre si una pareja pasa a estar emparejada.
    • Un secretario ausente prepara\(n\) cartas y sobres para enviar a\(n\) diferentes personas, pero luego mete las cartas al azar en los sobres. Se produce una coincidencia si se inserta una letra en el sobre adecuado.
    • \(n\)la gente con sombreros ha bebido demasiado en una fiesta. Al salir de la fiesta, cada persona agarra al azar un sombrero. Un partido ocurre si una persona obtiene su propio sombrero.

    Estos experimentos son claramente equivalentes desde el punto de vista matemático, y corresponden a seleccionar una permutación aleatoria\(\bs{X} = (X_1, X_2, \ldots, X_n)\) de la población\(D_n = \{1, 2, \ldots, n\}\). Aquí están las interpretaciones para los ejemplos anteriores:

    • Número de las parejas de 1 a\(n\). Entonces\(X_i\) es el número de la mujer emparejada con el\(i\) th hombre.
    • Numere las letras y los sobres correspondientes del 1 al\(n\). Entonces\(X_i\) es el número del sobre que contiene la letra\(i\) th.
    • Numere las personas y sus sombreros correspondientes del 1 al\(n\). Entonces\(X_i\) es el número del sombrero elegido por la persona\(i\) th.

    Nuestra suposición de modelado, por supuesto,\(\bs{X}\) es que se distribuye uniformemente en el espacio muestral de permutaciones de\(D_n\). El número de objetos\(n\) es el parámetro básico del experimento. También consideraremos el caso del muestreo con reemplazo de la población\(D_n\), ya que el análisis es mucho más fácil pero aún proporciona una visión. En este caso,\(\bs{X}\) es una secuencia de variables aleatorias independientes, cada una distribuida uniformemente sobre\(D_n\).

    Partidos

    Diremos que ocurre un partido en la posición\(j\) si\(X_j = j\). Así, número de coincidencias es la variable aleatoria\(N\) definida matemáticamente por\[ N_n = \sum_{j=1}^n I_j\] donde\(I_j = \bs{1}(X_j = j)\) está la variable indicadora para el evento de coincidencia en la posición\(j\). Nuestro problema es calcular la distribución de probabilidad del número de coincidencias. Se trata de un problema viejo y famoso en probabilidad que primero fue considerado por Pierre-Remond Montmort; a veces se refería como el problema de emparejamiento de Montmort en su honor.

    Muestreo con reemplazo

    Primero resolvamos el problema de coincidencia en el caso fácil, cuando el muestreo es con reemplazo. Por supuesto, esta no es la forma en que se suele jugar el juego de correspondencias, sino que el análisis nos dará alguna idea.

    \((I_1, I_2, \ldots, I_n)\)es una secuencia de ensayos de\(n\) Bernoulli, con probabilidad de éxito\(\frac{1}{n}\).

    Prueba

    Las variables son independientes ya que el muestreo es con reemplazo. Dado que\(X_j\) se distribuye uniformemente,\(\P(I_j = 1) = \P(X_j = j) = \frac{1}{n}\).

    El número de coincidencias\(N_n\) tiene la distribución binomial con parámetro de ensayo\(n\) y parámetro de éxito\(\frac{1}{n}\). \[ \P(N_n = k) = \binom{n}{k} \left(\frac{1}{n}\right)^k \left(1 - \frac{1}{n}\right)^{n-k}, \quad k \in \{0, 1, \ldots, n\} \]

    Prueba

    Esto se deduce inmediatamente del resultado anterior en los juicios de Bernoulli.

    La media y varianza del número de coincidencias son

    1. \(\E(N_n) = 1\)
    2. \(\var(N_n) = \frac{n-1}{n}\)
    Prueba

    Estos resultados se derivan del resultado anterior sobre la distribución binomial de\( N_n \). Recordemos que la distribución binomial con parámetros\(n\) y\(p\) tiene media\(n p\) y varianza\(n p (1 - p)\).

    La distribución del número de coincidencias converge a la distribución de Poisson con el parámetro 1 como\(n \to \infty\):\[ \P(N_n = k) \to \frac{e^{-1}}{k!} \text{ as } n \to \infty \text{ for } k \in \N \]

    Prueba

    Este es un caso especial de la convergencia de la distribución binomial al Poisson. Para una prueba directa, tenga en cuenta que\[ \P(N_n = k) = \frac{1}{k!} \frac{n^{(k)}}{n^k} \left(1 - \frac{1}{n}\right)^{n-k} \] Pero\(\frac{n^{(k)}}{n^k} \to 1\)\(\left(1 - \frac{1}{n}\right)^{n-k} \to e^{-1}\) como\(n \to \infty\) y como\(n \to \infty\) por un famoso límite del cálculo.

    Muestreo sin reemplazo

    Ahora consideremos el caso de interés real, cuando el muestreo es sin reemplazo, por lo que\(\bs{X}\) es una permutación aleatoria de los elementos de\(D_n = \{1, 2, \ldots, n\}\).

    Contar permutaciones con partidos

    Para encontrar la función de densidad de probabilidad de\(N_n\), necesitamos contar el número de permutaciones de\(D_n\) con un número especificado de coincidencias. Esto resultará fácil una vez que hayamos contado el número de permutaciones sin coincidencias; estas se llaman desórdenes de\(D_n\). Denotaremos el número de permutaciones de\(D_n\) con exactamente\(k\) coincidencias por\(b_n(k) = \#\{N_n = k\}\) for\(k \in \{0, 1, \ldots, n\}\). En particular,\(b_n(0)\) es el número de derrangements de\(D_n\).

    El número de derrangements es\[ b_n(0) = n! \sum_{j=0}^n \frac{(-1)^j}{j!} \]

    Prueba

    Por la regla del complemento para la medida de conteo\(b_n(0) = n! - \#(\bigcup_{i=1}^n \{X_i = i\})\). De la fórmula inclusión-exclusión,\[ b_n(0) = n! - \sum_{j=1}^n (-1)^{j-1} \sum_{J \subseteq D_n, \; \#(J) = j} \#\{X_i = i \text{ for all } i \in J\} \] Pero si\(J \subseteq D_n\) con\(\#(J) = j\) entonces\(\#\{X_i = i \text{ for all } i \in J\} = (n - j)!\). Por último, el número de subconjuntos\(J\) de\(D_n\) con\(\#(J) = j\) es\(\binom{n}{j}\). Sustituir en la ecuación mostrada y simplificar da el resultado.

    El número de permutaciones con\(k\) coincidencias exactamente es\[ b_n(k) = \frac{n!}{k!} \sum_{j=0}^{n-k} \frac{(-1)^j}{j!}, \quad k \in \{0, 1, \ldots, n\} \]

    Prueba

    El siguiente es un procedimiento de dos pasos que genera todas las permutaciones con\(k\) coincidencias exactamente: Primero seleccione\(k\) los enteros que coincidirán. El número de formas de realizar este paso es\(\binom{n}{k}\). En segundo lugar, seleccione una permutación de\(n - k\) los números enteros restantes sin coincidencias. El número de formas de realizar este paso es\(b_{n-k}(0)\). Por el principio de multiplicación de la combinatoria se deduce que\(b_n(k) = \binom{n}{k} b_{n-k}(0)\). Usar el resultado anterior para derrangements y simplificar da los resultados.

    La función de densidad de probabilidad

    La función de densidad de probabilidad del número de coincidencias es\[ \P(N_n = k) = \frac{1}{k!} \sum_{j=0}^{n-k} \frac{(-1)^j}{j!}, \quad k \in \{0, 1, \ldots, n\} \]

    Prueba

    Esto se desprende directamente del resultado anterior sobre permutaciones con coincidencias, ya que\(\P(N_n = k) = \#\{N_n = k\} \big/ n!\).

    En el experimento de emparejamiento, varíe el parámetro\(n\) y anote la forma y ubicación de la función de densidad de probabilidad. Para valores seleccionados de\(n\), ejecute la simulación 1000 veces y compare la función de densidad empírica con la función de densidad de probabilidad verdadera.

    \(\P(N_n = n - 1) = 0\).

    Prueba

    Una prueba probabilística simple es señalar que el evento es imposible, si hay\(n - 1\) coincidencias, entonces debe haber\(n\) coincidencias. También se puede construir una prueba algebraica a partir de la función de densidad de probabilidad\( N_n \) anterior.

    La distribución del número de coincidencias converge a la distribución de Poisson con el parámetro 1 como\(n \to \infty\):\[ \P(N_n = k) \to \frac{e^{-1}}{k!} \text{ as } n \to \infty, \quad k \in \N \]

    Prueba

    De la serie de potencia para la función exponencial,\[ \sum_{j=0}^{n-k} \frac{(-1)^j}{j!} \to \sum_{j=0}^\infty \frac{(-1)^j}{j!} = e^{-1} \text{ as } n \to \infty \] Así el resultado se desprende de la función de densidad de probabilidad de\( N_n \) arriba.

    La convergencia es notablemente rápida.

    En el experimento de emparejamiento, aumente\(n\) y observe cómo la función de densidad de probabilidad se estabiliza rápidamente. Para valores seleccionados de\(n\), ejecute la simulación 1000 veces y compare la función de frecuencia relativa con la función de densidad de probabilidad.

    Momentos

    La media y varianza del número de coincidencias podrían calcularse directamente a partir de la distribución. Sin embargo, es mucho mejor usar la representación en términos de variables indicadoras. La propiedad intercambiable es una herramienta importante en esta sección.

    \(\E(I_j) = \frac{1}{n}\)para\(j \in \{1, 2, \ldots, n\}\).

    Prueba

    \(X_j\)se distribuye uniformemente\(D_n\) para cada uno\(j\) de ellos\(\P(I_j = 1) = \P(X_j = x) = \frac{1}{n}\).

    \(\E(N_n) = 1\)para cada\(n\)

    Prueba

    Esto se desprende del resultado anterior y las propiedades básicas de valor esperado.

    Así, el número esperado de coincidencias es 1, independientemente de\(n\), así como cuando el muestreo es con reemplazo.

    \(\var(I_j) = \frac{n-1}{n^2}\)para\(j \in \{1, 2, \ldots, n\}\).

    Prueba

    Esto se desprende de\(\P(I_j = 1) = \frac{1}{n}\).

    Un partido en una posición parecería hacer más probable que hubiera un partido en otra posición. Así, podríamos adivinar que las variables indicadoras están correlacionadas positivamente.

    Para distintos\(j, \, k \in \{1, 2, \ldots, n\}\),

    1. \(\cov(I_j, I_k) = \frac{1}{n^2 (n - 1)}\)
    2. \(\cor(I_j, I_k) = \frac{1}{(n - 1)^2}\)
    Prueba

    Tenga en cuenta que\(I_j I_k\) es la variable indicadora del evento de un partido en posición\(j\) y un partido en posición\(k\). De ahí por la propiedad intercambiable\(\P(I_j I_k = 1) = \P(I_j = 1) \P(I_k = 1 \mid I_j = 1) = \frac{1}{n} \frac{1}{n-1}\). Como antes,\(\P(I_j = 1) = \P(I_k = 1) = \frac{1}{n}\). Los resultados se derivan ahora de fórmulas computacionales estándar para covarianza y correlación.

    Tenga en cuenta que cuando\(n = 2\), el evento de que hay un partido en la posición 1 está perfectamente correlacionado con el evento de que hay un partido en la posición 2. Esto tiene sentido, ya que habrá 0 coincidencias o 2 coincidencias.

    \(\var(N_n) = 1\)para cada\(n \in \{2, 3, \ldots\}\).

    Prueba

    Esto se desprende de los dos resultados anteriores sobre la varianza y la covarianza de las variables indicadoras, y las propiedades básicas de la covarianza. Recordemos eso\(\var(N_n) = \sum_{j=1}^n \sum_{k=1}^n \cov(I_j, I_k)\).

    En el experimento de emparejamiento, varíe el parámetro\(n\) y anote la forma y ubicación de la barra de desviación\( \pm \) estándar media. Para los valores seleccionados del parámetro, ejecute la simulación 1000 veces y compare la media de la muestra y la desviación estándar con la media de distribución y la desviación estándar.

    Para distintos\(j, \, k \in \{1, 2, \ldots, n\}\),\(\cov(I_j, I_k) \to 0\) como\(n \to \infty\).

    Por lo tanto, el evento de que se produzca un partido en posición\(j\) es casi independiente del evento de que se produzca un partido en posición\(k\) si\(n\) es grande. Para grandes\(n\), las variables indicadoras se comportan casi como los ensayos de\(n\) Bernoulli con probabilidad de éxito\(\frac{1}{n}\), que por supuesto, es lo que sucede cuando el muestreo es con reemplazo.

    Una relación de recursión

    En esta subsección, daremos una derivación alternativa de la distribución del número de coincidencias, en cierto sentido incorporando el experimento con parámetro\(n\) en el experimento con parámetro\(n + 1\).

    La función de densidad de probabilidad del número de coincidencias satisface la siguiente relación de recursión y condición inicial:

    1. \(\P(N_n = k) = (k + 1) \P(N_{n+1} = k + 1)\)para\(k \in \{0, 1, \ldots, n\}\).
    2. \(\P(N_1 = 1) = 1\).
    Prueba

    Primero, considere la permutación aleatoria\((X_1, X_2, \ldots, X_n, X_{n+1})\) de\(D_{n+1}\). Tenga en cuenta que\((X_1, X_2, \ldots, X_n)\) es una permutación aleatoria de\(D_n\) si y solo\(X_{n+1} = n + 1\) si y solo si\(I_{n+1} = 1\). De ello se deduce que\[ \P(N_n = k) = \P(N_{n+1} = k + 1 \mid I_{n+1} = 1), \quad k \in \{0, 1, \ldots, n\} \] De la defnición del argumento de probabilidad condicional tenemos\[ \P(N_n = k) = \P(N_{n+1} = k + 1) \frac{\P(I_{n+1} = 1 \mid N_{n+1} = k + 1)}{\P(I_{n+1} = 1)}, \quad k \in \{0, 1, \ldots, n\} \] Pero\(\P(I_{n+1} = 1) = \frac{1}{n+1}\) y\(\P(I_{n+1} = 1 \mid N_{n+1} = k + 1) = \frac{k+1}{n+1}\). Sustituir en la última ecuación mostrada da la relación de recurrencia. La condición inicial es obvia, ya que si\(n = 1\) debemos tener un partido.

    Este resultado se puede utilizar para obtener la función de densidad de probabilidad de\(N_n\) recursivamente para cualquier\(n\).

    La función de generación de probabilidad

    A continuación, recuerde que la función de generación de probabilidad de\(N_n\) viene dada por\[ G_n(t) = \E\left(t^{N_n}\right) = \sum_{j=0}^n \P(N_n = j) t^j, \quad t \in \R \]

    La familia de funciones generadoras de probabilidad satisface las siguientes ecuaciones diferenciales y condiciones auxiliares:

    1. \(G_{n+1}^\prime(t) = G_n(t)\)para\( t \in \R\) y\( n \in \N_+ \)
    2. \(G_n(1) = 1\)para\( n \in \N_+\)

    Tenga en cuenta también que\(G_1(t) = t\) para\(t \in \R\). Así, el sistema de ecuaciones diferenciales puede ser utilizado para computar\(G_n\) para cualquier\(n \in \N_+\).

    En particular, para\(t \in \R\),

    1. \(G_2(t) = \frac{1}{2} + \frac{1}{2} t^2\)
    2. \(G_3(t) = \frac{1}{3} + \frac{1}{2} t + \frac{1}{6} t^3\)
    3. \(G_4(t) = \frac{3}{8} + \frac{1}{3} t + \frac{1}{4} t^2 + \frac{1}{24} t^4\)

    Para\(k, \; n \in \N_+\) con\(k \lt n\),\[ G_n^{(k)}(t) = G_{n-k}(t), \quad t \in \R \]

    Prueba

    Esto se desprende de la ecuación diferencial para el PGF dada anteriormente.

    Para\(n \in \N_+\),\[ \P(N_n = k) = \frac{1}{k!} \P(N_{n-k} = 0), \quad k \in \{0, 1, \ldots, n - 1\} \]

    Prueba

    Esto se desprende del resultado anterior y las propiedades básicas de generación de funciones.

    Ejemplos y Aplicaciones

    Un secretario mete al azar 5 letras en 5 sobres. Encuentra cada uno de los siguientes:

    1. El número de resultados con exactamente\(k\) coincidencias, para cada uno\(k \in \{0, 1, 2, 3, 4, 5\}\).
    2. La función de densidad de probabilidad del número de coincidencias.
    3. La covarianza y correlación de una coincidencia en una envolvente y una coincidencia en otra envolvente.
    Contestar
    1. \(k\) 0 1 2 3 4 5
      \(b_5(k)\) 44 45 20 10 0 1
    2. \(k\) 0 1 2 3 4 5
      \(\P(N_5 = k)\) 0.3667 0.3750 0.1667 0.0833 0 0.0083
    3. Covarianza:\(\frac{1}{100}\), correlación\(\frac{1}{16}\)

    Diez parejas casadas son emparejadas al azar para un baile. Encuentra cada uno de los siguientes:

    1. La función de densidad de probabilidad del número de coincidencias.
    2. La media y varianza del número de coincidencias.
    3. La probabilidad de al menos 3 coincidencias.
    Responder
    1. \(k\) \(\P(N_{10} = k)\)
      0 \( \frac{16\,481}{44\,800} \approx 0.3678795\)
      1 \(\frac{16\,687}{45\,360} \approx 0.3678792\)
      2 \(\frac{2119}{11\,520} \approx 0.1839410\)
      3 \(\frac{103}{1680} \approx 0.06130952\)
      4 \( \frac{53}{3456} \approx 0.01533565 \)
      5 \( \frac{11}{3600} \approx 0.003055556 \)
      6 \( \frac{1}{1920} \approx 0.0005208333 \)
      7 \( \frac{1}{15\,120} \approx 0.00006613757\)
      8 \(\frac{1}{80\,640} \approx 0.00001240079\)
      9 0
      10 \(\frac{1}{3\,628\,800} \approx 2.755732 \times 10^{-7}\)
    2. \(\E(N_{10}) = 1\),\(\var(N_{10}) = 1\)
    3. \(\P(N_{10} \ge 3) = \frac{145\,697}{1\,814\,400} \approx 0.08030037\)

    En el experimento de emparejamiento, set\(n = 10\). Ejecuta el experimento 1000 veces y compara lo siguiente para el número de coincidencias:

    1. Las verdaderas probabilidades
    2. Las frecuencias relativas de la simulación
    3. Las probabilidades limitantes de Poisson
    Responder
    1. Ver parte (a) del problema anterior.
    2. \(k\) \(e^{-1} \frac{1}{k!}\)
      0 0.3678794
      1 0.3678794
      2 0.1839397
      3 0.06131324
      4 0.01532831
      5 0.003065662
      6 0.0005109437
      7 0.00007299195
      8 \(9.123994 \times 10^{-6}\)
      9 \( 1.013777 \times 10^{-6} \)
      10 \( 1.013777 \times 10^{-7} \)

    This page titled 12.5: El problema del emparejamiento is shared under a CC BY 2.0 license and was authored, remixed, and/or curated by Kyle Siegrist (Random Services) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.