?Es muy dif¨ªcil (estad¨ªsticamente) no dar ni una?

El conocido como amigo invisible es un ¡°juego¡± muy popular en grupos de amigos, familiares o compa?eros de trabajos, sobre todo en ¨¦pocas como la recientemente terminada Navidad. Aunque imagino que no habr¨¢ nadie que no sepa en qu¨¦ consiste, creo que conviene recordar su funcionamiento:

Se escriben en papelitos los nombres de todos los participantes y se mezclan dichos papelitos. Despu¨¦s, cada participante escoge al azar uno de ellos y debe hacer un regalo a la persona cuyo nombre aparece en ¨¦l. Si alguien coge el papel que tiene su propio nombre, el sorteo se repite.

Hoy vamos a hablar precisamente sobre esto ¨²ltimo, sobre cu¨¢l es la probabilidad de que el sorteo no se tenga que repetir. Es decir, vamos a hablar sobre la probabilidad de que en el primer sorteo no haya nadie que coja el papelito con su propio nombre, sobre la probabilidad de que nadie ¡°acierte¡± con su nombre. Antes de seguir, quiz¨¢s sea interesante que pens¨¦is sobre cu¨¢l podr¨ªa ser dicha probabilidad. Intentadlo, haced un peque?o ejercicio mental y pensad sobre ello.

Lo primero que podr¨ªa venirnos a la mente cuando pensamos sobre este tema es que la probabilidad de que no haya ning¨²n acierto con el nombre depender¨¢ del n¨²mero de personas que participan. Eso es cierto, y m¨¢s o menos evidente, pero lo interesante de verdad es analizar qu¨¦ comportamiento podr¨ªa tener dicha probabilidad conforme aumenta el n¨²mero de personas: ?sube o baja? ?Es peque?a o grande? ?Fluct¨²a sin control o se va acercando a un cierto n¨²mero? En este ¨²ltimo caso, ?a qu¨¦ n¨²mero? Tranquilos, responderemos a todas estas preguntas.

Met¨¢monos ya en faena. Tenemos un cierto n¨²mero N de participantes, numerados desde 1 hasta N. Si numeramos tambi¨¦n los papelitos de la misma forma, un sorteo ser¨¢ v¨¢lido cuando al 1 no le toque el 1, al 2 no le toque el 2, y as¨ª con todos. Vamos, cuando ninguno coincida consigo mismo.

La situaci¨®n se puede plantear como la b¨²squeda de las permutaciones de N elementos para los cuales no hay ninguna coincidencia de posici¨®n. Es decir, las permutaciones de los n¨²meros desde 1 hasta N en las cuales ninguno cae en su propia posici¨®n. Vamos a escribir dichas permutaciones como listas de n¨²meros entre par¨¦ntesis, y analizaremos las posiciones de la lista y el n¨²mero que hay en cada posici¨®n. Por ejemplo, la permutaci¨®n (1,4,5,2,3) indica que al primero le ha tocado el 1, al segundo le ha tocado el 4, al tercero el 5, al cuarto el 2 y al quinto el 3.

Analicemos todos los casos posibles para algunos valores peque?os de N. Si participan 2 personas (s¨ª, es un poco rid¨ªculo, pero en realidad es el primer caso que tiene algo de sentido), pueden ocurrir dos cosas: que a los dos les toque su propio nombre o que a cada uno le toque el nombre del otro. Escrito como permutaciones, las ¨²nicas son (1,2) (al 1 le toca el 1 y al 2 le toca el 2) y (2,1) (al 1 le toca el 2 y al 2 le toca el 1). Como buscamos las permutaciones en las que no haya coincidencias, s¨®lo nos valdr¨ªa la segunda. Y como hay dos opciones posibles, la probabilidad de que el sorteo no se tuviera que repetir ser¨ªa de 1/2=0¡¯5.

Supongamos ahora que participan 3 personas. En este caso, tenemos 6 posibles sorteos:

Como pod¨¦is ver (recuadrados en rojo), hay dos sorteos v¨¢lidos en este caso. Como hay 6 opciones posibles, la probabilidad de que no se tenga que repetir el sorteo es de 2/6=0¡¯333...

Analicemos ahora el caso en el que hay 4 personas. Ahora tenemos 24 sorteos distintos, de los cuales hay 9 que dan una situaci¨®n en la que no tendremos que repetir la asignaci¨®n de papelitos. Aqu¨ª ten¨¦is todas las posibilidades, con los sorteos v¨¢lidos recuadrados en rojo:

Hay 24 sorteos posibles, de los cuales nos valen 9. Por tanto, la probabilidad en este caso ser¨¢ 9/24=0¡¯375.

