Algoritmo, Generación Distribución Aleatoria Discreta de Suma 1
José Enrique González Cornejo
11 de julio 2012

El presente articulo entrega una descripción de la solución  del Algoritmo DocIRS,  con la cual hemos determinado la generación de distribuciones de variable discreta y aleatoria no uniforme,  sobre un conjunto finito de  elementos positivos (y menores que 1) , cuya suma es uno.  El algoritmo marca diferencia, - con otros publicados en Internet -, porque la descripción la dotamos de una aplicación, que demuestra los rápidos tiempos de respuesta.

Los resultados de la solución los ponemos a disposición como función, para aquellos usuarios que lo requieran.  Sólo se debe  ingresar el tamaño n de la serie de distribución y obtendrá el conjunto con los valores de la distribución aleatoria cuya suma es 1.  El resultado se visualiza en una tabla y admite ser exportada al Excel.  (Ver aplicación en Algoritmo en Acción)

1. Introducción

A raíz del modelamiento matemático, para simular los efectos de la inversiones sobre la Brecha de Empleo en una región determinada de Chile, surgió la necesidad de llenar la Matriz de Cifras, con distribuciones estadísticas de diversos tamaños con valores ficticios, mientras  el equipo de investigación establece las estimaciones reales,  desde las fuentes de datos oficiales.

Por tanto, debíamos encontrar una función capaz de construir series de distribución con valores ficticios,  que nos permitieran verificar la arquitectura y funcionalidades del sistema de simulación,  a nivel de insumos, de proceso y resultados. 

