egrosclaude / binomial

Distribución binomial

En el libro de Redes de Kurose se trata estadísticamente el problema de averiguar cuántos de entre usuarios comparten efectivamente un enlace en un momento dado, conociendo la frecuencia y duración de las ráfagas de actividad de un usuario.

El problema tiene otros análogos, como el de calcular la cantidad de licencias concurrentes adecuada para una aplicación de red. En este caso se trataría de averiguar cuántos usuarios mantendrán sesiones con un servidor concurrentemente, si es que la aplicación tiene noción de sesión. De lo contrario, habrá que registrar la duración promedio de una interacción y asumirla como la duración de una sesión virtual.

Para aplicar el tratamiento de Kurose hay que conocer la frecuencia y duración de las ráfagas de actividad de un usuario, y con esos datos determinar su probabilidad de transmitir en un momento dado.

El planteo es como sigue:

• A lo largo de un espacio de tiempo , la cantidad de veces que un usuario interactúa con el sistema nos da la frecuencia, . Junto con la duración promedio de sus ráfagas de actividad, se puede calcular la probabilidad de que ese usuario esté transmitiendo en un momento dado como .
• Llamemos al usuario que transmite en un momento dado. Llamemos . Ésta es la probabilidad de éxito en un ensayo de Bernoulli de probabilidad .
• La probabilidad de que cualquier no transmita en el mismo instante es .
• El evento "está transmitiendo y los demás no" es la conjunción de los eventos , que son independientes, y por lo tanto su probabilidad es el producto de las .
• El evento "está transmitiendo un usuario cualquiera de entre los , y los demás no" equivale al evento compuesto "transmite y los demás no, o transmite y los demás no, o transmite y los demás no...". Como esos eventos elementales son disjuntos, su probabilidad es la suma de las probabilidades individuales.
• P(esté transmitiendo un usuario cualquiera de entre los , y los demás no):

.

• En el caso anterior, existen exactamente maneras de elegir el usuario que esté transmitiendo, lo que se refleja en el coeficiente de las probabilidades. Para analizar el caso donde transmiten usuarios , hay muchas maneras de enumerar o elegir esos usuarios, y el factor que afecta a las probabilidades se expresa en forma de número combinatorio :
• Hay permutaciones o maneras de numerar los N usuarios.
• De éstas, hay maneras, redundantes, de numerar o elegir los usuarios que transmiten.
• Por cada una de éstas, existen maneras, redundantes, de numerar los restantes.
• La cantidad de combinaciones es . Luego .
• donde es la función de distribución o función de probabilidad acumulada usando el cómputo anterior para exactamente usuarios, con entre y .

Valor más probable

Ejemplo

Supongamos un universo de 50 usuarios donde cada uno está 10% del tiempo usando la aplicación.

• U1 transmite 10% del tiempo implica p(U1 esté transmitiendo) = p(U1) = P = 0.1.
• La esperanza o valor más probable es que en un momento dado estén transmitiendo 50 * 0.1 = 5 usuarios.
• Probabilidad de que cualquier Ui no transmita en el mismo instante es p(~Ui) = 1-P = 0.9.
• P(U1 ^ ~U2 ^ ~U3 ^ ...) = P * (1-P) * (1-P) * ... = P * (1-P)^(N-1) = 0.1 * 0.9^49 = .00057264
• P(esté transmitiendo un usuario cualquiera y los demás no) = P(U1 ^ ~U2 ^ ~U3 ^ ...) + P(~U1 ^ U2 ^ ~U3 ^ ...)

• P(~U1 ^ ~U2 ^ U3 ^ ...) +... = N * P * (1-P) ^ (N-1) = 50 * 0.1 * 0.9 ^ 49 = .02863205

Investiguemos qué pasará con una cota de 10 usuarios.

• P(10 Ui transmitan y el resto no) = C(N k) * P^k * (1-P)^(N-k) = C(50 10) * 0.1^10 * 0.9^40 =
  10272278170 * .0000000001 * .014780882941 = .015183334116
• P(más de 10 usuarios) = 1 - P(10 o menos usuarios) = 1 - F(10). F(10) = .99064539, luego P(más de 10 usuarios) = .00935460

Preparemos una tabla para esta aplicación hipotética donde hay 50 usuarios, con las probabilidades de "no más de k sesiones simultáneas" y la probabilidad de lo contrario ("más de k sesiones simultáneas"), para varios valores de k. Esto nos permitirá analizar los puntos de corte para determinar las modalidades de licencia convenientes.

 k    P(no más de k)   P(más de k) 
 0    .005153775207    .994846224793
 1    .033785859692    .966214140308
 2    .111728756344    .888271243656
 3    .250293905948    .749706094052
 4    .431198406817    .568801593183
 5    .616123007710    .383876992290
 6    .770226841775    .229773158225
 7    .877854916367    .122145083633
 8    .942132794247    .057867205753
 9    .975462064259    .024537935741
10    .990645398375    .009354601625
11    .996780078826    .003219921174
12    .998995380100    .001004619900
13    .998995380100    .001004619900
14    .998995380100    .001004619900

Script

Se adjunta el script en bc (la calculadora de Unix) que produce la tabla anterior. Modificando el parámetro scale se obtiene mayor precisión. Con scale=12, para 10 o 12 sesiones ya prácticamente no hay diferencia apreciable.

#!/usr/bin/bc -q
scale=12
N = 50
f = 0.1
define fact(x)
{
         if(x <= 1)
                 return 1;
         return x * fact(x-1);
}
#fact(3)
#fact(5)
#fact(13)
define comb(n,k)
{
         return fact(n) / (fact(k) * fact(n-k));
}
#comb(5,1)
#comb(5,2)
#comb(13,7)
define fprob(n,k,p)
{
         return comb(n,k) * (p ^ k) * ((1-p) ^ (n-k));
}
define fdistrib(n,k,p)
{
        suma = 0;
         for(i=0; i<=k; i++) {
                 suma += fprob(n,i,p);
         }
         return suma;
}

print "k, prob de <= k usuarios, prob de > k usuarios trabajando a la vez\n"

for(j=0; j<15; j++) {
       f = fdistrib(N,j,f)
       print j,"\t",f,"\t",1-f,"\n"
}

quit

Espacio no equiprobable

Si se puede separar a los usuarios en categorías de uso, con diferentes valores de frecuencia y duración , a cada categoría se asigna una probabilidad específica. La distribución correspondiente es la multinomial.