Solución al problema de la probabilidad de cada longitud

(English version available)

En la entrada sobre IMAP se preguntaba por la probabilidad de cada posible longitud de la cadena resultante en el generador de palabas al azar. El bucle tenía esta forma:

  for ($i = 0; $i < 7 + mt_rand(0, 4); $i++) /* añadir un carácter */ ;

La clave está en que el número extraído que sirve como condición de final de bucle puede variar en cada iteración. Es diferente de un bucle similar que fijara el número de antemano, porque entra en juego la intersección de sucesos. Veamos por qué y cómo.

En el momento en que $i alcanza el valor 7, si el valor de mt_rand es 0 entonces el bucle termina; si es cualquier otro valor, continúa. Es evidente que la probabilidad de que la longitud sea 7 es 1/5 = 20%.

Cuando el valor de $i es 8, hace falta que mt_rand devuelva 0 ó 1 para que el bucle termine, lo cual ocurrirá dos de cada cinco veces. Sin embargo, para que la longitud alcance el valor 8 es condición que primero mt_rand haya devuelto un valor entre 1 y 4, lo cual ocurrirá 4 de cada 5 veces. No son sucesos independientes. Por tanto, la probabilidad combinada es 4/5 · 2/5 = 8/25 = 32%.

Para que $i llegue a 9, se tienen que dar a la vez que mt_rand devuelva un valor entre 1 y 4 la primera vez, y un valor entre 2 y 4 la segunda vez. Además, el bucle parará cuando mt_rand esté entre 0 y 2, lo cual ocurrirá 3 de cada 5 veces. Combinando las probabilidades, tenemos P(longitud 9) = 4/5 · 3/5 · 3/5 = 36/125 = 28,8%.

Con el mismo razonamiento, la probabilidad de que llegue a 10 es 4/5 · 3/5 · 2/5 · 4/5 = 96/625 = 15,36%.

La que queda podemos calcularla bien siguiendo el mismo razonamiento, ahora que le hemos cogido carrerilla, o bien restando de 1 todas las anteriores: 4/5 · 3/5 · 2/5 · 1/5 · 5/5 = 24/625 = 3,84% = 100% - 20% - 32% - 28,8% - 15,36%.

Resumiendo:

• P(longitud 7) = 20%
• P(longitud 8) = 32%
• P(longitud 9) = 28,8%
• P(longitud 10) = 15,36%
• P(longitud 11) = 3,84%

O sea, será 8 casi una de cada tres veces, seguido de cerca por 9, luego 7, luego 10, y unas pocas veces llegará a longitud 11. Como siempre he dicho, la probabilidad no es intuitiva.

Este programa ayuda a verificar la corrección de los números:

<?php

  $MAX = 10000000;

  $arr = array(0, 0, 0, 0, 0);

  for ($n = 0; $n < $MAX; $n++)
  {
     for ($i = 0; $i < mt_rand(0, 4); $i++)
       ;
     $arr[$i]++;
  }

  $l = strlen($MAX);
  for ($i = 0; $i < 5; $i++)
  {
    printf("%2d -> %{$l}d/$MAX = %f%%\n", $i+7, $arr[$i], $arr[$i]/$MAX*100);
  }

?>

Aquí el resultado de una ejecución de muestra:

 7 ->  2000626/10000000 = 20.006260%
 8 ->  3198181/10000000 = 31.981810%
 9 ->  2879481/10000000 = 28.794810%
10 ->  1538148/10000000 = 15.381480%
11 ->   383564/10000000 = 3.835640%