Función de densidad de probabilidad de un documento, implementado con C++, que no funciona como estaba previsto

Question

Así que estoy implementando un algoritmo heurístico, y me he encontrado con esta función.

Tengo una matriz de 1 a n (0 a n-1 en C, w/e). Quiero elegir una cantidad de elementos que copiaré en otra matriz. Dado un parámetro y, (0 < y < = 1), quiero tener una distribución de números cuyo promedio sea (y * n). Eso significa que cada vez que llamo a esta función, me da un número, entre 0 y n, y el promedio de estos números es y * n.

De acuerdo con el autor, "l" es un número aleatorio: 0 < l < n. En mi código de prueba, actualmente está generando 0 < = l < = n. Y tenía el código correcto, pero me estoy metiendo con esto durante horas, y soy flojo para codificarlo.

Así que codifica la primera parte de la función, para y < = 0,5 I conjunto Y a 0,2, y n a 100. Eso significa que tuvo que volver un número entre 0 y 99, con un promedio de 20. Y los resultados no están entre 0 y n, pero algunos flotan. Y cuanto más grande es n, más pequeña es esta flotante.

Este es el código de prueba C. "x" es el parámetro "l".

//hate how code tag works, it's not even working now 
int n = 100; 
float y = 0.2; 
float n_copy; 

for(int i = 0 ; i < 20 ; i++) 
{ 
    float x = (float) (rand()/(float)RAND_MAX); // 0 <= x <= 1 
    x = x * n;        // 0 <= x <= n 
    float p1 = (1 - y)/(n*y); 
    float p2 = (1 - (x/n)); 
    float exp = (1 - (2*y))/y; 
    p2 = pow(p2, exp); 
    n_copy = p1 * p2; 
    printf("%.5f\n", n_copy); 
} 

Y aquí están algunos resultados (5 decimales truncados):

0.03354 
0.00484 
0.00003 
0.00029 
0.00020 
0.00028 
0.00263 
0.01619 
0.00032 
0.00000 
0.03598 
0.03975  
0.00704 
0.00176 
0.00001 
0.01333 
0.03396 
0.02795 
0.00005 
0.00860 

El artículo es:

http://www.scribd.com/doc/3097936/cAS-The-Cunning-Ant-System

páginas 6 y 7.

o buscar " cAS: astuto sistema de hormigas "en google.

Entonces, ¿qué estoy haciendo mal? No creo que el autor esté equivocado, porque hay más de 5 artículos que describen esta misma función.

todas mis internets a quien me ayude. Esto es importante para mi trabajo.

gracias :)

Answer 1

dmckee es realmente correcto, pero pensé que elaboraría más y trataría de explicar algo de la confusión aquí. Definitivamente podría fallar. f_s(l), la función que tienes en tu bonita fórmula anterior, es la función de distribución de probabilidad. Le dice, para una entrada dada l entre 0 y n, la probabilidad de que l sea la longitud del segmento. La suma (integral) para todos los valores entre 0 y n debe ser igual a 1.

El gráfico en la parte superior de la página 7 confunde este punto. Traza l contra f_s(l), pero tienes que tener cuidado con los factores extraviados que pone a un lado. Observa que los valores en la parte inferior van de 0 a 1, pero hay un factor de x n en el lateral, lo que significa que los valores l en realidad van de 0 a n. Además, en el eje y hay un x 1/n lo que significa que estos valores en realidad no van hasta aproximadamente 3, van a 3/n.

Entonces, ¿qué haces ahora? Bueno, necesitas resolver la función de distribución acumulativa integrando la función de distribución de probabilidad sobre l, que en realidad no es tan mala (lo hice con Wolfram Mathematica Online Integrator usando x para l y usando solo la ecuación para y < = .5). Sin embargo, eso estaba usando una integral indefinida y realmente se está integrando a lo largo de x de 0 a l. Si establecemos la ecuación resultante igual a alguna variable (z por ejemplo), el objetivo ahora es resolver para l como una función de z. z aquí hay un número aleatorio entre 0 y 1. Puedes intentar usar un solucionador simbólico para esta parte si lo deseas (lo haría). Entonces no solo has logrado tu objetivo de poder elegir aleatoriamente l de esta distribución, también has logrado el nirvana.

Un poco más trabajo

te ayudaré un poco más. Intenté hacer lo que dije sobre y < = .5, pero el sistema de álgebra simbólica que estaba usando no fue capaz de hacer la inversión (algún otro sistema podría hacerlo). Sin embargo, entonces decidí intentar usar la ecuación para .5 < y < = 1. Esto resulta ser mucho más fácil.Si cambio l ax en f_s(l) consigo

y/n/(1 - y) * (x/n)^((2 * y - 1)/(1 - y)) 

La integración de este sobre x desde 0 a l llegué (utilizando Mathematica integrador de línea):

(l/n)^(y/(1 - y)) 

No puede ser mucho más agradable que la con este tipo de cosas Si lo configuran igual a z y resuelve para l me sale:

l = n * z^(1/y - 1)  for .5 < y <= 1 

Una revisión rápida es para y = 1. En este caso, obtenemos l = n no importa lo que z es. Hasta aquí todo bien. Ahora, solo genera z (un número aleatorio entre 0 y 1) y obtienes un l que se distribuye como deseas para .5 < y < = 1. Pero espera, mirando el gráfico en la página 7 notas que la probabilidad la función de distribución es simétrica. Eso significa que podemos usar el resultado anterior para encontrar el valor de 0 < y < = .5. Simplemente cambiamos l ->n-l y y ->1-y y obtenemos

n - l = n * z^(1/(1 - y) - 1) 

l = n * (1 - z^(1/(1 - y) - 1))  for 0 < y <= .5 

De todos modos, que debería resolver su problema a menos que hiciera algún error en alguna parte. Buena suerte.

Answer 2

Dado que para cualquier valor L, Y, n, como se describe, los términos que llaman p1 y p2 son ambos en [0,1) y exp es en [1, ..) haciendo pow (p2, exp) también en [0,1) por lo que no veo cómo se obtendría una salida con el rango [0, n)

Answer 3

Puede malinterpretar lo que se espera de usted.

Dado un PDF (correctamente normalizado) y que desea lanzar una distribución aleatoria coherente con él, usted forma la Distribución de probabilidad acumulativa (CDF) integrando el PDF, luego invierta el CDF y utilice un predicado aleatorio uniforme como el argumento de la función invertida.

---

Un poco más de detalle.

f_s(l) es el PDF, y ha sido normalizado en [0,n).

Ahora que lo integran para formar la CDF

g_s(l') = \int_0^{l'} dl f_s(l) 

Tenga en cuenta que esta es una integral definida a un punto final especificado que he llamado l'. El CDF es por consiguiente una función de l'. Suponiendo que tenemos la normalización correcta, g_s(N) = 1.0. Si esto no es así, aplicamos un coeficiente simple para arreglarlo.

Luego invierta la CDF y llame al resultado G^{-1}(x). Para esto, es probable que desee elegir un valor particular de gamma.

Luego arroje un número aleatorio uniforme en [0,n), y utilícelos como argumento, x, en G^{-1}. El resultado debe estar entre [0,1), y debe distribuirse de acuerdo con f_s.

Como dijo Justin, puede usar un sistema de álgebra computacional para las matemáticas.