Generar valores al azar con una distribucuión arbitraria


Problema: tengo un conjunto arbitrario de palabras del lenguaje castellano y quiero obtener letras al azar de manera de que las más populares entre las palabras que tengo aparezcan más frecuentemente que las menos populares.

Por ejemplo, si la letra ñ casi no aparece, quiero que la probabilidad de obtenerla de la secuencia aleatoria sea más baja que la de las vocales que aparecen obviamente más frecuentemente.

Evidentemente los números pseudoaleatorios de las bibliotecas estándar no son útiles porque generan números uniformemente distribuidos en un intervalo.

En Java tenemos forma de generar valores (de diversos tipos aunque no caracteres, pero se los puede asociar a un rango de enteros) uniformemente distribuidos o de generar un valor de coma flotante con distribución normal(0, 1) .

Evidentemente no conocemos la distribución de las letras en el conjunto de palabras que tenemos así que tenemos que adaptar el mecanismo de generación pseudoaleatorio de Java a nuestro propósito.

Solución: la forma que encontré no está basada en mis conocimientos de probabilidades y estadística, sino que me inspiré en la interfaz de Java NavigableMap así que seguramente hay una forma mejor de hacer esto en algún libro de matemática.

La idea es que si tenemos un número uniformemente distribuido entre 0 y 1 (no incluyendo el 1), si asignamos el intervalo [0 ; 0,25)  para la letra A y en intervalo [0,25 ; 1) para la B, aplicando esa asignación tendremos que la probabilidad de obtener una A será de 0,25 y la de obtener una B de 0,75.

Podemos hacer esa asignación para todas las letras del abecedario asignando a cada una un intervalo proporcional a la frecuencia con la que aparece en nuestro conjunto de palabras.

Así es que calculamos para cada letra, la cantidad de veces que aparece y la dividimos por la cantidad total de letras de todas las palabras.

Por ejemplo tendríamos algo así:

  • a => 0.26
  • b => 0.45
  • c => 0.29

Los intervalos en ese caso quedarían:

  • [0; 0,26)
  • [0,26; 0,71)         0,71 = 0,26 + 0,45
  • [0,71; 1)               1      = 0,71 + 0,29

El problema ahora radica en seleccionar una estructura de datos que nos permita de manera óptima realizar la búsqueda entre los intervalos y saber qué letra está asignada a cada uno. Ahí es donde entra NavigableMap<K, V>.

El mensaje K floorKey(K key) nos devuelve la clave más grande que es menor a la proporcionada. K puede ser por ejemplo Double. Entonces si guardamos para cada intervalo en límite inferior asociado a la letra correspondiente nos quedará este NavigableMap

  • 0 => a
  • 0,26 => b
  • 0,71 => c

Cuando generemos un número pseudoaleatorio uniformemente distribuido entre 0 y 1 realizamos la búsqueda mediante floorKey y obtendremos el valor buscado.

Por ejemplo, si obtuvimos el 0,12343986564 floorKey nos devolverá 0. Para el 0,87 obtendremos el 0,71 y para el 0,529984 el 0,26.

Obtenido el valor, no tenemos más que buscar la letra asociada a él como con cualquier Map.

Esta técnica se puede usar para cualquier tipo de valores, no sólo letras. Basta con crear el NavigableMap del tipo que necesitemos.

NavigableMap  fue incorporado a la API de Java en la versión 1.6.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s