¿Por qué es la generación de 8 bits aleatorios uniforme en (0, 255)?

Question

Yo soy de la generación de 8 bits aleatorios (ya sea un 0 o un 1) y la concatenación de ellos para formar un número de 8 bits. Un simple Python simulación de rendimientos de una distribución uniforme en el conjunto discreto [0, 255].

Estoy tratando de justificar por qué esto tiene sentido en mi cabeza. Si yo comparo esto con el volteo de 8 monedas, no el valor esperado estar en algún lugar alrededor de las 4 cabezas/4 colas? Así que para mí, tiene sentido que mis resultados deben reflejar un pico en el medio de la gama. En otras palabras, ¿por qué una secuencia de 8 ceros o 8 queridos parecen ser igual de probable como una secuencia de 4 y 4, o 5 y 3, etc.? Lo que me estoy perdiendo aquí?

Answer 1

TL;DR: El agudo contraste entre los bits y las monedas es que en el caso de las monedas, estás ignorando la orden de los resultados. HHHHTTTT sea tratada según los mismos como TTTTHHHH (ambos tienen 4 cabezas y 4 colas). Pero en bits, que te importa el orden (porque tienes que darle a "pesos" a las posiciones de bits con el fin de obtener 256 resultados), por lo que 11110000 es diferente de 00001111.

---

Más explicación: Estos conceptos pueden ser más precisa unificado de si somos un poco más formal, en la formulación del problema. Considere un experimento para ser una secuencia de ocho ensayos con resultados dicotómicos y la probabilidad de "éxito" de 0,5, y un "fracaso" de 0,5, y que las pruebas son independientes. En general, voy a llamar a esta $k$ éxitos, $n$ total ensayos y $n-k$ fallas y la probabilidad de éxito es $p$.

• En el ejemplo de la moneda, el resultado "$k$ cabezas $n-k$ colas" ignora el orden de los ensayos (4 cabezas es de 4 cabezas no importa el orden de ocurrencia), y esto da lugar a su observación de que los 4 cabezas son más probable que 0 o 8 cabezas. Cuatro cabezas son más comunes debido a que hay muchas maneras de hacer cuatro cabezas (TTHHTTHH, o HHTTHHTT, etc.) que hay algún otro número (8 cabezas sólo tiene una secuencia). El teorema del binomio da el número de maneras de hacer estas configuraciones diferentes.

• Por el contrario, el orden es importante bits porque cada lugar tiene asociado un "peso" o "lugar de valor." Una propiedad del coeficiente binomial es que $2^n=\sum_{k=0}^n\binom{n}{k}$, es decir, si contamos todas las diferentes secuencias ordenadas, obtenemos $2^8=256$. Este se conecta directamente a la idea de cuántas maneras diferentes hay para hacer $k$ cabezas en $n$ binomial ensayos para el número de diferentes secuencias de bytes.

• Además, se puede mostrar que la de 256 resultados son igualmente probables por la propiedad de independencia. Los ensayos anteriores no tienen ninguna influencia en el siguiente ensayo, por lo que la probabilidad de un orden particular es, en general, $p^k(1-p)^{n-k}$ (porque la probabilidad conjunta de eventos independientes es el producto de sus probabilidades). Porque los juicios son justos, $P(\text{success})=P(\text{fail})=p=0.5$, esta expresión se reduce a $P(\text{any ordering})=0.5^8=\frac{1}{256}$. Porque todos los órdenes tienen la misma probabilidad, tenemos una distribución uniforme a través de estos resultados (que por codificación binaria se puede representar como números enteros en $[0,255]$).

• Por último, podemos tomar esto en un círculo completo, de vuelta para el lanzamiento de la moneda y de la distribución binomial. Sabemos que la aparición de 0 jefes no tienen la misma probabilidad de 4 cabezas, y que esto es debido a que hay diferentes maneras de ordenar las apariciones de 4 cabezas, y que el número de tales órdenes son dadas por el teorema del binomio. Por lo $P(\text{4 heads})$ debe ser ponderado de alguna manera, específicamente debe ser ponderada por el coeficiente binomial. Así que esto nos da la PMF de la distribución binomial, $P(k \text{ successes})=\binom{n}{k}p^k(1-p)^{n-k}$. Puede ser sorprendente que esta expresión es un PMF, específicamente porque no es inmediatamente obvio que las sumas a 1. Para comprobar, tenemos que comprobar que el $\sum_{k=0}^n \binom{n}{k}p^k(1-p)^{n-k}=1$, sin embargo esto es sólo un problema de los coeficientes binomiales: $1=1^n=(p+1-p)^n=\sum_{k=0}^n \binom{n}{k}p^k(1-p)^{n-k}$.

Answer 2

¿por qué una secuencia de 8 ceros o 8 queridos parecen ser igual de probable como una secuencia de 4 y 4, o 5 y 3, etc

La aparent paradoja se puede resumir en dos proposiciones:

1. La secuencia de $s_1: 00000000$ (ocho ceros) es igual de probable como secuencia $s_2: 01010101$ (cuatro ceros, cuatro). (En general: todos los $2^8$ secuencias tienen la misma probabilidad, independientemente de cómo muchos ceros,/que ya tienen.)

2. El evento "$e_1$: la secuencia tenía cuatro ceros" es más probable (de hecho, $70$ veces más probable) que el evento "$e_2$: la secuencia tenía ocho ceros".

