[CONTENIDOS - CLASE] Duda con probabilidades ejemplo de colisiones y cumpleaños

[frvalenzuela]

En la clase de hoy se vio un ejemplo de cumpleaños y colisiones, donde se habla sobre el calculo una probabilidad de que exista una colisión. No entiendo como se realizo dicho calculo. Primero se hablaba de ir sacando bolitas y luego llegar una colisión. Esto no lo entiendo, porque parte de n/n luego n-1/n luego 3/n. Esa parte no entiendo bien, y luego cuando hacemos n-2/n la probabilidad es cero, tampoco entiendo eso.

Luego se vio una formula con la productoria, que no entiendo de donde llega, y finalmente el como se llegue a una esperanza igual a la raíz de cuadrada de n.

Quede muy confundido cuando vimos toda esa parte, y agradecería la ayuda.

[mugartec]

Hola @frvalenzuela,

Lo primero que tiene que estar claro es que la probabilidad que estamos calculando es la probabilidad de que la primera colisión ocurra luego de n eventos. Pensemos nuevamente en los cumpleaños, pero considerando que los estudiantes van a ir entrando de uno en uno a una sala. La pregunta es entonces, dado un k, cuál es la probabilidad de que la primera colisión ocurra cuando entra el k-ésimo estudiante a la sala.

Para calcular dicha probabilidad, hay que pensar primero que para los k-1 estudiantes anteriores no se produjo ninguna colisión, y que justo cuando entró el estudiante k sí se produjo una colisión. La probabilidad de este evento es la probabilidad de que

• No se produjo una colisión cuando entró el primer estudiante,
• No se produjo una colisión cuando entró el segundo estudiante,
• ...
• No se produjo una colisión cuando entró el estudiante k-1,
• Se produjo una colisión cuando entró el estudiante k.

Dado que estamos en conjuntos finitos podemos pensar en las probabilidades de manera clásica, es decir casos favorables dividido por casos totales. Cuando entra el primer estudiante, de los 365 días del año él podría estar de cumpleaños cualquier día y no habría una colisión (ya que está solo), y por lo tanto la probabilidad del primer evento es 365/365=1.

La probabilidad del segundo evento es simplemente que el segundo estudiante esté de cumpleños cualquier día excepto el día en el que está de cumpleaños el primer estudiante, es decir tenemos 364 casos favorables, por lo que la probabilidad es 364/365.

La probabilidad del tercer evento es simplemente que el tercer estudiante esté de cumpleños cualquier día excepto alguno de los dos días en los que están de cumpleaños los primeros dos estudiantes. Como sabemos que estos dos cumpleaños son distintos, tenemos 363 casos favorables, por lo que la probabilidad es 363/365.

La idea anterior se generaliza para los primeros k-1 estudiantes. La probabilidad del último evento es la probabilidad de que el k-ésimo estudiante que entra a la sala esté de cumpleaños el mismo día que alguno de los k-1 estudiantes que ya estaban en la sala. Como estamos asumiendo que los k-1 estudiantes que estaban en la sala tienen todos cumpleaños distintos, los casos favorables son k-1. Con esto la última probabilidad será (k-1)/365.

Recopilando todo lo anterior, tenemos las siguientes probabilidades

• Pr[No se produjo una colisión cuando entró el primer estudiante] = 365/365
• Pr[No se produjo una colisión cuando entró el segundo estudiante] = 364/365
• ...
• Pr[No se produjo una colisión cuando entró el estudiante k-1] = (365 - (k - 2))/365
• Pr[Se produjo una colisión cuando entró el estudiante k] = (k-1)/365.

Aplicas principio multiplicativo y obtienes el resultado :).

---

Respecto de la segunda parte de tu pregunta, pensemos en el mismo ejemplo anterior y preguntémonos cuál es la probabilidad de que al entrar el estudiante número 367 se produzca la primera colisión. Esta probabilidad es cero dado que si ya hay 366 estudiantes en la sala, necesariamente hay una colisión. Esto se puede argumentar fácilmente en base al principio del palomar.

Espero que esto ayude. Me cuentas si no es así o si hay más dudas.

Saludos!

[josem7]

Para hacerlo más simple imagínate tenemos 4 posibles espacios o números para elegir. [ ] [ ] [ ] [ ] Lo que se intenta calcular es la probabilidad de que al intento N se produzca la 1era colisión.

entonces si N=1 la probabilidad es 0 ya que es imposible que se produzca una colisón eligiendo 1 solo elemento .

Si N = 2 la probbilidad es 1/4. Esto es por que el primer elemento que se sacó ocupa un espacio cualquiera [ ] [ ] [X] [ ] entonces, la probabilidad de elegir ese mismo espacio es 1/4

