reutilización de números aleatorios en el muestreo depósito

Question

Se preguntó en relación a otra pregunta recientemente: Given an unknown length list, return a random item in it by scanning it only 1 time

Sé que no debería, yo no puedo poner mi dedo en una explicación de por qué no canónica.

mirar el código ejemplo:

import random, sys 

def rnd(): # a function that returns a random number each call 
    return int(random.getrandbits(32)) 

class fixed: # a functor that returns the same random number each call 
    def __init__(self): 
     self._ret = rnd() 
    def __call__(self): 
     return self._ret 

def sample(rnd,seq_size): 
    choice = 0 
    for item in xrange(1,seq_size): 
     if (rnd() % (item+1)) == 0: 
      choice = item 
    return choice 

dist = [0 for i in xrange(500)] 
for i in xrange(1000): 
    dist[sample(rnd,len(dist))] += 1 
print "real",dist 
print 

dist = [0 for i in xrange(500)] 
for i in xrange(1000): 
    dist[sample(fixed(),len(dist))] += 1 
print "reuse",dist 

Las opciones para la toma de muestras depósito adecuado que genera un nuevo número aleatorio por artículo está muy bien distribuido uniformemente como debe ser:

real [1, 3, 0, 1, 2, 3, 2, 3, 1, 2, 2, 2, 2, 0, 0, 1, 3, 3, 4, 0, 2, 1, 2, 1, 1, 4, 0, 3, 1, 1, 2, 0, 0, 0, 1, 4, 6, 2, 3, 1, 1, 3, 2, 1, 3, 3, 1, 4, 1, 1, 2, 2, 5, 1, 2, 1, 0, 3, 1, 0, 2, 6, 1, 2, 2, 1, 1, 1, 1, 3, 2, 1, 5, 4, 0, 3, 3, 4, 0, 0, 2, 1, 3, 2, 3, 0, 2, 4, 6, 3, 0, 1, 3, 0, 2, 2, 4, 3, 2, 1, 2, 1, 2, 2, 1, 4, 2, 0, 0, 1, 1, 0, 1, 4, 2, 2, 2, 1, 0, 3, 1, 2, 1, 0, 2, 2, 1, 5, 1, 5, 3, 3, 1, 0, 2, 2, 0, 3, 2, 3, 0, 1, 1, 3, 0, 1, 2, 2, 0, 1, 2, 2, 3, 2, 3, 1, 1, 0, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 3, 3, 1, 0, 1, 1, 0, 1, 3, 2, 1, 4, 3, 4, 1, 1, 1, 2, 1, 2, 0, 0, 0, 1, 1, 2, 6, 0, 1, 1, 0, 1, 0, 1, 2, 2, 3, 0, 1, 2, 2, 1, 0, 4, 2, 1, 2, 2, 0, 4, 4, 0, 3, 2, 2, 1, 2, 4, 1, 2, 1, 0, 2, 1, 1, 5, 1, 2, 2, 3, 2, 3, 0, 1, 2, 3, 2, 5, 2, 3, 0, 1, 1, 1, 1, 3, 4, 2, 4, 1, 2, 3, 2, 5, 2, 1, 0, 1, 1, 2, 2, 3, 1, 1, 1, 2, 1, 2, 0, 4, 1, 1, 2, 3, 4, 3, 1, 2, 3, 3, 3, 2, 1, 2, 0, 0, 4, 3, 2, 2, 5, 5, 3, 3, 3, 1, 0, 1, 3, 1, 1, 2, 4, 3, 1, 4, 4, 2, 5, 0, 5, 4, 2, 1, 0, 4, 1, 3, 3, 2, 4, 2, 3, 3, 1, 3, 3, 4, 2, 2, 1, 1, 1, 1, 3, 3, 5, 3, 2, 4, 0, 1, 3, 2, 2, 4, 2, 2, 3, 4, 5, 3, 2, 1, 2, 3, 2, 2, 2, 4, 4, 0, 1, 3, 3, 3, 4, 1, 2, 4, 0, 4, 0, 3, 2, 1, 1, 4, 2, 1, 0, 0, 0, 4, 2, 2, 1, 4, 3, 1, 1, 3, 2, 4, 3, 4, 2, 1, 1, 2, 2, 3, 3, 1, 2, 2, 1, 1, 2, 3, 1, 9, 1, 3, 4, 2, 4, 4, 0, 1, 0, 1, 0, 2, 1, 0, 1, 2, 3, 3, 6, 2, 2, 1, 2, 4, 3, 3, 3, 2, 1, 2, 1, 2, 8, 2, 3, 1, 5, 3, 0, 2, 1, 1, 4, 2, 2, 1, 2, 3, 2, 1, 0, 4, 3, 4, 3, 1, 3, 2, 3, 2, 2, 1, 0, 1, 2, 5, 3, 0, 3, 1, 2, 2, 2, 1, 0, 1, 4] 

