[Python-es] ¿Cómo generar una distribución aleatoria?

[Chema Cortes]

El jue., 4 jul. 2019 a las 0:47, lasizoillo (<lasizoillo en gmail.com>)
escribió:

> Buenas,
>
> Tras leer el correo de Chema me puse a pensar en cuantos bits de
> información se podía obtener de randint(1,5) y cuantos necesitaba
> randint(1,7) y me dio por pensar que era ln2(5) y ln2(7). Lo cual
> seguramente es incorrecto (las mates no son lo mío), pero aun siendo una
> estimación menor que el ideal propuesto por Chema de 1.4 llamadas es mayor
> al usado en la solución de Mario (1). Así que había pensado en hacer unos
> tests de aleatoriedad sobre esa solución demasiado bonita para ser cierta,
> pero gracias por adelantarte.
>
> ¿Se deberían descartar todas las soluciones que hagan menos de 1.2 o 1.4
> llamadas a randint(1,5) para calcular randint(1,7)?
>
>
Yo muchas veces hablo más por intuición, por lo que considera ese límite
como una estimación.

Los estados definidos con randint(1,7) tienen más información que los
definidos por randint(1,5), de ahí la estimación de 1.4 (=7/5) (puedes
calcularlo en bits, pero sale lo mismo). Como 5 y 7 son primos entre sí, no
es posible establecer una relación directa de estados. Dicho de otro modo:
no existen n y m, números enteros, de modo que se cumpla la igualdad 5**n
== 7**m. Siempre será necesario despreciar casos iniciales para que la
distribución resultante sea más o menos uniforme.

Analizando la solución propuesta anteriormente: para un valor de
randint(1,7) es necesario llamar 3 veces a randint(1,5), con una
probalidadad de repetir llamada de 3/5 + 1/8 = 29/40 ~= 0.72, probabilidad
que es bastante alta.

Una posible mejora sería hacer sólo dos llamadas, 25 casos posibles, y
"mapearlos" con 21 estados de randint(1,7). Quedarían 4 casos sin mapear.
La probabilidad de repetir tirada sería 4/25 ~= 0.16 que está bastante
mejor.

El código quedaría así:
from random import randint
from functools import partial

# única función random que se permite usar
rand5 = partial(randint, 1, 5)

# yapf: disable
# matriz de conversión
conv = [
[1, 2, 3, 4, 5],
[6, 7, 1, 2, 3],
[4, 5, 6, 7, 1],
[2, 3, 4, 5, 6],
[7, 0, 0, 0, 0]
]
# yapf: enable


def rand7() -> int:
"""
Generador aleatorio de números en rango [1,7]
a partir de randint(1,5)
"""

res = 0
while not res:

# tomamos dos números aleatorios en el rango [1,5]
(a, b) = (rand5(), rand5())

# buscamos su correspondencia en el rango [1,7]
res = conv[a - 1][b - 1]

return res
Pero aún se puede hacer mejor. Podemos mapear los 125 estados posibles de 3
llamadas de randint(1,5) con 98 (2*7**2) estados de randint(1,7). La
probabilidad de tener que repetir la tirada sería de 0.216, algo peor que
en el caso anterior. Pero que el número de llamadas necesarias se reduzca a
1.5 nos acercaría bastante al límite ideal.

Como este caso es algo más largo, lo dejo disponible como gist, incluyendo
un test de uniformidad por probar algo:

https://gist.github.com/chemacortes/3d66daf14b2ebd2190cd50d969defaed

Una prueba completa de aleatoriedad es bastante compleja. Hay un artículo
sobre criptografía bastante bueno sobre el tema en:

https://www.incibe-cert.es/blog/comprobando-aleatoriedad



-- 
Hyperreals *R  "Quarks, bits y otras criaturas infinitesimales":
https://blog.ch3m4.org
Buscador Python Hispano: http://busca.ch3m4.org
<https://blog.ch3m4.org/pages/busqueda-python-es/>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://mail.python.org/pipermail/python-es/attachments/20190706/084e7031/attachment.html>