Si participan m¨¢s personas, el n¨²mero de opciones posibles crece bastante. Para 5 personas hay 120 sorteos posibles, para 6 personas hay 720, para 7 hay 5040, para 8 ser¨ªan 40320¡­ En general, para N personas hay N! (N factorial) sorteos. Por ello, no vamos a analizar uno a uno cada caso, pero s¨ª os voy a dar los valores de las probabilidades (redondeadas a 20 decimales) para los primeros 25 valores de N:

?Os parece alta o baja? ?Cuadra con lo que pensasteis en un principio? A m¨ª siempre me ha parecido bastante baja¡­???en el 63% de los casos tendremos que repetir el sorteo!!! Por tanto, si a partir de ahora hac¨¦is el amigo invisible con 5 o m¨¢s personas y ten¨¦is que repetir, tened en cuenta que no os ha ocurrido nada raro, ni mucho menos. De hecho, es bastante probable que as¨ª ocurra.

Volvamos al n¨²mero anterior, 0¡¯367879¡­, el valor l¨ªmite de la probabilidad cuando N crece indefinidamente. Este n¨²mero, aparte de ser m¨¢s bajo de lo que uno podr¨ªa pensar, es bastante ¡°especial¡±. Pero antes de desvelar el porqu¨¦, vamos a hacer alg¨²n comentario sobre el problema que nos ocupa y sobre c¨®mo calcular las probabilidades en cada caso.

El problema de calcular la probabilidad de que no haya ninguna coincidencia se denomina habitualmente The Matching Problem (tambi¨¦n pod¨¦is encontrarlo como Montmort¡¯s Matching Problem, en honor a Pierre-Remond Montmort, que parece que fue el primero que lo estudi¨®). Si llamamos X_n a la variable aleatoria que nos da el n¨²mero K de coincidencias (en nuestro caso, el n¨²mero de participantes que sacan el papelito con su propio nombre) para n personas, se puede comprobar que su funci¨®n de probabilidad es la siguiente (pod¨¦is ver los c¨¢lculos en esta web de la Universidad de Alabama):

Como nosotros queremos que no haya coincidencias, en nuestro caso se tiene que k=0. Haciendo tender n a infinito, tenemos que nuestra funci¨®n de probabilidad tiende a:

Es decir, la probabilidad de que no haya que repetir el sorteo tiende, conforme aumenta el valor de n, a 1/e. No me dig¨¢is que no es precioso.

Y si en el caso del amigo invisible la probabilidad de que no haya que repetir el sorteo podr¨ªa parecer baja, en otros ejemplos esta probabilidad de cero coincidencias puede parecer alta. Por ejemplo, imaginemos que en una fiesta se entrega a los asistentes sus abrigos de manera aleatoria. O que un profesor reparte unos ex¨¢menes de manera aleatoria entre sus alumnos. O que metemos tarjetas de regalo nominativas en sobres con nombre de forma tambi¨¦n aleatoria. En todos estos casos, la probabilidad de que no haya ni una sola coincidencia es de 1/e. Esto es, en un 36¡¯8% de los casos (aproximadamente) no daremos ni una. ?No os parece muy alta?

Y un ¨²ltimo comentario respecto a este matching problem. En las situaciones que hemos descrito no hay reemplazamiento. Es decir, cada participante escoge un papelito y se lo queda (no lo devuelve), por lo que otro participante no puede coger el mismo papel, y lo mismo para el resto de ejemplos. Pero podr¨ªamos tambi¨¦n estudiar estas situaciones con reemplazamiento. En el amigo invisible significar¨ªa que alguien toma un papelito, mira el nombre y lo devuelve al mont¨®n, por lo que otra persona podr¨ªa coger el mismo m¨¢s adelante.

?C¨®mo quedar¨ªa el estudio de la probabilidad de cero coincidencias en este caso? Pues¡­exactamente igual: en el matching problem con reemplazamiento, la probabilidad de que no se tenga que repetir el sorteo es tambi¨¦n 1/e. De nuevo, precioso.

La probabilidad, esa rama de las matem¨¢ticas a veces sencilla y en ocasiones muy complicada, y que en muchas circunstancias no sabemos interpretar correctamente. Por ello, podemos encontrar dentro de ella resultados curiosos y, por qu¨¦ no, en cierto modo contrarios a nuestra intuici¨®n. Seguro que muchos de vosotros conoc¨¦is otros casos que sean dignos de menci¨®n en un comentario. Si es as¨ª habladnos de ellos, posiblemente salgan cosas interesantes para ser comentadas aqu¨ª en pr¨®ximos art¨ªculos.