Distribución aleatoria ponderada continua, sesgada hacia un extremo

28

Actualmente estoy contribuyendo a un sistema de partículas para nuestro juego y desarrollando algunas formas de emisor.

Mi distribución aleatoria uniforme a lo largo de una línea o un área rectangular funciona bien, no hay problema.

Pero ahora me gustaría tener algo así como un gradiente unidimensional en esta distribución. Esto significaría, por ejemplo, que los valores más bajos son más comunes que los valores más altos.

No sé cuáles serían los términos matemáticos apropiados para este problema, por lo que mis habilidades de búsqueda son bastante inútiles con este. Necesito algo que sea computacionalmente simple, ya que el sistema de partículas debe ser eficiente.

didito
fuente
¿Nadie va a mencionar el cálculo?
Alec Teal

Respuestas:

42

Echa un vistazo a esta imagen:

Mapeo de curvas

Muestra el proceso de mapear un valor (aleatorio) a una curva. Suponga que genera un valor aleatorio X distribuido uniformemente, que va de 0 a 1. Al asignar este valor a una curva, o, en otras palabras, usando f (X) en lugar de X, puede sesgar su distribución de la forma que desee .

En esta imagen, la primera curva hace que los valores más altos sean más probables; segundo hace que los valores más bajos sean más probables; y el tercero hace que los valores se agrupen en el medio. La fórmula exacta de la curva no es realmente importante, y se puede elegir a su gusto.

Por ejemplo, la primera curva se parece un poco a la raíz cuadrada y la segunda al cuadrado. El tercero es un poco como un cubo, solo traducido. Si considera que la raíz cuadrada es demasiado lenta, la primera curva también se ve como f (X) = 1- (1-X) ^ 2 - una inversión del cuadrado. O una hipérbole: f (X) = 2X / (1 + X).

Como muestra una cuarta curva, simplemente puede usar una tabla de búsqueda precalculada. Se ve feo como una curva, pero probablemente será lo suficientemente bueno para un sistema de partículas.

Esta técnica general es muy simple y poderosa. Independientemente de la distribución que necesite, solo imagine un mapeo de curvas, e ideará una fórmula en poco tiempo. O, si su motor tiene un editor, ¡simplemente cree un editor visual para la curva!

No importa
fuente
Muchas gracias por su explicación minuciosa y comprensible. todas las otras publicaciones también fueron muy útiles, pero realmente pude entender tu publicación de la manera más fácil y rápida. sobresalió porque realmente dio en el clavo por mi forma de entender las cosas. ¡y los aspectos que está explicando son exactamente lo que estaba buscando (o deambulando)! me permitirá usar esto en muchos casos en el futuro. Así que gracias de nuevo! Por cierto, jugué con algunas de tus curvas y funciona como un encanto.
didito
55
FYI: Estas se llaman funciones cuantiles: en.wikipedia.org/wiki/Quantile_function
Neil G
8

Una explicación más larga:

Si tiene una distribución de probabilidad deseada , como el gradiente solicitado por @didito, puede describirlo como una función. Digamos que desea una distribución triangular, donde la probabilidad en 0 es 0.0, y desea elegir un número aleatorio de 0 a 1. Podríamos escribirlo como y = x.

El siguiente paso es calcular la integral de esta función. En este caso, es . Evaluado de 0 a 1, eso es ½. Eso tiene sentido: es un triángulo con base 1 y altura 1, por lo que su área es ½.X=1X2

Luego elige un punto aleatorio uniformemente desde 0 hasta el área (½ en nuestro ejemplo). Llamemos a esto z. (Estamos seleccionando uniformemente de la distribución acumulativa ).

El siguiente paso es ir hacia atrás, para encontrar qué valor de x (lo llamaremos x̂) corresponde a un área de z. Estamos buscando , evaluado de 0 a x̂, que es igual a z. Cuando resuelve , obtiene .X=1X21X̂2=zx̂=2z

En este ejemplo, elige z de 0 a ½ y luego el número aleatorio deseado es . Simplificado, puede escribirlo como , exactamente lo que recomienda eBusiness.2zrand(0,1)

amitp
fuente
Gracias por su valioso aporte. Siempre me gusta escuchar cómo las personas calificadas resuelven problemas. pero todavía tengo que entenderlo para ser sincero ...
didito
Esto es asombroso. Siempre hice sqrt(random())toda mi vida, pero llegué empíricamente. Intentando vincular un número aleatorio a una curva, y funcionó. Ahora que soy un poco más experto en matemáticas, ¡es muy valioso saber por qué funciona!
Gustavo Maciel
5

Probablemente obtendrá una aproximación cercana a lo que desea utilizando un sistema exponencial.

