Mi solución al otro problema del cumpleaños

Pues eso, que me piqué —y parte de la culpa la tiene este sujeto— con el otro problema del cumpleaños y he aquí el código —exacto salvo redondeos, no mediante simulaciones— que he usado para resolverlo:

f <- function(n, k = 365, v = NULL){

  if(is.null(v))
    v <- c(1, rep(NA, k))

  res <- 1

  for(j in (k-1):1){
    v[k-j] <- ifelse( is.na(v[k-j]), f(n, k-j, v), v[k-j])
    res    <- res - choose(k,j) * ((k-j)/k)^n * v[k-j]
  }

  res
}

f(2287)
#0.5003708
f(2286)
#0.4994142

Lo que hay al final son los ensayos últimos de mi mecanismo de cutrebúsqueda binaria para acotar la solución usando la función f. Esta función calcula la probabilidad de que una distribución aleatoria de n bolas en k urnas no deje vacía nunguna de ellas.

La solución es recursiva y está basada en el hecho de que la probabilidad buscada es la complementaria de que: la distribución deje solo una urna vacía xor la distribución deje solo dos urnas vacías xor, etc.

Y que la probabilidad de dejar solo m urnas vacías se reduce al problema anterior: hay que seleccionar las m urnas (el número combinatorio), forzar a que todas las bolas, n, caigan en las k-m urnas restantes y, finalmente, que no queden huecos dentro de las k-m urnas.

Y algebraicamente (para parecer un tipo serio y confundir todavía más a quienes leen esto y luego creen que lo hago de veras, veras):

p_k^n=1-\sum_{j=1}^k\binom{k}{j}\left(\frac{k-j}{k}\right)^np_{k-j}^n

4 comentarios sobre “Mi solución al otro problema del cumpleaños

  1. luis 13 febrero, 2014 22:25

    p[i] = probabilidad que con n personas haya i-1 huecos,
    inicialmente hay una sola persona n=1 y por tanto hay necesariamente 364 huecos es decir p[365]=1. De manera recurrente vamos agregando una nueva persona y ahora la probabilidad de h huecos es que antes hubiese h huecos y la nueva persona no ocupe ninguno más la probabilidad de que hubiese h+1 huecos antes y la nueva persona haya nacido en uno de los h+1 huecos.

    Programando en Julia usamos h+1 ya que los vectores en julia empiezan en 1 y no podemos usar p[0]

    El código es el siguiente:

    julia> function birthday()
    c = 365.0
    p = zeros(366)
    p[365] = 1.0
    n = 1
    while (p[1] birthday()
    2-element Array{Float64,1}:
    2287.0
    0.500371

    julia> @elapsed birthday()
    0.016727926

  2. luis 13 febrero, 2014 22:33

    No se pegó bien el texto, a continuación el correcto:

    Una solución exacta obtenida de una definición recursiva implementada en el lenguaje de programación Julia. Como los vectores en julia se indexan de 1 en adelante, no se puede poner p[0] para h huecos y uso p[h] = probabilidad de h-1 huecos cuando hay n personas.

    Inicialmente hay una sola persona y por tanto hay 364 huecos es decir p[365]=1. De manera recurrente vamos agregando una nueva persona y ahora la probabilidad de h huecos es que antes hubiese h huecos y la nueva persona no ocupe ninguno más la probabilidad de que hubiese h+1 huecos antes y la nueva persona haya nacido en uno de los h+1 huecos.

    El código es el siguiente:

    function birthday()
    c = 365.0
    p = zeros(366)
    p[365] = 1.0
    n = 1
    while (p[1] @elapsed birthday()
    0.016727926

  3. luis 13 febrero, 2014 22:36

    Hay algún tipo de impedimento en la página que no permite copiar bien el código que tenía (tal vez por usar dos tabuladores para indentar el código). Aquí va de nuevo, y disculpas por las varias pruebas:

    function birthday()
    c = 365.0
    p = zeros(366)
    p[365] = 1.0
    n = 1
    while (p[1]<0.5)
    for h =1:365
    p[h] = (p[h]*(c-h+1)+p[h+1]*h)/c
    end
    n = n+1
    end
    [n,p[1]]
    end

  4. Carlos J. Gil Bellosta 13 febrero, 2014 22:38

    Raro que se trunque el código de esa manera. Debe de haber elementos en el código que se confunden con etiquetas HTML.

    Trata de colocar tu código entre etiquetas pre y/o code de HTML.

Los comentarios están desabilitados.