Estas proposiciones no son contradictorias; de hecho, son ambas verdaderas. Debido a que el evento $e_1$ incluye muchas secuencias.

Answer 3

Todos los de la $2^8$ secuencias tienen la misma probabilidad 1/$2^8$=1/256. Es un error pensar que las secuencias que tienen más cerca a igual número de 0s y 1s es más probable que la pregunta se interpreta.. debe quedar claro que llegamos a 1/256 porque asumimos la independencia de juicio a prueba. Es por eso que se multiplican las probabilidades y los resultados de un ensayo no tiene ninguna influencia sobre el siguiente.

Answer 4

Sycorax la respuesta es correcta, pero parece que no está del todo claro por qué. Al voltear a 8 monedas o generar aleatorio de 8 bits el fin de tomar en cuenta, el resultado va a ser una de las 256 posibilidades igualmente probables. En su caso, cada uno de los 256 posibles resultados de forma exclusiva mapa a un entero, por lo que obtener una distribución uniforme como su resultado.

Si usted no toma el orden en cuenta, tales como la consideración de cómo muchas cabezas o colas que tienes, sólo hay 9 resultados posibles (0 Cabezas/8 Colas - 8 Jefes/0 Colas), y ya no son igualmente probables. La razón de esto es porque fuera de los 256 posibles resultados, hay 1 combinación de volteretas que le da 8 Cabezas/0 Colas (HHHHHHHH) y 8 combinaciones que dan a los 7 Jefes/1 Colas (una de las Colas en cada una de las 8 posiciones en el orden), pero 8C4 = 70 maneras de 4 Cabezas y 4 Colas. En la moneda volteando el caso de cada uno de esos 70 combinaciones de mapas a 4 Cabezas/4 Colas, pero en el número binario problema de cada uno de esos 70 resultados que se asigna a un número entero único.

Answer 5

El problema, es decir, es: ¿por Qué es el número de combinaciones de 8 dígitos binarios aleatorios tomado como 0 a 8 dígitos seleccionados (por ejemplo, la 1) en un momento diferente de la cantidad de permutaciones de 8 dígitos binarios aleatorios. En el contexto del presente documento, de una elección al azar de 0's y 1's significa que cada dígito es independiente de cualquier otro, de manera que los dígitos están correlacionadas y $p(0)=p(1)=\frac{1}{2}$; .

La respuesta es: Hay dos diferentes codificaciones; 1) codificación sin pérdida de permutaciones y 2) con pérdida de la codificación de combinaciones.

Ad 1) sin pérdida De codificar los números de modo que cada secuencia es única, podemos ver que el número como un entero binario $\sum_{i=1}^82^{i-1}{X_i}$ donde ${X_i}$ son de izquierda a derecha $i^{th}$ dígitos, en el binario secuencia aleatoria de 0's y 1's. Lo que hace es que cada permutación único, como cada uno de los dígitos al azar luego de posición codificada. Y el número total de permutaciones, a continuación,$2^8=256$. Entonces, casualmente uno puede traducir esos dígitos binarios en la base 10 números de 0 a 255 sin pérdida de singularidad, o para el caso de que uno puede reescribir ese número con cualquier otra codificación sin pérdida de información (por ejemplo, comprimido sin pérdida de datos, Hexadecimal, Octal). La pregunta en sí misma, sin embargo, es un archivo binario. Cada permutación es entonces igualmente probables debido a que hay sólo un camino, cada uno único de codificación de la secuencia puede ser creado, y hemos asumido que la aparición de un 1 o un 0 es igual de probable en cualquier lugar dentro de esa cadena, de tal manera que cada permutación es igual de probable.

Ad 2) Cuando la codificación sin pérdida de información es abandonado por sólo teniendo en cuenta las combinaciones, entonces tenemos una pérdida de codificación en el que los resultados se combinan y se pierde información. Luego, podemos ver el número de serie, w.l.o.g. como el número de 1's; $\sum_{i=1}^82^{0}{X_i}$, que a su vez reduce a $C(8,\sum_{i=1}^8{X_i})$, el número de combinaciones de 8 objetos tomados $\sum_{i=1}^8{X_i}$ a en el tiempo, y para que otro problema, la probabilidad de que exactamente 4 1 70 ($C(8,4)$) veces mayor que la obtención de 8 a 1, debido a que hay 70, igualmente probable permutaciones que se pueden producir de 4 a 1.

Nota: En el momento actual, a la respuesta anterior, es el único que contiene una explícita computacional de la comparación de las dos codificaciones, y la única respuesta que incluso menciona el concepto de codificación. Me tomó un tiempo para obtener el derecho, que es por qué esta respuesta ha sido votada abajo, históricamente. Si hay pendientes quejas, deja un comentario.

Actualización: Desde la última actualización, me complace ver que el concepto de codificación que se ha empezado a captar en las otras respuestas. Para mostrar esto de forma explícita para el actual problema que tengo conectado el número de permutaciones que son con pérdida codificados en cada combinación.

Tenga en cuenta que el número de bytes de información perdida durante cada combinatoria de codificación es el equivalente al número de permutaciones de que la combinación menos uno [$C(8,n)-1$donde $n$ es el número del 1], es decir, para este problema, de $0$ $69$por la combinación o $256-9=247$ total.