Haga que la x se base en algo como 1- (valor rnd ^) (suponiendo que rnd esté entre 0 y 1) y obtendrá algunos comportamientos diferentes de sesgo de izquierda a derecha según lo que use. Un valor más alto le dará una distribución más sesgada

Puede usar una herramienta gráfica en línea para obtener algunas ideas aproximadas sobre los comportamientos que le darán las diferentes ecuaciones antes de colocarlas, o simplemente puede manipular las ecuaciones directamente en su sistema de partículas, dependiendo de qué estilo sea más adecuado para sus gustos.

EDITAR

Para algo así como un sistema de partículas en el que el tiempo de CPU por partícula es muy importante, usar Math.Pow (o equivalente de lenguaje) directamente puede conducir a una disminución en el rendimiento. Si se desea más rendimiento y no se cambia el valor en tiempo de ejecución, considere cambiar a una función equivalente como x * x en lugar de x ^ 2.

(Los exponentes fraccionales podrían ser más problemáticos, pero alguien con un fondo matemático más fuerte que yo probablemente podría encontrar una buena manera de crear una función de aproximación)

Lunin
fuente
1
En lugar de utilizar un programa de gráficos, puede simplemente trazar la distribución Beta, ya que este es un caso especial. Para un dado value, esto es Beta (valor, 1).
Neil G
Gracias. Traté de trazar algunos gráficos y creo que podría llevarme a donde quiero.
didito
@Neil G, gracias por el consejo con la "distribución beta" - esto suena interesante y útil ... Investigaré sobre ese tema
didito
3

El término que está buscando es que la Weighted Random Numbersmayoría de los algoritmos que he visto usan funciones trigonométricas, pero creo que descubrí una forma que será eficiente:

Cree una tabla / matriz / Lista (lo que sea) que contenga un valor multiplicador para la función aleatoria. Rellenar a mano o programáticamente ...

randMulti= {.1,.1,.1,.1,.1,.1,.2,.2,.3,.3,.9,1,1,1,} 

... luego multiplique randompor un elegido al azar randMultiy finalmente por el valor máximo de la distribución ...

weightedRandom = math.random()*randMulti[Math.random(randMulti.length)]*maxValue

Creo que esto será mucho más rápido que el uso sqrt, u otras funciones más complejas desde el punto de vista computacional, y permitirá más patrones de agrupación personalizados.

AttackingHobo
fuente
2
Si puede sacrificar la memoria, una tabla de 100 valores precalculados sería más rápida (y un poco más precisa). Dudo que el usuario pueda distinguir entre las versiones completas y precalculadas.
Daniel Blezek
@Daniel sería más rápido, pero con 100 valores aleatorios, es bastante fácil ver patrones repetitivos.
AttackingHobo
El hecho de que parece haber un patrón repetitivo no significa que no sea aleatorio. La esencia de la aleatoriedad es su imprevisibilidad, lo que literalmente significa que aunque uno no puede predecir que no habrá un patrón, tampoco se puede predecir que podría haber uno (al menos por un corto tiempo). Tendrá que hacer algunas pruebas, pero si encuentra patrones con múltiples pruebas utilizando diferentes semillas, entonces su algoritmo para generar números pseudoaleatorios puede necesitar ser revisado.
Randolf Richardson
@AttackingHobo gracias por ese truco. Me gusta el uso de LUT. y la fórmula es bastante fácil de entender. No lo había pensado de esta manera antes. no ver la madera de los árboles ... :) también creo que se deben evitar los patrones repetitivos, pero probablemente no se reconocerán en este caso de todos modos. aun así, precalcular todos los valores dañaría la experiencia visual. de todos modos, thx por recordarme que este es un factor a considerar en el tema de la aleatoriedad ...
didito
¡también gracias por mencionar el término "números aleatorios" ponderados!
didito
2

Creo que lo que pides es la distribución lograda usando una función de raíz cuadrada.

[position] = sqrt(rand(0, 1))

Esto dará una distribución en el campo de dimensión única [0, 1]donde la probabilidad de una posición es equivalente a esa posición, es decir, una "distribución triangular".

Generación alternativa sin raíz cuadrada:

[position] = 1-abs(rand(0, 1)-rand(0, 1))

