Gaussianos » The matching problem o cómo no formar ninguna pareja

The matching problem o cómo no formar ninguna pareja

Imaginemos que nos encontramos alguna de esta situaciones y nos planteamos la pregunta que viene en cada una de ellas:

Un profesor manda un trabajo para casa a un grupo de alumnos. Ellos entregan los mismos al profesor y cuando éste los va a devolver corregidos lo hace aleatoriamente. ¿Cuál es la probabilidad de que ninguno de los alumnos reciba su propio trabajo?
En una fiesta hay un cierto número de hombres ataviados con sombrero. Dejan los mismos en una sala y al término de la celebración cogen su sombrero de forma aleatoria. ¿Cuál es la probabilidad de que ninguno de los hombres lleve su propio sombrero?
Vamos a enviar felicitaciones de Navidad a nuestros familiares. Rellenamos las tarjetas por un lado y los sobres por otro y luego metemos las tarjetas en los sobres aleatoriamente. ¿Cuál es lo probabilidad de que ninguna de las tarjetas acabe en el sobre que le corresponde?

Todos estos ejemplos son casos en los que podemos aplicar el, al parecer, llamado The Matching Problem, aunque también he visto que lo llaman Montmort’s matching problem en honor a Pierre Raymond de Montmort, matemático francés nacido en 1678.

Bueno, vamos al tema. Para empezar, creo que se ve bastante claro que todos los casos son equivalentes. Entonces, ¿cuál diríais que es la probabilidad que se nos pide? Lo primero que uno podría pensar es: depende del número de alumnos, hombres y familiares que haya en cada caso. Es decir, que lo normal sería pensar que esa probabilidad depende del número de individuos que tenga la población. Pues no es así. La probabilidad es siempre la misma. Bueno, no exactamente. En realidad la probabilidad se acerca a un número concreto conforme el número de individuos se acerca a infinito. Curioso, ¿no?

Y ahora la pregunta es: ¿cuál es esa probabilidad? Pues bueno, teniendo en cuenta que si llamamos $N_n$ a la variable aleatoria que nos indica el número de emparejamientos válidos de entre $n$ se puede llegar a que su función de probabilidad es la siguiente:

$\displaystyle{P(N_n=k)=\cfrac{1}{k!} \cdot \sum_{j=0}^{n-k} \cfrac{(-1)^j}{j!}}$ con $k=0,1, \ldots ,n$

la probabilidad de que no se haya formado ninguna pareja válida nos la da la probabilidad de que $N_n$ sea igual a ${0}$ . Es decir:

$\displaystyle{P(N_n=0)=\sum_{j=0}^{n} \cfrac{(-1)^j}{j!}}$

¿Os suena esta suma? Seguro que a muchos sí. Hacemos límite cuando $n \to \infty$ y obtenemos lo que queremos:

$\displaystyle{P(N_n=0)=\sum_{j=0}^{n} \cfrac{(-1)^j}{j!} \xrightarrow{n \to \infty} \cfrac{1}{e}}$

Es decir, que la probabilidad de que no se forme ninguna pareja válida se acerca a $\cfrac{1}{e}$ tanto más como grande sea $n$ . Al parecer con $n=5$ ya nos queda una buena aproximación. Lo sorprendente es que cuanto más grande sea $n$ mejor es la aproximación a $\cfrac{1}{e}$ . Y digo yo: ¿cuánto vale ese número? Pues algo así como $0.367879441$ . Es decir, que en una situación de este tipo no se forma ninguna pareja válida aproximadamente el $36,8$ % de las veces. Y ese tanto por ciento se va acercando cada vez más a $\cfrac{1}{e} \cdot 100$ conforme aumenta el valor de $n$ .

Realmente curioso el asunto. ¿Esperabais que la probabilidad fuera más alta o más baja?

Fuentes:

Matching Problem en Math Fun Facts
The Matching Problem en Università di Firenze
The Matching Problem en The University of Alabama in Huntsville

Escrito por ^DiAmOnD^, 30 de Octubre de 2007 en Curiosidades, Estadística, Otras constantes

8 comentarios

Trackback para este post

b3co - 30 de Octubre de 2007 9:34

Estos problemas tan normales que llevan a un número importante de resultado me encantan, este es casi tan bueno como la aguja de buffon, jeje.

Saludos.
Irene - 30 de Octubre de 2007 11:06

Pues yo estoy sorprendida de que sea tan alta.

El nombre del problema Matching me ha llevado a pensar en las agencias que te buscan pareja. Si cada persona tiene un “alma gemela” y nos “repartimos” al azar, hay un 36.8% de que TODO el mundo acabe con la “pareja equivocada”!!
La leche!, TODO EL MUNDO es mucha gente!!

Please, que alguien me corrija si no he comprendido bien el problema (habrá sido el amor… :D)
Domingo H.A. - 30 de Octubre de 2007 11:06

Sí señor, precioso problema y preciosa solución
Álvaro - 30 de Octubre de 2007 12:40

Algo razono yo mal, a ver qué es:

La posibilidad de repartir mal el primer examen en un grupo de n alumnos es

$\frac{n-1}{n}$

o sea, todos los exámenes posibles (menos el bueno) dividido por el total de alumnos. Para el siguiente alumno tenemos un elemento menos en cada población, de modo que la probabilidad total es

$P(N_n = 0) = \frac{(n-1)!}{n!} = 1/n$

La probabilidad cuando son 2 alumnos es de 0.5 (dar mal el primero y el último ya está colocado) y se va haciendo menor según va creciendo la población (lo cual pensado dejando las matemáticas aparte tiene su lógica).
Depe - 31 de Octubre de 2007 1:37

Álvaro, si el primero no coge su sombrero es porque coge el de otro. Y por lo tanto, ese otro tendrá una probabilidad 1 de no coger su sombrero.
discipulodegauss - 2 de Noviembre de 2007 19:42

YO esperaba que fuera menos ……….muy interesante ,saludos.
Tiempo finito y logarítmico » 1/e - 9 de Noviembre de 2007 4:12

[...] Si cada persona tiene un “alma gemela” y nos “repartimos” al azar, hay un 36.8% de que TODO el mundo acabe con la “pareja equivocada”!! — Irene@Gaussianos [...]
Tiempo finito y logarítmico » Es la misma probabilidad - 20 de Noviembre de 2007 7:30

[...] Suena familiar: es exactamente la misma probabilidad de formar un desordenamiento en n elementos cuanto n tiende a infinito. ¿Coincidencia? ¿O habrá alguna relación? Quién sabe. Un profesor de probabilidad prometió revisar el asunto, aunque es un problema dificil y probablemente no tenga tiempo. Publicaré si me entero de algo. [...]