Mientras que cuando se vuelva a utilizar el mismo número al azar para todos los elementos, se obtiene una distribución asimétrica de los números muy bajos:

reuse [92, 50, 34, 19, 23, 16, 13, 9, 9, 9, 11, 10, 6, 7, 8, 5, 5, 6, 4, 2, 2, 3, 2, 3, 3, 6, 6, 1, 4, 3, 5, 2, 2, 1, 1, 2, 3, 4, 3, 4, 1, 3, 1, 0, 0, 1, 5, 3, 1, 2, 0, 2, 0, 1, 1, 6, 2, 0, 2, 2, 4, 2, 2, 0, 2, 2, 2, 0, 3, 0, 4, 1, 2, 1, 4, 2, 2, 0, 1, 0, 1, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 2, 1, 3, 1, 0, 1, 2, 0, 4, 3, 0, 0, 2, 0, 0, 1, 0, 0, 2, 0, 2, 1, 0, 1, 0, 0, 1, 1, 3, 0, 1, 1, 0, 2, 0, 1, 2, 0, 1, 1, 4, 1, 1, 1, 2, 1, 0, 1, 2, 0, 2, 1, 1, 2, 0, 1, 1, 0, 2, 0, 2, 0, 0, 2, 0, 1, 0, 2, 1, 1, 0, 0, 1, 2, 4, 1, 0, 2, 0, 1, 2, 1, 3, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 2, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 4, 1, 0, 2, 1, 0, 0, 2, 1, 1, 3, 3, 2, 0, 1, 0, 2, 0, 1, 1, 0, 0, 3, 1, 0, 0, 1, 0, 3, 2, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 2, 0, 4, 1, 0, 0, 2, 0, 1, 1, 0, 0, 3, 1, 3, 2, 2, 1, 3, 1, 2, 0, 1, 1, 3, 0, 3, 1, 2, 0, 2, 0, 2, 0, 3, 0, 3, 0, 3, 1, 0, 2, 3, 1, 1, 0, 1, 3, 3, 1, 1, 1, 0, 2, 1, 1, 4, 1, 1, 1, 2, 0, 3, 1, 1, 0, 4, 1, 1, 0, 1, 3, 1, 0, 1, 1, 0, 3, 3, 0, 2, 4, 0, 1, 2, 1, 6, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 4, 2, 0, 1, 2, 0, 1, 4, 1, 2, 0, 5, 2, 2, 0, 6, 2, 2, 1, 3, 0, 3, 1, 1, 0, 3, 1, 4, 2, 0, 1, 0, 1, 2, 3, 1, 1, 3, 0, 0, 0, 1, 1, 4, 3, 3, 0, 0, 1, 0, 1, 1, 2, 1, 0, 2, 1, 4, 5, 1, 1, 3, 0, 1, 1, 1, 3, 1, 1, 0, 3, 3, 1, 3, 0, 1, 0, 0, 1, 1, 3, 2, 1, 0, 3, 1, 1, 3, 1, 3, 1, 2, 2, 2, 0, 0, 5, 1, 3, 0, 1, 4, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 1, 2, 2, 3, 2, 2, 1, 0, 3, 3, 1, 3, 3, 3, 2, 1, 2, 3, 3, 3, 1, 2, 2, 2, 4, 2, 1, 5, 2, 2, 0] 

¿Cuál es la matemática aquí? ¿Por qué no puedes volver a usar el mismo número aleatorio?

Answer 1

Editar, en respuesta al comentario: muestreo depósito

La forma debe trabajo es: desea seleccionar exactamente la proporción adecuada de muestras de cada uno de los contenedores existentes con el fin de compensar una bandeja adicional la misma probabilidad. En su bucle sample(), dado que usted ha muestreado al azar una de item contenedores, es necesario seleccionar muestras de cada bin con probabilidad 1/(item + 1).

Sin embargo, con fixed(), tanto la decisión de selección y el número bin anterior dependen del mismo número de 32 bits fija. Esto significa que la probabilidad de que se retire una muestra de cada uno de los contenedores no será uniforme.

---

considere lo que sucede durante la tercera iteración del bucle sample(). Tiene tres bandejas existentes (0, 1 y 2) y desea elegir 1/4 de las muestras en cada una y agregarlas a un contenedor recién creado 3.