Si N=3 la probabilidad es [(3/4)]*(2/4) ya que la probabilidad de que el 1er elemento esté en un lugar vacío es 1, la que el segundo esté en un lugar vacío es 3/4 (ya que hay un espacio ocupado y 3 vacíos) [ ] [X] [X] [ ] y luego hay 2 espacios para hacer colisión (2/4).

N=4 la probabilidad es [(3/4)(2/4)](3/4). Similar a lo anterior que el 1er espacio esté vació es 1 luego, que el segundo esté vacío es (3/4), que el 3ero esté vacío es (2/4) [ ] [X] [X] [X] y por úlitimo hay 3 espacios ocupados para hacer colisón (3/4)

N = 5 la probabilidad es [(3/4)(2/4)(1/4)]*1 Esto es que todos los anteriores hayan escogido un espacio vacío [(3/4)(2/4)(1/4)] [X] [X] [X] [X] y luego la probabilidad de colisión es 1. ( gracias marceloarenassaavedra por la aclaración :D )

N = 6 Como la probabilidad de que hubo colisón en N=5 es 1 y a nosotros nos interesa solamente la 1era colisión, la probabilidad de que la 1era colisión sea con N=6 es 0.

La productoria es la probabilidad de elegir espacios vacíos y luego se multiplica por la probabilidad de elegir un espacio lleno.

El profesro no sacó el calculo de como se llega a la esperanza de raíz cuadrada pero dijo que tiende a ese número (¿magia?). Espero que quede claro con esto :D perdón por lo largo.

[marceloarenassaavedra]

Gracias @josem7 por la explicación, muy clara. Solo un comentarios para el caso N = 5: en este caso la probabilidad es [(3/4)(2/4)(1/4)]*1, porque como tú mencionas la probabilidad de hacer colisón es 1.

Saludos!

[marceloarenassaavedra]

Veamos ahora cómo se llega a que la esperanza es la raíz cuadrada. Primero vamos a hacer esto de manera empírica.

Basado en las muy buenas explicaciones de @mugartec y @josem7, consideremos un experimento donde se saca un elemento desde el conjunto {1, ..., n} al azar y con reemplazo (vale decir, una vez sacado un elemento i se devuelve al conjunto y puede ser sacado nuevamente).

Definimos la variable aleatoria X tal que X = k representa el hecho de que la primera colisión se produjo al sacar el k-ésimo elemento desde el conjunto. Como se vio en los comentarios anteriores, tenemos que

• Pr[X = 1] = 0, no es posible tener una colisión al sacar un solo elemento

• Pr[X = 2] = 1/n, lo cual corresponde a la probabilidad de que el segundo elemento sea igual al primero

• Pr[X = 2] = ((n-1)/n)*(2/n),  lo cual corresponde a la probabilidad de que el segundo elemento sea distinto al primero, y el tercer elemento sea igual al primero o al segundo, puesto que la primera colisión se produjo al sacar el tercer elemento

• ...

• Pr[X = k] = (Product_{i=1}^{k-1} (n-(i-1))/n) * (k-1)/n

En la definición de Pr[X = k] estamos utilzando notación de WolframAlpha, la cual va a ser muy útil en el curso. En particular Product_{i=1}^{k-1} (n-(i-1))/n representa una productoria con término (n-(i-1))/n que va desde i = 1 hasta i = k-1.

La esperanza de la variable aleatoria X está dada por la expresión E[X] = Sum_{k=1}^{n+1} k*Pr[X = k], vale decir

E[X] = Sum_{k=1}^{n+1} ((k(k-1)/n) * (Product_{i=1}^{k-1} (n-(i-1))/n))

donde Sum corresponde a la sumatoria en WolframAlpha.

Ahora podemos considerar distintos valores de n y ver si E[X] se acerca al valor sqrt(n), donde sqrt(n) es la raíz cuadrada de n. Consideremos algunos casos concretos evaluados en WolframAlpha:

Con n = 400 obtenemos 25.738098 (hacer clik aquí para el cálculo). El error en este caso es de 28.69% con respecto a sqrt(400) = 20.

Con n = 900 obtenemos 38.269539 (hacer clik aquí para el cálculo). El error en este caso es de 27.56% con respecto a sqrt(900) = 30.

Con n = 1600 obtenemos 50.801824 (hacer clik aquí para el cálculo). El error en este caso es de 27% con respecto a sqrt(1600) = 40.

Vemos como el error va disminuyendo en la medida que aumenta n. Nótese que consideramos valores pequeños de n por el tiempo que toma realizar el cálculo, en clases consideramos n = 2^64.

En el próximo mensaje va la explicación de cómo se calcula esta esperanza de manera analítica.

Saludos!