Una raíz cuadrada en una implementación óptima es solo unos pocos comandos de multiplicación y suma sin ramas. (Ver: http://en.wikipedia.org/wiki/Fast_inverse_square_root ). Cuál de estas dos funciones es más rápida puede variar según la plataforma y el generador aleatorio. En una plataforma x86, por ejemplo, se necesitarían solo unas pocas ramas impredecibles en el generador aleatorio para hacer el segundo método más lento.

aaaaaaaaaaaa
fuente
La probabilidad de una posición no será igual a la posición (eso es matemáticamente imposible, trivialmente, el dominio y el rango de la función incluye 0.50 y 0.51), ni es una distribución triangular. ( en.wikipedia.org/wiki/Triangular_distribution )
1
Si bien sqrt ofrece algunos patrones interesantes, los sistemas de partículas generalmente deben tener mucha luz de CPU por partícula, por lo que recomendaría evitar las raíces cuadradas (que son computacionalmente lentas) siempre que sea posible. A veces puede salirse con la suya precalculando, pero puede hacer que sus partículas tengan patrones notables con el tiempo.
Lunin
1
@ Joe Wreschnig, ¿leíste ese artículo de Wikipedia tú mismo? Ingresa a = 0, b = 1, c = 1 en la fórmula de generación y obtienes la fórmula en mi publicación.
aaaaaaaaaaaa
3
@Lunin, ¿por qué te quejas de la raíz cuadrada cuando tienes un exponente en tu respuesta?
aaaaaaaaaaaa
1
@Lunin: La teoría del rendimiento es un campo bastante descuidado, mucho de lo que la gente cree saber sabe hace aproximadamente 30 años cuando las ALU eran muy caras y lentas. Incluso la función de exponente que acaba de descubrir que es una función aritmética bastante lenta rara vez es un pecador de rendimiento muy significativo. La ramificación (usando una instrucción if) y los errores de caché (lectura de un dato que no reside actualmente en la memoria caché) suelen ser los que cuestan más rendimiento.
aaaaaaaaaaaa
1

Solo usa una distribución Beta:

  • Beta (1,1) es plano
  • Beta (1,2) es un gradiente lineal
  • Beta (1,3) es cuadrático

etc.

Los dos parámetros de forma no necesitan ser enteros.

Neil G
fuente
Gracias por tu ayuda. Como se indicó anteriormente, la distribución beta suena interesante. pero todavía no puedo entender el contenido de la página de wikipedia. o una fórmula / código. bueno, tampoco tengo tiempo en este momento para investigar más a fondo: si veo que el impulso tiene código para las distribuciones beta, pero esto sería excesivo. bueno, supongo que primero tengo que revisarlo y luego escribir mi propia versión simplificada.
didito
1
@didito: No es tan difícil. Simplemente reemplaza su uniform_generator()llamada con gsl_ran_beta(rng, a, b). Ver aquí: gnu.org/software/gsl/manual/html_node/…
Neil G
Gracias por la pista. No uso GSL (en realidad no he oído hablar de eso antes), pero es una buena decisión. ¡Comprobaré la fuente!
didito
@didito: En ese caso, iría con la solución de Lunin. Buena suerte.
Neil G
0

Aún más simple, dependiendo de la velocidad de su generador aleatorio, puede generar dos valores y promediarlos.

O, aún más simple, donde X es el resultado de la RNG, en primer lugar double y = double(1/x);, x = y*[maximum return value of rng];. Esto pesará los números exponencialmente a los números más bajos.

Genere y promedie más valores para aumentar la probabilidad de acercar los valores al centro.

Por supuesto, esto solo funciona para distribuciones de curvas de campana estándar o versiones "plegadas" de las mismas *, pero con un generador rápido, podría ser más rápido y sencillo que usar varias funciones matemáticas como sqrt.

Puede encontrar todo tipo de investigación sobre esto para las curvas de campana de dados. De hecho, Anydice.com es un buen sitio que genera gráficos para varios métodos de lanzar dados. Aunque está utilizando un RNG, la premisa es la misma, al igual que los resultados. Por lo tanto, es un buen lugar para ver la distribución incluso antes de codificarla.

* Además, puede "doblar" la distribución de resultados a lo largo de un eje tomando el eje y restando el resultado promedio y luego sumando el eje. Por ejemplo, desea que los valores más bajos sean más comunes, y digamos que quiere que 15 sea su valor mínimo y 35 sea su valor máximo, un rango de 20. Por lo tanto, genera y promedia dos valores con un rango de 20 ( dos veces el rango que desea), lo que dará una curva de campana centrada en 20 (restamos cinco al final para cambiar el rango de 20 a 40, de 15 a 35). Tome los números generados X e Y.

Número final,

z =(x+y)/2;// average them
If (z<20){z = (20-z)+20;}// fold if below axis
return z-5;// return value adjusted to desired range

Si cero es su mínimo, incluso mejor, haga esto en su lugar,

z= (x+y)/2;
If (z<20){z = 20-z;}
else {z = z - 20;}
return z;
TheAlicornSage
fuente