Tenga en cuenta que todos los números de fixed() de 32 bits en bin 1 será aún (ya que el primero pase selecciona todos los números divisibles por 2), y todos los números en bin 0 será par (porque las pares se movieron a bin 1). El segundo pase mueve todos los números divisibles por tres a bin 2 (que debe estar bien hasta ahora, y no cambia el incluso división/impar en los contenedores de 0 y 1).

La tercera pasada mueve todos los números fixed() divisibles por 4 en la bandeja 3. Pero seleccionará la mitad de los números de la bandeja 1 (porque la mitad de todos los números pares son divisibles por 4) y ninguno de los números de la bandeja 0 (porque son todos raros). Así, a pesar de que el tamaño esperado de la nueva bandeja debe ser correcta, los tamaños esperados de los contenedores viejos ya no son los mismos.

Así es como fixed() genera una distribución desigual: la suposición implícita de que puede seleccionar una fracción exacta de cada contenedor eligiendo un número aleatorio se infringe si ese número depende de manera predecible de los números utilizados para elegir el papelera original.

---

La propiedad básica de los números aleatorios es que cada muestra se debe distribuir independientemente de las muestras anteriores, en un sentido estadístico. Los algoritmos basados ​​en números aleatorios dependen de esta propiedad.

Los generadores de números pseudoaleatorios (PRNG) no son en realidad aleatorios; como sabes, sus resultados son en realidad una secuencia fija. Los resultados de PRNG están codificados deliberadamente para que actúen lo suficiente como los números aleatorios reales para la mayoría de los propósitos. Sin embargo, si el PRNG es "débil" para una aplicación en particular, el funcionamiento interno del PRNG puede interactuar con los detalles de la aplicación de maneras extrañas, hasta resultados muy no aleatorios.

Lo que está probando aquí, al volver a usar el mismo número aleatorio, es crear un PRNG malo. Los resultados reales dependen de los detalles de cómo la aplicación utiliza los números aleatorios ...

Aunque fixed() es un PRNG roto intencionadamente, muchos biblioteca comercial de PRNG son "débiles", y puede terminar con interacciones extrañas similares con algunas aplicaciones. Como una cuestión práctica, la "debilidad" es relativa a la aplicación, y, aunque existen pruebas estadísticas que se usan ampliamente para tratar de exponer los PRNG débiles, no hay garantía de que su aplicación no tropezará con alguna extraña correlación de incluso un PRNG "fuerte".

Answer 2

Piense en esto: ¿Qué sucede cuando su número fijo es realmente pequeño?

Answer 3

Si elige un número aleatorio cada vez, el siguiente elemento de la secuencia tiene 1/CURRENTSIZE posibilidad de superar el elemento elegido anteriormente.

¿Cuál es el problema con un número aleatorio por secuencia? ¿Por qué sesga la distribución?

Todavía no he encontrado una respuesta completa, pero tengo una idea.

Por ejemplo, permite tomar una secuencia de 100 números y elegir un número aleatorio 0 ... 999. Ahora lo miramos desde el punto de vista del segundo elemento.

¿Cuándo gana? Bueno, antes que nada, debe ser N% 2 == 0. Entonces tiene que ser un número par. Además, también es vencido por cada otro múltiplo de cada múltiplo de 2 en la secuencia, 4 ... 6 ... 8 ... 10 etc. Pero gana, por ejemplo, en 106.

Cálculo de todos los números ¡gana con 0..999 y obtenemos 81 veces!

Ahora vamos a tomar 4, debe ser N% 4 == 0 y es vencido por todos los múltiplos de 4 a N (8 ... 12 ... 16). Si calculamos cuántas veces 4 puede ganar, ¡tenemos 45 veces ...! Entonces la distribución no es justa.

Esto se puede arreglar si se hace que el número aleatorio sea el máximo del tamaño de la secuencia, y luego todos tienen 1 posibilidad de ganar, lo que lo convierte en una distribución pareja nuevamente.

Por ejemplo, si tenemos un tamaño de secuencia de 100, y elegimos un número aleatorio de 0..199. Sabemos que los primeros 100 números aleatorios tienen exactamente 1 coincidencia, por lo que se distribuyen de manera uniforme. Pero, ¿qué ocurre con los números aleatorios 99 ... 199? ¡La distribución no es pareja! Por ejemplo, 101 solo dará 101% X == 0 para 1. Esto es cierto para todos los números primos (101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199). Entonces, el ítem uno tiene MUCHA posibilidades de ganar que los otros.

Este no es el caso si elige un nuevo número aleatorio para cada artículo, en ese caso se pueden agregar las posibilidades. Por ejemplo, cuando aparece el primer elemento, tiene posibilidades de ganar, es decir:

NO (1/2 + 1/3 + 1/4 + 1/5 + 1/6 (... etc))