Encontrar manualmente distribuciones de diferentes longitudes que sumarán 1, era una tarea aritmética tediosa que demandaba demasiado tiempo. Buscamos entonces, desarrollar una rutina computacional que determine distribuciones de variable discreta y aleatoria,  sobre un conjunto finito de  elementos,  cuyos términos tomen sólo valores positivos (y menores que 1). Donde su suma es igual  a uno.  En términos estadísticos, es análogo a  buscar distribuciones de densidad discreta en el intervalo Real ]0,1[ .

Nuestro primer  paso fue indagar en Internet la existencia de rutinas y algoritmos que nos facilitaran la solución. Ciertamente encontramos  centenas de rutinas métodos (Montecarlo),  en los más diversos lenguajes, pero ninguno cumplía con lo requerido. Entonces recurrimos a nuestra propia experiencia, utilizando Análisis Numérico y en cierta forma a la Teoría de Números para lograr el proceso preciso de lo que necesitábamos. Es decir, encontrar la serie, pero que el algoritmo nos permitiera forzar ciertos valores y también incluir ciertos patrones de comportamiento. 

Los resultados de la solución los ponemos a disposición, con una herramienta  computacional (aplicación),  para aquellos usuarios que requieran distribuciones aleatorias cuya suma es 1. El usuario sólo debe  ingresar el tamaño de la serie de distribución  (limitado a n<=300), ejecutar el algoritmo y obtendrá el conjunto con los valores de la distribución aleatoria cuya suma es 1. El resultado se visualiza en una tabla y admite ser exportada al Excel.  (Ver Algoritmo en Acción)

2. Enunciado

Dado un n Î N, encontrar un conjunto A = {l1, l2, l3,...., ln} de n valores seleccionados aleatoriamente, tal que S li = 1 , donde li Î R /   0< li < 1 ,  " i = 1,2,3,..n

3. Aproximación Inicial

Inicialmente desarrollamos un algoritmo  que generaba conjuntos de valores aleatorios mediante iteraciones. Es decir, el algoritmo iba acumulando o sumando los valores aleatorios en una variable S, y salía del ciclo cuando el valor absoluto de la diferencia de su suma con 1 se localizaba en un intervalo de error pequeño (|S -1|<0.00001) . Este algoritmo inicial, presentaba tiempos de respuesta largos cuando el tamaño n >25, por tanto no era la solución apropiada. Nótese que el numero de distribuciones que cumple con las condiciones del enunciado es infinito.

4. Breve descripción de la Solución


Idea de la Solución

A fin de encontrar un algoritmo más simple y de respuestas más rápidas, recurrimos a trabajar con el residuo (diferencias finitas) y colocaciones en torno a la densidad uniforme pm = 1/n , asegurando la convergencia hacia 1, con  un tiempo de respuesta muy rápido, utilizamos un error de redondeo  e<=10-5 , y valores a 5 decimales (cifras significativas).  Es decir, la solución pasa por aproximar la serie de n valores, pareando armónicamente. Esto es, una vez se  obtiene un valor aleatorio b<pm (u otras variante de b dentro de un rango), sumarlo a pm  asignándolo a una variable li del arreglo y  al mismo tiempo restarlo en otra  lj, donde i ¹ j.  Para finalizar el ciclo, se hace la distinción entre n par o impar, dado que que el contador finaliza la iteración en el término(s) central(es) de la serie.  

En síntesis la idea es colocar los valores aleatorios ßi  espaciados para cada par de términos de la serie de longitud n, llevándola a un error e muy pequeño, la aproximación  de la suma se hace extremadamente exacta y rápida, obteniendo así la distribución buscada.

5. Solución Normalizando la serie A

Otra forma rápida que utilizamos aleatoriamente al interior de la función FDoc(n), es generar previamente los n valores aleatorios y  aplicar una cierta normalización. Es decir, dividir cada uno de los elementos por la suma total la serie. De esta forma aplanar la secuencia obtenida.

En síntesis: Sea S=Sli ,entonces una vez generado el conjunto A (Ver párrafo 2), normalizamos el conjunto y obtenemos  A*= {l1/S, l2/S, l3/S,...ln/S}, asegurando que la distribución es igual a uno.

<script type="text/javascript">
/***********************************************
* Algoritmo de Distribución Aleatoria ~ Suma=1/ Script- © DocIRS
* José Enrique González Cornejo
* Este mensaje debe quedar intacto por uso ético
* Visitar DociRS http://www.docirs.cl/
***********************************************/
var n =30;                          ///longitud de la distribución requerida, puede ser cualquier Natural (n<1000).
var w=new Array();           ///arreglo que almacena los términos aleatorios
var suma1=0;                    ///suma de los valores aleatorios generados
var suma2=0;                    ///suma de los valores normalizados
var decimales=5;              ///cifras significativas a publicar

////1.- Se generan los n valores aleatorios en w[i] y su suma
for(var i = 1;i<=n;i++)
{
 w[i]=Math.random();
 suma1=suma1 + w[i];
}

////2.-Se normalizan los n valores dividiendo c/u de los w[i] por la suma
/// y se imprimen en la tabla.

document.write ("<table border='1' width='20%' align='center'>")
document.write ("<tr><th width='5%'>i</th><th>ßi</th></tr>")
for(var i = 1;i<=n;i++)
{
w[i]=w[i]/suma1;
var valor=w[i];
suma2=suma2+ valor;
valor=valor.toFixed(decimales);
document.write ("<tr><td align='center'>" + i + "</td><td>" + valor + "</td></tr>")
}

document.write ("<tr><th>Suma</th><th>" + suma2.toFixed(decimales) + "</th></tr>")
document.write ("</table>")
</script>


6. La función FDoc(n)

La función que sintetiza el algoritmo, la denominamos FDoc(n), y definida desde los Naturales hacia un conjunto de valores reales del intervalo ]0,1[.

7. Continuación de la Solución...

Para forzar valores el algoritmo recurre a la función Fdoc(n).

En efecto, supongamos el usuario desea una distribución de longitud n, donde el valor de un término lo ingresa directamente.

Sea b1 el valor forzado, donde  0< b1 <1 con  j=1,2,3...n  => Que debemos buscar un distribución aleatoria discreta  cuya suma D= 1-b1 , entonces ejecutamos la función FDoc(n-1) y los n-1 valores de esta serie resultante lo multiplicamos por D, configurando nuevamente la serie Af = {b1, l2, l3,...., ln} 

Así sucesivamente para los m valores forzados  bj, que el usuario desee forzar. Nótese que  m<n y  Sbj <1  , el algoritmo ejecutará la función FDoc(n-m) y los n-m términos de la serie resultante como ponderadores de la diferencia D = 1- Sbj . Finalmente obtiene un serie que tiene m valores fijados por el usuario y n-m generados aleatoriamente por el sistema.

Ejemplo de Serie con Valores Forzados Af

Con el siguiente ejemplo, ilustraremos el algoritmo interno que opera en la aplicación, para el tratamiento de series aleatorias discretas con valores forzados.

Sea n=10  e ingresemos 2 valores forzados en la serie Af , de modo que debemos buscar 8 términos aleatorios que complementen la distribución.

Tabla 1

ßi Forzados
1 0,4
2 0,21
3  
4  
5  
6  
7  
8  
9  
10  
Suma 0,61

Por tanto la diferencia D = 1- 0,61 = 0,39 . Es decir, debemos encontrar 8 términos aleatorios que sume D=0.39

Entonces aplicamos FDoc(8) y obtenemos los siguientes 8 valores aleatorios cuya suma es 1

Tabla 2

Fdoc(8)

 
 
0,1739
0,2261
0,0484
0,0983
0,202
0,1201
0,0177
0,1136

1

Luego ponderamos la diferencia D con los valores de la Tabla 2, obteniendo la siguiente serie

Tabla 3

0,39*

0,067821
0,088179
0,018876
0,038337
0,07878
0,046839
0,006903
0,044304

0,39

Finalmente uniendo las Tablas 1 y 3 obtenemos la serie resultante Af :

Tabla4

 

Af

1* 0,4
2* 0,21
3 0,067821
4 0,088179
5 0,018876
6 0,038337
7 0,07878
8 0,046839
9 0,006903
10 0,044304
Suma

1

En los próximo capítulos,  aplicaremos el algoritmo en forma múltiple en matrices de dimensiones de n x m.

8. Ejemplo de la aplicación Algoritmo en Acción

Sea n=30, entonces pm = 1/30 = 0,03333
Haciendo uso de la aplicación Algoritmo DocIRS, que ejecuta FDoc(n), se obtiene una distribución como se ilustra a continuación:

i li
1 0,0243
2 0,03703
3 0,02785
4 0,0545
5 0,03368
6 0,01872
7 0,00983
8 0,00333
9 0,01212
10 0,06095
11 0,05243
12 0,01611
13 0,01524
14 0,01748
15 0,03555
16 0,03112
17 0,04918
18 0,05143
19 0,05056
20 0,01423
21 0,00572
22 0,05454
23 0,06333
24 0,05684
25 0,04795
26 0,03298
27 0,01217
28 0,03882
29 0,02963
30 0,04236
Suma 0,99998

 

Ejemplo Distribución Aleatoria Discreta Normalizada

Sea n = 10

i li li*
1 0,89160079 0,1620929
2 0,57186675 0,1039653
3 0,16055519 0,02918891
4 0,606964 0,11034597
5 0,44551595 0,08099474
6 0,92854755 0,16880982
7 0,42257943 0,07682488
8 0,12867277 0,02339269
9 0,76400423 0,13889586
10 0,58024759 0,10548893
Suma 5,50055424 1

 

  Obtenga su distribución aleatoria cuya suma es uno

Volver


Notas.-

  • Existen numerosos algoritmos de generación de números (pseudo) aleatorios. En particular, las diferentes variantes de RANLUX, disponibles en todas las bibliotecas matemáticas modernas (CERN, GSL, etc.)

  • Nótese que nuestro error de aproximación fue fijado en  e<=10-5. Sin embargo para n>1000 se puede utilizar error absoluto de la estimación que decrece como (1/n)½  en virtud del teorema Central de Límite.

  • FDoc(n), desarrollado por DocIRS, pertenece a una clase de algoritmos computacionales basado en ensayos aleatorios repetidos para calcular el resultados. Por ejemplo, el Método de Monte Carlo se utiliza con frecuencia en simulaciones de sistemas físicos y matemáticos.

Volver